The problem set of this SRM is awesome. Although I couldn’t manage to solve even a single problem in the contest, I could say that I really had fun doing it! 😀

I spent the whole 75 minutes doing the 500 pt problem, in which I got TLE because my code run about 2.* s. First, I miscalculated the space complexity of my algorithm (I thought it was O(n^3), but actually it was O(n^5)) After spending about 45 minutes coding and testing the must-be-MLE (Memory Limit Exceeded) code, I figure out that this code was actually using O(n^5) space. Ouch ><“. Then, I quickly changed my solution totally to the one described below:

My solution was based on KMP string matching algorithm which run in O(n^5). Failing to get it fast enough, I did my last optimization in the last minute, compiled, and clicked submit button without doing any testing. Yes, it’s definitely a desperate submission. But at least there was some hope for it to pass. I love this kind of hope and optimistic, it seems that I born to be an optimistic person =D

At the challenge phase, without waiting for a long time, my code was challenged. Nice, my last optimization actually made my code run slower. I started looking for the remaining two 500 pt solutions in my room. Both were coded by red coders. After reading one of the code for a while, I decided to challenge it since the complexity was hard to count (I only could bound it roughly and it seemed that the order was really high). My challenge was obvious worst case, “aaa…a” (47 a’s). And without any surprise (because it was coded by a red coder =P), my challenge was unsuccessful. Of course! What on earth I was thinking about, a red coder submitted his/her solution without testing it with such dumb case? XD

Well, the SRM was ended dramatically. I got -25 points and got my old color! Blue coder again, such a nostalgic color…

Well, here is my solution on 500 pt which I successfully optimized after the contest and passed the system test in the practice room.

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

#define REP(i,n) for(int i = 0, _n = (n); i < _n; i++)
#define FOR(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i,a,b) for (int i = (a), _b = (b); i >= _b; i--)

using namespace std;

class TheBoringStoreDivOne {
public:
	string find(string, string);
};

int fail[205];

inline void comppref (const char *B, int blen) {
	int k = fail[0] = -1;
	FOR (i, 1, blen - 1) {
		while (k >= 0 && B[k + 1] != B[i])
			k = fail[k];
		if (B[k + 1] == B[i])
			k++;
		fail[i] = k;
	}
}

inline int kmp (const char *A, const char *B, int blen) {
	int k = -1, ret = 0;
	comppref (B, blen);
	REP (i, strlen (A)) {
		while (k > -1 && B[k + 1] != A[i])
			k = fail[k];
		if (B[k + 1] == A[i])
			k++;
		ret = max (ret, k + 1);
		if (k == blen - 1) {
			k = fail[k];
		}
	}
	return ret;
}

int alen, blen;
char a[55], b[55], s[205];
char ans[55];
int anslen = 0;
char J[55], B[55];

string TheBoringStoreDivOne::find(string AA, string BB) {
	strcpy (J, AA.c_str());
	strcpy (B, BB.c_str());
	
	int Jlen = strlen (J), Blen = strlen (B);
	
	anslen = 0;
	ans[anslen] = 0;
	
	REP (i, Jlen) {
		alen = 0;
		a[alen] = 0;
		FOR (j, i, Jlen - 1) {
			a[alen++] = J[j];
			a[alen] = 0;
			strcpy (b, a);
			REP (k, Blen) {
				FOR (l, k, Blen - 1) {
					a[alen++] = B[l];
					a[alen] = 0;
					int slen = 0;
					FOR (p, j + 1, Jlen - 1) s[slen++] = J[p];
					s[slen] = 0;
					int xx = kmp (s, a, alen);
					slen = 0;
					FORD (p, Blen - 1, l + 1) s[slen++] = B[p];
					s[slen++] = '$';
					FORD (p, k - 1, 0) s[slen++] = B[p];
					s[slen] = 0;
					reverse (a, a + alen);
					int yy = kmp (s, a, alen);
					reverse (a, a + alen);
					if (xx && yy && xx + yy >= alen && (alen > anslen || (alen == anslen && strcmp (a, ans) < 0))) {
						for (int w = 0; a[w]; w++)
							ans[w] = a[w];
						anslen = alen;
					}
				}
				strcpy (a, b);
				alen = strlen (a);
			}
		
		}
	}
	
	return (string) ans;
}


//Powered by [KawigiEdit] 2.0!

Explanation:

First, to make it easier, denote A, B, C, D as the corresponding variables in the problem statement, John is the string J in the parameter of the subroutine, and Brus is the string B in the parameter of the subroutine (to avoid confusion of using two B’s).

The outer-most O(n^4) loop is obvious, they iterate through all possible first names. After that, we search the second name which is not overlapping the first name. We can suppose B is on the right side of A but D can be in any sides of C (either left or right). Search the length of the longest sub-string of string J on the right side of A which is the prefix of A+C by using KMP. Let’s say it is xx (according to the variable name used in my code). And suppose we change C with “$” in Brus. Let’s denote the new string formed as string s. Count the length of the longest sub-string of s which is also the suffix of A+C. It can be done by the same way as searching the longest prefix of A+C in s. Speaking in more detail, it can be done by reversing both A+C and s and search the longest prefix of the reverse of A+C in the reverse of S [Tips for beginner: If you don’t know how to do this and willing to know how to do this, you should learn KMP more carefully =P In KMP with normal implementation, the length of the longest prefix match so far (or the length – 1) is stored in a variable when the matching function is executed]. Since the “$” sign is not part of A+C, the longest suffix found must be either on the left of C or on the right side of C. If the length of such sub-string is yy and xx + yy >= the length of (A + C), we know that (A + C) is one of the candidate solution. The rest is easy.

The adding “$” sign trick that I used in my code speed it up by almost a factor of two and makes my code pass the system test.

P.S.: Sorry for my terrible English. Any correction in Grammar, Spelling, or anything are expected and VERY welcome 😀

#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

#define REP(i,n) for(int i = 0, _n = (n); i < _n; i++)
#define FOR(i,a,b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i,a,b) for (int i = (a), _b = (b); i >= _b; i–)

using namespace std;

class TheBoringStoreDivOne {
public:
string find(string, string);
};

int fail[205];

inline void comppref (const char *B, int blen) {
int k = fail[0] = -1;
FOR (i, 1, blen – 1) {
while (k >= 0 && B[k + 1] != B[i])
k = fail[k];
if (B[k + 1] == B[i])
k++;
fail[i] = k;
}
}

inline int kmp (const char *A, const char *B, int blen) {
int k = -1, ret = 0;
comppref (B, blen);
REP (i, strlen (A)) {
while (k > -1 && B[k + 1] != A[i])
k = fail[k];
if (B[k + 1] == A[i])
k++;
ret = max (ret, k + 1);
if (k == blen – 1) {
k = fail[k];
}
}
return ret;
}

int alen, blen;
char a[55], b[55], s[205];
char ans[55];
int anslen = 0;
char J[55], B[55];

string TheBoringStoreDivOne::find(string AA, string BB) {
strcpy (J, AA.c_str());
strcpy (B, BB.c_str());

int Jlen = strlen (J), Blen = strlen (B);

anslen = 0;
ans[anslen] = 0;

REP (i, Jlen) {
alen = 0;
a[alen] = 0;
FOR (j, i, Jlen – 1) {
a[alen++] = J[j];
a[alen] = 0;
strcpy (b, a);
REP (k, Blen) {
FOR (l, k, Blen – 1) {
a[alen++] = B[l];
a[alen] = 0;
int slen = 0;
FOR (p, j + 1, Jlen – 1) s[slen++] = J[p];
s[slen] = 0;
int xx = kmp (s, a, alen);
slen = 0;
FORD (p, Blen – 1, l + 1) s[slen++] = B[p];
s[slen++] = ‘$’;
FORD (p, k – 1, 0) s[slen++] = B[p];
s[slen] = 0;
reverse (a, a + alen);
int yy = kmp (s, a, alen);
reverse (a, a + alen);
if (xx && yy && xx + yy >= alen && (alen > anslen || (alen == anslen && strcmp (a, ans) < 0))) {
for (int w = 0; a[w]; w++)
ans[w] = a[w];
anslen = alen;
}
}
strcpy (a, b);
alen = strlen (a);
}

}
}

return (string) ans;
}

//Powered by [KawigiEdit] 2.0!

Advertisements