Problem Link Can anyone figure out my code's bug without running my code? :)
Here is my submission: Submission link
Here is my steps for solving this problem:
- sort the array in decrease order
- extract the consecutive subarray that the difference between the two elements is <= 1.
- greedily choose the edges for rectangles in order.
I was just sharing my kind of interesting bug, I have figured out where I am wrong before I post this blog. Why people downvote it without any comment? :( Negative contribution is disappointing.
int A = 0;
?When I saw this problem, I thought I would code something similar to your code and would made mistakes in indexes and would be debugging it for a long time. But I thought one more time and came up with simple solution without indexes
The "A" means the un-matched edges in the last "block", for example, 7 7 6 6 6 6 5 2 2, I look it as [7 7 6 6 6 6 5] and [2 2], after processing the first block, I get (7 7 6 6) and (6, 6) unpaired, so A will be 6 after this. Then with the [2, 2], I get (6 6 2 2).
Oh, now I understand and found counterexample:
4
4 3 3 2
answer is 6, you output 0
I was intending to look this 4 term as a block. But when I calculate block, I use a[i] <= a[j] + 1, I need to compare a[j] and it previous term. :D This bug let me wondering why my so straightforward greedy is wrong. Confident about anything when I submit, doubt about anything after get WA. And thank you @Igorjan94.