| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 2 | maomao90 | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
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.