TCO 2013 round 2C: bummer (And editorial for 250)

For some minutes I felt like I actually solved the hard problem during a match. It was short-lived, because I quickly figured there was no way it was correct.

250

Link to problem statement.

I opened this problem. Somehow I figured up quickly that everything depended on the distance between the Foxes. But I spent time trying to prove myself of it. I coded a solution that seemed correct and passed examples (Recursive logic that divided by 2), was about to submit it and I figured that there was something wrong with it - You can't introduce the same Fox to multiple people during a song -. I predicted that this was going to be a juicy challenge case. I fixed it up, but it was very late. I could only score 170-ish points. I was not going to advance with just that.

The editorial for this problem is finished. You can read an explanation there. I am trying a new approach and it is to develop a problem's editorial as soon as I understand the problem. Instead of waiting to solve the other problems... This should make editorials faster. I think.

500

Link to problem statement.

For some reason I missed the "simple" dynamic programing solution. This problem seemed harder than it was, so I decided to open the 1000.

1000

Link to problem statement.

I actually thought I could solve this thing. I thought of something involving ternary search.

I think the top-level logic is sort-of correct (and I actually survived two challenge cases), but I took too many shortcuts. Returning 0 when the increment is too big is for example not really valid, because it could be possible to try to be lucky and still get more than A-1 moves. I figured out this mistake after submitting, there were 10 minutes left. I should have spent these minutes generating a test case with a distance of 49 for the foxes in 250, but I still wasted them trying to come up with a correct solution.

Challenge phase

I tried to generate a test case with 49 distance between foxes during intermission, but I was taking too long to do the ascii art. I should have made a python script to generate it for me. By the time I finished making the test case, the solutions in my room using division by 2 were all challenged.

I doubt I could have scored the 300 challenge points necessary to allow me to advance anyway. Although I could have possibly earned a t-shirt. I think though that I am going to win a TCO 13 t-shirt from the Marathon round I am participating at. So it probably does not matter.

I guess it is another year in which I do not get even close to advancing to the algorithm finals. Bummer.

Opinions, etc

It was a good problem set. I just need to improve.