roadsandjunctions-seed2
Algorithm

The Hardest TCO Round 1 in the Past 3 Years



As I write this post, my local system tests are running in order to determine if I have a lot of bugs in my current solution, or just several (or maybe none this time).
Traditionally, I will not provide fancy stats and graphs Rustyoldman did, because I do not have them. Instead, I will allow myself to use the exclusive status of a blogger and err.. violate the rules a bit. To start with, as of now 180 competitors are aware of algorithm A1 that runs in quadratic time and solves a simpler version of the task.
Are there better algorithms for the task given? Are they stable enough? This is for you as a competitor to decide.

But Please Do Not Discuss This Yet


The rules of the scoring were altered severely during the first days of the contest, so in case you do not follow the forums, here they are:
t-mac: It has come to our attention that given the nature of this problem, rank-type scoring does not work well, and leaves a lot to chance. We are moving instead to a relative scoring system (best/your)^2 to calculate overall leaderboard position. I will re-run tests and the leaderboard will be updated shortly.


Alter your solution to reflect this if you already have not done so.

The Task


The task was written by Nickolas and tested by t-mac. It asks you to connect all given vertices with Cartesian coordinates into a tree, possibly adding some auxiliary vertices. You are fine to add zero auxiliary nodes. One extra caveat to take care of is that the auxiliary vertices require additional cost and they may fail. That is to say, even if you “pay” for an auxiliary vertex and place it into a good location, you are not safe: the vertex may be removed by the tester code and you are in some troubles.

The Leaderboard


The current leader is a former Algorithm champion tourist, with 997165 points. The runner-up sdya, 996988 points, has a strong SRM history as well. Multiple Marathon champion Psyho, takes only 11th place with 996468 points. mugurelionut, the highest ranked from last year’s onsite marathoners, is on 5th place.

How To Solve It


Coming soon...