Radebush's blog

How to solve this problem?
By Radebush, history, 6 years ago, In English

I recently spotted this problem of IOI 2018. I couldn't come up with a proper approach. Only thing that I know is the solution is associated with graph. Can you please help me to solve this problem?

https://ioi2018.jp/wp-content/tasks/contest1/werewolf.pdf

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

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

You can find the solution here

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. Create a new directed graph having 2*n nodes.
  2. The first n nodes are marked as H1, H2, ...., Hn and last n are marked as W1, W2, ..., Wn.
  3. For two node Hu and Hv, connect it if there is a edge between u and v and can be visited in human form. Similar things goes for Wu and Wv.
  4. Add a edge between every Hu and Wu.
  5. Run DFS(Hsoruce) and see if you can reach Wdestination.

The best part is you don't create the above graph explicitly. You calculate the graph on the fly form the original one. And most graph algorithm actually uses another implicit graph which is calculated on the fly (yes, Dijkstra too).

→ Reply