vatsal's blog

E-olymp way via mountain
By vatsal, 6 years ago, In English

How do I solve this DP problem? Notice the word "tunnel" in the problem statement which confused me. https://www.e-olymp.com/en/problems/5852

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

Comments Comments (15)
| Write comment?
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How the word ``tunnel'' can confuse???

DP subproblems should be: "What minimal distance magus should walk to get from start vertex to vertex #i, using not more than j bridges?".

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

    I think tunnel means that no 2 bridges can intersect. Yes, i figured out that dp. It will be kn^2 right.

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

      I implemented the DP you told but I got WA.

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

        A typical mistake solving this problem is to consider (incorrectly!) that no returns can be useful. Sometimes they may be. For example, look picture at the top of page 195 of http://ws.kh.ua/media/sbornik/Sbornik2010.pdf, assuming that K = 2 (only two bridges are allowed), neither AE nor FJ bridges are allowed because they intersect surface near C and near H respectively, and neither AJ nor AH nor CJ bridges are allowed because each of these segments' length is greater than R (maximal length of bridge).

        (That book is in Russian, but you may at least look at the picture and at equations.)

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

          Which bridges are not allowed? 1) Those whose distance are more than R 2) Those which intersect the line formed by joining the points

          Am I correct?

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

            Yes, except that some points or segments of the bridge can touch the surface of the earth.

            In other words, bridge cannot go under earth surface (polygonal chain), but some vertice or some segments of polygonal chain may belong to some bridges. For example, if we have polygonal chain

            0 10
1 0
2 10
3 0
4 10

            and R ≥ 4, we may build a single bridge from 0 10 to 4 10, although the bridge comes through 2 10

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

              So bridges need to be straight lines?

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

  1. This question was duplicated in http://codeforces.net/blog/entry/59717

  2. This looks like this problem is used in some current contest, so let's wait for some days before further answering.

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

    Hey! I am still unable to solve the problem can you please help!!

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

    Now?

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

      Well, AFAIK it's much more efficient not to check does given bridge intersect surface, but to build graph of all possible bridges in a special algorithm stage before (main) DP stage. In this way, it's quite easy to build all O(N2) bridges totally in Θ(N2) time and O(N2) space.

      For example, to build all possible bridges from vertex v1 (1-based), one can maintain "current maximal slope" (let's name it maxSlope). It's initialized as v1v2 vector (vector(v[1],v[2]) in notation of pseudocode below); then, 

      for each further i, 
  if vector(v[1],v[i]) is counterclockwise or co-directed with maxSlope 
  {
    if dist(v[1],v[i])<=R
    {
      bridges between v[1] and v[i] is allowed
    }
    maxSlope is re-assigned as vector(v[1],v[i])
  }
      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

H-m, it looks like checking of this problem at e-olymp.com is incorrect. Try at ejudge.ckipo.edu.ua, contest #16 "Upsolving of Ilya Porublyov's and DrPepper's day of ISSPS'13 // Дорешивание дня Ильи Порублёва и команды DrPepper ISSPS'13", problems F and G respectively (F for smaller constraints, G for full). (There are no English-language statements at that site, but one can switch its interface to English.)

I've already sent bug report to e-olymp.com admin, but still have no reply for it.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    Thanks, I fixed it. Enjoy!

    P.S. I did not retest all solutions, who got 0 points, please send again your solution.

    → Reply