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)
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)
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; // it's ordered
			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;
		}
 
	}
}