JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat  | Threaded  | Tree
Previous Thread  |  Next Thread
div 2 p1000 | Reply
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.
Re: div 2 p1000 (response to post by lantimilan) | Reply
If a girl initially has X juice, then there's only 2 * lg X reachable amounts of juice. So it's, um.. very small?
Re: div 2 p1000 (response to post by dolphinigle) | Reply
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...
Re: div 2 p1000 (response to post by Betlista) | Reply
Please ignore this post (I thought I misread something, but it turns out I didn't)
Re: div 2 p1000 (response to post by Betlista) | Reply
Let's say Xi denotes the integer for the i-th girl in the beginning of the game (oh, well Xi = numbers[i]). Then, there's only 2 * lg Xi possible reachable integers of the i-th girl. So, for 5 girls, there are only (2 * lg Xi)^5 possible configurations of integers, right?
Re: div 2 p1000 (response to post by dolphinigle) | Reply
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)
Re: div 2 p1000 (response to post by Betlista) | Reply
* 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 espr1t) | Reply
"...they have to be next to each-other..."

That's what I missed...
Re: div 2 p1000 (response to post by Betlista) | Reply
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;
		}
 
	}
}
Re: div 2 p1000 (response to post by Betlista) | Reply
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.
Re: div 2 p1000 (response to post by Renato_Ferreira) | Reply
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...
Re: div 2 p1000 (response to post by espr1t) | Reply
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
Re: div 2 p1000 (response to post by dolphinigle) | Reply
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 straight-forward Java solution.
Re: div 2 p1000 (response to post by cpoc) | Reply
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 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.
Re: div 2 p1000 (response to post by cpoc) | Reply
As far as I know no straight-forward 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.
RSS