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.

**features**

#### 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}:

**example**

We mostly have 10-50 clusters with big size and 1000-3000 clusters with single vertex.

**why?**

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