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
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
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
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