JOIN
Get Time
forums  Revision History
Search My Post History  |  My Watches  |  User Settings
Forums Algorithm Matches SRM 534 Re: div 2 p1000 Revision History (1 edit)
Re: div 2 p1000 (response to post by Betlista)
* 4 ways to reduce to { 2 1 1 0 0 }

How do you do that? In order for girls to drink they have to be next to each-other and each should have non-zero integer.

The sketch of the solution is:
Each number is represented in binary. If at some point the number of some of the girls end in 0 (i.e. it is even) she MUST divide it by two, thus removing the zero. If the last bit is 1, then she either can subtract one (converting the bit from 1 to 0), or divide by two (removing the digit, as in previous case).
So, the solution is represent each of the girls' numbers in binary. Do a 5-dimensional DP, each dimension denoting to which bit of her number each girl has got to (and if it was 1, whether it was changed to 0). That gives, roughly (log2(10000) * 2)^5 states. Actually, the hard part of the problem is noticing each girl has 26 possible states (not 28, as the upper formula suggests, which would lead to memory limit).
Even a better solution would be not to make the DP 5-dimensional, but to encode the state in a single dimension. That's not only easier to write, but also faster. I will explain the solution in more detail in the editorial in a few days.

Edit: Also, the really evil part was that {10000, 10000, 10000, 10000, 10000} was NOT the hardest possible testcase, as 10000 contains only few 1s in its binary representation (and as we said, if the number ends in 0, it MUST be divided). The worst case is {8191, 8191, 8191, 8191, 8191}, where all digits are 1 and greatest number of states is visited (killing all map and bruteforce solutions).
Re: div 2 p1000 (response to post by Betlista)
* 4 ways to reduce to { 2 1 1 0 0 }

How do you do that? In order for girls to drink they have to be next to each-other and each should have non-zero integer.

The sketch of the solution is:
Each number is represented in binary. If at some point the number of some of the girls end in 0 (i.e. it is even) she MUST divide it by two, thus removing the zero. If the last bit is 1, then she either can subtract one (converting the bit from 1 to 0), or divide by two (removing the digit, as in previous case).
So, the solution is represent each of the girls' numbers in binary. Do a 5-dimensional DP, each dimension denoting to which bit of her number each girl has got to (and if it was 1, whether it was changed to 0). That gives, roughly (log2(10000) * 2)^5 states. Actually, the hard part of the problem is noticing each girl has 26 possible states (not 28, as the upper formula suggests, which would lead to memory limit).
Even a better solution would be not to make the DP 5-dimensional, but to encode the state in a single dimension. That's not only easier to write, but also faster. I will explain the solution in more detail in the editorial in a few days.