sandeepgogarla61's blog

Can someone explain a DP approach for 1472B (FAIR DIVISION) ?
By sandeepgogarla61, history, 2 years ago, In English

1472B - Fair Division :|

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
2 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Let dp[i] be the absolute difference between the weights of A and B considering the first i items.

Note that dp[i] can only be 0,1 or 2.

Base Case: dp[1] = v[1]

Transition is simply dp[i] = abs(v[i] — dp[i-1]).

Note that parity is maintained on transition, so seeing a stone of weight 1 always changes parity of dp[i], and 0 and 2 don't change parity.

There is only one trick, suppose we have dp[i-1] = 0, and v[i] = 2. It's possible that we might be able to place 2 on one side, and move two previous 1 weight stones over on the other side. Therefore, just keep count of how many 1s we have seen, and if we've seen more than 2, make sure the transition from 0 -> 2 ends in 0 instead of 2.

Of course, to recover the answer, we simply need to check if dp[n] is 0 or not.

150316817 for clarity.

→ Reply