А точнее, топ-350 по параметру "минимальное из мест на раундах 2A, 2B и 2C".

It doesn't work for me too >_< Does anyone know how to fix it? It would be so disappointing to miss this round because of this.

Edit: the Topcoder forum's URL is also broken. No idea how can we contact admin to ask..

Edit2: The applet works now :)

You should ask such questions only after the end of the Challenge Phase.

250: let's sort our bricks in nonincreasing order and let's put them in such a pattern (number is an index of the sorter array):

 1  11   2   9
12   7  15   3
 6  16   8  13
10   5  14   4

Any permutation of bricks 1-8, 9-10, 11-14, 15-16 will be fine.

500: already explained in Russian in this post.

UPD. I've changed the comment after eatmore has pointed to my error, but didn't mention it. Now everything is fine :).

250: The area is the sum of absolute values of height differences between all neighboring blocks. We can guess that it's best to use a chessboard coloring and put the larger 8 blocks on black squares and smaller ones on white squares. Then, we figure out that it's best to put the 2 smallest blocks in the 2 central white squares and blocks 7 and 8 to the corner white squares (to maximize the number of times larger h are added in abs(h-0)).

500: Bruteforce, sort the wolves by a and first try splitting the sequence into the prefix that goes left, suffix that goes right and center. If the wolves are in correct order now, it's easy to compute the cost; otherwise, center must be empty and you can choose the prefix (in sorted order by b) that will be left on the left (lol), count the number of wolves which need to pass through the passage (lol again) once more, and then count the distances. Time's probably something around O(N⁴).

250: "fair" solution would be submask dynamic: you just put elements one-by-one from the largest to the smallest and keep the mask of the occupied cells. If you put an element somewhere, you have to subtract its value * number of neighbouring cells in the mask (since it is smaller then values in these cells). However, everyone submitted the following greedy: put 8 smallest and 8 greatest values in chess-order, preferring central cells for the larger (smaller) numbers. Should be pretty straight-forward to prove, but I didn't do it during the contest (seemed pretty painful to strictly prove it).

500: There are 2 cases: either there is an element which was not both at the left end and at the right end (this case is trivial), or was there is not. If it was not, each element either came to some end and stayed there, or came to some end, then to the other, and stayed there. You can sort items by their final position, and then iterate through possible left-right splits, and then determine who has to also go to the other end for the split.

1000: DFS on states (tree edge, number of tokens in subtrees separated by that edge)

1000: Suppose we want to move the red tile from node a to node b. Let's freeze its movement in the middle of the edge (a, b). Note that at this moment both a and b are empty. Also, we know that there are k black tiles in the subtree of the node b and total - k in the subtree of a. Here the subtree of the node a is the connected component of a after removing the edge (a, b). Let's call three numbers (a, b, k) the state.

There are O(N²) states in total, because we have O(N) edges and O(N) possible values of K. Now we need to define transitions between these states. Before we start our movement from a to b we need to rearrange black tiles in the subtree of b in some way. Let's iterate over the node c that will be our next destination (after we reach b). We can iterate over all possible values of k', which is the number of black tiles in the subtree of c with respect to the edge (b, c). Note, that we can easily find the bounds of k'. In this way we can find all the states (b, c, k') that are reachable from (a, b, k).

Now we just need to do a bfs/dfs in this new graph, where the vertices correspond to our states. The complexity is O(N³).

100, {1, 2, 98}, {99, 2, 98}

Иногда надо сходить в левый конец, а потом в правый.

Потому что иногда выгодно пойти и направо, и налево. Например, L=10, a={1,2,3,8}, b={1,9,3,8}. Второй волк сначала идёт налево, а потом перебегает направо.

Иногда кому-то выгодно ходить и туда, и туда. Последний семпл вроде на это.

Ровно это же писал. Тоже не проходит последний семпл?

Бывает, что какому-то волку надо выйти слева, а потом ещё и выйти справа.

А вот что не так с этим решением, если добавить ещё следующее:

1. Перебираем x и y от 0 до n.
   
2. Перегоняем левые x налево, остальных — направо.
   
3. Дальше, перегоняем тех, кто справа, но должен оказаться среди левых y волков, налево. Аналогично наоборот.
   
4. Дальше ставим всех волков на их места.
   

Это уже спрашивают выше.

Более того, пятница вчера была и у всех остальных красных.

И ходят даже слухи, что не только у красных.

Нет, просто сегодня была суббота.

Может быть, дело все-таки в пятнице, а не в задаче? :)

Просто у меня было такое ощущение, что я когда-то что-то подобное решал и что там сдавалась жадность, а маленькие ограничения здесь — это для сбивания с толку.

Хотя парадоксальности в задаче как-раз нет. Вероятно, многие из красно-желтых купились на низкие ограничения и начали писать экспоненциальное решение. Зря я, короче говоря, написал этот коммент.

Учитывая то, что ограничения маленькие, и обычно 250 какой-нибудь простенький перебор или дп, мышление сильно направлено не в правильную сторону.

Отличная задача. На то, чтобы подумать в правильную сторону, а не просто взять и написать.

Лично я попробовал несколько паттернов, похожих на правильный, но не являющихся им — отчаялся и написал random + hill climbing.