CodeChef submission 130863 (C++ 4.0.0-8) plaintext list. Status: TLE, problem J5, contest NOV09. By yashwa7 (Yashwant Vijayakumar), 2009-11-11 13:22:34.
#include<cstdio>
#include<string>
#include<iostream>
#include<map>
#include<cstdlib>
 
using namespace std;
 
#define MANY_TESTCASES
 
map<string, string> magicStringMap;
 
string computeMagicString(string input, bool oddLesser);
string chooseBest(string &first, string &second, string &third);
string chooseBest(string &first, string &second);
 
int main() {
	#ifndef ONLINE_JUDGE
	freopen("input.txt","r",stdin);
	#endif
	int i = 0;
	int noOfTestCases;
	
	#ifdef MANY_TESTCASES
	scanf("%d", &noOfTestCases);
	#else
	noOfTestCases = 1;
	#endif
	
	while(i < noOfTestCases) {
		char inputString[2000];
		scanf("%s", inputString);
		string input(inputString);
		string output = computeMagicString(input, true);
		printf("%s\n", output.data());
		magicStringMap.clear();
		i++;
	}
	
	return 0;
}
 
string computeMagicString(string input, bool oddLesser) {
	int length = input.length();
	char oddLesserChar = (oddLesser == true) ? '1' : '0';
	
	//cout<<input<<endl;
	
	if(length == 1)
		return input;
	
	if(length == 2) {
		if(oddLesser) {
			if(input[0] < input[1])
				return input;
			else
				return string(1, input[1]);
		}
		else {
			if(input[0] > input[1])
				return input;
			else
				return string(1, input[0]);
		}
	}
 
	map<string, string> :: iterator iter = magicStringMap.begin();
	iter = magicStringMap.find(input + oddLesserChar);
	if(iter != magicStringMap.end())
		return magicStringMap[input + oddLesserChar];
	
	string magicString;
	
	if(oddLesser && (input[0] < input[length - 1]) || !oddLesser && (input[0] > input[length - 1])) {
		string return0 = computeMagicString(input.substr(1, length - 2), !oddLesser);
		string temp = input[0] + return0 + input[length - 1];
		if(temp != input) {
			string return1 = computeMagicString(input.substr(0, length - 1), oddLesser);
			string return2 = computeMagicString(input.substr(1, length - 1), oddLesser);
			magicString = chooseBest(temp, return1, return2);
		}
		else 
			magicString = input;
	}
	
	else {
		string return1 = computeMagicString(input.substr(0, length - 1), oddLesser);
		string return2 = computeMagicString(input.substr(1, length - 1), oddLesser);
 
		magicString = chooseBest(return1, return2);
	}
	
	magicStringMap[input + oddLesserChar] = magicString;
	
	return magicString;
		
}
 
string chooseBest(string &first, string &second, string &third) {
	string one = chooseBest(first, second);
	return chooseBest(one, third);
}
 
string chooseBest(string &first, string &second) {
	if(first.length() > second.length())
		return first;
	else if(first.length() < second.length())
		return second;
	
	return first < second? first : second;
}