11456 - Trainsorting

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11456 - Trainsorting

Post by shiplu_1320 » Sat Jun 21, 2008 9:10 pm

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

Code: Select all

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

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

Re: 11456 - Trainsort

Post by rio » Sat Jun 21, 2008 9:25 pm

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

Post by RC's » Sun Jun 22, 2008 4:03 am

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

Post by wahab » Sun Jun 22, 2008 5:12 am

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

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

Re: 11456 - Trainsort

Post by emotional blind » Sun Jun 22, 2008 6:27 am

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

Post by baodog » Sun Jun 22, 2008 6:46 am

Nevermind.

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

Re: 11456 - Trainsort

Post by rest » Mon Jun 23, 2008 7:01 pm

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

Post by wahab » Mon Jun 23, 2008 7:11 pm

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

you can read about them at

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

Post by shiplu_1320 » Mon Jun 23, 2008 10:03 pm

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 :D
A learner......

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

Re: 11456 - Trainsort

Post by wahab » Mon Jun 23, 2008 10:11 pm

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

Post by saiful_sust » Sun May 24, 2009 8:50 pm

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
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
Learning poster
Posts: 98
Joined: Fri Aug 17, 2012 9:23 pm
Location: Dhaka
Contact:

Re: 11456 - Trainsort

Post by Mukit Chowdhury » Wed Mar 13, 2013 5:23 pm

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

Post by Ider » Tue Jul 16, 2013 1:26 pm

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

Post by brianfry713 » Tue Jul 16, 2013 11:17 pm

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

Post by jddantes » Tue Jun 03, 2014 2:44 am

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.

Post Reply

Return to “Volume 114 (11400-11499)”