811C: Vladik and Memorable Trip

Note the English transaltion of the problem is a bit misleading: the problem actually means for each city’s traveller, either all on the same segment, or none selected at all, i.e., impossible to have case where some people are going to city x while some won’t

This means that we will have the cascading effect, i.e, we need to merge all overlapping [l, r] segments until there is no overlapping one, if we ever want to pick one city in the overlapping segments

after that we can just do a brute force DP, for each r that is an end, look for all start l, can calculate the XOR, and update the DP result.

808D: Array Division

since all numbers are positive, we can calculate the prefix sum, and then for each number, we look for (half of total) + that number , see if there exists one such prefix sum.

807D: Dynamic Problem Scoring(!!!)

What I did wrong

I was trying to brute force search on the final band of problems, but realize that one new account will affect the band of ALL past problems bands!!!

Insights

  1. From a new account, implementation wise, we don’t need to submit wrong answers at all, since only the total account number matters

  2. For each problem, we either need increase its good rate or lower good rate

  3. Consider the case when we only need to increase the good rate. To minimize number of accounts created, each account should submit right to as many problems as possible, so as to improve the pass rate of multiple questions, e.g., we can do better with one account submit right to two problems than two accounts each submit to one??

  4. When we need to lower the good rate, the account just do nothing at that problem, and is optimal

  5. Therefore, we have an optimal scheme that satifies 3 and 4 at the same time, the key insight being because of 2, the two cases don’t interfere with each other

  6. Note that we can not binary search on answers, because we can not pile on new account when there is unsolved problems => which will only lower the rate of the problems we want to increase

  7. Worse case, we just need to increase n by 32 times, to dilute all problems to 500 or make it 3000, so its 32 * 5 * 120