pabloskimg's blog

By pabloskimg, history, 5 years ago, In English

I'm trying to solve the problem Routing from ACM ICPC World Final 2006, and I don't have any ideas on how to solve it. Since the number of nodes in the graph is at most 100, I guess a Floyd-Warshall preprocessing should be no problems and could probably help, but after that I really don't have any ideas on what to do next.

Any tips will be appreciated.

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

| Write comment?
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

AFAIK that one is same with problem KAMPANJA.

Solution link.

You can model the problem into a bitonic tour instance, and run a shortest path algorithm on the state graph. Time complexity is about O(n3) ~ O(n4).

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

I have tried to get the problem accepted most of the day. But I can not get it correct. I have written different solutions, but they all the same wrong result. I have tried writing with and without a blank line after each test case. I have also tried writing "Impossible" instead of "IMPOSSIBLE" because that is what the solution on uDebug does. Any help is appreciated.

Here is my python solution, which gets TLE(the TLE is not the problem, because it gets the same result as the c++ solution):

This is my brute force:

I use this script to generate data:

This is a modification of the c++ solution ko_osaga posted:

I have tried submitting here:

and here:

I have tried testing my solution here: and here