RECNDROT - Editorial

https://www.codechef.com/viewsolution/32367791
can somebody help me with my solution. i have used lower bound and still getting TLE.

You are sorting vector and that is costing time, and you just complicating so much, just one map having all the positions of the number would be sufficient.
You forgot to use fast I/O too that might had also effected it.
You can refer to my code.
https://www.codechef.com/viewsolution/32359615
I just used flag only for the smallest elements index.

Input:
2
8
1 6 2 5 5 4 4 3
6
1 6 2 5 4 3
Output:
4
4

Iā€™m not able to understand the explanation given, can some describe more briefly.

for this array the ans should be 4
7 3 2 1 4 5 8 9 2
LIS will be=12345789
why its correct ans is 3

Can someone tell me the TC for which above solution fails ? Cant find whats wrong with the logic, am getting WA

Iā€™m a bit confuse in this question can you please help me understand it better.
In the given test cases, For the third test case

5
1 3 2 1 2

the answer is 2
And I donā€™t get it.
for me the answer Should be 1. Because if we append it (one more time) or not the length of LIS will remain 2.
Please clear my doubt.
PS: sorry for any grammatical mistakes.

1 Like

where is the editorialistā€™s solution?
oof, my bad author is same .

Can anyone please tell me any test case where my code is wrong, i have tried all the test cases and did in o(n) time, please have a look at my code and tell me where i am wrong
Thanks in advance!
Code link::
https://www.codechef.com/viewsolution/32353135

if m==1 then lis is [1,2]
if m==2 then lis is [1,2,3]

for m=1 you will get lis=[1,2]
for m=2 you will get lis=[1,2,3,4,5]
for m==3 lis=[1,2,3,4,5,7,8,9]
so m=3.

Sorry sir But Iā€™m still confuse!!
How do we get [1,2,3] ?
The given array is [1,3,2,1,2] and if we write it two times m == 2 we get [1,3,2,1,2, 1,3,2,1,2] and I couldnā€™t able to find out [1,2,3] in it. Please help.

Tell me what would be the longest increasing subsequence in [1,3,2,1,2,1,3,2,1,2]?

Read Longest Increasing Sub sequence here

Strictly increasing longest sub sequence would be
[1, 3] because after that weā€™ll get 2 which is less than 2 similarly
[1,2], [1,3], [1,2] all have the length of 2 and if I donā€™t append it than also weā€™ll get LIS of length 2 so I think that 1 would be correct answer. right?

A sub sequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

You can delete the rest except [1 2 3], which are in order in the sequence.

1 Like

Now I get it. Actually I thought it must be continuous because the problem statement says Strictly increasing sub sequence . Thanks for the reference.

strictly increasing just means that duplicates arenā€™t allowed.

1 Like

Strictly is No duplicates.

For the same sequence, if it was mentioned NON STRICT

The LIS could be [1 1 2 3] or [1 1 1 1] and many more.

1 Like

Can you guys help me? My approach is in O(n).
https://www.codechef.com/viewsolution/32378681