### Petr's blog

By Petr, history, 19 months ago,

• +99

 » 19 months ago, # |   +25 Huh, as I read this, my solution to E seems to have zero things common with editorial as well. I solve $O(nk)$ problems where each element is $0$ or $1$ with some probability (depending on its position). For binary strings original problem can be solved while keeping two variables — what is the optimal cost if I have an interval opened and what if I don't have it opened. Using that insight, for each prefix I count number of sequences that will lead me to each state of dp (and there are $O(n^2)$ states of this dp for each prefix, so $O(n^3)$ in total, so my solution works in $O(n^4k)$.
•  » » 19 months ago, # ^ |   +18 Right, this is exactly my approach as well!
•  » » 19 months ago, # ^ |   +17 By the way, do you have a proof for the reduction to 0/1 problems? It feels right intuitively, but I can't formulate easily why :)
•  » » » 19 months ago, # ^ |   +45 You might want to read the editorial to problem Landscaping from 2016 US Open. That's what I did during the AGC.
•  » » » » 19 months ago, # ^ |   +56 US Open? I thought they play tennis there or something :p
•  » » » 19 months ago, # ^ |   +10 I don't, I went with my intuition as well :p
•  » » 19 months ago, # ^ |   0 I believe this was roughly scott_wu's approach as well, though I think he optimized the DP down to n^2 transitions. I think this is actually not so different from the official solution; once you observe that it suffices to solve the 0-1 problem, the dp to solve the 0-1 version is really equivalent to the editorial's; you just got there without proving the 0-1 reduction.
 » 19 months ago, # |   -53 sir recommend some good resources for cp
•  » » 19 months ago, # ^ |   -15 You don't need any just make one submission(Accepted or wrong answer doesn't matter) in a rated contest then you will reach 3000 in 9-10 days because 2_din_me_rating_double xD!