11456 - Trainsort

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

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

[wahab]

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

you can read about them at

http://en.wikipedia.org/wiki/Longest_increasing_subsequence

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