There are many ways of solving this easiest problem of the contest. I list them in the order of increasing realization difficulty:

1. If you use C++. Take permutation (1, 2, ..., 9). Suppose elements 1-4 are numbers we're looking for. Use next_permutation() to generate all possible combinations of numbers and just check that all conditions are met.

2. Pure brute-force — just 4 nested for() cycles for each unknown number. Here one should not forget to check that all numbers are pairwise different. This takes additional 6 comparisons.

3. One may note that, given the first number in the left upper cell, one may restore rest of the numbers in O(1). So, just check 9 numbers in the first cell (let it be x), restore other numbers from the given conditions:

(x, a)

(b, c)

a = r1-x, b = c1-x, c = r2-b = r2-c1+x

and check that they all lie in [0..9] and rest of the conditions are met.

4. O(1) solution — one may derive it from the previous approach: since x+c = d1 => 2*x + r1 — c1 = d1 => x = (d1+c1-r1)/2

So, you find x, check that it is in [0..9], restore all other numbers as in the previous approach and check that all conditions are met.

This was purely technical problem. String type is the best way to store the number. The main steps to get this problem is just to follow problem statement on how a number in the financial format is stored:

1. Divide the number in the input into integer and fractional parts looking for position of the decimal point in the input number (if input number doesn't have decimal point — assume fractional part is empty string)

2. Insert commas into integer part. This is done with one for() / while() cycle

3. Truncate/add zeroes to length 2 in the fractional part

4. Form the answer [integer part].[fractional part]. If initial number had minus in the beginning — add brackets to both sides of the answer.

Due to quite low constraint this problem is easily solvable by brute-force. Without loss of generality assume that A <= B <= C. Then it is clear that A cannot exceed , and, given A, B cannot exceed . Then all solution is just two cycles:

for (long long a = 1; a*a*a <= n; ++a) if (n%a == 0){

for (long long b = a; b*b <= n/a; ++b) if ((n/a)%b == 0){

long long c = n/a/b;

...

}

}

Since we assumed A <= B <= C, now it is not clear which parameter (A, B or C) is the height of haystack, so inside the cycle one should consider all three possibilities. For any N <= 10^9 the code inside the second loop runs no more than 25000 times, so this solution fits timelimit even for N <= 10^11 and maybe larger. Why it's so quick? It's because of the fact that number of divisors of arbitrary number N does not exceed about . That's why all similar solutions and maybe some other streetmagic that has anything common with divisors of N, should get AC.

This problem was not on derivation of the general formula m*n — (m*n)/2 (only this would be too simple for the second/fourth problem, isn't it?) but rather on accurate investigation of several cases. Unfortunately, many participants were very eager to submit the formula above, that's why there were so many hacks. I would say: this is not jury fault — pretests were made very weak intentionally, partially — to give you some space for hacks; but jury didn't presume there would be so many hacks. This is your fault of submitting unproven solutions. This is large risk given Codeforces rules, and this time risk-lovers were not lucky =)

Ok, let's come to the solution. Without loss of generality let's assume m <= n. Then we have the following cases:

1. m = 1 x n fields. It is obvious that here the answer is n.

2. m = 2 x n >= 2 fields. Here the correct formula is 2*[2*(n/4) + min(n%4, 2)]. Why so? To see this draw the board for arbitrary n and draw all possible knight moves on it. In general, you'll see four not overlapping chains. Since you cannot place soldiers in the neighboring cells of any chain, then for a chain of length L the answer doesn't exceed (L — L/2). On the other hand, it is clear that the answer (L — L/2) is always possible since soldiers on different chains never hurt each other. If you consider fields with different remainders n%4, the formula above becomes clear.

3. m >= 3 x n >= 3 fields, except the cases 3 x 3, 3 x 5, 3 x 6 and 4 x 4. Here one may use general formula m*n — (m*n)/2. Why so? It is known (or becomes known with google) that for all such fields knight tours exists. Any knight tour is just a chain of lenght m*n, so by the logic above one cannot place more than m*n — (m*n)/2 soldiers on it. On the other hand, if one makes chessboard coloring of the field, it is clear that the answer above is always achievable if one chooses cells of one color as places for soldiers. So, formula above is proved.

4. Cases 3 x 3, 3 x 5, 3 x 6 and 4 x 4. Here we can't use the logic above to prove that the above formula is also right here. The easiest way is to verify it using brute-force or pen and paper. This concludes the solution.

This is technical problem, one may use several approaches to solve it. Additional complexity is to restore the answer after you got it.

1. Dynamic programming "on the broken profile" — I'll not explain the approach here in detail, you can find explanation of it on the Internet or even on Codeforces. Worth to point out, care should be taken of your code memory usage.

2. Search with memorization — one jury solution uses logic like DP with usual (not broken) profile: move by rows (or by columns), try all possible T placements such that upper cell of T's is in the given row and run the same search procedure for the next raw, passing the state of the two last filled rows of the board to it. For the given board state save the answer recursive function returned (max number of T's one may place on the not-yet-filled part of the board) and use it in the future as the answer for the given state. This requires only O(n*2^(2^m)) of memory and works about 2 sec. on maxtest 9 x 9.

3. Branch and bound. Another jury solution recursively tries all possible tilings of the board with T's. If on some step it occured that number of T's on the board plus number of T's one can theoretically place on the remaining part of the board doesn't exceed existing best answer — trim this node. Such solution is the easiest to code and it works only 0.5 sec. on maxtest, however it is not obvious from the very beginning.

4. Precalc — not to write a lot of code (applying DP or search with memorization) and not to deal with possible time/memory limits, some participants did the right thing: using the third approach, just precalculated answers for large (or for all possible) inputs.

Solving this problem involves two basic steps: firstly, to recognize that we have nothing else than generalised version of Nim and secondly, to solve it.

The first part is not difficult: assuming we don't have rows with soldiers of only one color (in which case the game usually becomes trivial, since one or both players may play infinitely long), let the number of cells between two soldiers in every non-empty line be the size of the corresponding piles in nim. Then attack according to the rules of the given game is the move in the corresponding nim that allows you to take as much as you like stones from at most k piles (but at least 1 stone should be taken). Such generalized nim is called Moore's nim-k, and we should solve it to find the winner in the initial game. As any source you may google (except Russian Wikipedia) shows, solution to the Moore's nim-k is the following:

Let's write binary expansions of pile sizes, and for any position check that sum of digits on the given position in all expansions is divisible by k+1. If this holds for all positions — then the winner is the second player, otherwise — the first player. Proof of the fact may be found here: http://www.stat.berkeley.edu/~peres/yuvalweb/gath9.pdf

Let's consider the following case for k = 2:

R-G--

R--G-

R---G

R---G

Corresponding 4-piles nim-2 for this test is (1, 2, 3, 3). After writing binary expansions of piles sizes we get

01

10

11

11

Sums of digits in both positions (3) are divisible by k+1=3, so here Second wins.

But this is still not full solution to the initial game, because we forget about retreat possibility. But it is simple here: only player losing the game in which only attacks allowed may want to retreat (winner just plays corresponding nim by attacking). But if loser retreats, winner just restores initial position attacking in the corresponding rows. And since loser cannot retreat infinitely, he cannot improve his win chances with retreat moves. That's it.

And finally, don't forget about tests like:

2 2 2

GG

RR

Answer: Second

All such tricky cases were in pretests.

This problem was "just" about finding the shortest path on a cone. Unfortunately, even though jury lowered precision requirements to 10^-6 and included all possible general cases in pretests, nobody tried it =(

For solution, let's consider all possible cases of two points on the cone surface (including its basement):

1. Both points on the basement. Here it is clear that Euclidean distance between points is the answer to our problem.

2. Both points on the lateral surface. One may think that optimal path is also always lies on the lateral surface. In this case it is easy to find length of an optimal path from geometric considerations (by considering loft of the lateral surface). But 10-th pretest disproves that it is always optimal:

100 100

99 0 1

-99 0 1

Answer: 202.828427124746210

So, optimal path may go through the basement. In this case it has two points that lie at the same time on the basement and on the lateral surface (let's call them A' and B'), so length of the path through this points is easy to find by adding length of the three different segments — AA', A'B' and B'B. So the problem is reduced to finding optimal positions of A' and B'? Let's assume that polar angle of the first point in XOY plane is a1 (0 <= a1 < 2*PI) and polar angle of the second point is a2 (0 <= a2 < 2*PI). Length of the shortest path between A and B passing through the points A' and B' (AA' + A'B' + B'B) is some function of two arguments that we want to minimize — f (a1, a2). One may minimize it using, for example, grid or any other suitable numerical approach.

3. One point on the basement and another point on the lateral surface. This case is similar to the previous one — optimal path passes some point C' on the "brink" whose optimal polar angle we are to find. In this case we optimize function of one argument g(polar angle(C')) = AC' + C'B.

На протяжении раунда вы снова будете помогать жителям Тридевятого царства в решении повседневных задач.

Хочу поблагодарить Артема Рахова за неоценимую помощь в подготовке раунда, Марию Белову за перевод задач, Михаила Мирзаянова за отличную систему CF и всех участников за то, что не оставляют это событие без внимания.

Больше полных решений и высокого рейтинга всем! gl & hf

1. tourist

2. PavelKunyavskiy

3. Egor

4. Fefer_Ivan

5. fhlasek

6. Coder

7. RAVEman

8. neal

9. WXYZ

10. whhone

1. vyvtjp643

2. songlj

3. t.gogniashvili

Задача такая. Дано порядка 10000 точек в N-мерном (N небольшое - не более 10) единичном кубике, для каждой нужно найти K (K < 100) ближайших. Строгих ограничений, понятно, нет, но хотелось бы, чтобы на обычном компьютере это укладывалось в несколько секунд.

Буду рад любым идеям как это можно решать хотя бы приближенно. Заранее спасибо за советы.

Как решал я. Для каждого слова посчитал хэш, запихал все в сет. Потом для каждого префикса каждого слова считал его хэш, и хэш оставшейся части (амортизационно - за О(1) ), и проверял, есть ли хэши обеих частей в сете. Почему-то упорно получал ВА(5). Кто сдавал так же - в чем может быть проблема, и заходило ли такое решение?

Не писал, но вроде бы все что надо - аккуратно построить граф с вершинами-участками и ребрами-стримостями сноса стен между ними, и затем в нем найти минимальное остовное дерево. Вопрос - что делать с внешней территорией. Можно рассмотреть 2 случая: когда она не входит в оптимальное решение (просто строим остовное дерево в исходном графе) и когда входит (по сути, получаем еще одну вершину в исходном графе).

Буду благодарен за разбор

UPD: разбор от Jokser'а см. ниже в комментариях

Противная задача с нечеткими ограничениями, но все, что нужно - как-то написать то, что описано в условии. Для быстрой проверки того, выбрал ли пользователь i приложение j я завел битовую матрицу 10000 x 10000, проверку для каждого пользователя делал фактически в лоб (даже без всяких бинпоисков), логично предполагая, что хитрых тестов с такими раздолбайскими ограничениями не будет. Задача зашла мгновенно.

Почему-то относительно мало участников сдавали, хотя задача, имхо, проще той же D. Выполняем бинпоиск по ответу, для каждой длины в лоб за O(N²) проверяем, подходит ли эта длина. При заданных ограничениях без всяких оптимизаций просто летает.

UPD: как указал jte ниже, задачу можно решать даже целочисленно (если умножить все длины на 2 и потом не забыть разделить ответ на 2), что еще более ускоряет поиск ответа.

Посидев несколько минут с карандашиком, можно было вывести нехитрую формулу при A <= B;

Всем привет!

Привожу разбор задач для раунда #78.

Еще раз приношу свои извинения за ситуацию с задачей B (div. 1) / D (div. 2). Также, приношу свои извинения за недооценку сложности задач. По крайней мере, надеюсь, что задачи показались участникам интересными.

В этой задаче необходимо округлить число по обычным математическим правилам, за исключением случая, когда последняя цифра целой части числа равна 9: в этом случае необходимо было вывести "GOTO Vasilisa.". Можно заметить, что для проверки того, что дробная часть числа не меньше 0.5, достаточно рассмотреть только первую цифру сразу после десятичной точки. Если эта цифра равна 5 или больше - мы добавляем 1 к последней цифре целой части числа, и задача решения. Возможно, самым удобным способом обработки входных данных (которые, как было указано в условии, могли быть очень длинными), было использование строковых переменных.

В задаче нужно было аккуратно проверить что требовалось по условию. Прежде всего, проверим, что все объемы компота во входных данных равны - в этом случае выведем "Exemplary pages.". В противном случае найдем два кубка с наибольшим и наименьшим объемами. Предположим, что их номера a и b, и объемы компота в них соответственно v[a] и v[b]. Теперь предположим, что до предполагаемого переливания их объемы были равны V. Тогда они содержали 2V миллилитров компота до (и после) переливания. Поэтому, необходимо проверить, что (v[a] + v[b]) делится на 2. Если это не так - выводим "Unrecoverable confihuration.". В противном случае присвоим кубкам предполагаемый объем компота до переливания: v[a] = v[b] = (v[a] + v[b])/2. Теперь, если только одно переливание было совершено, объемы компота во всех кубках должны стать равны, и мы выводим соответствующее сообщение "... ml. from ... to ...". Если объемы не равны, выводим "Unrecoverable configuration".

В этой задаче необходимо найти количество различных раскрасок граней куба шестью заданными цветами. Вероятно, самое простое решение данной задачи - как то упорядочить грани (скажем, 0 - передняя, 1 - задняя, 2 - верхняя, 3 - нижняя, 4 - левая, 5 - правая), затем рассмотреть 720 = 6! размещений цветов по граням. Каждое размещение есть некоторая перестановка заданных на входе символов. Для каждого размещения мы находим все 24 возможных вращения куба с заданной раскраской - получаем 24 строки символов Лексикографически минимальная строка будет представителем этой раскраски. Ответ к задаче - количество различных представителей.

В этой задаче предполагалось численное решение. Но сначала нужно рассмотреть несколько случаев. Ниже без потери общности мы считаем a <= b.

1. l <= a <= b. В этом случае ответ ограничен длиной гроба, поэтому ответ есть l, и понятно, что гроб размерами l x l может быть пронесен через коридор (a, b) - будем обозначать размеры коридора таким образом.

2. a < l <= b. В этом случае ответ есть a, и понятно, что никакое большее число не может быть ответом. В самом деле, в противном случае гроб размерами (w > a) x (l > a) невозможно пронести через коридор (a, b).

3. a <= b < l. Этот случай наиболее общий, здесь мы должны повернуть гроб в месте изгиба коридора. Для максимизации ширины гроба, мы хотим перемещать его таким образом, что один угол гроба касается одной из внешних стен коридора (предположим, самая нижняя стена на рисунке к задаче), а другой угол, прилегающий к той же длинной стороне гроба, касается другой внешней стены коридора (самая левая стена на рисунке к задаче). Введем систему координат таким образом, что нижняя стена будет осью OX, а левая стена - осью OY. Предположим, что в процессе "вращения" один угол гроба находится в точке (x,0) (0 <= x <= l), тогда другой угол гроба должен быть в точке (0,sqrt(l*l-x*x)). И ответ, который мы ищем, есть min {расстояние от отрезка (x,0) - (0,sqrt(l*l-x*x)) до точки (a,b) }, где min{} берется по всем 0 <= x <= l. Обозначим расстояние в точке x за f(x). Поскольку f(x*) минимальна в некоторой точке x* и возрастает слева и справа от x*, можно использовать тернарный поиск для нахождения ее минимума.

В этой задаче возможно также и точное решение: задача сводится к минимизации косого произведения векторов (a-x,b) and (-x,sqrt(l*l-x*x)) по x. Однако эта задача сводится к нахождению корней многочлена четвертой степени, что, вероятно, не есть самое удачное решение в условиях 2-х часового контеста.

Эта задача по мотивам известной головоломки "Ханойские башни", в которой диаметры некоторых дисков могут быть равны. Как же ее решить? Хорошая (и в то же время несложная) вещь, которую можно сделать - написать решение BFS-ом для проверки оптимальности ваших идей для небольших входных данных (кстати, BSF работает достаточно быстро практически для всех башен, имеющих до 10 дисков) и затем попытаться придумать оптимальный алгоритм решения головоломки.

Пусть C (x1, x2, ..., xn) будет решением задачи (под "решением" здесь мы подразумеваем оптимальное количество ходов - сами ходы могут быть легко получены с использованием рекурсивной процедуры; также "решение" есть количество ходов переместить группу дисков с одного стержня на любой другой стержень (а не какой-либо конкретный) ) головоломки, когда мы имеем x1 одинаковых самых больших дисков, x2 одинаковых дисков, вторых по величине, и так далее. И пусть U (x1, x2, ..., xn) будет решением головоломки когда разрешено не сохранять порядок дисков (необходимо соблюдать условие первоначальной головоломки не класть большие диски на меньшие, но в конце диски равного диаметра могут лежать как угодно).

Тогда одно из оптимальных решений задачи следующее:

C (x1, x2, ..., xn) = U (x1, x2, ..., xn) если x1 = 1 (*)

C (x1, x2, ..., xn) = 2*x1 - 1 если n = 1 (**)

C (x1, x2, ..., xn) = U (x2, ..., xn) + x1 + U (x2, ..., xn) + x1 + C (x2, ..., xn). (***)

U (x1, x2, ..., xn) = U (x2, ..., xn) + x1 + U (x2, ..., xn) (****)

Почему так? Можно заметить, что U() - "почти" решение нашей задачи: оно "переворачивает" группу самых нижних одинаковых дисков, порядок остальных дисков остается тем же! (попробуйте понять почему)

Поэтому верно (*).

(**) довольно очевидно.

(***) означает следующее: переместить (x2, ..., xn) со стержня 1 на стержень 2 без сохранения порядка. Затем переместить x1 одинаковых дисков со стержня 1 на стержень 3, затем переместить (x2, ..., xn) со стержня 2 на стержень 1 без сохранения порядка (но оказывается, что после того, как мы применим U() к той же самой группе дисков дважды, порядок сохраняется!), затем переместить x1 равных дисков со стержня 3 на стержень 2, и затем использовать C() для перемещения (x2, ..., xn) со стержня 1 на стержень 2 (здесь мы используем C() для сохранения первоначального порядка дисков). Так что (***) тоже верно.

А (****) довольно очевидное выражение для U(): переместим все диски кроме группы самых больших дисков тем же алгоритмом, затем переместим самые большие диски (вот почему если x1 > 1, порядок дисков в самой большой группе "переворачивается"), и затем переместим все остальные диски к группе x1 тем же самым алгоритмом.

Эта задача была на оптимальную игру в эту "простую-на-первый-взгляд" игру. Ключевая вещь, которую нужно было понять - это то, что называть только карты, которых у вас нет на руках, не всегда оптимально. Иногда оптимально попытаться обмануть соперника, назвав карту, которая имеется у вас на рука. В этом случае... да, он может подумать, что карта, которую вы назвали - это карта на столе, и проиграть своим следующим ходом. Теперь задача - понять, когда выгодно использовать стратегию уменьшения количества карт соперника, когда - блефовать как описано выше и когда пытаться угадать карту на столе. Но вместо "когда" верный вопрос - "как часто", поскольку перед нами не что иное, как обычная матричная игра с постоянной суммой, и оптимальной стратегией является смесь этих трех стратегий (то есть, на каждом ходу - выбор одной из трех с некоторыми вероятностями). Но сначала сконструируем матрицу. Игрок 1 имеет три чистые стратегии: "игра" (когда он играет в игру и на самом деле пытается определить карты соперника и карту на стоде), "угадывание" (когда он пытается угадать карту на столе) и "блеф" (когда он пытается обмануть соперника, чтобы тот проиграл, назвав в качестве карты на столе карту, которая на самом деле в руке первого игрока). В свою очередь, если первый игрок использовал стратегию "блефа", или в результате использования стратегии "игра" случайно назвал карту на столе, его соперник имеет две альтернативы: "проверка" (то есть, поверить первому игроку, что он не назвал карту в своей руке и попытаться угадать карту на столе, назвав эту карту) и "далее" (то есть, решить, что это была стратегия "блеф" и игра просто должна быть продолжена, но с исключением карты, названной первым игроком, из списка возможных карт на столе). Обозначим P(m,n) вероятность выиграть игру, когда первый игрок имеет на руках m карт, а второй игрок - n карт. Тогда P(m,n) есть цена матричной игры со следующей матрицей (строки - стратегии первого игрока, столбцы - стратегии второго игрока):

                                  "проверка"                                    "далее"

"игра"              n/(n+1)*(1-P(n-1,m))        1/(n+1) + n/(n+1)*(1-P(n-1,m))

"угадывание"            1/(n+1)                                     1/(n+1)

"блеф"                            1                                       1-P(n,m-1)

Как получить числа в матрице? Рассмотрим первую строку: стратегия "игра" первого игрока, "проверка" второго игрока. Первый игрок просто называет наугад одну из n+1 карт. С вероятностью 1/(n+1) от называет карту на столе, второй проверяет ее и выигрывает (так что вероятность выиграть для первого игрока 0), с вероятностью n/(n+1) первый игрок называет одну из карт на руках второго игрока, и игра продолжается, второй игрок выигрывает с вероятностью P(n-1,m) в этом случае. Тогда общая вероятность выигрыша первого игрока с таким сочетанием чистых стратегий есть n/(n+1)*(1-P(n-1,m)). Так же точно заполняются остальные элементы матрицы. Затем мы решаем игру (это можно сделать либо напрямую, или одной формулой, если заметить, что стратегия "угадывание" неоптимальна в случае когда m>=1 и n>=1 и в матрице нет седловых точек) и получаем ответ для исходной задачи - P(m,n).

И последнее, что нужно заметить: когда m==0 понятно, что своим ходом второй игрок выигрывает, поэтому первый должен "угадывать", и P(0,n) = 1/(n+1). Когда n==0 P(m,0)==1 - первый просто совершает одно верное угадывание.

Всем привет!

Автором сегодняшнего раунда являюсь я, Сергей Ведерников.

По ходу раунда Вам придется помогать жителям Тридевятого царства решать каждодневные проблемы, а иногда - просто бороться за свое существование!

Раунд будет "красным" =), поэтому задачи не должны показаться сложными, и вы получите удовольствие от их решения.

Владеющим русским языком я рекомендую читать условия задач на русском языке. И дело здесь совсем не в переводе - просто английский язык плохо передает русский фольклорный стиль.

Напоследок хотелось бы выразить благодарность Артему Рахову за неоценимую помощь в подготовке раунда, Марии Беловой за качественный перевод задач, Михаилу Мирзаянову за прекрасную систему КФ и всем участникам - за то, что не оставили данное мероприятие без внимания.

Всем больше полных решений и высокого рейтинга! gl & hf

Div. 1: 1000-1500-1500-1000-???

Div. 2: 500-500-1500-2000-2000

That's why I don't very like this contest. But, once again, problems were interesting, thanks to the author!

Now short editorial.

Problem A - Cableway (div. 2)

The only thing in this problem is to write expression for time of the arrival for final group of students of each color. This could be done with the following code:

Problem B - African crossword (div. 2)

Due to the small restrictions, the problem could be solved with the straightforward O(n*m*(n+m)) algo of finding for each symbol whether there is other such symbol in the corresponding row or column. More fast approach is to count for each symbol how many times it appears in any row/column, and do corresponding checks in O(1) instead.

Problem A (div. 1) / C (div. 2) - Robbery

Good problem, and I don't agree with scoring of 500 for div. 1, I think the optimal score for this problem is 1000. The idea is the following: if n is even, then the answer is 0. If n is odd, then the answer is min (mn, (m/(n/2+1))*k), where mn is the minimum number of diamonds in some odd cell i. Now let's explain this formula.

If n is even, then all cells may be divided into pairs, and sum in each pair should remain constant => sum in all cells should remain constant => Joe cannot steal anything!

If n is odd, suppose Joe managed to steal D diamonds before some check. Let's prove that he should rearrange diamonds in cells so that any odd cell now contains D diamonds less, and any even cell - D diamonds more. Why so? Consider any odd cell. Again, remaining cells could be divided into neighboring pairs (n/2 of them) such that sum in every pair should remain constant => if Joe has stolen D diamonds, cell that we consider (any odd cell) should contain D diamonds less after robbery! But this entails (since pairsums should remain constant) that even cells should contain D diamonds more now. So, thus we proved first part of the formula under min() - Joe cannot steal more diamond than there is at any odd cell. But this is not the only restriction. In each of the k turns he may perform not more than m operations. How to economize operations to steal more diamonds? Well, the minimum number of operations to steal 1 diamond is n/2+1 (try to think why), so in every turn Joe may steal not more than m/(n/2+1) diamonds, and since there are only k turns, we get second part of the formula under min() function at the beginning.

Problem B (div. 1) / D (div. 2) - Widget Library

Pretty straightforward realization. Things to remember are:

 - sizes of widgets can be as large as 100*2^30+

 - when evaluate sizes of widgets recursively, memorize answers that are already evaluated. Otherwise you will need up to 2^30+ operations to get answers

"Bad" tests are of the following type:

76

Widget a(100,100)

HBox b

b.pack(a)

b.pack(a)

HBox c

c.pack(b)

c.pack(b)

...

HBox z

z.pack(y)

z.pack(y)

Problem C (div. 1) / E (div. 2) - Chip Play

From test 1 it becomes clear that the game process is dependent on history, so any DP schemes will not work. So, we perform straightforward simulation: take every chip and go. But the following test shows that straightforward simulation can take O(n^3) time to finish:

1 5000

R(2500 times)L(2500 times)

Answer: 5000 2

To speed the process up, one can use linked lists to get next cell with chip in O(1). The more tricky and easy-to-write approach is in my solution. It fits in timelimit, unfortunately, I can't prove complexity easily: http://pastebin.com/3KB7s0Le

Problem D - Space mines (div. 1)

I can't understand why it's D. It's pretty straightforward, it's easy to write. The only thing to understand is that it cannot be the case when Death Star intersects some spike and doesn't intersect its endpoint. Why? Remember: radius the the Star is not less than radius of any mine, and length of each spike is at most 3/2 of radius of mine. Then show by yourself that the situation described above is improssible.

That's all! Now just find all times where Death Star touches mine surface or touches spike end and take minimum of those. Pretty easy (one quadratic equation), I think - on the level of problem A: http://pastebin.com/YCSAbju1

Problem E - Fire and Ice (div. 1)

Who can explain this to me?

На прошедшем туре Яндекс.Алгоритма случился вот такой инцидент: следующий код к задаче D взломался совершенно глупым простым тестом (50000 рэндомных add и потом 50000 sum подряд) - улетел по ВА. Однако потом в дорешивании этот же код получил ОК, попытки повторить ошибку не удались.

UPD: Чтобы не было придирок. Самое первое решение было неверно. Однако потом оно было исправлено, но все равно получило ВА, источник которого мне не ясен. Предложенный ниже код - это третья посылка по задаче, на мой взгляд - верная, но не прошедшая взлом.

Как по-вашему, код верный, и это какой-то глюк Codeforces, или вы сможете предложить тест, на котором он не работает (или хотя бы объяснить, почему он может работать неверно)?

Спасибо за помощь!

Собственно, вот сам код: http://pastebin.com/70w636Qb

Кто писал, или просто смотрел задачи - у меня 2 вопроса:

(Кто хочет посмотреть - вот ссылки:

Первая - http://www.topcoder.com/stat?c=problem_statement&pm=11418&rd=14530

Вторая - http://www.topcoder.com/stat?c=problem_statement&pm=11424&rd=14530

Третья - http://www.topcoder.com/stat?c=problem_statement&pm=11372&rd=14530)

1. Какой самый плохой тест для второй? У меня 10000 шагов пересчета возможных позиций на всем поле улетели. Какой тест дает больше? (UPD: упал на тесте ".CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.CKC.", 50, 49 дает в ответе 29401, обидно)

2. Как просто решить третью? Я придумал алгоритм, но не очень простой. А там ее даже синие сдавали. Либо я недооцениваю синих, либо может быть есть относительно простое решение задачи?

Спасибо!

Сразу хочется сказать - пост нацелен на то, чтобы показать людям, которые ругаются, что контест - маздай, автор контеста - бяка, и как вообще можно давать задачи с непонятной оценкой сложности (типа второй), что они не правы, и после непродолжительных размышлений оказывается, что сложность алгоритма - O(n^2*log(максимальное число)), пусть и с бОльшей константой, нежели при простом бинарном поиске. Этим как раз и хороша задача - она проверяет, действительно ли кодер умеет оценивать сложность, или только знает набор стандартных шаблонов.

Пусть C - это разрыв между максимальным и минимальным числами в нашем наборе, числа могут быть любыми. После не более чем n-1 шагов работы жадного алгоритма (взять минимальное число и проделать, что написано в задаче) мы получаем новое значение разрыва C^ < C*(1-1/n). Почему так? Очевидно, что минимальное число придется увеличить на величину не меньше, чем C/n (в худшем случае - когда еще n-2 числа мимимальны, а последнее - на C больше). Остальные числа, если они оказываются меньше нового минимального - увеличиваются как минимум до его же уровня (а на самом деле - больше, поскольку среднее в это время тоже растет, мы же, из консервативности, зафиксировали его на уровне минимального числа + C/n).

Вот и получается, что за не более чем за n-1 шаг жадного алгоритма разрыв (C) сокращается как минимум до C*(1-1/n). А это все, товарищи! Это означает, что количество шагов жадного алгоритма будет порядка O(n*log(С, логарифм по основанию 1+1/(n-1))), а поскольку каждый шаг - это O(n), то общая сложность - O(n^2*log(максимальное число)), as was stated in the beginning of this outline! Правда, работать это будет чуть дольше, чем бинарный поиск - поскольку логарифм по основанию 1+1/n, то есть в худшем случае порядка 1.02, но константа 1/ln(1.02) ~ 1/0.2 ~ 50 совсем некритична.

P.S. То есть, на самом-то деле, при n --> INF любители математики могут получить, что сложность есть O(n^3*log(max)), предполагая обычный двоичный логарифм и обычную константу, но даже в этом случае при заданных ограничениях задача все равно летает.

Старался объяснить настолько понятно, насколько мог. Если нужно что пояснить - пишите.