wanbo's blog

A very implicit bug for me, can you find it rapidly?

By wanbo, 9 years ago, In English

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.

  • Vote: I like it
  • +12
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Oh, now I understand and found counterexample:
      4
      4 3 3 2
      answer is 6, you output 0

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply