Competitions » Main CodeFu Competitons » CodeFu 2013 » Results

Results

Final Round Results

birbbit's solution for 500: NamingSnakeTwins, written in C++, submitted on 09.06.2013 14:13:04

#include<cctype>
#include<cmath>
#include<string>
#include<list>
#include<deque>
#include<stack>
#include<utility>
#include<sstream>
#include<bitset>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
#include<queue>
#include<set>

#define mp make_pair
#define pb push_back
#define ms(x,y) memset((x),(y),sizeof((x)))
#define all(c) c.begin(),c.end()
#define emp(a,i) (!((a) & (1<<(i))))
#define sh(a) (1<<(a))

using namespace __gnu_cxx;
using namespace std;


int dp[40][20][sh(18)][2];

class NamingSnakeTwins
{
  public:
  inline int find(char p){
    if(p=='A')
        return 0;
    return 1;
  }
  inline int fastmod(int x){
    if(x>1000007)
        x-= 1000007;
    return x;
  }
    int getCount(string str)
    {
        int n=str.size(), mod = 1000007;
        if(str.size()%2==1) return 0;
        //ms(dp,0);

        int N=n/2;


        dp[0][0][0][0]=1;
        for(int i=0;i<n;i++){
            for(int j=0;j<=N;j++){ // <=
                for(int q=0;q<=sh(N);q++){
                int w=j>=i-j ? 0 : 1;
                if(dp[i][j][q][w]!=0){
                    // da go zeme ovoj ako moze
                    if(j>=i-j){
                        if(j!=N){
                            dp[i+1][j+1][q*2+find(str[i])][0]=
                            fastmod(dp[i][j][q][0]+dp[i+1][j+1][q*2+find(str[i])][0]);
                        }
                        // da proba da go zeme drugiot
                        if((str[i]=='A' && emp(q, 2*j-i-1)) ||
                           (str[i]=='B' && !emp(q, 2*j-i-1))){
                            if(j==i-j)
                                dp[i+1][j][q][1]=fastmod(dp[i][j][q][0]+dp[i+1][j][q][1]);
                            else
                                dp[i+1][j][q][0]=fastmod(dp[i][j][q][0]+dp[i+1][j][q][0]);
                        }
                    }
                    if(i-j>=j){ // w = 1
                        if(i-j<N){
                            if(i-j>j)
                                dp[i+1][j][q][1]=fastmod(dp[i][j][q][1]+dp[i+1][j][q][1]);
                            else
                                dp[i+1][j][q][1]=fastmod(dp[i][j][q][0]+dp[i+1][j][q][1]);
                        }
                        if((str[i]=='A' && !emp(q, 2*j-i-1)) ||
                           (str[i]=='B' && emp(q, 2*j-i-1))){
                            if(j==i-j-1)
                                dp[i+1][j][q*2+find(str[i])][0]=fastmod(dp[i][j][q][1]+dp[i+1][j][q*2+find(str[i])][0]);
                            else
                                dp[i+1][j][q*2+find(str[i])][1]=fastmod(dp[i][j][q][1]+dp[i+1][j][q*2+find(str[i])][1]);
                        }
                    }
                }
            }
            }
        }

    int sum=0;
    for(int q=0;q<=sh(N);q++)
        sum=fastmod(sum + dp[n][N][q][0]);

      return fastmod(2*sum);
  }
};

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	6	Wrong
6.	"AABBABAB"	8	2	Wrong
7.	"AAABABAA"	12	4	Wrong
8.	"BBBBABAAABAAABAAABABABBBAAABABAAABAB"	147900		Timeout
9.	"AABAABBABBAAAABBABBBAABAAABAAABBBAAB"	24		Timeout
10.	"BABABBABABAA"	28	8	Wrong
11.	"ABBBAABAABABBAAAABBBAAABBBBBABBBABAB"	2880		Timeout
12.	"BBABBAAAABAAABABAAABBABABAABABBBBBAB"	4640		Timeout
13.	"BBBBAABABAAABAABAABABBBABBBBBBAAAAAA"	575033		Timeout
14.	"AAAAABBAABAABBABBBBBAABABABABABABABB"	29814		Timeout
15.	"BBABAABAABAABAABABABABABBABABAAABAAB"	46576		Timeout
16.	"BAABAAABABBAAAABBABBBAAAAAAAABBABABA"	504		Timeout
17.	"ABAABAAABBAAABBABBBABBAAAABAABBAABBA"	15040		Timeout
18.	"BAAABBBBAABBABAABAABABBBAABBBBAABABB"	384		Timeout
19.	"BAAABBBABAABAAABBBAABBABBAAAABBABABB"	1608		Timeout
20.	"BABABABAAA"	18	8	Wrong
21.	"ABBABBBAAABABAAB"	8	6	Wrong
22.	"BABABAAABAABABABAAAABABBAA"	600	330	Wrong
23.	"BBBBBABBAB"	40	20	Wrong
24.	"BABAAABBABAAABAAABABAABABBAABA"	11036	1704	Wrong
25.	"BBBBABAAABAA"	36	12	Wrong
26.	"AAABBAAAAABBAABAABBABA"	210	120	Wrong
27.	"BBABBABBAAAAABBABAABBAABBBBBBBAABB"	57176	2544	Wrong
28.	"AABBAABABBBBBBABBBBBAAAABBBB"	13248	976	Wrong
29.	"BABABAABBBABAAAABBBA"	8	8	Correct
30.	"ABABAABB"	8	2	Wrong
31.	"ABABAABABABBAABAAAAABAABABBBBBABBAAA"	27000		Timeout
32.	"ABAABBBAAABBAA"	36	36	Correct
33.	"BBAABBABABBABBBBAB"	104	32	Wrong
34.	"BABBBBAAAABABABBAABABABABBAA"	144	72	Wrong
35.	"BABBABABBABBBBBB"	360	138	Wrong
36.	"ABABBBBBABBBBBABAAAA"	368	106	Wrong
37.	"BBBBAAAAABABBABBAB"	720	80	Wrong
38.	"ABAABABABBBBBAABBBBA"	120	80	Wrong
39.	"ABABBAAABBABBBABABBBBBAAAAAA"	3840	760	Wrong
40.	"BBABAAABAAAABAAABAAA"	944	292	Wrong
41.	"BBBABBAABABBABABBBBBBBABABBBAABABABB"	603000		Timeout
42.	"AAAABAABBBABBBBAAABAABBBABABBB"	784	144	Wrong
43.	"BBBAABABBBAAABABAAAABABBBBAAAABABABB"	9776		Timeout
44.	"ABBBBABAAABBBABAABBBBABABBABABBB"	410	86	Wrong
45.	"BBABBABBBBAAAABAABBBBBBBBBBABA"	103488	3960	Wrong
46.	"AABBAABBAAABABABBBABBBBB"	6988	468	Wrong
47.	"BBBBBABA"	20	10	Wrong
48.	"BBABAABBBBBBABAAABABABBABBAABABBBA"	90	90	Correct
49.	"AAAABBABBAABBBBABAAB"	16	12	Wrong
50.	"ABABBBAAAA"	36	8	Wrong
51.	"AABBABBBAABAABAABBAABAAABBABBBAAAB"	96	48	Wrong
52.	"AABBAABABBBAAAABABBAABBABAAABBABBAAA"	27172		Timeout
53.	"ABABBAABAAAABB"	48	12	Wrong
54.	"BBABABBB"	12	4	Wrong
55.	"BABBBABABBAABAAAAABAAB"	628	404	Wrong
56.	"AAABBAABABBAABAABBBBABAAABAAAAABAB"	50644	2662	Wrong
57.	"AABBABBBAAAABABAABAABAAAABBAAB"	2880	1152	Wrong
58.	"BABAAAAA"	20	10	Wrong
59.	"ABABBBABABAAAA"	104	26	Wrong
60.	"ABBBABAAABBBBAAABABABABBAAABBBAABBAA"	9334		Timeout
61.	"ABABAABAAABBAB"	24	12	Wrong
62.	"ABBBBBABAABBBBABABAABAAB"	22	20	Wrong
63.	"BAABBABBBABAAABABBABABAAAABBAABABA"	1072	504	Wrong
64.	"ABBAAABBBBBBABBBABBBAABBBBAA"	90	90	Correct
65.	"BBABAABAABAAAABBBBBBABABBBABBABAAAAA"	13210		Timeout
66.	"BABBBBBABABBAABBABAAAAABABBABBBABB"	5742	2310	Wrong
67.	"BBABBAAABABAAABBABBABBBBBBAAAA"	46980	2768	Wrong
68.	"BBAAAAAA"	40	10	Wrong
69.	"AAAABAABBBBBBAAABAAABBBBBABBBABB"	22400	1596	Wrong
70.	"AABBAABBAAABBBBAABAB"	2	2	Correct
71.	"BBBBBBBBABBABBBABBBAAABABBBA"	552	402	Wrong
72.	"AABBAAAAABBBABBABBBABABAAAAAABAAABAA"	173040		Timeout
73.	"BABBBBABABBAABBBABABBABBABBA"	310	238	Wrong
74.	"AAABAAABABAB"	28	20	Wrong
75.	"ABAABBBAABABBABBAAAAABBBAABBAA"	480	240	Wrong
76.	"ABABBBABBBBAAAAABBABABBBBBBABABBBABA"	23490		Timeout
77.	"BAAAABAABAABBBBB"	20	10	Wrong
78.	"BBBBAABABBABBBBABAABBABBBBBBABBBBABB"	320304		Timeout
79.	"BAAABAABBABABBABBAAABBAAAB"	60	48	Wrong
80.	"AABABBABBBAAAAABABBABBBAAABABABB"	8984	602	Wrong
81.	"BABBAABABBAABBAAAABAABBBBB"	7840	630	Wrong
82.	"BBAABAAAAABBBAAABBAAAABBAAABBABBAA"	32064	1194	Wrong
83.	"AABAABABAABA"	28	18	Wrong
84.	"BBABABABABAABABAAABB"	738	88	Wrong
85.	"BABABBAAAAABABABAAAABBAB"	468	462	Wrong
86.	"BBABBBAB"	6	6	Correct
87.	"BBBBBBBBABBAABABAABBAA"	5264	448	Wrong
88.	"AAABAABBABBAAAABBABABBAABB"	168	112	Wrong
89.	"AAAABAABAABBABABAABBABABAAABAB"	26732	3054	Wrong
90.	"ABABABBAABBBABBABABB"	354	118	Wrong
91.	"AABBBBBBBBABBBBBBBBABABAAABABAABAB"	22568	3738	Wrong
92.	"ABABABBBBBAABABBBABAABAAAB"	116	108	Wrong
93.	"BABABAABAABBAAAA"	152	22	Wrong
94.	"BBABBAAABAABBBAAAABBBABBBBBA"	60	42	Wrong
95.	"AABBABAABABABABBABABBB"	1340	160	Wrong
96.	"BABABABBABAABBBBBBBBBABBABBAABBB"	26136	2472	Wrong
97.	"BBAABBABBABBABAAABBAABBAAAAAAABA"	364	112	Wrong
98.	"BBAABABBBAABABBBBBBBABBBBAAABABBBABB"	9504		Timeout
99.	"AABAABABBAABBBBBABBABBAABA"	1280	960	Wrong
100.	"BABABBBBBBABBBBBAABAABAABAAABABBAABAAA"	153268		Timeout