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. asked 16 Apr '18, 22:45

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_{i1} + 1$ we have an invalid situation. To fix it, $t_{i1}$ needs to be increased to $t_i  1$. But now $t_{i1}$ may be $> t_{i2} + 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 answered 22 Apr '18, 21:46
thanks a lot for reply :)
(22 Apr '18, 23:35)
if you had similar problem like this then please share.
(22 Apr '18, 23:37)
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.
(23 Apr '18, 23:15)
