## 11456 - Trainsorting

Moderator: Board moderators

shiplu_1320
New poster
Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka
Contact:

### 11456 - Trainsorting

I am getting WA in this problem since the contest.Help anyone........

Code: Select all

``````Removed After AC
``````
Last edited by shiplu_1320 on Wed Jun 25, 2008 8:49 pm, edited 2 times in total.
A learner......

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

### Re: 11456 - Trainsort

Try this.

Code: Select all

``````1
10
3
8
1
5
10
4
9
2
7
6
``````
Correct output is 5 (10(or 9)-8-5-4-2) but your code outputs 4.
-----
Rio

RC's
Learning poster
Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

### Re: 11456 - Trainsort

By the way, could you share your algorithm here ? Brute force will certainly get Time Limit Exceeded...

wahab
New poster
Posts: 7
Joined: Tue Apr 17, 2007 1:18 am
Location: Egypt
Contact:

### Re: 11456 - Trainsort

RC's wrote:By the way, could you share your algorithm here ? Brute force will certainly get Time Limit Exceeded...
1. Compute LIS and LDS using DP O(n^2)
2. loop and compute max(LIS+LDS-1) for all i

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

### Re: 11456 - Trainsort

wahab wrote: 1. Compute LIS and LDS using DP O(n^2)
Better approach is O(nlogk).
Here k=length of LIS/LDS.

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

### Re: 11456 - Trainsort

Nevermind.

rest
New poster
Posts: 1
Joined: Mon Jun 23, 2008 6:49 pm

### Re: 11456 - Trainsort

wahab wrote:
RC's wrote:By the way, could you share your algorithm here ? Brute force will certainly get Time Limit Exceeded...
1. Compute LIS and LDS using DP O(n^2)
2. loop and compute max(LIS+LDS-1) for all i

plz.. explain what do you mean by LIS or LDS ?

wahab
New poster
Posts: 7
Joined: Tue Apr 17, 2007 1:18 am
Location: Egypt
Contact:

### Re: 11456 - Trainsort

rest wrote:plz.. explain what do you mean by LIS or LDS ?

LIS = Longest_increasing_subsequence starting at location i
LDS = Longest_decreasing_subsequence starting at location i

http://en.wikipedia.org/wiki/Longest_in ... ubsequence

shiplu_1320
New poster
Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka
Contact:

### Re: 11456 - Trainsort

for the input given by rio above,
LIS[0]=4
LDS[0]=5
so LIS[0]+LDS[0]-1= 8
A learner......

wahab
New poster
Posts: 7
Joined: Tue Apr 17, 2007 1:18 am
Location: Egypt
Contact:

### Re: 11456 - Trainsort

shiplu_1320 wrote:for the input given by rio above,
LIS[0]=4
LDS[0]=5
for the input above

LIS ARRAY IS 3 2 3 2 1 2 1 2 1 1
LDS ARRAY IS 2 4 1 3 4 2 3 1 2 1

then the best value is at

LDS[1]+LIS[1] = 4 + 2 -1 = 5

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 11456 - Trainsort

Hi can any one explain this problem........
I can understand this:
LDS[0]=5;LIS[0]=5;
BUT
wahab wrote:
shiplu_1320 wrote:for the input given by rio above,
LIS[0]=4
LDS[0]=5

LIS[0]=4
LDS[0]=5
so LIS[0]+LDS[0]-1= 8
for the input above

LIS ARRAY IS 3 2 3 2 1 2 1 2 1 1
LDS ARRAY IS 2 4 1 3 4 2 3 1 2 1

then the best value is at

LDS[1]+LIS[1] = 4 + 2 -1 = 5
LIS ARRAY [0]=3; && LDS ARRAY[0]=2.how it possible?????
CAN any expain it................

Mukit Chowdhury
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

### Re: 11456 - Trainsort

saiful_sust wrote: LIS ARRAY [0]=3; && LDS ARRAY[0]=2.how it possible?????
CAN any expain it................
Here LIS[1] means how much integers you can take in increasing order taking the value of a[1]
LIS[2] means how much integers you can take in increasing order taking the value of a[2]
.............................................................................................................
LIS[n] means how much integers you can take in increasing order taking the value of a[n]
And...
LDS[1] means how much integers you can take in decreasing order taking the value of a[1]
LDS[2] means how much integers you can take in decreasing order taking the value of a[2]
.............................................................................................................
LDS[n] means how much integers you can take in decreasing order taking the value of a[n]

Then from the value of LIS & LDS you can easily get your desired output...

Ider
New poster
Posts: 1
Joined: Tue Jul 16, 2013 1:18 pm
Contact:

### Re: 11456 - Trainsort

Why do we apply LIS and LDS reversely? Dose question mentioned the cars were pulled from bottom to top?
Wouldn't the order of weights be the order to put cars?

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11456 - Trainsort

When each car arrives, 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.
Check input and AC output for thousands of problems on uDebug!

jddantes
Learning poster
Posts: 73
Joined: Sat Mar 08, 2014 8:55 am

### Re: 11456 - Trainsort

Wouldn't you need to find the LIS and LDS with each car as the starting point?

Something like this (TLE):

Code: Select all

``````#include <vector>
#include <cstdio>
#include <algorithm>

using namespace std;

int main(){

int cases, e;
scanf("%d",&cases);
for(e=0; e<cases; e++){

int n, i;
scanf("%d",&n);

int arr[n];

for(i=0; i<n; i++){
scanf("%d",&arr[i]);
}

int best = 0;
int k;
for(k=0; k<n; k++){
// Get longest decreasing sequence for bot

vector<int> top;
vector<int> bot;

int z;
for(z=k; z<n;z++){
if(z>k){
if(arr[z] < arr[k]){
bot.push_back(arr[z]);
} else {
top.push_back(arr[z]);
}
}
}

// Print stuff
//printf("Starting at %d\n",arr[k]);
int t;
//printf("Dec:\n");
//for(t=0; t<bot.size(); t++)
//    printf("%d ",bot[t]);
// printf("\nInc:\n");
//for(t=0; t<top.size(); t++)
//    printf("%d ",top[t]);
// printf("\n");

int bot_size = bot.size();

int bot_dp[bot_size];

int bot_maxi = 0;
int bot_maxlen = 0;

for(i=k; i<bot_size; i++){
bot_dp[i] = 1;
int j;
for(j=k; j<i; j++){
if(bot[j] > bot[i] && bot_dp[j] + 1 > bot_dp[i]){
bot_dp[i] = bot_dp[j] + 1;
}

if(bot_dp[i] > bot_maxlen){
bot_maxlen = bot_dp[i];
bot_maxi = i;
}
}
}

//printf("Longest for decreasing is %d\n", bot_maxlen);

// Get longest increasing sequence for inc

int top_size = top.size();

int top_dp[top_size];

int top_maxi = 0;
int top_maxlen = 0;

for(i=k; i<top_size; i++){
top_dp[i] = 1;
int j;
for(j=k; j<i; j++){
if(top[i] > top[j] && top_dp[j] + 1 > top_dp[i]){
top_dp[i] = top_dp[j] + 1;
}

if(top_dp[i] > top_maxlen){
top_maxlen = top_dp[i];
top_maxi = i;
}
}
}

//printf("Longest for increasing is %d\n", top_maxlen);

// Remeber to add the starting cart in the sequence

if(1+top_maxlen+bot_maxlen > best){
best = 1+top_maxlen+bot_maxlen;
}
}
printf("%d\n",best);
}

return 0;
}
``````
So it would be O(n * n^2) or O(n * nlogn) depending on which you use for the LIS/LDS.