CodeChef submission 130247 (C++ 4.0.0-8) plaintext list. Status: WA, problem J5, contest NOV09. By abremod (abremod), 2009-11-11 04:04:10.
#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
 
 
class SymmetricString {
 
protected:
  virtual bool lex_less_than(const SymmetricString& rhs) const = 0;
  const int length_;
public:
  SymmetricString(int length) : length_(length) {}
  
  inline int length() const {return length_;}
 
  inline bool shorter_than(const SymmetricString& rhs) const {
    return length_ < rhs.length_;
  }
 
  inline bool operator<(const SymmetricString& rhs) const {
    if (shorter_than(rhs)) return true;
    if (!shorter_than(rhs)) 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) {}
  bool operator<(const SymmetricString& rhs) const { return shorter_than(rhs);}
 
  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_;}
  // guaranteed to be the same subclass
  virtual bool lex_less_than(const SymmetricString& rhs) const {
    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 (*x2 < *x1) return x1;
    return x2;
  }  
 
  const SymmetricString* longest3(const SymmetricString* x1, const SymmetricString* x2, const SymmetricString* x3) {
    return longest(longest(x1, x2), x3);
  }
  
 
  const SymmetricString* longest(const SymmetricString* x1, const SymmetricString* x2, const SymmetricString* x3) {
    if (x1->length() > x2->length()) return longest(x1, x3);
    if (x2->length() > x1->length()) return longest(x2, x3);
    // x1 and x2 have the same length
    if (x3->length() > x1->length()) return x3;
    if (x1->length() > x3->length()) return longest(x1, x2);
 
    // all 3 have the same length (possible optimization here)
    return longest3(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 (calculated_best_left_handed_[i][j]) {
      return calculated_best_left_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_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);
 
    calculated_best_left_handed_[i][j] = longest(best_take_both, best_skip_left, best_skip_right);
    if (calculated_best_left_handed_[i][j] != best_take_both && best_take_both != empty_string_) {
      delete best_take_both;
    }
    return calculated_best_left_handed_[i][j];
  }
 
  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];
  }
};
 
int do_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;
}
 
 
 
 
void test_value(const string& a_string, int expected_value) 
{
  Instance an_instance(a_string);
  const SymmetricString* computed_value = an_instance.longest_left_handed();
  cout << a_string << ' ' << *computed_value << " " << computed_value->length() << " == " << expected_value << '\n';
  
}
 
 
int main() {
  test_value("a", 1);
  test_value("", 0);
  test_value("ab", 2);
  test_value("aa", 1);
  test_value("ba", 1);
  test_value("aba", 2);
  test_value("bab", 2);
  test_value("cba", 1);
  test_value("abc", 3);
 
  test_value("difference", 10);
  test_value("similarq", 6);
  test_value("caaat", 3);
 
  string random_string;
  for (int i = 0; i < 2000; ++i) {
    random_string.push_back('a'+(i %26));
  }
  test_value(random_string, 99);
  return 0;
}