Competitions » Main CodeFu Competitons » CodeFu 2013 » Results

Results

Final Round Results

igorkulev's solution for 500: NamingSnakeTwins, written in Java, submitted on 09.06.2013 14:12:10

public class NamingSnakeTwins {

	public static void main(String[] args) {
		int answer = new NamingSnakeTwins().getCount("AAABABAA");
		//System.out.println(answer);
	}
	
	int bases[];
	int MODULO = 1000007;
	int UNDEFINED = 1000000000;
	
	public int getCount(String snakeString) {
		int i,j,k;
		int N = snakeString.length();
		
		if (N%2 == 1) {
			return 0;
		}
		
		int L = N/2;
		bases = new int[L+1];
		bases[0] = 1;
		for (i=1;i<=L;i++) {
			bases[i] = bases[i-1]*2;
		}
		
		int opt[][][] = new int[2][L+1][bases[L]];
		
		// A - 0
		// B - 1
		
		for (j=1;j<=L;j++) {
			for (k=0;k<bases[j];k++) {
				opt[0][j][k] = UNDEFINED;
			}
		}
		
		if (snakeString.charAt(0) == 'A') {
			// we have the valid combination 0 (A)
			opt[0][1][0] = 1;
		} else {
			opt[0][1][1] = 1;
		}
		
		int pos;
		int tk;
		
		for (i=1;i<N;i++) {
			int PREV = (i-1)%2;
			int CURR = i%2;
			
			for (j=1;j<=L;j++) {
				for (k=0;k<bases[j];k++) {
					opt[CURR][j][k] = UNDEFINED;
				}
			}
			
			char c = snakeString.charAt(i);
			
			// if we put the character in the second name
			for (j=1;j<=L;j++) {
				
				int f = j;
				int s = i+1-j;
				
				//System.out.println("FS: "+f+" "+s);
				
				if (s > f) {
					continue;
				}
				
				
				for (k=0;k<bases[j];k++) {
					if (opt[PREV][j][k] != UNDEFINED) {
						
						pos = i - j;
						
						if ((pos >= 0)&&(pos < (i+1-j)&&(pos < L))) {
						
							if ((bases[pos]&k) == 0) {
								// we expect A
								if (c == 'A') {
									
									if (opt[CURR][j][k] == UNDEFINED) {
										
										opt[CURR][j][k] = opt[PREV][j][k];
									} else {
										opt[CURR][j][k] += opt[PREV][j][k];
										opt[CURR][j][k] %= MODULO;
									}
									
								}
							} else {
								// we expect B
								if (c == 'B') {
									
									if (opt[CURR][j][k] == UNDEFINED) {
										opt[CURR][j][k] = opt[PREV][j][k];
									} else {
										opt[CURR][j][k] += opt[PREV][j][k];
										opt[CURR][j][k] %= MODULO;
									}
									
								}
							}
						}
						
					}
				}
			}
			
			// if we put the character in the first name
			if ((i == 1)&&(c == snakeString.charAt(0))) {
				if (c == 'A') {
					if (opt[PREV][1][0] == UNDEFINED) {
						opt[CURR][1][0] = 1;
					} else {
						opt[CURR][1][0] = opt[PREV][1][0] + 1;
					}
				} else {
					if (opt[PREV][1][1] == UNDEFINED) {
						opt[CURR][1][1] = 1;
					} else {
						opt[CURR][1][1] = opt[PREV][1][1] + 1;
					}
				}
			}
			
			for (j=1;j<L;j++) {
				for (k=0;k<bases[j];k++) {
					if (opt[PREV][j][k] != UNDEFINED) {
						if (c == 'A') {
							tk = k;
							if (opt[CURR][j+1][tk] == UNDEFINED) {
								opt[CURR][j+1][tk] = opt[PREV][j][k];
							} else {
								opt[CURR][j+1][tk] += opt[PREV][j][k];
								opt[CURR][j+1][tk] %= MODULO;
							}
						} else {
							tk = (k|bases[j]);
							if (opt[CURR][j+1][tk] == UNDEFINED) {
								opt[CURR][j+1][tk] = opt[PREV][j][k];
							} else {
								opt[CURR][j+1][tk] += opt[PREV][j][k];
								opt[CURR][j+1][tk] %= MODULO;
							}
						}
					}
				}
			}
			
			//System.out.println("\nITERATION: "+(i+1));
			for (j=1;j<=L;j++) {
				for (k=0;k<bases[j];k++) {
					//System.out.println("opt["+j+"]["+k+"] = "+opt[CURR][j][k]);
					
				}
			}
			
		}
		
		int CURR = (N-1)%2;
		
		int res = 0;
		for (i=0;i<bases[L];i++) {
			if (opt[CURR][L][i] != UNDEFINED) {
				res += opt[CURR][L][i];
				res %= MODULO;
				//System.out.println("R: "+opt[CURR][L][i]);
			}
		}
		
		res += res;
		res %= MODULO;
		
		return res;
	}

}

Test cases result

#	Test Case input	Expected	Received	Status
1.	"BABA"	2	2	Correct
2.	"BABBAB"	4	4	Correct
3.	"BBBAAA"	0	0	Correct
4.	"AB"	0	0	Correct
5.	"BBBBABBA"	8	8	Correct
6.	"AABBABAB"	8	4	Wrong
7.	"AAABABAA"	12	6	Wrong
8.	"BBBBABAAABAAABAAABABABBBAAABABAAABAB"	147900	11256	Wrong
9.	"AABAABBABBAAAABBABBBAABAAABAAABBBAAB"	24	24	Correct
10.	"BABABBABABAA"	28	8	Wrong
11.	"ABBBAABAABABBAAAABBBAAABBBBBABBBABAB"	2880	1440	Wrong
12.	"BBABBAAAABAAABABAAABBABABAABABBBBBAB"	4640	3290	Wrong
13.	"BBBBAABABAAABAABAABABBBABBBBBBAAAAAA"	575033	59200	Wrong
14.	"AAAAABBAABAABBABBBBBAABABABABABABABB"	29814	3932	Wrong
15.	"BBABAABAABAABAABABABABABBABABAAABAAB"	46576	17440	Wrong
16.	"BAABAAABABBAAAABBABBBAAAAAAAABBABABA"	504	168	Wrong
17.	"ABAABAAABBAAABBABBBABBAAAABAABBAABBA"	15040	2848	Wrong
18.	"BAAABBBBAABBABAABAABABBBAABBBBAABABB"	384	376	Wrong
19.	"BAAABBBABAABAAABBBAABBABBAAAABBABABB"	1608	804	Wrong
20.	"BABABABAAA"	18	8	Wrong
21.	"ABBABBBAAABABAAB"	8	6	Wrong
22.	"BABABAAABAABABABAAAABABBAA"	600	330	Wrong
23.	"BBBBBABBAB"	40	28	Wrong
24.	"BABAAABBABAAABAAABABAABABBAABA"	11036	1704	Wrong
25.	"BBBBABAAABAA"	36	18	Wrong
26.	"AAABBAAAAABBAABAABBABA"	210	140	Wrong
27.	"BBABBABBAAAAABBABAABBAABBBBBBBAABB"	57176	3060	Wrong
28.	"AABBAABABBBBBBABBBBBAAAABBBB"	13248	1024	Wrong
29.	"BABABAABBBABAAAABBBA"	8	8	Correct
30.	"ABABAABB"	8	2	Wrong
31.	"ABABAABABABBAABAAAAABAABABBBBBABBAAA"	27000	2160	Wrong
32.	"ABAABBBAAABBAA"	36	36	Correct
33.	"BBAABBABABBABBBBAB"	104	56	Wrong
34.	"BABBBBAAAABABABBAABABABABBAA"	144	72	Wrong
35.	"BABBABABBABBBBBB"	360	138	Wrong
36.	"ABABBBBBABBBBBABAAAA"	368	106	Wrong
37.	"BBBBAAAAABABBABBAB"	720	120	Wrong
38.	"ABAABABABBBBBAABBBBA"	120	80	Wrong
39.	"ABABBAAABBABBBABABBBBBAAAAAA"	3840	760	Wrong
40.	"BBABAAABAAAABAAABAAA"	944	534	Wrong
41.	"BBBABBAABABBABABBBBBBBABABBBAABABABB"	603000	52054	Wrong
42.	"AAAABAABBBABBBBAAABAABBBABABBB"	784	192	Wrong
43.	"BBBAABABBBAAABABAAAABABBBBAAAABABABB"	9776	932	Wrong
44.	"ABBBBABAAABBBABAABBBBABABBABABBB"	410	86	Wrong
45.	"BBABBABBBBAAAABAABBBBBBBBBBABA"	103488	6336	Wrong
46.	"AABBAABBAAABABABBBABBBBB"	6988	810	Wrong
47.	"BBBBBABA"	20	14	Wrong
48.	"BBABAABBBBBBABAAABABABBABBAABABBBA"	90	90	Correct
49.	"AAAABBABBAABBBBABAAB"	16	16	Correct
50.	"ABABBBAAAA"	36	8	Wrong
51.	"AABBABBBAABAABAABBAABAAABBABBBAAAB"	96	96	Correct
52.	"AABBAABABBBAAAABABBAABBABAAABBABBAAA"	27172	8646	Wrong
53.	"ABABBAABAAAABB"	48	12	Wrong
54.	"BBABABBB"	12	8	Wrong
55.	"BABBBABABBAABAAAAABAAB"	628	404	Wrong
56.	"AAABBAABABBAABAABBBBABAAABAAAAABAB"	50644	3904	Wrong
57.	"AABBABBBAAAABABAABAABAAAABBAAB"	2880	2304	Wrong
58.	"BABAAAAA"	20	10	Wrong
59.	"ABABBBABABAAAA"	104	26	Wrong
60.	"ABBBABAAABBBBAAABABABABBAAABBBAABBAA"	9334	3042	Wrong
61.	"ABABAABAAABBAB"	24	12	Wrong
62.	"ABBBBBABAABBBBABABAABAAB"	22	20	Wrong
63.	"BAABBABBBABAAABABBABABAAAABBAABABA"	1072	504	Wrong
64.	"ABBAAABBBBBBABBBABBBAABBBBAA"	90	90	Correct
65.	"BBABAABAABAAAABBBBBBABABBBABBABAAAAA"	13210	7112	Wrong
66.	"BABBBBBABABBAABBABAAAAABABBABBBABB"	5742	2310	Wrong
67.	"BBABBAAABABAAABBABBABBBBBBAAAA"	46980	3116	Wrong
68.	"BBAAAAAA"	40	20	Wrong
69.	"AAAABAABBBBBBAAABAAABBBBBABBBABB"	22400	2128	Wrong
70.	"AABBAABBAAABBBBAABAB"	2	2	Correct
71.	"BBBBBBBBABBABBBABBBAAABABBBA"	552	498	Wrong
72.	"AABBAAAAABBBABBABBBABABAAAAAABAAABAA"	173040	14680	Wrong
73.	"BABBBBABABBAABBBABABBABBABBA"	310	238	Wrong
74.	"AAABAAABABAB"	28	26	Wrong
75.	"ABAABBBAABABBABBAAAAABBBAABBAA"	480	240	Wrong
76.	"ABABBBABBBBAAAAABBABABBBBBBABABBBABA"	23490	1434	Wrong
77.	"BAAAABAABAABBBBB"	20	10	Wrong
78.	"BBBBAABABBABBBBABAABBABBBBBBABBBBABB"	320304	34192	Wrong
79.	"BAAABAABBABABBABBAAABBAAAB"	60	48	Wrong
80.	"AABABBABBBAAAAABABBABBBAAABABABB"	8984	1054	Wrong
81.	"BABBAABABBAABBAAAABAABBBBB"	7840	630	Wrong
82.	"BBAABAAAAABBBAAABBAAAABBAAABBABBAA"	32064	2388	Wrong
83.	"AABAABABAABA"	28	24	Wrong
84.	"BBABABABABAABABAAABB"	738	136	Wrong
85.	"BABABBAAAAABABABAAAABBAB"	468	462	Wrong
86.	"BBABBBAB"	6	6	Correct
87.	"BBBBBBBBABBAABABAABBAA"	5264	594	Wrong
88.	"AAABAABBABBAAAABBABABBAABB"	168	168	Correct
89.	"AAAABAABAABBABABAABBABABAAABAB"	26732	4064	Wrong
90.	"ABABABBAABBBABBABABB"	354	118	Wrong
91.	"AABBBBBBBBABBBBBBBBABABAAABABAABAB"	22568	7476	Wrong
92.	"ABABABBBBBAABABBBABAABAAAB"	116	108	Wrong
93.	"BABABAABAABBAAAA"	152	22	Wrong
94.	"BBABBAAABAABBBAAAABBBABBBBBA"	60	60	Correct
95.	"AABBABAABABABABBABABBB"	1340	270	Wrong
96.	"BABABABBABAABBBBBBBBBABBABBAABBB"	26136	2472	Wrong
97.	"BBAABBABBABBABAAABBAABBAAAAAAABA"	364	196	Wrong
98.	"BBAABABBBAABABBBBBBBABBBBAAABABBBABB"	9504	2820	Wrong
99.	"AABAABABBAABBBBBABBABBAABA"	1280	1120	Wrong
100.	"BABABBBBBBABBBBBAABAABAABAAABABBAABAAA"	153268	15322	Wrong