9

Changing > to <= causes wrong answer when it practically doesn't matter!

 1 year ago
source link: https://codeforces.com/blog/entry/110366
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

Hi! I was solving 230A. Dragons when I encountered a strange problem.

I tried to solve it this way with the greedy method:
We make a pair< int, int > a[n] array which puts the powers in the first component of the pairs and puts the bonuses in the second component (a[i].first = x[i], a[i].second = y[i]). Then we sort the array a by the first component (powers). The problem is in sorting the second component. We shouldn't care about second component (the bonus) while sorting right? Suppose all the powers are equal to p. If our current strength is lower than or equal to p, we can't proceed so we can't kill all the dragons. If it's greater that p, the we can kill all the dragons with the power of p regardless of getting any more bonus.

These are my submissions:
Submission 1
Submission 2

In one of them in the compare function while comparing the second component of two pairs, I used > and in one of them I used <=. And in one of them I get wrong answer and in one of them the code gets accepted. Why is this happening? By the way, when I ran the "wrong" code in my computer with the same test cases, I got segmentation fault.

Thanks :)


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK