### Golovanov399's blog

By Golovanov399, history, 4 months ago, translation, ,

We are sorry for not having controlled the situation about the streamed editorial and also for the broadcast message about an unethical behaviour of someone from community: here is explanatory comment to the message. When we tried to move the casino problem one position below, something went wrong leading to it being moved one position above (however, Radewoosh didn't seem to feel that something was wrong, congratulations!).

Nevertheless, we hope that you liked the problems, and those of you who decided to do something else after you knew that the round was made unrated can solve the problems when convenient (if they wish).

Problem A of final/div2 (Technogoblet of Fire)
Problem B of div2 (Mike and Children)
Problem B of final/C div2 (System Testing)
Problem C of final/D div2/A div1 (Diana and Liana)
Problem D of final/F div2/C div1 (Compress String)
Problem E of final/E div2/B div1 (Once in a casino)
Problem F of final/D div1 (Power Tree)
Problem G of final/E div1 (The very same Munchhausen)
Problem H of final/F div1 (Secret Letters)

• +157

 » 3 months ago, # |   0 Auto comment: topic has been updated by Golovanov399 (previous revision, new revision, compare).
 » 3 months ago, # |   +2 Anyone please link analysis to contest page.
 » 3 months ago, # | ← Rev. 2 →   +8 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)
•  » » 3 months ago, # ^ |   +2 Same here, but if you really want to know the implementation just go to the Standings of the contest and look for submissions of other people.For example in Div2, Diazzz has some nice clean solutions that should be understandable. It took him 3 minutes to solve a task I couldn't do in 2 hours.
 » 3 months ago, # |   0 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.
 » 3 months ago, # |   -15 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.
•  » » 5 weeks ago, # ^ |   0 Thank you Mooncrater. I really stuck with it before I found your remark.
 » 3 months ago, # |   +13 1120DSo we calculate where where this value means the minimal possible cost where in the subtree of there are not covered leaves. It can be shown that these values are enough to calculate 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
 » 3 months ago, # |   -10 Please help me with task C(div.2), the solution is not full enough. I am trying to solve it for 4 hours.
 » 3 months ago, # |   0 It is funny that I can use KMP + binary search + dp for problem F div2
•  » » 3 months ago, # ^ |   0 How did u use binary search in F?
•  » » » 3 months ago, # ^ |   0 It is very natural, for each index i of string s, I want to find the largest index j such as s[i:j] is a substring of s[0:i). So I will use binary search for j with each i. To check whether s[i:j] is substring of s[0:i), I use KMP. The rest of the problem is dynamic programming, it is a DAG problem.Sorry for my bad English
 » 3 months ago, # |   0 Div1D: Why do it have to be spanning tree? Making components, which every has sum on nodes equal to 0, isn't sufficient?
 » 3 months ago, # |   0 For those with WA31 in Div2 D try the following testcase: 9 3 3 2 1 1 4 2 4 3 2 2 2 3 4 
 » 3 months ago, # |   0 For Div2 F/Div1 C I got a solution in O(n²*log n). I followed the editorial's recurrence and the main problem when we are in a state 'p' is to find the l's described in the editorial. To do that I used binary search to see what is the first 'l'. This combined with a double hash to check in O(n) if s[l..p] is a substring of s[1..(l-1)] gives the state 'p' in O(n*log n) when we already know all previous states. So, we have the complexity O(n²*log n) to get state 'n'. This solution almost don't pass. So I would like to know if there is a way to get O(n²) using hashes.
 » 2 months ago, # | ← Rev. 2 →   0 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).
 » 3 weeks ago, # | ← Rev. 2 →   0 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.