Given a list of coordinates x1, x2, ..... xn, and each of coordinates has a value time t1, t2, ... tn. U can start at anywhere in the ox axis, u have to find the smallest time to reach all the points x1, x2... xn, and u also have to reach every points in the time of that point, meaning that assume at time t u reach xk point, so t<=tk. Output the smallest time or "No solution".
please help me this problem xD P/s: link this problem :D Your text to link here...
The idea is as follows. Let's enumerate all treasures from the leftmost to the rightmost. Note that there are not so many states of interest, and it allows us to use DP approach. Let dp0(l, r) be the time that is needed to collect all the treasures between l and r and end up in the treasure l (in the left border), Similarly, let dp1(l, r) be the time that is needed to collect all the treasures between l and r and end up in the treasure r (in the right border). Now try to find how to calculate dp1(l, r) and dp0(l, r) based on calculated values dp0 and dp1 for ranges with a smaller length.
Yeah, it's natural to come up with that solution, since if you take two treasures, say l and r, it's obvious you'll also take all those in the middle too when you get from one treasure to the other.
The only detail here is that there are 10000 treasures, 10 test cases and the time limit is little more than half a second...
Time limit is 3 seconds, and problem doesn't say that there's 10 testcases all of them n=10,000
I submitted that solution and got AC
Can u share me your code? i have submitted but it was limited 3seconds.!!
I wrote dp[n][n][3] algorithm and use n^2*2 complexity.
length=3 to n
i from 1 to n — length + 1 then i calculate dp[i][i+length-1][0](and 1)
so i think n=10000 is not possible to be enough in N^2*2 algo, i think u have some improvements here XD
I think using huge memory will make your code too slow, so I used only O(n) memory link
Thank you guy! i got accepted and rank 18 ;v i thought it would be normal cause in my computer i ran it normally but when submitted it got tle. i thought that cause N^2 @@ btw ty xd
Right, I see this version is incredibly easy then... The one I was talking about is this -> Alibaba
Try solving that one with an O(N2) algorithm...
Hello, but can i ask u some about your answer? XDXD i dont see it correctly cause i have some little questions that. if the answer for i..j interval is from i+1,j,0 and i,j-1,1 right? so if have a path from middle of i,j like i-1<k<j-1(meaning we travel from k to i. not i to i+1) so i think that dp is not good! can u explain for me some? Thank you many XD
In this approach you can start from any treasure in [l; r] range. The only important thing is that you will definitely finish in some of two borders.