Блог пользователя vatsal

Автор vatsal, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
8 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

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

»
8 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
  1. This question was duplicated in http://codeforces.me/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.

  • »
    »
    8 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    8 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Now?

    • »
      »
      »
      8 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

      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])
        }
      
»
8 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +10 Проголосовать: не нравится

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.