11456 - Trainsorting

[shiplu_1320]

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

Code: Select all

Removed After AC

Thanx in advance.

[rio]

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]

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

[wahab]

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]

1. Compute LIS and LDS using DP O(n^2)

Better approach is O(nlogk).
Here k=length of LIS/LDS.

[baodog]

Nevermind.

[rest]

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]

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

you can read about them at

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

[shiplu_1320]

could you please explain further.
for the input given by rio above,
LIS[0]=4
LDS[0]=5
so LIS[0]+LDS[0]-1= 8
but answer should be 5.
thanx in advance

[wahab]

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]

Hi can any one explain this problem........
I can understand this:
LDS[0]=5;LIS[0]=5;
BUT

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
but answer should be 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

LIS ARRAY [0]=3; && LDS ARRAY[0]=2.how it possible?????
CAN any expain it................

[Mukit Chowdhury]

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]

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]

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.

[jddantes]

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.