So, about that CF contest today

I tried a division 1 CF contest today. I'll keep trying them but it seems things haven't improved that much. The first two levels were trivial. The middle one easy but a pain to implement. The rest harder than I could solve. It is the same sandwich feeling I got in my last CF contest last year :/

Problem A
I had terrible luck with this one. I rushed to implement it, but a bug in the implementation made my computer freeze because of using too much RAM. I need to implement measures on my CF testing thing such that things with too much RAM will be killed. 10 minutes later after surviving the freeze and fixing the mistake I am already quite behind in the standings.

Problem B
I thought I solved it, but apparently there is something tricky with this problem that not even the problem setter could see before this contest.

Problem C
At first it was very hard to read this problem. After decoding it a little, I could see it was a very obfuscated dp problem. But otherwise a simple one at that.

You can define your state with three values : (t, x, o) . t is the number of subjects you have already picked. x is the id of the last one. and o is equal to (picked number of tasks) - a[x], for that last subject. Note that b[x] - a[x] will be at most 100, so o can be at most 100. Also, x as parameter works because you have to pick the subjects in strictly ascending order of complexity, so you just need to worry about the other subjects that have a larger complexity. This makes the recurrence acyclic and actually simple.

After defining the state, you can see the problem as maximizing two variables : a) The best number of subjects you can pick following the conditions and b) The best number of tasks you can get by using that previous argument. Of course, a) must be equal to n, else the assignment is impossible. Then you just pick the assignment with the best b). Building the assignment using the data from the recurrence requires you to recall the recurrence again.

Once I debugged this solution and passed pretests, I received the announcement that the round will be canceled. I decided to use my time on an assignment to write a Pacman clone for school instead of the contest. Aided because I read problem D and it seemed complicated.

Turns out I failed problem C, it is likely a small issue. I am right now not sure about what the problem with B is, but it is likely that I was affected by the same bug that made the judge's solution fail.

I am sort of glad it got canceled, because at the end my position depended solely on my speed in A, and that one was 8 minutes higher than it should be due to bad luck.