1
Your rating: None Average: 1 (1 vote)

CodeChef submission 130622 (C++ 4.0.0-8)

CodeChef submission 130622 (C++ 4.0.0-8) plaintext list. Status: AC, problem J5, contest NOV09. By askvij (Ashok Vijay), 2009-11-11 10:43:51.
  1. #include <vector>
  2. #include <map>
  3. #include <algorithm>
  4. #include <iostream>
  5. #include <cstdio>
  6. #include <ctime>
  7. #include <cstring>
  8.  
  9. using namespace std;
  10. #define SZ 2002
  11. string A = "abcdefghijklmnopqrstuvwxyz" ;
  12. bool found [ 27 ];
  13. char in [ SZ ];
  14. int odd ( int , int );
  15. int even ( int , int );
  16. int memo_odd [ SZ ][ SZ] ,memo_even [SZ][SZ], POS [ SZ ] [27], POS1 [SZ][27],cnt;
  17. int memo_odd1 [SZ][SZ] ,memo_even1 [SZ][SZ];
  18. typedef pair < bool , int > PBI;
  19. typedef pair < PBI ,int > PBII;
  20. map < PBII ,string > MEMO;
  21. int even ( int idx1 , int idx2 )
  22. {
  23.     if ( idx1 > idx2 ) return 0;
  24.     if ( memo_even[idx1][idx2] != -1 ) return memo_even [idx1][idx2];
  25.     int ret = 0, tmp = 0,i ,j,k;
  26.     if ( in [ idx1 ] > in [idx2 ] ) 
  27.          tmp = odd( idx1 + 1, idx2 -1 ) + 2 ;
  28.     if ( tmp > ret ) ret = tmp;
  29.     tmp = even ( idx1+ 1, idx2 );
  30.     if ( tmp > ret ) ret = tmp;
  31.     tmp = even ( idx1 , idx2-1 ) ;
  32.     if ( tmp > ret ) ret = tmp;
  33.     if ( ret == 0 && idx2 - idx1 >= 0 ) ret = 1;
  34.     return memo_even [idx1][idx2] = ret;
  35. }
  36. int odd ( int idx1 ,int idx2 )
  37. {
  38.     if ( idx1 > idx2 ) return 0;
  39.     if ( memo_odd[idx1][idx2] != -1 ) return memo_odd [idx1][idx2];
  40.     int ret = 0, tmp = 0,i ,j,k;
  41.     if ( in [ idx1 ] < in [idx2 ] ) 
  42.          tmp = even( idx1 + 1, idx2 -1 ) + 2 ;
  43.     if ( tmp > ret ) ret = tmp;
  44.     tmp = odd ( idx1+ 1, idx2 );
  45.     if ( tmp > ret ) ret = tmp;
  46.     tmp = odd ( idx1 , idx2-1 ) ;
  47.     if ( tmp > ret ) ret = tmp;
  48.     if ( ret == 0 && idx2 - idx1 >= 0 ) ret = 1;
  49.     return memo_odd [idx1][idx2] = ret;
  50. }
  51. /*void print_ans ( int n )
  52. {
  53.      int i ,j, k ,idx1 = 0 , idx2 = n-1;
  54.      for ( i = 0 ; i < n ;i++ ,cout <<"\n" ) for ( j = 0 ; j < n ;j++ ) cout << memo_odd [i][j] << " ";cout<<"\n\n";
  55.      for ( i = 0 ; i < n ;i++ ,cout <<"\n" ) for ( j = 0 ; j < n ;j++ ) cout << memo_even [i][j] << " ";cout<<"\n\n";
  56.      
  57. }*/
  58. string recurse ( bool isodd , int idx1 , int idx2 )
  59. {
  60.        int i ,j,k;
  61.        if ( idx1 > idx2 ) return "";
  62.        string ret  = "" ,tmp ;
  63.        PBII a = make_pair ( make_pair ( isodd ,idx1 ) ,idx2 );
  64.        if ( MEMO[a].size() ) return MEMO [a];
  65.        int n,m;
  66.        if ( isodd ) n = memo_even1 [idx1][idx2];
  67.        else n = memo_odd1 [idx1][idx2];
  68.        if ( n == 1 ) 
  69.        {
  70.             for ( i = 0 ; i < cnt; i++ ) if ( POS [idx2][i] > idx1 ) 
  71.             {
  72.                 return MEMO [a] = A[i];
  73.             }
  74.        }
  75.        for ( i = 0 ; i < cnt ;i++ ) if ( POS1[idx1][i] != -1)
  76.        {
  77.            int b = POS1 [idx1][i];
  78.            if ( isodd ) 
  79.            {
  80. 		   	  	int last = -1;
  81.                 for ( j = i+1  ; j < cnt ; j++ ) if ( POS [idx2][j] != -1 )
  82.                 {
  83.                     k = POS [idx2][j];
  84.                     if ( k <= b || last > k ) continue;
  85.                     last = max ( last ,k );
  86.                     if ( memo_odd1 [b][k]+2 == memo_even1[idx1][idx2] ) 
  87.                     {
  88.                          tmp = A [i] + recurse ( !isodd , b ,k)  +A [j];
  89.                          if ( ret.size() == 0 ) ret = tmp ; else ret = min ( ret ,tmp );
  90.                     }
  91.                 }
  92.            }
  93.            else 
  94.            {
  95. 		   		int last = -1;
  96.                 for ( j = 0 ; j < i  ;j++ ) if ( POS [idx2][j] != -1 )
  97.                 {
  98.                     k = POS [idx2][j];
  99.                     if ( k <= b || last > k ) continue; 
  100.                     last = max ( last ,k );
  101.                     if (memo_even1 [b][k]+2 == memo_odd1[idx1][idx2]  ) 
  102.                     {
  103.                          tmp =  A [i] + recurse (!isodd,b,k ) + A [j] ;
  104.                          if ( ret.size() == 0 ) ret = tmp ; else ret = min ( ret ,tmp );
  105.                     }
  106.                 }
  107.            }
  108.            if ( ret.size()  ) return MEMO [a] = ret;
  109.        }
  110.        for ( i = 0 ; i < cnt; i++ ) if ( POS [idx2][i] > idx1 ) 
  111.        {
  112.                 return MEMO [a] = A[i];
  113.        }
  114.        return MEMO[a] = ret;
  115. }
  116. int main ()
  117. {
  118.    // double start = clock();
  119.     int t;
  120.    // freopen ( "J5_1.in", "r",stdin );
  121.     //freopen ( "J5_14.out", "w",stdout );
  122.     for ( scanf("%d",&t ) ; t ;t-- )
  123.     {
  124.         int i ,j,k;
  125.         scanf("%s",in );
  126.         int n = strlen ( in );
  127.         memset ( found , false ,sizeof ( found ) );
  128.         memset ( POS , -1 ,sizeof ( POS ) );
  129.         memset ( POS1 , -1 ,sizeof ( POS1 ) );
  130.         for ( i = 0 ; i < n ;i++ ) found [ in [i] - 'a' ] = true;
  131.         j = 0;
  132.         for ( i = 0 ; i < 26 ;i++ ) if ( found [i] )
  133.         {
  134.             A [j] = 'a' + i;
  135.             j++;
  136.         }
  137.         memset ( found ,false ,sizeof ( found ) );
  138.         for ( i = 0 ; i < j ;i++ ) found [i] = true;
  139.        // cout << A <<" "<<j<<"\n";
  140.         cnt = j;
  141.         for ( i = 1 ; i < n ;i++  )
  142.         {
  143.             for ( j = 0 ; j < cnt ;j++ ) if ( in [i-1]  == A[j] ) POS [i][j] = i-1 ; else POS [i][j] = POS [i-1][j];
  144.         }
  145.         for ( i = n - 2 ; i >= 0 ;i-- )  
  146.         {
  147.             for ( j = 0 ; j < cnt ;j++ ) if ( in [i+1]  == A[j] ) POS1 [i][j] = i+1 ; else POS1 [i][j] = POS1 [i+1][j];
  148.         }
  149.         //memset ( memo_even,-1 ,sizeof (memo_even ) );
  150.         //memset ( memo_odd,-1 ,sizeof (memo_odd ) );
  151.         memset ( memo_even1,0 ,sizeof (memo_even1 ) );
  152.         memset ( memo_odd1,0 ,sizeof (memo_odd1 ) );
  153.         //int ans = odd ( 0,n-1);
  154.         for( i = 0 ; i < n ;i++ ) memo_odd1 [i][i] = memo_even1 [i][i] = 1;
  155.         for ( i = n - 1; i >= 0 ;i-- ) 
  156.         {
  157. 		 	for ( j = i + 1 ;j < n ;j++ )
  158. 		 	{
  159. 			 	memo_odd1 [i][j] = max ( memo_odd1 [i+1][j] ,memo_odd1[i][j-1] );
  160. 			 	memo_even1 [i][j] = max ( memo_even1 [i+1][j] ,memo_even1[i][j-1] );
  161. 			 	if ( in [i] > in [j] ) memo_even1 [i][j] = max ( memo_even1 [i][j] , memo_odd1 [i+1][j-1]+2 );
  162. 			 	if ( in [i] < in [j] ) memo_odd1 [i][j] = max ( memo_odd1 [i][j] , memo_even1 [i+1][j-1]+2 );
  163. 		   }
  164. 	   }
  165. 	   int ans = memo_odd1 [0][n-1];
  166. 	   //cout << ans << "\n";
  167. 	  /* for ( i = 0; i < n ;i++ ,cout <<"\n") for ( j = 0 ; j < n ;j++ ) cout << memo_odd [i][j] << " "; cout <<"\n";
  168. 	   for ( i = 0; i < n ;i++ ,cout <<"\n") for ( j = 0 ; j < n ;j++ ) cout << memo_odd1 [i][j] << " "; cout <<"\n";
  169. 	   cout << in << "\n";
  170. 	   for ( i = 0; i < n ;i++ ,cout <<"\n") for ( j = 0 ; j < n ;j++ ) cout << memo_even [i][j] << " "; cout <<"\n";
  171. 	   for ( i = 0; i < n ;i++ ,cout <<"\n") for ( j = 0 ; j < n ;j++ ) cout << memo_even1 [i][j] << " "; cout <<"\n";*/
  172.        MEMO.clear();
  173.         if ( ans  == 1 ) 
  174.         {
  175.              string ret = "z";
  176.              for ( i = 0 ; i < n ;i++ ) ret [0] = min ( ret [0] , in [i] ) ;
  177.              cout << ret <<"\n";
  178.              continue;
  179.         }
  180.         if ( ans == 2 ) 
  181.         {
  182.              bool flag = false;
  183.              j = k = 0;
  184.              for ( i = 0 ; i < cnt ;i++ ) if ( A [i] == in [0] ) j = i ; else if ( A [i ]== in [n-1] ) k = i;
  185.              POS1[0][j] = 0; POS [n-1][k] = n-1;
  186.              for ( i = 0 ; i < cnt && !flag;i++ ) if ( found [i] ) for ( j = i + 1 ; j < cnt && !flag;j++ ) if ( found [j] && POS[n-1][j] > POS1 [0][i]) 
  187.              {
  188.                  cout << A[i]<<A[j]<<"\n";
  189.                  flag = true;
  190.              }
  191.              continue;
  192.         }
  193.         string tmp ,ANS = "" ;
  194.         bool flag = false;
  195.         for ( i = 0 ; i < cnt && !flag;i++ ) if ( found [i] ) 
  196.             for ( j = i + 1 ;  j < cnt ;j++ ) if ( found [j] )
  197.             {
  198.                 int a = POS1[0][i] , b = POS[n-1] [j];
  199.                 if ( in [0]  == A[i] ) a = 0;
  200.                 if ( in [ n-1]  == A[j] ) b = n-1;
  201.                 if (   memo_even1 [ a+1 ] [ b-1 ] + 2 == ans  )
  202.                 {
  203.                      tmp= A[i] + recurse ( false ,a , b ) + A[j];
  204.                      if ( ANS.size() < tmp.size() ) ANS = tmp;
  205.                      else if ( ANS.size() == tmp.size() ) ANS = min ( ANS , tmp );
  206.                      flag = true;
  207.                 }
  208.             }
  209.         cout << ANS << "\n";
  210.         //printf("%s\n",ANS.c_str() );
  211.     }
  212.     //double stop = clock();
  213. //	cout << (stop - start )/CLOCKS_PER_SEC << "\n";
  214.     return 0;
  215. }
  216.

Comments