CodeChef submission 130602 (C++ 4.0.0-8) plaintext list. Status: TLE, problem J5, contest NOV09. By abremod (abremod), 2009-11-11 10:05:15.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
 
 
class SymmetricString {
 
protected:
 
  const int length_;
public:
  virtual bool lex_less_than(const SymmetricString* rhs) const = 0;
  SymmetricString(int length) : length_(length) {}
  
  inline int length() const {return length_;}
 
  inline bool longer_than(const SymmetricString& rhs) const {
    return length_ > rhs.length_;
  }
 
  inline bool operator<(const SymmetricString& rhs) const {
    if (longer_than(rhs)) return true;
    if (rhs.longer_than(*this)) return false;
    return lex_less_than(&rhs);
  }
 
  virtual void print(ostream& os) const=0;
  friend ostream& operator<<(ostream& os, const SymmetricString& rhs);
};
 
 
ostream& operator<<(ostream& os, const SymmetricString& rhs) {
  rhs.print(os);
  return os;
}
 
 
class EmptyString : public SymmetricString {
public:
  EmptyString() : SymmetricString(0) {}
 
  void print (ostream& os) const {}
 
  // guaranteed to be the same subclass
  virtual bool lex_less_than(const SymmetricString* rhs) const {
    return false;
  }
 
};
 
class SingleChar : public SymmetricString {
  const char x_;
  
public:
  SingleChar(char x) : SymmetricString(1), x_(x) {}
 
  void print(ostream& os) const {
    os << x_;
  }
 
 
  // guaranteed to be the same subclass
  virtual bool lex_less_than(const SymmetricString* rhs) const {
    return x_ < static_cast<const SingleChar *>(rhs)->x_;
  }
};
 
 
class FullSymmetricString : public SymmetricString {
  const char first_;
  const SymmetricString* middle_;
  const char last_;
public:
  FullSymmetricString(char first, const SymmetricString* middle, char last) : 
    SymmetricString(middle->length() + 2), first_(first), middle_(middle), last_(last)
  {}
 
  void print(ostream& os) const {
    os << first_;
    os << *middle_;
    os << last_;
  };
 
  virtual int length() const {return length_;}
 
  char first() const {return first_;}
  char last() const {return last_;}
 
  // guaranteed to be the same subclass
  virtual bool lex_less_than(const SymmetricString* rhs) const {
    if (this == rhs) return false;
    const FullSymmetricString* casted_rhs=static_cast<const FullSymmetricString*>(rhs);
    if (first_ < casted_rhs->first_) return true;
    if (first_ > casted_rhs->first_) return false;
    //    if (*(this->middle_)  < *(casted_rhs->middle_)) return true;
    //    if ( *(casted_rhs->middle_) < *(this->middle_)) return false;
    return last_ < casted_rhs->last_;
  }
};
 
 
class Instance 
{
  string full_sequence_;
  EmptyString* empty_string_;
  //  typedef enum {unknown = 0, take_both, take_left,  take_right} optimal_decision;
  vector<vector<const SymmetricString*> > calculated_best_left_handed_; // always > 0 if computed
  vector<vector<const SymmetricString*> > calculated_best_right_handed_;
 
  int max(int x1, int x2, int x3) {
    if (x1 > x2 && x2 >= x3) return x1;
    if (x1 > x3 && x3 >= x2) return x1;
    if (x2 > x3) return x2;
    return x3;
  }
 
 
  const SymmetricString* longest(const SymmetricString* x1, const SymmetricString* x2) {
    if (*x1 < *x2) return x1;
    return x2;
  }  
 
 
  const SymmetricString* lex_least(const SymmetricString* x1, const SymmetricString* x2) {
    if (x1->lex_less_than(x2)) return x1;
    return x2;
  }
 
  const SymmetricString* lex_least(const SymmetricString* x1, const SymmetricString* x2, const SymmetricString* x3) {
    if (x1->lex_less_than(x2)) return lex_least(x1, x3);
    if (x2->lex_less_than(x1)) return lex_least(x2, x3);
    if (x1->lex_less_than(x3)) return x1;
    return x3;
  }
  
 
  const SymmetricString* longest(const SymmetricString* x1, const SymmetricString* x2, const SymmetricString* x3) {
    if (x1->longer_than(*x2)) return longest(x1, x3);
    if (x2->longer_than(*x1)) return longest(x2, x3);
    // x1 and x2 have the same length
    if (x1->longer_than(*x3)) return x1;
    if (x3->longer_than(*x1)) return x3;
    return lex_least(x1, x2, x3);
  }
 
 
public:
  
  Instance(const string& a_string) : full_sequence_(a_string), 
				     empty_string_(new EmptyString()),
				     calculated_best_left_handed_(a_string.length()),
				     calculated_best_right_handed_(a_string.length()) {
    for (unsigned i = 0; i != a_string.length(); ++i) {
      calculated_best_left_handed_[i].resize(a_string.length());
      calculated_best_right_handed_[i].resize(a_string.length());
      calculated_best_left_handed_[i][i] =  new SingleChar(full_sequence_[i]);
      calculated_best_right_handed_[i][i] =  new SingleChar(full_sequence_[i]);
    }
  }
 
 
  const SymmetricString* longest_left_handed()  {
    return longest_left_handed(0, full_sequence_.length()-1);
  }
 
 
  const SymmetricString* longest_left_handed(int i, int j)  {
 
    if (i > j) return empty_string_;
    if (const SymmetricString* result = calculated_best_left_handed_[i][j]) {
      return result;
    }
    
    const SymmetricString* best_take_both = empty_string_;
    if (full_sequence_[i] < full_sequence_[j]) {
      best_take_both = new FullSymmetricString(full_sequence_[i], longest_right_handed(i+1, j-1), full_sequence_[j]);
    }
    const SymmetricString* best_skip_left = longest_left_handed(i+1, j);
    const SymmetricString* best_skip_right = longest_left_handed(i, j-1);
 
    const SymmetricString* result = longest(best_take_both, best_skip_left, best_skip_right);
 
 
    if (result != best_take_both && best_take_both != empty_string_) {
      delete best_take_both;
    }
    calculated_best_left_handed_[i][j] = result;
    return result;
  }
 
  const SymmetricString* longest_right_handed(int i, int j)  {
    if (i > j) return empty_string_;
 
    if (calculated_best_right_handed_[i][j]) {
      return calculated_best_right_handed_[i][j];
    }
    
    const SymmetricString* best_take_both = empty_string_;
    if (full_sequence_[i] > full_sequence_[j]) {
      best_take_both = new FullSymmetricString(full_sequence_[i], longest_left_handed(i + 1, j - 1), full_sequence_[j]);
    }
    const SymmetricString* best_skip_left = longest_right_handed(i+1, j);
    const SymmetricString* best_skip_right = longest_right_handed(i, j - 1);
    calculated_best_right_handed_[i][j] = longest(best_take_both, best_skip_left, best_skip_right);
    if (calculated_best_right_handed_[i][j] != best_take_both && best_take_both != empty_string_) {
      delete best_take_both;
    }
    return calculated_best_right_handed_[i][j];
  }
};
 
//#include "test_magic.cpp"
 
#if 1
int main() {
  int n_cases;
  string test_value;
  cin >> n_cases;
  for (int i = 0; i < n_cases; ++i) {
    cin >> test_value;
    Instance instance(test_value);
    cout << *(instance.longest_left_handed()) << '\n';
    
  }
  return 0;
}
 
#endif