Challenges marathon round of Yandex. Algorithm 2017

And again, as in previous years, the final of the Yandex.Algorithm contest is approaching. This year we have introduced a new round - marathon. It is a single optimization problem without an exact solution, which participants were asked to “twist” within 48 hours. This format is similar to solving practical problems more than popular competitions in sports programming.

A feature of most practical problems is the lack of an exact solution — or the algorithms for finding it turn out to be too slow. The team and the individual developer need to make a good prototype of the solution that will be implemented in the final algorithm. Tasks of this kind have long been encountered in TopCoder competitions, annual Marathon24 , Deadline24 , Google Hash Code and other competitions. The competition lasts longer than standard algorithmic rounds, so that participants can implement the invented method in a relaxed atmosphere and at a convenient time for themselves.

We, the organizers of the Algorithm, really want the diverse participants to successfully show themselves. Therefore, the addition of the marathon round is seen as a way to expand the audience and popularize such competitions.

We asked the participants who showed the best result to explain how they achieved it.

We suggest that you try to solve the problem ! Anyone who will show the best result before the final of the Algorithm, we will present a t-shirt with the symbols of the competition. The final will take place on July 18th. Both those who decided the round within the framework of the Algorithm and new participants are invited to participate.

The condition of the task "The separation of the country

  4 6 3
 0 0
 13
 thirty
 3 5
 2 4
 2 2 

  aaabbc
 aaabbc
 aaabbc
 cccccc 

Konstantin Khadaev (Russia, 7th place according to the results of the round)

First we find some paths from one source to another. This is a standard threading task. Some participants here used min-cost max-flow, but in my decision it did not give any gain, and in the latest version I left the algorithm Dinnitsa.

Next you need to somehow distribute all the other cells. I did this very primitive. We pass through all undistributed cells, choose a random neighbor. If a neighbor is given to a son, we give this cell to him. Otherwise, leave undefined. And so we iterate until we distribute all the cells. A small optimization: if three neighbors are given to the same son, we must give him a cage.
')
Of course, randomness can be added to both previous steps. Shuffle the vertices for Dynitsa, iterate over the cells in a random order.

Next we have some kind of map, we will optimize it locally.

Here I have three cases:

• A cell has only one neighbor from the same territory as it, and at least two neighbors with another. Then she should be transferred there, with whom she has two neighbors.
• The cell has two neighbors from the same territory and two from some other. Then the usefulness of the transfer depends on the areas of these territories.
• The cell has one neighbor from the same territory and one neighbor from three more.

To quickly understand what is more profitable to do in cases 2 and 3, you need to maintain the area and perimeters of all territories. But each case gave a fairly noticeable increase.

Well, all this can be done many times while there is time, and choose the best.

In this form, the solution is already gaining quite a lot of points, but it often slips into local minima. A possible way to deal with this: in cases 2 and 3, even if the change does not bring benefits, it is still with some probability to do it, and this probability decreases with each iteration. This change increased the result by almost 200 points.

And about the feedback:
I did not like the fact that it intersects with the VK Cup. By the way, this also concerns the next round - it’s on the same day as the Russian code cup and Distributed code jam, I’m not going to pull out three contests on the same day. And the task is very pleasant, yes.

Eryx (Poland, 2nd place at the end of the round)

Thank you for the great competition and a very interesting challenge. It was a pleasure to work on it. The only thing I did not like was a slightly incomprehensible description of the generation of test data (“some random distribution” —but what?). Perhaps it was worth adding the “official” data generator (without the initial value), and we should leave a non-trivial part where we need to “make sure that the solution exists”.

A version of my solution with comments can be found here:
https://www.mimuw.edu.pl/~erykk/yandex/solution.cpp

I see that some of the final tests fell (although with public tests everything was fine). I had no idea to use min-cost max-flow to build paths. I think if I used this as an alternative approach, I would get the correct answers on the above tests, and possibly improve other results.

Ilya Kornakov (Switzerland, 6th place in the round)

I already wrote something in http://codeforces.com/blog/entry/51858?#comment-358766

I liked the task, according to the Java brakes module. The solution is as follows:

• First, min-cost-max-flow searches for paths connecting sources and drains.
• Then the paths expand greedily until the field is filled. Greedy steps are trying to add one by one cell, as well as a column / row segment to an existing component. The objective function is the change in the sk / (the number of added cells + 10).
• The resulting solution is greedily optimized by throwing cells or column / row segments between components (with the same objective function).
• The described process is launched many times, the best solution is chosen. The process is added randomly: the edges in the graph for the flow are mixed, the cores in greed are multiplied by a random number from 1 to 1.2.

Most of all points were brought by rewriting the solution from Java to C ++ (~ + 150). In addition, greedy improvements after the solution was generated - apparently a useful idea. From unrealized - try more changes in greed (for example, cut off the "corners" - a pair of sides) and instead of the flow do something that is better adapted to the target metric (since for the flow a long horizontal path is much better than the diagonals with the same horizontal displacement, and from the point of view of the target metric - much worse). Another idea was to try simulated annealing instead of greed, but there was no time left.