Passing solutions just have cache in 6-dimensional array to get rid of overhead with HashMap.

I don't consider these constraints fair, because they allow straightforward solution for C++, but not for Java.]]>

Unfortunately it's still too high for straight-forward Java solution.]]>

I did highly optimized solution in practice room, with no array cloning, customized hashcode/equals for keys to DP map.

It passes the sample {{10000, 10000, 10000, 10000, 10000}} in 1.5 seconds, but there is another case {{4095, 4030, 3966, 4095, 4095}}, which (guessing by approximation to localhost) runs in ~2.5 seconds.

With dumb (2 * log(Xi))^5 solution it's undoable in Java without some custom very quick associative cache (at least 2 times faster than HashMap with optimized hashcode/equals).

Maybe there is more clever solution with less states...]]>

Also, inside your DP function you generate the array oa 5 times, but it isn't necessary, is it? You could just restore its state after dividing.]]>

]]>importjava.util.Arrays;importjava.util.HashMap;importjava.util.Map;publicclassEllysFiveFriends {privatestaticintMOD = 1000000007;privatestaticMap<State, Integer> cache =newHashMap<State, Integer>( 1000000 );publicintgetZero(finalint[] numbers ) { cache.put(newState(newint[] { 0, 0, 0, 0, 0 } ), 1 );return(int) getZero(newState( numbers ) ); }publicstaticlonggetZero(finalState s ) {if( cache.containsKey( s ) )returncache.get( s );if( justOneIsNonZero( s ) )return0;longres = 0;for(inti = 0; i < 5; ++i ) {if( s.a[ i ] == 0 )continue;finalintj = ( i + 1 ) % 5;if( s.a[ j ] == 0 )continue;finalint[] oa =newint[5];for(intk = 0; k < oa.length; ++k ) oa[ k ] = s.a[ k ];if( ( oa[ i ] % 2 ) == 1 && ( oa[ j ] % 2 ) == 1 ) { --oa[ i ]; --oa[ j ]; res += getZero(newState( oa ) ); ++oa[ i ]; ++oa[ j ]; oa[ i ] /= 2; oa[ j ] /= 2; res += getZero(newState( oa ) ); }else{ oa[ i ] /= 2; oa[ j ] /= 2; res += getZero(newState( oa ) ); } } res %= MOD; cache.put( s, (int) res );returnres; }privatestaticbooleanjustOneIsNonZero(finalState s ) {intcnt = 0;for(finalintx : s.a )if( x > 0 ) ++cnt;returncnt == 1; }privatestaticclassState {int[] a =newint[5];publicState(finalint[] a ) {for(inti = 0; i < 5; ++i ) { this.a[ i ] = a[ i ]; } } @OverridepublicinthashCode() {finalintprime = 31;intresult = 1; result = prime * result + Arrays.hashCode( this.a );returnresult; } @Overridepublicbooleanequals(finalObject obj ) {if(this== obj )returntrue;if( obj ==null)returnfalse;if( this.getClass() != obj.getClass() )returnfalse;finalState other = (State) obj;if( !Arrays.equals( this.a, other.a ) )returnfalse;returntrue; } } }

As far as the suggestion about (2 lg x)^5 goes, I think example #1 debunks that solution:

{2, 1, 1, 1, 2}

Returns: 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).]]>

That's what I missed...]]>

When I try to find the number of ways (papers) for {2 2 1 1 0} I'm getting 15.

There is:

* 1 way to reduce to { 2 2 0 0 0 }

* 4 ways to reduce to { 2 1 1 0 0 }

** 2 ways how to reduce { 2 1 1 0 0 } to { 1 1 0 0 0 }

* 1 way to reduce to { 1 1 1 1 0 }

* and 6 ways how to reduce { 1 1 1 1 0 } to { 1 1 0 0 0 }

together it is 1 + 4*2 + 6 = 15 ways to win.

But for more complicated situation in test case 1 the expected result is just 10 (and {5, 3, 2, 1, 1} can be reduced to {2 2 1 1 0} in two steps).

I think that I misunderstood how to count the ways. I think that "The order in which she wrote down the two girls does not matter." means that there is just one way to reduce {1 1 0 0 0} to {0 0 0 0 0} (A, 1, 2) is same as (A, 2, 1), but I'm not sure if number of ways to reduce {1 1 1 1 0} to {1 1 0 0 0} is correct even if the possibilities are:

(A, 1, 2)

(A, 1, 3)

(A, 1, 4)

(A, 2, 3)

(A, 2, 4)

(A, 3, 4)]]>