

As far as I know no straightforward C/C++ solution passes (i.e. using hashmap or map). Can you please show me an example of such code? Using arrays for cache instead of hashmap/map is kind of the definition of "dynamic programming" for programming contests. 

After checking correct problems in practice room. I haven't seen anything more clever then really checking 2*(lg(Xi))^5 states.
Passing solutions just have cache in 6dimensional 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. 

It's actually only (2*lg(Xi))^5 / 5. Because the rotation of circle doesn't matter for # of combinations. Even (2*lg(Xi))^5 / 10 is possible, because the direction also doesn't change the result.
Unfortunately it's still too high for straightforward Java solution. 

I think this problem has too loose constraints for Java.
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... 

I see you are using HashMap  maybe it's too slow, I'd rather encode the state as espr1t said.
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. 

This code is working fine  it returns correct result, but it is too slow for espr1t's worst case example (almost 10s on localhost). I'm not sure if some optimization helps, maybe it will be quick enought in C++
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
public class EllysFiveFriends {
private static int MOD = 1000000007;
private static Map<State, Integer> cache = new HashMap<State, Integer>( 1000000 );
public int getZero( final int[] numbers ) {
cache.put( new State( new int[] { 0, 0, 0, 0, 0 } ), 1 );
return (int) getZero( new State( numbers ) );
}
public static long getZero( final State s ) {
if ( cache.containsKey( s ) )
return cache.get( s );
if ( justOneIsNonZero( s ) )
return 0;
long res = 0;
for ( int i = 0; i < 5; ++i ) {
if ( s.a[ i ] == 0 ) continue;
final int j = ( i + 1 ) % 5;
if ( s.a[ j ] == 0 ) continue;
final int[] oa = new int[5];
for ( int k = 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( new State( oa ) );
++oa[ i ];
++oa[ j ];
oa[ i ] /= 2;
oa[ j ] /= 2;
res += getZero( new State( oa ) );
} else {
oa[ i ] /= 2;
oa[ j ] /= 2;
res += getZero( new State( oa ) );
}
}
res %= MOD;
cache.put( s, (int) res );
return res;
}
private static boolean justOneIsNonZero( final State s ) {
int cnt = 0;
for ( final int x : s.a )
if ( x > 0 ) ++cnt;
return cnt == 1;
}
private static class State {
int[] a = new int[5];
public State( final int[] a ) {
for ( int i = 0; i < 5; ++i ) {
this.a[ i ] = a[ i ];
}
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + Arrays.hashCode( this.a );
return result;
}
@Override
public boolean equals( final Object obj ) {
if ( this == obj ) return true;
if ( obj == null ) return false;
if ( this.getClass() != obj.getClass() ) return false;
final State other = (State) obj;
if ( !Arrays.equals( this.a, other.a ) ) return false;
return true;
}
}
}


I can't wait to read the editorial. I knew my simple recursive solution would fail a ton of test cases, but I felt the need to solve the problem _somehow_.
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 

"...they have to be next to eachother..."
That's what I missed... 

* 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 eachother and each should have nonzero 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 5dimensional 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 5dimensional, 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). 

You are right that there is not a lot of states (at least I think so  that's how I wrote about decreasing quickly), but I definitely missed something in statement.
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) 

Let's say Xi denotes the integer for the ith girl in the beginning of the game (oh, well Xi = numbers[i]). Then, there's only 2 * lg Xi possible reachable integers of the ith girl. So, for 5 girls, there are only (2 * lg Xi)^5 possible configurations of integers, right? 

Please ignore this post (I thought I misread something, but it turns out I didn't) 

I didn't understand your hint. X was not input, just the numbers[]...
First I thought that the numbers will decrease quickly because of second rule
if ( numbers[i] % 2 == 0  numbers[j] % 2 == 0) {
numbers[i] /= 2;
numbers[j] /= 2;
}
But there is a problem, it's not decreasing so fast... 

If a girl initially has X juice, then there's only 2 * lg X reachable amounts of juice. So it's, um.. very small? 

Anyone give a hint? it seems that whether you can reach all zero or not does not need the apple operation, but I do not see how to count. 
