Hi, fellow programmer :)
I want to describe ideas that I used during ICPC Challenge 2020: Marathon.
First, how to get more than 600k score?
For 600k score we can just implement what this article says. Lets start with each cluster having only one vertex. (1) Then do the following thing until converge: choose random vertex and move it to one of the adjacent vertices cluster if it makes result better. (2) Now compress each cluster to one vertex and make new graph with weighted edges, then do everything like in (1) but now you are making clusters of clusters. I think image in article above explains it quite good. So, do (1) once and (2) until converge. Basically, that's it.
Second, let's analyze recieved clusters
As we get relatively close to optimal result, we now can analyze the structure of our partition. Here is random example for A3 in form {size of clusters : number of clusters with such size}:
We mostly have 10-50 clusters with big size and 1000-3000 clusters with single vertex.
So we can improve result by making better partition of big clusters or choosing better singleton vertices.
Third, kind of genetic algorithm
Notice that in (1) and (2) we are using random, so every new run give us new partition. The main idea is the next: different partitions are better than other partitions in some local regions; So we can combine them to get better result.
Particularly, what i did:
- generate 50-200 partitions
- choose random 5-15 of them and make new partition according to the next principal: 2 vertices are in the same cluster only and only if they are in the same cluster in every of chosen 5-15 partitions. Take a look on image.
- run 5-10 times (2) on new partition (do 3. on the same new partition from 2. 8 times, parallelly on processor cores and than take the best one)
- replace the worst one of 5-15 partitions chosen on 2. with the best one of 8 partitions generated on 3.
- do 2.->3.->4. 500-5000 times (it takes 5-20 hours on my laptop depending on A1/A2/A3)
Also you can take 5-100 the best partitions, generate 195-100 new partitions and do 5. again. This way you will probably stuck at different local maximum.
One more small improvement
So far in (1) and (2) we were only moving vertices to adjacent clusters. We can get extra 100-200 points if we will also try to move vertices to new singleton cluster.
That's all. Hope my english is not too bad and you like this post <3
