harry_porter_7's blog

Idea for a DP problem
By harry_porter_7, history, 8 years ago, In English

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

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Can u share me your code? i have submitted but it was limited 3seconds.!!

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I think using huge memory will make your code too slow, so I used only O(n) memory link

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

            → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply