https://www.codingame.com/training/hard/mars-colonization

Send your feedback or ask for help here!

Created by @java_coffee_cup,validated by @JBM,@Niako and @Deltaspace.

If you have any issues, feel free to ping them.

https://www.codingame.com/training/hard/mars-colonization

Send your feedback or ask for help here!

Created by @java_coffee_cup,validated by @JBM,@Niako and @Deltaspace.

If you have any issues, feel free to ping them.

Hello

I was solving this puzzle and found smaller numbers than the answers. Can you check my answer?

for test case â€ś20 Stationâ€ť I found this:

[[5874, 373]]

[[5182, 5463], [6975, 6202], [6463, 4958], [4551, 3561], [4256, 4324], [2824, 5476], [6587, 8269], [5643, 7942]]

[[1950, 8000], [1977, 8641], [2221, 9172], [3086, 8470]]

[[7569, 1922], [9338, 1031]]

[[9585, 8798]]

[[9060, 5456]]

[[1269, 2130], [1573, 1547], [652, 765]]

as my 7 colonies.

The minimun distance is : 1980.72

but the answer should be: 2103.10

Can you check this out?

Thanks

You cluster division is correct.

The longest (minimax) distance within each cluster is between [6975, 6202] and [6587, 8269], which is sqrt(4423033) ~= 2103

Does it make sense?

2 Likes

Thank you. Problem solved. I was calculating the distance wrongly

I am not sure if it is obvious but I assume that 1 station can be connected at the most to 2 other stations right? Otherwise just 1 station with sat comm can be used to connect every station to each other.

No such restriction in statement.

If it is an induction result of your own, you should make sure you can prove it before relying on it. I do not have this proof in hand.

The discussion of the 20-stations above has given away some hints of approach.

The stations can be divided into clusters. Within each cluster they commu by wireless. Cluster-to-cluster can commu by sat coms.

You have to figure out how the clusters should be formed, and how to control the number of clusters.

Have fun.