Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Tanzir5's blog

By Tanzir5, history, 6 years ago, In English

Can someone please give any idea about how to solve problem G.Tourist of this set?

The problem basically gives you a directed graph, a source, a destination and a list of interesting nodes. You have to start from the source and reach the destination and visit all the interesting nodes on your path. You are allowed to visit a node multiple times but you cannot use more than n^2 nodes in your path. You have to print the path or say it is not possible. Number of nodes is 2000 and number of edges can be 2000*2000.

I have a O(V*E) solution for the problem. But that is not going to be enough. Can someone give any better idea?

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