[Bridges] - Please explain the test Case

#1

for input

4

2 5 8 10

6 4 1 2

why valid inputs are (8,1) and (10,2)
but here 2,6 ; 5,4 ; 8,1 and 10,2 all endpoints are instersecting.

Please, explain these input test case as well

1 2 3 4 5 6

3 4 5 6 1 2

#2

hey Vikash!
see these statements

  1. bridge starting from the ith end point on one side can only end on the ith end point on the other side
    2.The tribe just wants to make as many non-cutting bridges as possible, with the constraint in mind.
    for 1st test:
    4
    2 5 8 10
    6 4 1 2
    ans is 2 because of (1,8) and (2,10)
    for explanation refer this image
    bridge
    hence the problem boils down to LIS or LDS(longest decreasing subsequence)
    considering both arrays simultaneously!
#3

Test cases are failing could you please suggest what test cases are not covered by my code . https://ide.codingblocks.com/s/251591

#4
#5

actually we have to sort it (as we might miss some even taking both LIS and LDS) but sorting should be pairwise(so that relative order is not destroyed, may this was what you said earlier!)!
then just find LIS!

#6

I have updated the code and when and even after shuffling the given inputs i am getting correct output. But while submission its failing. I have updated my code in IDE.

#7

your bridges can intersect at endpoints!
so dp condition should be >=, also don’t use map as it omits duplicate endpoints

#8

I have modified the code as you have suggested but still two of the test cases are failing. Could you please suggest what i am missing…

#9


You may refer to my code(implemented same logic!)

#10

What is different in my code . In the given code you are taking LDS and its working. I am getting what is different in my code. Even i tried executing the code after removing the LDS still same two test cases were failing

#11
  • you are not taking LDS …
#12

i have updated code in in the given coding block ide as well. Not getting what i am missing. Could you please provide me some test cases for which my code is not proper.

#13

I have sorted the array pairwise, so LDS is not required.

#14

You may download the test cases from editorial/solution section and see where your code fails.

#15

I have also sorted array pairwise . Could you please suggest what i am missing ?

#16

your sorting is bit incorrect,
first give priority to smaller array[i].first, if in case when array[i].first==array[j].first, give priority to smaller array[].second, means that element with smaller second element should come first.

#17

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.