jjang36524's blog

An Infamous Korean TSP Problem
By jjang36524, history, 3 hours ago, In English

Two days ago, a infamous problem in BOJ, a Korean OJ was solved(by me).

It is named 814-3 and it can be found here

The problems ask you to solve a TSP problem with 8000 randomly placed nodes on integer coordinate in square (0,0)-(814000,814000) and 140 salesman to travel them. The goal is to minimize the max distance that a salesman needs to travel. You do not have to find the exact solution, but you need to get an average score of 416280 or lower in order to solve this problem in 50 fixed test cases. Do note that this problem is not output only, and you need to do all the calculations in 4.814 seconds.

Input looks like this:

8000 140(fixed)

129309 230298

198309 129380......

Output should be 140 lines like this:

(Number of nodes that salesman 1 will visit) (list of them)

Example: 5 13 37 420 365 24

Wanna give this problem a try?

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

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

...score of 416280 or lower...
...do all the calculations in 4.814 seconds...
too scary

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

my thinking:

Binary search the answer $$$a$$$. Build a graph $$$G=(V=[1,8000],E=\{(i,j)\mid d(i,j)\le a\}$$$, and check if the graph can form $$$140$$$ paths that:

  • cover all nodes
  • every node only lies on one path
  • all have a length less than $$$a$$$

so how to check???

→ Reply