MERGEDLIS - Editorial

I did exactly what the editorial says. But I am getting WA. Can anyone please tell me why I am getting WA? Thanks in advance!
https://www.codechef.com/viewsolution/56935766

No , its not because of repeated numbers .
See this, it might help :slight_smile:

Try to use inbuilt functions such as lower_bound() and upper_bound() instead of writing the entire binary search algorithm , which is much prone to errors and also may result in infinite loops if you are not careful.

I tried that also but still got WA. please check this out
https://www.codechef.com/viewsolution/56942785

Use upper_bound() instead of lower_bound().
Here its asking for LNDS length and not LIS . If two elements are equal , then it will add to our current existing length .
For example LNDS for [1,2,2,3] is 4 and NOT 3
If you use lower_bound() when i=2 (0 based indexing) , your x in line 72 will return 2 , hence overwriting the existing “2” that is already present.
Also in line 62, initializing a vector like that will make it 0 based indexing, hence x would not be the LNDS length . Use x+1 instead

1 Like

Thanks! It got accepted. Thank you so much @bugbuster404

You are using INF as 1e9 . But the array elements itself go upto 1e9 . Take something bigger than that , like 1e9+1 or INT_MAX :slight_smile:
Like this (Just changed INF to 1e9+1):-
https://www.codechef.com/viewsolution/57008207

Why my approach is giving TLE

TLE: CodeChef: Practical coding for everyone
O((N+M)*(Log(N+M))

Is my approach wrong?

Yes

Thanks

I found, it will fail for

A=> 8 4 5 7
B=> 6 9 10
my C=> 8 4 5 7 9 10 (ans=5)
but actual C=> 8 4 5 6 7 9 10 (ans=6)

Thanks, I haven’t read Constraints Carefully, I thought it to be 1e5.

hii
can anyone tell me why my code is not working?
it is able to pass sample cases but fails for test cases.

for _ in range(int(input())):
    n1,n2=map(int,input().split())
    a1=list(map(int,input().split()))
    a2=list(map(int,input().split()))
    c1=c2=1
    c=1
    for i in range(1,n1):
        if a1[i]>=a1[i-1]:
            c+=1
        else:
            if c>c1:
                c1=c
            c=1
    if c>c1:
        c1=c
    c=1
    for i in range(1,n2):
        if a2[i]>=a2[i-1]:
            c+=1
        else:
            if c>c2:
                c2=c
            c=1
    if c>c2:
        c2=c
    print(c1+c2)

can anyone share test cases where it fails?
thanks in advance.

Tell me what you have done briefly . I don’t know python

initialized a variable c1 with value 1. and another variable c with 1 again. traversed through the array from 1 index and compared it with its previous element,if a[i]>=a[i-1]. increased c value +1 and if its false, compared c value with c1, if c>c1,c1=c and then reset c value to 1. indirectly I am trying to get the longest non decreasing substring length from both the array and adding them.

Approach is correct . Might be some implementation fault
Try using
A = [4,2,3]
B = [3]
and see whether you are getting 3 or not.

m getting 3

You method of calculating LNDS length is not correct. You are simply checking only the previous element , i.e if a1[i]>=a1[i-1] you are incrementing c else setting c=1.
Basically you are calculating longest non-decreasing subarray and not subsequence. Both are different

ohh ,i got it now,thank you so much

Why do you reverse the list there is no need of reversing the list. You discard the condition that order can’t we changed

thanks man