# | User | Rating |
---|---|---|

1 | tourist | 3843 |

2 | jiangly | 3705 |

3 | Benq | 3628 |

4 | orzdevinwang | 3571 |

5 | Geothermal | 3569 |

5 | cnnfls_csy | 3569 |

7 | jqdai0815 | 3530 |

8 | ecnerwala | 3499 |

9 | gyh20 | 3447 |

10 | Rebelz | 3409 |

# | User | Contrib. |
---|---|---|

1 | maomao90 | 171 |

2 | awoo | 164 |

3 | adamant | 162 |

4 | TheScrasse | 159 |

5 | nor | 154 |

6 | maroonrk | 153 |

7 | -is-this-fft- | 152 |

8 | Petr | 146 |

9 | orz | 145 |

10 | pajenegod | 144 |

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/14/2024 08:19:53 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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