Codechef June 2013

I’ll describe my solutions of Codechef – June 2013. In this contest I have solved 5 problems using C++.

  • Lapindromes (Ad Hoc – Implementation)
  • Predictopus (Probability)
  • W String (Ad Hoc – Implementation)
  • Dessert Wizard (Ad Hoc – Implementation)
  • Little Elephant and Mouses(Dynamic Programming)

Problem Level 1: Lapindromes (Ad Hoc – Implementation)

[latexpage]After analyse the problem we can say that a Palindrome is an string of the next form:

begin{equation}sum_{i=0}^{N/2-1}{(cad_i = ch)} = sum_{i=N/2+1}^{N-1}{(cad_i = ch)}  text{for ch = a,b,c, … ,y,z}end{equation}

Ok we know that with only 26 letters using only lowercase English alphabet we can iterate for each character in the string $cad$ and obtain the total sum of each character from ‘a’ to ‘z’ on left side and right side of this string. Before that we can obtain see if left side have the same number of characters of each kind.

But simpler, we can obtain the total count of left side and we can remove the total count of left side with the right side. Before that we can verify if the count is 0 (zero) for each character from ‘a’ to ‘z’.

bool isALapindromo(string& s) {
	vector<int> count(26, 0);
	int N = s.size();
	for(int i=0; i<N/2 ;i++)
		count[ s[i]-'a' ]++;
	for(int i=N/2+(N&1); i<N ;i++)
		count[ s[i]-'a' ]--;
	for(int i=0; i<26 ;i++)
		if(count[i])
			return false;
	return true;
}

int main() {
	int T;
	string s;
	scanf("%d", &T);
	for(int cas=0; cas<T ;cas++) {
		cin >> s;
		if(isALapindromo(s)) printf("YESn");
		else printf("NOn");
	}
}

Problem Level 1 – Predictopus (Probability)

In this problem we can use the weighted arithmetic mean formula (http://en.wikipedia.org/wiki/Weighted_mean) to obtain the expected amount of money for different bets mounts.

Replacing the Prize formula on the Weighted Mean formula, we can prove that always we will win rupees and the best is to bet 10000 rupees. Now we can probe that the best bets are when we put 10000 on A or B.

With this we only need to obtain maximum prize doing the bet on A or B.

double winRupees(double m, double p) {
	return 10000.0*p - 20000.0*p*p - m + 2.0*m*p;
}

int main() {
	int T;
	scanf("%d", &T);
	double p, prize;
	for(int cas=0; cas<T ;cas++) {
		scanf("%lf", &p);
		prize = max(winRupees(0, p), winRupees(10000, p)) + 10000.0;
		printf("%.7lfn", prize);
	}
}

Problem Level 2 – W String (Ad Hoc – Implementation)

This problem is little tricky to implement, actually we can describe the problem with the next formula.

begin{equation}F(A-1)+1+G(A+1,B-1)+1+G(B+1,C-1)+1+F^{-1}(C+1)end{equation}

And we are searching the values A, B, C that maximize that formula, in order to have accepted (don’t obtain TLE) we can obtain the values on $O(n)$ but we have a problem when searching the maximum values with F, G and F^-1 functions.

$F$ is the maximum value using a character ch from 0-th to (A-1)-th

$G$ is the maximum value using a character ch from (X+1)-th to (Y-1)-th without a sharp character between them.

$F^{-1}$ is the maximum value from (C+1)-th to (N-1)-th

We can obtain these values ​​separately in $O(n*26)$ and save them in arrays to obtain the maximum value.

#define FOR(i,a,b)  for(int i=(a),_##i=(b);i<_##i;++i)
#define F(i,a)      FOR(i,0,a)
#define S           size()

int c0[10000], c1[10000], c2[10000];

int main() {
	int T, N, count[26], genCount[26], maxi0, maxi1, maxi2, total, res;
	char ch;
	string s;
	scanf("%d", &T);
	F(cas, T) {
		memset(count, 0, sizeof(count));
		memset(genCount, 0, sizeof(genCount));
		vector<int> its;
		cin >> s;
		N = s.S;
		total = 0;
		F(i, N) {
			if(s[i] == '#') {
				maxi0 = maxi1 = 0;
				F(j, 26) {
					maxi0 = max(maxi0, genCount[j]);
					maxi1 = max(maxi1, count[j]);
					count[j] = 0;
				}
				its.PB(i);
				c0[i] = maxi0;
				c1[i] = maxi1;
			}
			else {
				ch = s[i]-'a';
				count[ch]++;
				genCount[ch]++;
				total++;
			}
		}

		memset(genCount, 0, sizeof(genCount));
		for(int i=N-1; i>0 ;i--) {
			if(s[i] == '#') {
				maxi2 = 0;
				F(j, 26) maxi2 = max(maxi2, genCount[j]);
				c2[i] = maxi2;
			}
			else genCount[s[i]-'a']++;
		}

		res = 0;
		F(i, its.S-2) {
			if(c0[its[i]] && c1[its[i+1]] && c1[its[i+2]] && c2[its[i+2]]) {
				maxi0 = c0[its[i]];
				maxi1 = c1[its[i+1]] + c1[its[i+2]];
				maxi2 = c2[its[i+2]];
				res = max(res, maxi0+maxi1+maxi2+3);
			}
		}
		printf("%dn", res);
	}
}

Problem Level 2 – Dessert Wizard (Ad Hoc – Implementation)

typedef long long   LL;
int N, D[10000];
LL midMinD[10000], midMaxD[10000];

int main() {
	int T;
	LL total, minleft, maxleft, minright, maxright, minmid, maxmid, res;
	scanf("%d", &T);
	for(int cas=0; cas<T ;cas++) {
		scanf("%d", &N);
		for(int i=0; i<N ;i++)
			scanf("%d", D+i);
		total = minleft = maxleft = midMinD[N-1] = midMaxD[N-1] = D[N-1];
		for(int i=N-2; i>0 ;i--) {
			total += LL(D[i]);
			minleft = min(minleft+LL(D[i]), LL(D[i]) );
			maxleft = max(maxleft+LL(D[i]), LL(D[i]) );
			midMinD[i] = min(midMinD[i+1], min(minleft, total));
			midMaxD[i] = max(midMaxD[i+1], max(maxleft, total));
		}
		total = minright = maxright = minmid = maxmid = D[0];
		res = max(abs(D[0] - midMinD[1]), abs(D[0] - midMaxD[1]));
		for(int i=1; i<N-1 ;i++) {
			total += LL(D[i]);
			minright = min(minright+LL(D[i]), LL(D[i]) );
			maxright = max(maxright+LL(D[i]), LL(D[i]) );
			minmid = min(minmid, min(minright, total));
			maxmid = max(maxmid, max(maxright, total));
			res = max(res, abs(maxmid - midMinD[i+1]) );
			res = max(res, abs(minmid - midMaxD[i+1]) );
		}
		printf("%lldn", res);
	}
}

Problem Level 3 – Little Elephant and Mouses(Dynamic Programming)

#define MP          make_pair
int n, m;

pair<int,int> used1[102][102], used2[102][102];
int A[102][102], DP1[102][102], DP2[102][102];

void solve(int x, int y) {
	int always = A[x][y+1] + A[x+1][y];

	int a1 = DP1[x][y-1] + always + ((used1[x][y-1] == MP(x-1, y))? 0:A[x-1][y]);
	int a2 = DP2[x][y-1] + always + ((used2[x][y-1] == MP(x-1, y))? 0:A[x-1][y]);
	DP1[x][y] = min(a1, a2);
	used1[x][y] = MP(x+1, y-1);

	int b1 = DP1[x-1][y] + always + ((used1[x-1][y] == MP(x, y-1))? 0:A[x][y-1]);
	int b2 = DP2[x-1][y] + always + ((used2[x-1][y] == MP(x, y-1))? 0:A[x][y-1]);
	DP2[x][y] = min(b1, b2);
	used2[x][y] = MP(x-1, y+1);
}

int main() {
	int T;
	scanf("%d", &T);
	string s;
	for(int cas=0; cas<T ;cas++) {
		scanf("%d %d", &n, &m);
		memset(A, 0, sizeof(A));
		for(int i=0; i<n ;i++) {
			cin >> s;
			for(int j=0; j<m ;j++)
				A[i+1][j+1] = (s[j]-'0');
		}
		DP1[1][1] = DP2[1][1] = A[1][1] + A[1][2] + A[2][1];
		for(int i=2; i<=n ;i++) {
			used1[i][1] = used2[i][1] = MP(i-1, 2);
			DP1[i][1] = DP2[i][1] = DP1[i-1][1] + A[i][2] + A[i+1][1];
		}
		for(int j=2; j<=m ;j++) {
			used1[1][j] = used2[1][j] = MP(2, j-1);
			DP1[1][j] = DP2[1][j] = DP1[1][j-1] + A[2][j] + A[1][j+1];
		}

		for(int i=2; i<=n ;i++) {
			for(int j=2; j<=m ;j++) {
				solve(i, j);
			}
		}
		printf("%dn", min(DP1[n][m], DP2[n][m]) );
	}
}