IOI 2013 day2

Всем Салам!
Сейчас идет второй день IOI.
Подробнее про первый день и про олимпиаду можете узнать тут . Про участников с Казахстана тут

Тут будет блог-трансляция

• А пока прошло 2 часа и результаты:

Жанадиль - 126 (46-0-80) баллов
Мейрам - 63 (12-14-37) баллов
Аман - 46 (46-0-0) баллов
Нурлан - 28 (0-28-0) баллов

Жанадиль походу написал неявное двумерное дерево отрезков,  наверное, все-таки написал дерево отрезков декартовых деревьев! А двумерное вроде берет 100 или нет... А Мейрам 10 деревьев отрезков... Неожиданно наши решают самую сложную задачу.
А 46 по первой и 28 по второй берут решения "в лоб"

• 132 минута Нурлан берет 100 по первой!

Нурлан - 128 (100-28-0) баллов
Жанадиль - 126 (46-0-80) баллов
Мейрам - 63 (12-14-37) баллов
Аман - 46 (46-0-0) баллов

Нурлан и Жанадиль на бронзе пока.

• 154 минута Нурлан сдает game на 37. Жанадиль сдает тупняк на robot, 14 баллов

Нурлан - 165 (100-28-37) баллов
Жанадиль - 140 (46-14-80) баллов
Мейрам - 63 (12-14-37) баллов
Аман - 46 (46-0-0) баллов

Нурлан почти на серебре, Жанадиль в конце бронзы

• 159 минута - Мейрам доделал robot на 28

Нурлан - 165 (100-28-37) баллов
Жанадиль - 140 (46-14-80) баллов
Мейрам - 63 (12-28-37) баллов
Аман - 46 (46-0-0) баллов
Что-то Аман молчит...

• Прошло 3 часа, Мейрам допилил robot на 53 балла. Ему нужно брать 100 по одной задаче для медали...

Нурлан - 165 (100-28-37) баллов

Жанадиль - 140 (46-14-80) баллов
Мейрам - 102 (12-53-37) баллов
Аман - 46 (46-0-0) баллов

Надеюсь, Аман что-то умное пишет так долго...

• 193 минута, Аман все-таки делает 100 по первой задаче! Но этого не достаточно для бронзы. Тем временем, Жанадиль тоже слетает с бронзы

Нурлан - 165 (100-28-37) баллов

Жанадиль - 140 (46-14-80) баллов
Мейрам - 102 (12-53-37) баллов
Аман - 100 (100-0-0) баллов

• Осталось 1.5 часа. Жанадиль и Мейрам пытаются сдать первую, остальные пока думают.
• Аман сдает robot на 14.

Нурлан - 165 (100-28-37) баллов

Жанадиль - 140 (46-14-80) баллов
Аман - 100 (100-14-0) баллов
Мейрам - 102 (12-53-37) баллов

Нурлану надо допилить robot(53) и game(63) или брать 100 по robot для серебра.

Аману можно 37 по game (10 деревьев отрезков) и 28 по robot для уверенной бронзы.

Жанадилю надо делать 100 по первой для бронзы и еще 53 по robot для серебра.

Мейраму надо делать 100 и написать двумерное дерево отрезков на 63 по game для бронзы.

Интересный факт - самый ближайшии участник, который взял >=80 по game, стоит на золоте. 

• Осталось 55 минут. Мейрам сдает robot на 90! Ну ему надо решать первую на 100 для медали

Нурлан - 165 (100-28-37) баллов

Жанадиль - 140 (46-14-80) баллов
Мейрам - 139 (12-90-37) баллов
Аман - 114 (100-14-0) баллов

• Осталось 45 минут. Мейрам сдает cave на 25! Делай ее на 100, дааваай!!!

Нурлан - 165 (100-28-37) баллов

Жанадиль - 140 (46-14-80) баллов
Мейрам - 152 (25-90-37) баллов
Аман - 114 (100-14-0) баллов

• 28 минут до конца. Аман сдает robot на 39. Несколько баллов остается до бронзы... Делай!

Нурлан - 165 (100-28-37) баллов

Жанадиль - 140 (46-14-80) баллов
Мейрам - 152 (25-90-37) баллов
Аман - 139 (100-39-0) баллов

• 23 минуты. Жанадиль сдал robot на 53!

Жанадиль - 179 (46-53-80) баллов
Нурлан - 165 (100-28-37) баллов

Мейрам - 152 (25-90-37) баллов
Аман - 139 (100-39-0) баллов
Жанадиль давай еще чуть-чуть!!! Мейраму надо 100 по первой и Аману хоть что-то по последней. Давайте пацаны!!!
Нурлан вроде уже бронза, до серебра тяжко.
Жанадиль с 80 по game просто обязан сделать медаль!

• ВСЕ! Эхх... всего 15-20 баллов от бронзы у Амана и Жанадиля. И 70-80 у Мейрама.

Поздравляю Нурлана с бронзой!!! До серебра реально тяжко было. Молодец! 

В итоге:

За второй день 

Нурлан - 165 (100-28-37) баллов + 105 за первый день = 270 баллов и 122 место

Жанадиль - 179 (46-53-80) баллов +  22 за первый день = 201 баллов и 167 место
Аман - 139 (100-39-0) баллов + 61 за первый день = 200 баллов и 168 место
Мейрам - 152 (25-90-37) баллов + 3 за первый день = 155 баллов и 192 место

После фэйла первого дня, очень хорошо выступили!
По результатам только второго дня, все берут медали. 

У Амана уже есть медаль, а у других еще минимум 1 шанс есть доказать что они могут выступить лучше!
Нурлан, Жанадиль, Мейрамбек порвите всех в Тайване!

P.S. Виноват во всем их сбой системы первого дня! ;)

P.S.S. Все-таки Казахстан второй день выступает лучше первого
UPD: Результаты

Про задачи: (с codeforces)

Решения написаны белым цветом, чтобы желающие могли порешать сами. Оно становится заметным, если его выделить.

caves. В задаче дано N дверей, и N переключателей. Можно 70000 раз сходить устоновить переключали в любое положение, и узнать какая дверь закрыта первой. Надо узнать какой переключатель соответствует какой двери, и какое из двух положений открывает какую дверь.

Решение Будем определять переключатель по двери, начиная с первой. Зафиксируем все предыдущие двери открытыми, после этого можно считать, что их просто нет. Соответствующий переключатель после этого ищется бинарным поиском. Возможно нужно делать это достаточно аккуратно, чтобы уложиться в 70000 на последней подгруппе. . Конец решения

robots. В этой задаче есть слабые и маленькие роботы. У вещи есть вес и размер. Слабые роботы не могут носить слишком тяжелые вещи, меленькие — слишком большие вещи. Надо распределить работу по роботам, так чтобы минимизировать время выполнения.

Решение Я напишу жадность, которую умею строго доказывать. Сделаем бинпоиск по ответу. Отсортируем вещи по убыванию длины. Будем отдавать вещь самому слабому роботу, который сможет ее поднять, у которого еще есть свободное время. Оставшиеся задачи раздадим маленьким роботам. Это делается за NlogN c деревом отрезков. Вроде бы, если развернуть, то будет достаточно сета. Получится жадность вроде отдавать слабым роботам в порядке возрастания силы самые большие игрушки, которые можно. Это делается с сетом. . Конец решения

game. Есть поле 109 × 109. Надо отвечать на запросы изменить значение в клетке, и посчитать gcd на прямоугольнике. Изначально везде нули. Решение В задаче русским по белому написано, что надо сделать какую-то двумерную струтуру данных. Например двумерное неявное дерево отрезков, или дерево отрезков декартовых деревьев. В любом случае надо искать баланс между временем и памятью и прочими радостями жизни. Слава богу, у топа время на написание будет предостаточно. . Конец решения