Автокомментарий: текст был обновлен пользователем Golovanov399 (предыдущая версия, новая версия, сравнить).

Auto comment: topic has been updated by Golovanov399 (previous revision, new revision, compare).

Anyone please link analysis to contest page.

Спасибо за разбор!

It would be nice if you could provide the codes to the solutions of the problems. I think people would like to see how some things are implemented. I see the idea but don't know how to write it down (I'm still a noob :P)

Hello, guys. Can anybody explain me, how we can check the necessary condition of interest on each test of each solution in task C (div.2) ? I have already made array with start solution treatment time.

Diazzz's solution, for Div2 C (System Testing) uses an array used, which signifies that a solution i will be "interesting" only a single time.

I was confused, because in the third example input of the question, processes 1 and 5 will be testing case 36 at 36% completion. So, a total of 7 should be the answer. But if one reads the question carefully, it can be found that the number of interesting solutions is asked, and not the number of times the condition mentioned above is fulfilled. Therefore, even though the condition is met more than one times for a solution, only 1 will be added to the answer.

so the most non-trivial (at least for me) part of this solution, how to calculate the answer, is just omitted in this editorial. lol

Please help me with task C(div.2), the solution is not full enough. I am trying to solve it for 4 hours.

It is funny that I can use KMP + binary search + dp for problem F div2

Div1D: Why do it have to be spanning tree? Making components, which every has sum on nodes equal to 0, isn't sufficient?

No mention of DP solution for Div1 D?

We can calculate min cost of (1) setting all leaves in the subtree to zero (or any given number, since it's the same), and (2) setting all leaves in the subtree to any number as long as it's the same.

For (2) we need to set one child subtree to any number (2), and then set all other child subtrees to the same number (1).

For (1) we either set all child subtrees to zero (1), or set the entire subtree to the same number and then buy the root node.

Once we calculated the answer we can do the same process again and collect the resulting set optimal nodes (it seems too expensive to try to collect it on the first run).

I realise I'm rather late to this, but there is a simpler O(N) solution to F that doesn't require any convex hulls.

Suppose P sends a letter via R at time t0. Let the next time W sends a letter be at time t1. By considering a few cases, one can show that it is always optimal for W to send that letter via R (it can make that letter more expensive, but by at most the same amount it saves on the cost of P's letter by picking it up earlier).

Next, as noted in the original analysis, if P also sends a letter at time t (t0 < t < t1), it should go via R iff t1-t <= d/c. We can now use DP to answer the question "what is the cost of sending letters i..N if letter i goes via R?" by sweeping i downwards. To compute this, assuming P sends letter i, we need to know

• the index and time (t1) of the next letter from W

• the number and cost of letters from P in the interval [t1 — d/c, t1) that come after i, assuming they are collected at t1 by W.

As we consider each i, we also consider it being the first letter to go via R and add d*i to the cost to obtain a candidate solution.

Solution: https://mirror.codeforces.com/contest/1120/submission/54658246