prob : http://codeforces.com/contest/957/problem/D?mobile=false
I have seen the editorial but didn’t understand it. Can someone please explain me it in an easier way.
Let the number of marks above or at the water level on day i be x_i. Of course x_i = m_i + 1. The problems asks to minimize \sum_{i=1}^{n} d_i. Denote total marks on day i by t_i. Minimizing \sum_{i=1}^{n} d_i means minimizing \sum_{i=1}^{n} t_i - x_i = \sum_{i=1}^{n} t_i - \sum_{i=1}^{n} x_i. Since you cannot change any x_i, the second term is constant and minimizing \sum_{i=1}^{n} d_i is same as minimizing \sum_{i=1}^{n} t_i.
Now t_i = x_i + d_i. We do not know the values for d_i yet, but we can say t_i \ge x_i. Remember that we want to minimize the sum of t_i so we should keep each t_i at the limit value we got above. However the marks are never erased so the total can never be less than that of any earlier day, which means t_i \ge \max_{1 \le j \le i} x_j. Again, we should keep it at the limit value.
But that may not give a valid answer because there is an additional constraint that only one mark may be added per day. So whenever t_i > t_{i-1} + 1 we have an invalid situation. To fix it, t_{i-1} needs to be increased to t_i - 1. But now t_{i-1} may be > t_{i-2} + 1, which needs to fixed similarly. It makes sense that the best way to do this is to iterate backwards from n to 1 and fix all such instances.
Now we have the optimum values of t_i, all that is left is to calculate the answer. My solution: 36594354
2 Likes
thanks a lot for reply 
if you had similar problem like this then please share.
Sorry I don’t think I have seen anything similar. The logic for some problems (like this one) cannot be generalized, so you’ll probably not find other problems like it.