inbarin's blog

When the problem (G) is sus — round 719 div 3
By inbarin, history, 4 years ago, In English

did anyone else notice the LONG evaluation time or am I a noob? insert inspirational quote here to make this post seem reasonable

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

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was your logic for solving it ?

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

    since the cost is the sum we can think of portals as a different edge to the "portal dimension". I didn't realize this until just now, so I had the following idea: there are two options. A — just walk the entire way or B — walk from the start to a portal, and then from a portal to the end. calculating A is possible with a graph search (but block visited nodes) calculating B is possible with 2 more searches. (it is actually 2 parts — from start to portal + from portal to end.

    then the minimum cost of the 2 options is the true cost. note: time needed = cost

    I am bad at explaining so my best attempt is to claim that you can prove this answer correct,

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

Something similar was discussed in this blog. The last tests run very slowly.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

sus :flushed:

→ Reply