Hi everybody!
Today at 21:00 UTC there will be Yandex.Algorithm 2017 Marathon Round.
You have two days for creating an efficient solution for the optimizational problem we have prepared for you. You may submit for the whole 48 hours of the contest.
This round is the first one among the four elimination rounds. Don't miss!
UPD Testing on final testset will happen tomorrow. Thank you for participation!
What is this, a cheap way to get my phone no.?
I'd be happy to help you figure out your Yandex account issues through personal messages
The system doesn't allow me to submit a solution I have sent before. In a contest where only the last submission counts it's a desired feature, I think.
I have managed to submit by changing a small thing in the code, but still it seems to me that it should be working properly.
Also when I submit too early (less than 5 minutes after the last submit), the site tells me, that I have already submitted that code, although the submission was refused.
I couldn't participate in the marathon round , will I be able to participate in later stages of the contest ? If yes , how would marathon round affect me?
It is not necessary to participate in all rounds, your final result is calculated only using the rounds you have participated in.
Refer to the Rules section of the competition.
I just read the rules, in both languages, and didn't find anywhere a phrase about using the rounds you have participated in. Instead, I found that final score for any participant is the sum of the scores for all 4 rounds + the lowest place taken as a tiebreaker. Did I miss something?
I suppose this just meant that the rounds are equally important and you don't drop out (or get any kind of penalty) for not taking part in some of them.
ania says everything correctly, that was the informal description. When you don't participate in a round, you get the zero points and rank infinity, so it is effectively equivalent to not considering this round for you at all. You are not penalized in any manner.
I am not sure what the "lowest rank" means. If lower = worse, then your lower rank becomes infinity if you do not participate, i.e., you lose the tiebreaker. The wording "A Contestant will rank higher [...] if they have higher scores [or] their lowest rank for the four rounds [...] is higher" suggests that this is the case. Also, if the worst rank matters, it would be illogical to not consider this infinity, because then not participating in a round might be a better choice than participating ("I am second in the first round, definitely tiebreaker at least, let's not participate just to not destroy my good standing with respect to the tiebreaker" -- with two rounds and 11 advancers this would seem to be the case).
As the round is over, here is my code, around 7500 points on the public tests. Ugly to read, not recommended.
First I generate random pairs of life and magic fountains. I try to connect these pairs along the shortest path (I also tried Hungarian method, didn't work that well). When creating pairs, close fountains have a higher probability to be grouped together. I fill the rest of the map in the following manner: when an empty field has two neighbors of the same region, that empty field gets added to that region. Next I assign fields with only one non-empty neighbor, then the remaining fields.
For the second half of the available time I try to further optimize my best solution so far: select a random border and move it. If the score gets higher, I keep that solution. I sometimes move multiple edges in the same round to exit the local optimum.
This code still times out on two of the public tests. Is anyone ranked higher willing to share his strategy?
I did almost the same, but I generated matching by min-cost-flow with random edge weights. Also I didn't change color of multiple cells at once (was lazy about it :D), but did a lot of iterations. Got about ~7550 points on public testset.
Here is the gist of my method (gets around 7700+, the remaining ≤ 100 points obtained by relatively small hacks)
Generate pairs by min-cost-max-flow with all edge costs of 1. Then fill remaining pixels greedily by adding a pixel each time such that the total score is as high as possible after that step.
Refine this solution by trying to "grow corners" — loop through all possibilities in random order (selecting random pixel, direction, and number of layers ≤ 10 = MAGIC to grow) and apply an update as long as it improves score or there is time left. Example of "corner growth" at the bottom. Growing corners is useful because it allows to get from a square of size N × N to the one bigger, and square is the shape with the optimal "convexity", I think.
Hack that brings biggest improvement: when the test case is from the third group, in MCMF instead of making the cost of every edge 1, make cost of using pixels (i, j) such that i or j is divisible by MAGIC=5, equal to 0. In this way, the obtained set of paths is likely to be more disperse, rather than crammed all together around the line joining the squares from which the sources are generated.
Around 7700 on public tests if implemented in C++ (and 7550 — if in Java).
First, run min-cost-max-flow to match sources and targets. Add these paths to the solution, and grow them greedily, adding one cell or continuous horizontal or vertical sequence at a time (score := delta_target_function / (5 + number of cells)). Once the field is full, do a similar process of improving solution: move one cell or continuous horizontal or vertical sequence from one group to another if it increases the score (this is tricky implementation-wise, since we have to check we don't disconnect areas; I just ran full connectivity check, but maybe one can do smth smarter and faster).
Finally, there are many places where one can add randomness here: order of edges in min-cost flow, random fluctuations in greedy & final hill-climbing scores. Add all this randomness, and repeat the procedure for 2 seconds, choosing the best answer. Locally this was giving +200 points (evaluating on 1000 testcases), but on public tests Java version didn't improve much (likely because it didn't have time to do more than O(1) iterations). I didn't have time to evaluate C++ version though.
7668.32
Generate paths by min-cost-max-flow. Expand them by bfs. Then while possible to increase score do mutations of two types: 1) Take side (edge?) of some region and paint several lines near it in the same color. 2) Take side of some region and fill it with neighbour colors.
Some hacks like "we can take just part of side" or "let's check improvement after each painting" significantly increased the execution time but also helped to get up from ~7500 to 7670.
BTW, on my local tests I get ~8150.