You are not logged in. Please login at www.codechef.com to post your questions!

×

help in a codeforces greedy problem 957D Riverside Curio

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

pk301's gravatar image

2★pk301
62710
accept rate: 16%

edited 22 Apr '18, 21:48

meooow's gravatar image

6★meooow ♦
7.1k718


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

link

answered 22 Apr '18, 21:46

meooow's gravatar image

6★meooow ♦
7.1k718
accept rate: 48%

edited 22 Apr '18, 21:47

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
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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