### sandeepgogarla61's blog

By sandeepgogarla61, history, 2 years ago,
| Write comment?
 » 2 years ago, # | ← Rev. 3 →   0 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.
•  » » 7 months ago, # ^ |   0 instead of carrying the counts of 1, simply sort the vector in descending order and calculate dp[i]=abs(dp[i-1] -v[i]);https://codeforces.com/problemset/submission/1472/232719835 for more clarity