lolzz's blog

By lolzz, history, 7 years ago, In English

I have been thinking about this problem for about a week now. But I have not been able to understand the logic behind the solution. Any help is really appreciated. Thanks!

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Let xi be the number of dresses in the i-th machine and d be the desired number of dresses in each machine. Take a look at some machine at the position i. She has two neighbours at positions i - 1 and i + 1. And let and . You may notice that in optimal solution dresses moves from i to i - 1 only if Sl < i·d and from i to i + 1 only if Sr < (n - 1 - id. And how much dresses will moved are al = Sl - i·d and ar = Sr - (n - 1 - id. Since we can move dress only in one direction in each step, through i-th machine in optimal answer will be moved al + ar dresses. The answer is maximum of this sum over all possible i.

Unfortunately, not to much formally.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for answering nickitat. I am able to understand the solution but unfortunately I'm not getting the intuition behind the fact that "The answer is maximum of this sum over all possible i." It's okay till the point where you say that look to the left and right of the ith washing machine, and calculate the number of necessary operations for this machine. But how do you combine this expression for all machines and say that the answer is maximum expression for any machine. Operations on washing machines is not independent, right?