Это не баг

Нет, придется ждать окончания. Вопросы по этому поводу, как понимаете, не ко мне :)

1. Не знаю
2. См. пост

Ну вот зеркало на всякий: http://acm.ssau.ru/statements/000006.html

В H легко показать, что нам достаточно знать размер самой большой кучки. Будем обозначать позицию через размер этой кучки. Тогда если позиция вида 2^k-1 (т.е. размер максимальной кучки 1, 3, 7...) — она проигрышная. Иначе мы своим ходом всегда можем поделить так, чтобы размер максимальной кучки стал проигрышным — и поэтому позиция выигрышная.

F. Допустим, у одной вершины в данный момент нет одного поддерева. Но мы знаем, какие значения могут придти в это поддерево, к тому же это интервал значений. Отсюда выходит решение: храним все пары интервалы+глубина в сете, и когда приходит новая вершина, то соответствующий интервал из сета удаляем, а вставляем два новых, которые на уровень глубже, а к ответу прибавляем глубину.

Вот тут, например

Ну так призраки есть. Галку "показывать неофиц" ткните.

Решим обратную задачу: найти количество способов получить число N из 1, переходы осуществляются тогда не делением, а наоборот — умножением на какое-либо число.

Для этого найдем все делители числа N, это можно сделать за sqrt(N). Теперь посчитаем легкую динамику: dp[i] — количество способов добраться до числа i от 1. Для каждого делителя "влоб" будем перебирать все делители же, в которые мы можем из него можем перейти и обновлять для них ответ.

Так как делителей N порядка N ^ (1 / 3), то наша программа будет иметь время работы примерно O(sqrt(N) + N ^ (2 / 3)) = O(N ^ (2 / 3)), что прекрасно влазит по времени, также как и массив размера N по памяти.

(p*p+q*q)/(p+q)

Treap?

Достаточно одной priority queue. Нетрудно понять, что в каждый момент времени выгодно выбирать самый дорогой экзамен. Отсюда решение: итерируемся по моментам времени, в каждый момент времени заносим в priority queue все экзамены, которые становятся доступны сейчас, а потом достаем самый дорогой. Так делаем, пока не обработаны все экзамены, или пока priority queue не пуста. Очень простое решение за N*log(N).

Представим, что мы не сдавали экзамены, пока последний по хронологии экзамен не станет доступен. В этом случае у первого экзамена будет стоимость cost[1] + (day[n] — day[1]), у второго — cost[2] + (day[n] — day[2]) и т.д. Очевидно, что тогда оптимально будет сдавать экзамен с максимумом такой величины.

Но в каждой величине присутствует day[n], если мы его вычтем из каждого значения, порядок не поменяется. Значит мы нашли критерий сравнения двух экзаменов: cost[i] — day[i]. Чем выше этот показатель, тем раньше экзамен надо сдавать.

Теперь все вообще просто: считываем все экзамены, сортируем их также по дню начала, но при равенстве дней раньше ставим экзамен с большей стоимостью. Также будем хранить первый день, в который возможна сдача экзаменов.

Все, для решения все готово. Экзамены будем для простоты хранить в куче (heap, priority_queue). На каждом экзамене пытаемся сдать экзамены, уже находящиеся в куче, если возможный день их сдачи раньше дня открытия текущего экзамена. После этого пихаем в кучу текущий экзамен и переходим на следующую итерацию. В конце надо не забыть достать из кучи оставшиеся в ней экзамены.

Асимптотика решения, как видно, O(n * log(n) + n * log(n)) = O(n * log(n))

Да

Ну если лень с ними возиться и хочется побыстрее получить Accepted, можно было сделать бинпоиск (так как разница площадей сначала одного знака, а потом другого), или вообще тернарник :D

А так, конечно, два указателя решают.

Я сделал тернарнк. Получилось весьма быстро.

Да-да, я также J на пустом месте усложнил http://codeforces.net/blog/entry/5409#comment-106890

Make sure that you don't miss the word "each" in the statement

На тренировках это формально не запрещено... Так что это вопрос, насколько сильно будет мучать совесть по этому поводу.

Кстати, во время контеста в онлайне был только один аккаунт из этой команды, другое дело, со скольки компов под ним одновременно сидели. Возможно, что они на самом деле играли с одного компьютера, две задачи подряд — такое все-таки бывает, а убирать из таблицы за такое — жалко. Тем более что когда-нибудь в этот контест придет vepifanov и наведет в нем порядок :D

Probabilities of choosing the coins before and after the first throw are not equal.

It's an application of Bayes' theorem.

P(B | A) = P(A |^| B) / P(A) = (1/2 * p * p + 1/2 * q * q)/(1/2 * p + 1/2 * q)

P(B) = probability to get heads on the second throw, P(A) — probability to get heads on the first throw. P(A |^| B) — probability to get heads on both throws.

So P(B | A) is the probability to get heads on the second throw if we are given that we got heads on the first one.

а у вас общаги дают?

Я слышал, что у вас отчисляют :D

Хорошо, мишки, не буду портить вам рекламу. Сегодня на вашей улице праздник. СГАУ — замечательный вуз. И очень радует, что вы многие свои локальные соревнования выкладываете в тренировки. Другие вузы, следуйте примеру :) Хотя то, что написано в предыдущей правке, не перестает быть правдой.

Последняя прошедшая команда решила 9 задач. Кстати, это вроде бы легко выясняется...

Simulation using a linked list.

Go all vector saving the last occurrence of the value v [i] was in position i, and then for each current position look at it already existed an equal element earlier, if so, create an edge of the current position for this last occurrence. Just make a bfs or dp to find the shortest path.

Yes