652A — Gabriel and Caterpillar

I have lost count of number of different challenges in this problem. Only 14 author tests for such a tricky problem were clearly not enough. There were 2 types of challenges.

The first type use integer overflow. When I saw that both h₁, h₂ and a, b are bounded by 10⁵ I suspected that overflow could be a problem. But my solution divided heights by speeds to get the number of days. Surely there are no need to multiply these quantities I thought. Boy I was wrong. A lot of solutions used a simulation of the process. As long as a > b and the caterpillar is going up, there is no problem. But if the caterpillar is going down, you need to give up eventually and return -1. The largest positive answer is about 10⁵/12 but the largest lose of height per day is about 12·10⁵. The product is about 10¹⁰ > 2³¹ and the caterpillar mistakenly finds an apple at the high earth orbit as a result. The challenge test looks like this:

1 100000
1 100000

The second type of challenges were small tests with the answer ≤2. The most popular challenge were

1 9
1 1

where the caterpillar reaches the apple at exactly the end of the day. I think the absence of such edge-case test was an oversight. The next most popular bug was trying to calculate the number of hours to reach the apple instead of calculating the caterpillar position after given amount of hours. This could backfire when the number of hours is not a whole number and rounding in integer division is not working in the direction you need. Such bugs were challenged by tests like these:

1 18
2 1

1 18
2 2

Another popular problem is using division to calculate the number of days but getting negative number. It can happen in the test

1 2
4 3

The caterpillar reaches apple in the first day, but if you continue its trajectory backwards, it will also reach apple in the day before.

A few people misunderstood the problem and thought that they need to calculate the number of days since the initial observation. They were challenged with test case where the caterpillar reaches apple in the beginning of the day:

1 90
10 1

The rest of the challenges are too diverse. I will only highlight submission 16927302 where I had to use h₁ not equal to 1. It was a case of confusion between the marker value and a normal value.

652B — z-sort

There were 5 challenges for this problem. The author test set contained only single test with odd n greater than one. So it was not surprising that 3 out of 5 challenges used the first non-trivial odd case of n equal to 3. The other 2 challenges exploited reads just beyond the end of the vector. I used custom invocation tab to print the value beyond the end of the vector and construct a test where this value confuses program.

653C — Foe Pairs

There were 2 self-challenges that revealed worst cases for O(n²) solutions. Both used the same test:

300000 299999
1 2 ... 300000
1 300000
2 300000
...
299999 300000

I wonder how many more solution failed it after the challenge phase. One more challenge was a random test for solution which had correct time complexity but was too close to time limit (998ms). My first challenge used a bug in removing same consecutive foe pairs from the input. Can you see it?

    if(count && u[count-1] == u[count] && v[count] == v[count]);
    else count++;

The worst part is that deduplication was not needed. It wouldn't work anyway since same foe pairs may not be adjacent in the input. Deduplication also played a fatal role for my second challenge. This time, it was done correctly but solution didn't take into account that it got less than m pairs. So the program read foe pairs beyond the end of the vector and produced wrong result.

654D — Nested Segments

If you used unordered_map to compress coordinates in this problem, you had a bad time... It took me quite a lot of attempts to construct an anti-hash test for this problem but all hash solutions failed on it. There were no other hacks. The author test set is very good for this problem.

654E & 654F — Pursuit For Artifacts & Ants on a Circle

I didn't have time to challenge solutions of these problems and no one else been able to do that too. But it wasn't all for nothing — stoyan_malinin was able to hack one of the author solutions for F. I don't know whether there were a particular idea for that test or it happened by accident though.