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.

Very nice writeup. Actually I was at the PIZZA contest recently (28 March), and it was pretty much analogous to M24 or D24, just on a smaller scale — it took about 8-10 hours, if I remember correctly. There were only two tasks (one similar to Pokemon battles, and the other was like a Bomberman game with gathering resources like in your TCO Finals and of course killing people), so I took the Bomberman, while the remaining two members of the team concentrated on the Pokemons. A week before the competition, I encountered your writeup of CTF on M24, as I was searching for strategies for similar contests. I found it very instructive, and decided to preimplement basic skeleton for visualization beforehands (also in CImg.h — thanks! That's excellent quick prototyping pick!). This was very beneficial, as I was having instant feedback, decreasing time to implement core features. Especially in the very beginning — I was probably the first one to implement a basic gathering bot that does not kill itself within seconds. In the end, my solution for Bomberman was the second best (the winners were steering only manually, and they started doing that in about half of the contest, but they still won — the final rounds were much more valuable in points). Unfortunately we had a pretty bad solution for Pokemons, so we finally took third place overall.

Probably the main error I did was not implementing any manual controls in my solution — it was pretty hard to do anything more complex than simple strategies without sacrificing too much time and debugging. Also, after a few hours I was completely out of ideas, so I was pretty mch staring at the screen, looking at other people's movements, trying to find out their strategies. Nothing was quite good however, so I could equally well just play the game on my own.

I hope we will meet some day at a competition of some kind — I'd love to exchange a few words with you :)

PS: do you know more contests like that? I can't find too many of them :/

Most of the bad submissions would either timeout, or give WA in such case, whichever the problem it has. What would be the use of hacks then? Moreover, max tests would overload the servers even more — and I think Codeforces are already having troubles serving so many people at once.

I think taking 404th place feels better x)

Good to see somebody enjoying my explanation :) (below, I will use E(X) to denote expected value of X)

We need to calculate

E( d(i,j) + d(j,k) + d(i,k) ),

where expected values are taken over every triple of distinct numbers i,j,k. Thanks to linearity of expected value (http://en.wikipedia.org/wiki/Expected_value#Linearity), we can rewrite this as:

E(d(i,j)) + E(d(j,k)) + E(d(i,k))

Since every of those three terms is independent of the remaining two, we can just calculate first one — the other two will be the same. Thus, what we need is actually equal to:

E(d(i,j)) * 3

with expected value (still) taken over every triple of distinct numbers i,j,k. But since k is absent in this equation, we may as well drop it, leaving taking average only over all PAIRS of distinct numbers i,j. Which is what I wrote above. I hope that is more clear now.

The easiest way is to notice that expected value they ask for, is just: Sum of distances between all pairs of vertices(i,j), multiplied by 3 (because there are 3 Santas) and divided by n(n-1)/2 (number of pairs of vertices)

The only non-trivial part of the above quantity is sum of distances. It can be rewritten as: Sum of (for every edge e) cost[e]*frequency[e], where frequency[e] is number of paths in the tree that pass through that edge. Notice that if we know frequency[e] for every edge, we can easily answer every query in constant time by subtracting (change of cost of edge)*frequency[e]

So, the only thing left is to calculate the frequencies for every edge — and they are static (do not change in time). How to do it? The way I approached this problem is by making DFS from vertex 0, that returns number of vertices in the subtree below. Then you can notice that for every edge (u,v) the numebr of paths that pass through it is: (number of vertices in the subtree) * (N-number of vertices in subtree).

Hahahah, that was a nice find. Thank you :)

Damn, failed on 47th test... Is there any way to download the tests to see what went wrong?

Well, for example non-terminated C-string, or too small allocated size for char buffer...

I did it in the same way — probably a useful structure is >> int last_before[i] << , indicating where is the last occurence of t in s, that ends before i. Then the recurrence can be sumarized to:

dp[i+1]=dp[i]+sumdp[last_before[i+1]]

sumdp[i+1]=sumdp[i]+dp[i+1]

(with edge cases and similar stuff added, of course)

For div2, a lot of solutions for B had bad complexity O(a) — I managed to submit only two hacks though, due to the server being down for the final fifteen minutes.