×

help in a codeforces greedy problem 957D Riverside Curio

 0 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 2★pk301 627●10 accept rate: 16% 6★meooow ♦ 7.1k●7●18

 2 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 answered 22 Apr '18, 21:46 6★meooow ♦ 7.1k●7●18 accept rate: 48% thanks a lot for reply :) (22 Apr '18, 23:35) pk3012★ if you had similar problem like this then please share. (22 Apr '18, 23:37) pk3012★ 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) meooow ♦6★
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,000
×682

question asked: 16 Apr '18, 22:45

question was seen: 227 times

last updated: 23 Apr '18, 23:15