[UVa] 11456 - Trainsorting

Method:
The problem at first glance seems too straightforward but it's not that much. Think a bit about the lines "Erin can add it to the beginning or end of her train, or refuse to add it at all. The resulting train should be as long as possible, but the cars within it must be ordered by weight.". What I understand from these lines is.

1. Erin can choose to start making the train from any point of the arrivals of the cars. So she may have started to make the train from either 1st or n-1st or nth or n/2nd, any point.
2. And from the point in time where she starts this, she checks if the new car is smaller in weight than the last car of her train or higher in weight than the first car or vice versa.
3. So the sorting can start from any point and the optimal choice is at any point.
Ofcourse you have to use LIS, but you also need LDS. Why??

Because suppose she starts from position i. Since she wants to make the train as long as possible so she must make sure the train is optimal from the last till i. Then after i she wants to join the longest possible train using the cars i+1 to n. So, she wants to join the LIS(1 -> i) with LDS(i+1 -> n).

In my solution, I subtracted 1 from LIS(i)+LDS(i) because in both the i car is present. So erased it from 1 of them.

// BISMILLAHIRRAHMANIRRAHIM

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <vector>
#include <list>
#include <iostream>
#include <sstream>
#include <fstream>
#include <algorithm>
#include <queue>
#include <stack>

#define swp(type, a, b) {type x=a; a=b; b=x;}

typedef long long lint;
typedef unsigned long long ulint;

using namespace std;

int seq[10000];
int lis[10000], lds[10000];

int LIS(int n) {
 
 int i, j, mx=0;
 
 
 for (i=n-1 ; i>=0 ; i--) {
  lis[i] = 1;
  for (j=i+1 ; j<n ; j++) {
   if (seq[i]<seq[j]) {
    lis[i] = max(lis[i] , 1+lis[j]);
   }
  }
  mx = max(mx, lis[i]);
 }
 return mx;
}

int LDS(int n) {
 
 int i, j, mx=0;
 
 
 for (i=n-1 ; i>=0 ; i--) {
  lds[i] = 1;
  for (j=i+1 ; j<n ; j++) {
   if (seq[i]>seq[j]) {
    lds[i] = max(lds[i] , 1+lds[j]);
   }
  }
  mx = max(mx, lds[i]);
 }
 return mx;
}



int main ( void ) {
 
 int i, kount, kase, n, x, mx, mnn, mxx, len, res;
 
 
 
 cin >> kase;
 
 while (kase--) {
  cin >> n;
  mx = n;
  
  len = 0;
  kount = 0;
  while (mx--) {
   cin >> x;
   seq[kount++] = x;
  }
  
  LDS(n); LIS(n);
  
  res = 0;
  
  for (i=0 ; i<n ; i++) {
   res = max(res, lis[i]+lds[i]-1);
  }
  
  
  /*cout << "{ debug-start" << endl;
  for (i=0 ; i<n ; i++) {
   cout << seq[i] << " ";
  } cout << endl;
  for (i=0 ; i<n ; i++) {
   cout << lis[i] << " ";
  } cout << endl;
  for (i=0 ; i<n ; i++) {
   cout << lds[i] << " ";
  } cout << endl;
  cout << "end-debug }" << endl;*/
  
  cout << res << endl;
 }
 
 return 0;
}

[UVa] 437 - The Tower of Babylon

Method: LIS (Modified)
You can only see the problem as an LIS Problem but you cannot solve it using LIS principles. All the six sides of the blocks have to be considered. If you test them using the rotational if in the LIS algorithm, they are just testing one or two but all the sides. So you have to make the list with six sides. -Thanks to Rakib (My team mate for contests) for pointing this out :) Code:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>

typedef int lint;

using namespace std;

typedef struct blk {
 int x, y, z; 
} block;


bool comp( block a, block b ) {
 if (a.x != b.x) return (a.x<b.x);
 else if (a.y!=b.y) return (a.y<b.y); 
 else return (a.z<b.z);
}

vector<block> lst;
int lis[1000];

int LIS( int n ) {

 int max_lis(-1), i, j, k;
 
 for (int i=0 ; i<n ; i++) {
  lis[i] = lst[i].z;
  for (int j=0 ; j<i ; j++) {
   if (( (lst[i].x > lst[j].x && lst[i].y > lst[j].y) || (lst[i].x > lst[j].y && lst[i].y > lst[j].x) ) ) {
    lis[i] = max ( lis[i] , lis[j]+lst[i].z );
   }
  }
  max_lis = max ( lis[i] , max_lis );
 }
 return max_lis;
}

int main( void ) {

 int n, i, x, y, z, kase=1;

 while ( scanf("%d",&n) && n ) {
 
  lst.clear();
 
  for (i=0 ; i<n ; i++) {
   scanf("%d %d %d",&x,&y,&z);
   
   lst.push_back( (block) {x,y,z} );
   lst.push_back( (block) {x,z,y} );
   lst.push_back( (block) {y,x,z} );
   lst.push_back( (block) {y,z,x} );
   lst.push_back( (block) {z,x,y} );
   lst.push_back( (block) {z,y,x} );
  }
  
  sort(lst.begin(), lst.end(), comp);
  
  int res = LIS( lst.size() );
  
  printf("Case %d: maximum height = %d\n",kase++,res);
 } 
 return 0;
}