JOIN
 Revision History
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums 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 cache = new HashMap( 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 cache = new HashMap( 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; }   } } ```