Only 2 TC are passing in bridges problem

#1

My code

#2

@er.garganant
See this
We are given N pairs of start-point and endpoint in which a bridge can be built from the starting point to the endpoint. Two bridges is said to cut each other iff they share a common point that is not endpoint. Find the maximum number of bridges can be built.

Solution: At first I thought this it is a knapsack problem and tried to solve it as follows: Firstly we need to sort the pairs such that the starting points are in increasing order. Let M(i, x) be the maximum number of bridges that can be built between [i … N] such that the lowest coordinate of endpoint is x. Then M(i,x) = max {M(i+1, x) , 1 + M(i+1, endpoint[i] (if endpoint[i] >= x) )} The complexity of the algorithm is a pseudo polynomial O(N|M|) where N is the number of pairs, and M is the range of endpoints. Unfortunately this does not pass the time limit.

The better approach is to realize that the problem can be modeled as a longest increasing subsequence problem, where for each possible bridge, we check the maximum number of bridges can be built with the current bridge as the last one to be built. My implementation has an O(N2) complexity and it passed the time limit :smiley:

I think you can further optimize this to an O(NlgN) LIS solution, might be worth the try.

#3

Hey,
I tried the O(N^2) approach but 2 TC are still failing.

#4

@er.garganant
Great work
Just do 2 things
pass vec to solve() by reference
And use fast IO

#5

I did the said changes but still the same. 2 TC still not passing.

#6

@er.garganant
One more optimisation
Set a, b and vec as global variables with fixed sized
push_back increases time complexity due to array growing

#7

Still the same 2 TC are failing.

#8

@er.garganant
I can assure you your code is completely perfect and works in exactly 0(n*n)
TLE must be due to some split seconds
So I request you to also see this code https://ide.codingblocks.com/s/212945
You can learn another way to solve the question this way
Happy Coding !!

1 Like
#9

@Aarnav-Jindal-1059677350830863 thanks a lot for helping me out. But why is time complexity such a big issue with these small constraints? Is the time limit less than even 1 sec?

#10

@er.garganant
Even I’m surprised why it isn’t working. I’ve shared this concern with the team as well. Maybe we need to make the time limit a little more to accommodate N^2 approach or there is something in the code which we are not able to figure out.
Till then I request you to move on with other questions and enjoy the course.
Happy Coding !

1 Like
#11

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.