hagu's blog

Gym problem

By hagu, 9 years ago, In English

Recently i encountered this problem Make It Through Your Way. I am not able to figure out why this code passes , i think it should give TLE. Link to code

Here each '.' can be called multiple times with values [0,v]. so it will increase the complexity to a large factor but still this code passes. Can anybody give me a proper analysis of time complexity of this code.

Thanks.

  • Vote: I like it
  • 0
  • Vote: I do not like it

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

Do you know how to create such test? (where your solution gets TL)

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

    No, I'm not able to do that either.

    But I just wanted to ask , how am I supposed to know that these type of solutions will pass or am I supposed to just go with my intuition.

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

Can you explain me the question. The statement is quite unclear

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

    This problem asks you whether there is a way to reach the end point from the starting point without being detected.

    You can make at most v moves during day or night. In each move you can move to adjacent cell (left,right,top,down).

    If you move during the day you can move from one 'F' to another 'F' only, since forest provides you cover, while during night you can move anywhere since the night provides you cover. It doesn't matter how many days or night you take to reach the end point.

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

I can't give you a proper formal complexity analysis, but I can kinda explain why it works.

The idea is to use a modified djikstra where whenever you reach an 'F' you reset the value to 0 and where you ignore stuff that can't be reached (dist > v) to check for the daytime walks.

Now, when you do a regular djikstra and pop something out of the priority queue, you are sure that that's the shortest path because if that node ever gets pushed in the priority queue again, it will be with a bigger distance, because:

  • If you popped it from the pq, it means that any other path that may lead to that node that's already in the pq is bigger (having higher priority) and you'll ignore them after

  • If you reach that node again, it will be from a bigger path (only bigger ones left in the pq) + distance to that node, which is bigger (or the same path + distance, which will be bigger and not a simple path).

What happens in this code is that you can actually find a smaller path later when you reach a '.', because when you reach a 'F' the distance becomes 0. So you can get to a '.' and then later get to an 'F' that is closer to it and have a smaller path to it.

BUT, the shortest path to the '.' can only be updated by a closer 'F'. And when you reach a '.' and keep traversing the graph, the first 'F' you'll reach after that '.' is the closest 'F' to it (if you haven't already come from a closer 'F'), which will update the value. After that, any other 'F' you reach is further than the closest one, so the value of the '.' won't be updated again, therefore you update it at most twice (once coming from the origional path and once you reach its closest 'F' if it wasn't already in that original path).

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

hahahahaahhaahahahahahahahhaahahahahhahahahahaha

→ Reply