[Community Puzzle] Travelling Salesman

Puzzles
#21

@java_coffee_cup where in the description does it state that this is a maximization problem? As far as I can tell it doesn’t.

#22

What do you mean by “hardcoding” ? Please forgive me for this question if you find it dumb, I’m just trying to learn…

#23

Detecting the validator input and outputting a solution computed offline, since the validators are public.

#24

That was back when the ranking in the leaderboard was problematic. It was fixed afterwards.

#25

I just solved this with the very simple method of “always go to the unvisited node closest to your current node”. I assume most solutions are the same given most of them have the same score, but I’m curious how people achieved even better scores?

I attempted for each path, check the 2 closest nodes next path, and choose the one the second step of which will be shorter, but it resulted in an even longer path. Analyzing the whole path is impossible due to time constraints, but analyzing more than 1 node at a time is mysteriously counter-productive?

#26

Hello there,
I was working on this problem and found that the time of reading the first variable is more than 2 secs.
In python:

import time
start = time.time()
n = input()
print(time.time()-start)

The printed time is already 2.2 secs, which is almost half of the allowed response time (5 secs in this case).
Is there a possibility to improve the reading time? Do you know if this issue is related to my connection? the language? the problem? the platform?

Thanks in advance.

#27

I think the time you have recorded does not matter. You may check out the following link and code (for Test case 1) for your reference:
https://www.codingame.com/forum/t/questions-about-how-time-is-calculated/191835

import time
n = int(input())
for i in range(n):
    x, y = [int(j) for j in input().split()]
start_time = time.time()
while True:
    if time.time() - start_time > 5:
        break
print("0 2 1 3 4 0")
1 Like
#28

Thanks,
That link is what I needed.
However, according to the link discussion, the timer starts just after the first input. In your example, after n = int(input())
Thanks again!

#29

Yup, I know, just to illustrate that the case passes even if I start the timer later :wink:

1 Like
#31

With Hierholzer algorithm, how to detect the edge to change in the path because it’s not optimal ?

Also I try to use concorde but i have this error in the makefile :slight_smile:

for i in BIGGUY LOCALCUT COMBS CUT EDGEGEN FMATCH HELDKARP KDTREE LINKERN LP PQ TINY TOOLS
TSP UTIL VERIFY; do
i était inattendu.
#32

I have sorted the vertex , it’s for that it bugs, but i do only 235000. it miss me 20000 points.