11456 - Trainsort

Moderator: Board moderators

11456 - Trainsort

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......
shiplu_1320
New poster

Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka

Re: 11456 - Trainsort

Try this.
Code: Select all
`11038151049276`

Correct output is 5 (10(or 9)-8-5-4-2) but your code outputs 4.
-----
Rio

rio
A great helper

Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Re: 11456 - Trainsort

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

Posts: 65
Joined: Fri Jul 13, 2007 3:17 pm

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[i]+LDS[i]-1) for all i
wahab
New poster

Posts: 7
Joined: Tue Apr 17, 2007 1:18 am
Location: Egypt

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.

emotional blind
A great helper

Posts: 383
Joined: Mon Oct 18, 2004 8:25 am

Re: 11456 - Trainsort

Nevermind.
baodog
Experienced poster

Posts: 197
Joined: Wed Jul 04, 2007 6:53 am

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[i]+LDS[i]-1) for all i

plz.. explain what do you mean by LIS[i] or LDS[i] ?
rest
New poster

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

Re: 11456 - Trainsort

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

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

http://en.wikipedia.org/wiki/Longest_increasing_subsequence
wahab
New poster

Posts: 7
Joined: Tue Apr 17, 2007 1:18 am
Location: Egypt

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......
shiplu_1320
New poster

Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka

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
wahab
New poster

Posts: 7
Joined: Tue Apr 17, 2007 1:18 am
Location: Egypt

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................
saiful_sust
Learning poster

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

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[i] & LDS[i] you can easily get your desired output...
Mukit Chowdhury
Learning poster

Posts: 59
Joined: Fri Aug 17, 2012 9:23 pm
Location: CUET