As I don't see the post discussing the round, I decided to write this.
I do not participate much in contests now. But I love Code Jam. Thanks to problem writers and organizers!
It seemed to me that this round was no more difficult than the previous one. How do you like it?
I liked the problems:
- A (tags: interactive, constructive): strange problem — the most naive approach fits into the requirements on the total cost of requests;
- B (tags: number theory, dp): I wrote some kind of DP with memorization of $$$(a, s)$$$, where $$$a$$$ is the last element in the sequence we already placed (I build in increasing order) and $$$s$$$ is the total sum for the future elements. I don't have a proof why it works fast, probably because of the number of divisors is small.
- C (tags: combinatorics, recurrence): the last occurrence of
1is the position of $$$n$$$, so we can divide sequence with this position on two parts and use DP to calculate the answer (don't forget to multiply on binomial coefficient);
- D (tags: graphs, flows, greedy): I used min-cost-flow to match Ms on the first field and the second in optimal way. I tried all possible values of flow to iterate over all possible pairs of Ms I want to match and took best cost among all choices.