CodeChef submission 130259 (C++ 4.0.0-8) plaintext list. Status: TLE, problem J5, contest NOV09. By anshulgoel (Anshul Goel), 2009-11-11 04:18:02.
#include<iostream>
#include<cstring>
#include<vector>
 
using namespace std;
 
bool chkS(string k,int *a=NULL )
{
 int l=k.length();
 int z=0;
 for(int i=0;i<l;i++)
 z+=a[i];
 
 char s[l-z];
 int c=0;
 for(int i=0;i<l;i++)
 if(a[i]==0)s[c++]=k[i];
 
 
 
 for(int i=0;i<l-z;i++)
  if(s[i]<'a'||s[i]>'z')return false;
 
 
 for(int i=1;i<=(l-z)/2;i++)
 {
     if(i%2==1){if(s[i-1]>s[l-i])return false;}
     if(i%2==0){if(s[i-1]<s[l-i])return false;}
 }
 return true;
}
 
string mini="";
 
int length(string k,int* a)
{
    int l=k.length();
 int z=0;
 for(int i=0;i<l;i++)
 z+=a[i];
 return l-z;
}
 
string conv(string k,int *a)
{
    int l=k.length();
 int z=0;
 for(int i=0;i<l;i++)
 z+=a[i];
 
 string s="";
 int c=0;
 for(int i=0;i<l;i++)
 if(a[i]==0)s[c++]+=k[i];
 
 
 return s;
 
}
 
string subS(string s,int i,int j)//i to j
{
 string tmp=new char[j-i+1];
 for(int k=i;k<=j;k++)
   tmp[k]=s[k];
 
   return tmp;
}
 
string SminC(string s,int i)//leave index i
{
 string tmp=new char[s.length()-1];
 int c=0;
 for(int k=0;k<s.length();k++)
  if(k!=i) tmp[c++]=s[k];
 
   return tmp;
}
 
 
 
 
int find(string s,int p,int q,bool odd)//find poss cand at the end
{
 if(p>q)return -1;
 
    int l=q-p+1;
  for(int i=q;i>=p;i--)
  {
   if(s[p-1]==s[i])continue;
   if((s[p-1]<s[i])==odd)return i;
  }
return -1;
}
 
char s[2001];
bool maximum[2001];
bool a[2001];
int C=0,d=0,N;
 
void disp()
{
  for(int i=0;i<N;i++)
  if(maximum[i])cout<<s[i];
}
 
void copy()
{
    C=d;
 for(int i=0;i<N;i++)
    maximum[i]=a[i];
   // disp();
}
 
int size()
{
    int sum=0;
    for(int i=0;i<N;i++)
    if(a[i])sum++;
 
    return sum;
}
 
 
 
 
void disp(bool arr[])
{
  for(int i=0;i<N;i++)
  if(arr[i])cout<<s[i];
}
 
bool lexless()
{
 int p=0,q=0;
 
 while(p<N&&q<N)
 {
   while(a[p]==0){p++;if(p==N)return true;}
   while(maximum[q]==0){q++;if(q==N)return true;}
 
//   cout<<p<<q<<s[p]<<s[q]<<(a[p]<maximum[q]);
 
   if(s[p]<s[q]){return true;}
   if(s[p]>s[q]){return false;}
   p++;q++;
 }
 //cout<<"prob \n";disp(a);disp();cout<<endl;
 return true;
}
 
void add(int x)
{
 d+=x;
 if(d==C){//cout<<"d==C";disp(a);disp();cout<<lexless();}
        }
 if(d>C||(d==C&&lexless())){copy();}
}
 
int mmgc(string sfaaltu,int l,int r,bool odd=true)//max with first letter start
{
    //cout<<" Call : "<<l<<" "<<s[l]<<","<<r<<" "<<s[r]<<endl;
    //int d=size();
    if(l>r){
        //cout<<"\nl>r : "<<C<<endl;
        return 0;}
 if(l==r){
 
    // cout<<" l==r : "<<l<<" "<<s[l]<<endl;
     a[l]=true;add(1);
     a[l]=false;d--;
     return 1;
     }
 
 if(d+r-l+1<C){//cout<<"\nNo use"<<l<<","<<r<<d<<C<<endl;
     return 0;}
int z,q,qmax=0;
 
 int pos,tmp=-1;
 
 do{
 if(tmp==-1) pos=find(s,l+1,r,odd);
 else pos=find(s,l+1,tmp-1,odd);
 
 
 //cout<<"\nPos for "<<s[l]<<"\t"<<pos<<endl;
 
 if(pos==-1)break;
 if(tmp!=-1){//cout<<"\n LOOP : "<<s[pos]<<s[tmp]<<endl;
 if(s[pos]>=s[tmp])break;}
 
  tmp=pos;
 // cin.get();
 //cout<<"\nSelecting "<<s[l]<<l<<s[pos]<<pos<<endl;
a[l]=true;
 a[pos]=true;add(2);
 
  q=mmgc(s,l+1,pos-1,!odd)+1;// select s[l]
  //if(q>C){C=q;copy();}
  qmax=qmax>q?qmax:q;
 a[l]=false;
 a[pos]=false;d-=2;
 
 }while(pos!=-1);
//cout<<"\nLeaving "<<s[l]<<l<<endl;
 int p=0;
 if(qmax<r-l+1)p=mmgc(s,l+1,r,odd);//dont select s[l]
 //if(p>C){C=p;copy();}//copy to max
 
 z=p>q?p:q;
 
 return z;
 
 
  //if(p.size()==q.size()){}  else
 
// max=max.size()>z.size()?:q;
 
}
 
 
int main()
{
   /* string T;
    cin>>T;
    s=new char[T.length()];
    for(int i=0;i<T.length();i++)
    s[i]=T[i];
 
    maximum=new char[T.length()];
*/
 
 
 
int T;
cin>>T;
while(T--)
{
cin>>s;
N=strlen(s);
for(int i=0;i<N;i++)
a[i]=false;
 
    //vector<char> res=mmgc(s,0,s.length());
 
    //for(int i=0;i<res.size();i++)
   // cout<<res[i];
  //cout<<
  mmgc(s,0,strlen(s)-1);
 
 disp();
 
}
//cin.get();
//cin.ignore();
}