I think the trick in this qualification was to submit something for all problems, and don't spend too much time optimising. Even if the answer was extremely sub-optimal, as long as it passed verification the score for each problem would be in 50-70 range, which would give a total between 250-350.

If all you're after is qualification to the final round, I'm pretty sure quite simple brute force approach for all tasks is enough — but it's important to do all of them, as a loss of even just guaranteed points (40% or so for most problems) is too big to be compensated by good scores in others.

Unfortunately, I don't see the problem statements (they seem to be removed from the website), so I'll tell what I remember:

1. Eurovision Song Contest (71.5/100) — this one was made by other team member, so no comment.

2. Network (75.6/100) — the first idea I thought of was the most successful here — just starting at a random house, then BFSing to the closest unvisited house, without even looking at costs (apart from obstacles). I tried treating fields with cost>threshold as obstacles or randomly taking the second-closest house instead (and taking best result of many iterations), but this was giving worse results.

3. Palm Tamagotchi (67.3/100) — given scores of other teams, I guess many of them used the same approach as we did — use only Grow commands, building the needed tree, then reset to time=0 and build the next one, until all trees are processed. That is, we completely ignored possibility of reverting to non-0 time and deleting some branches.

4. Puzzle (75.6/100) — greedy approach, that is: for all postions, try to fit every possible puzzle in any orientation. If impossible, go to next square and repeat. After going through the whole board, check whether the number of completed pieces is greater than best solution so far and if so, save this solution. Then repeat the whole process thousands of times after randomly shuffling the puzzles.

5. Firemen (72.1/100) — hill-climbing algorithm. First put fire stations at random places, then make thousands of iterations of loop, in which one of the fire station is moved in random direction (in the first iterations, by distance equal to half of the board size, then gradually decreasing to 1 step per iteration), then cost of current configuration is computed and compared with current best, saving current one as best if needed. The cost itself was computed using BFS from all stations at once in O(nm) every time. Likely it was possible to avoid so many calculations, but this worked nicely anyway.

I guess we could squeeze an extra ten or so points from the third task, as probably even a small improvement in score could throw us above teams using similar approach. But the contest was aleady ending, so we decided not to implement more ambitious solution, in order to have any solution at all. Turned out to be a good decision — leaderboard shows we're 28th, which, if 'm correct, places us in the finals.

Let's also discuss the rules: it is said that "20 to 30 teams with highest score in qualifying round that will be invited to participate in finals" so I wonder, is it 20 or 30 :)

Also, I wonder if I'm the only one who thinks that current scoring rules are weird. We didn't submit 3 tests in EUR and 3 tests in NET, and it turned out to be a very bad idea: random low-quality submissions on these tests scored 6-7 points, so this costed us more than 10 positions in the leaderboard (also I wonder how is it possible that all scores on these tests are above 6? Do I misunderstand the scoring rules?). As a random suggestion: maybe have a simple baseline (not public) for each problem, and submissions which score below the baseline get zero points?

As for the problems. Our approaches were as follows:

• STR: greedy algorithm, choosing point at each step which minimizes target function on this step. Apparently this is suboptimal on many tests (especially the smaller ones), but is scored 9.9 on the largest test.

• PUZ: brute force solves smaller tests, larger tests are (partially) solved by brute-force with cutoffs

• PAL: greedy, on each turn pick the palm which can be obtained from one of the already generated palms in the smallest number of steps. This works really good, and I guess many other teams implemented smth similar (looking at scores)

• NET: generate some sane permutation of houses, and then perform hill-climbing starting from the permulation. Use Dijkstra to obtain score for a given permutation (this probably was a bad idea, because it was really slow on big tests).

EUR: 83 6 Just considering as a knapsack problem(just vote for itself), use gain/cost efficiency to greddily pick which country to vote. Looks very suboptimal but it's enough for a fairly acceptable score

Thanks for the contest! I was solving Firemen and Network and enjoyed both of them. One of the most exciting parts was how to write some reusable code for grid problems :)

I'd like to point at one thing: because of some teams with very long names (especially #COSANOSTRA#TEMANTURAL#ANONIMOWIBIAŁKOHOLICY#EATCLENTRENHARD — they had no spaces in the teamname) standings were a bit screwed and it was pretty annoying to scroll horizontally each time. I don't really know what to do with this issue. Maybe just limit the team name with, say, 30 characters, or display such long names like #COSANOSTRA#TEMAN....

STR/Firemen (#1 place) — generate many random placements and choose the best one. Improve it in loop with climbing hill. Choose a random cell, find the nearest 2-5 stations and try to move them a bit many times. Chosen stations are close to each other so we can care about their surroundings only. Tests #7 and #10 were very dense (51% and 20% of cells can be stations) so I rewrote my program. There I generate one random placement and this time in loop I move only one station to its neighbor. It turned out to be great solution for those two tests and I had the best scores by huge gap.

And super-awesome-optimization for PAL — instead of resetting to time 0, we can grow two children from root first and later always reset to time 1. We can do it because in all trees a root has two children. It gave me 78.4 points.

Did you receive invitation email for qualification round?

I'll write something about PAL (as I had pretty decent scores on this task).

First of all, we don't want to revert back to beginning when getting between two sought configs. In fact, if we have two trees T_a, T_b of sizes a and b, there's a standard dynamic quadratic-time programming solution which computes the size of their largest common rooted subtree (let call this subtree ).

OK, so now we would like to describe the whole process as a rooted tree in the space X of binary rooted trees (that is: 'vertices' are binary trees and vertex c can be a child of p if T_c is a subtree of T_p). Let's order trees from input in any way we like: T₁, ..., T_n. Then we take any two consecutive trees T_p, T_p + 1, find their common subtree and insert it instead of them. Continuing the process, we finally arrive at one subtree. Reverting the whole process, we construct a rooted binary tree in X whose leaves are the sought trees. Whole construction uses only growth potion and well-chosen time reversals.

Now the whole thing is probably better than many solutions (it's now better than "construct a tree, delete it, construct next tree, ..."). But there is still some room for improvements. I used a O(n³) dynamic-programming algorithm for finding a good order of joining the trees (its idea is almost identical to finding optimal matrix multiplication order). Moreover, I used some hill-climbing over the permutation of trees in the input. Both improvements probably gave me a comfortable win on inputs 7-10.

Also a note on PUZ: some people (including me) may have known the puzzle as Eternity II. Input puz07 has the same dimensions as original puzzle. Can someone prove/disprove it's the same instance of problem? :P