Лог второго тура:
12:46 - Всё, пойду встречать ребят. Так ничего и не изменилось для команды России, похоже, так и останется два золота и два серебра. В целом >= 200 баллов уже у 86 участников, и, конечно, за оставшиеся 15 минут станет ещё больше.
12:24 - По задаче про попугаев стали появляться 99 баллов. Да, люди сильно продвинулись в изучении неточных решений. При этом сотен по этой задаче всего шесть. Также смотрю за Димой и Егором. У Димы много сабмитов по 26 баллов - похоже, он не придумал решения в слонах. А вот сабмит от Егора на 10 баллов, сделанный 15 минут, вселяет некоторую надежду, что у него просто какие-то баги в дереве.
12:11 - У Саши 100 за слонов! Надеюсь, два золота у нас уже железно. Догадается ли Саша сделать ход назад? И что же случилось у Димы и Егора?
12:00 - У Саши 295, 97 за слонов! К сожалению, Дима и Егор так и не вылезли пока из глубокого серебра, а Паша не заменил свои 98 на 100. При этом уже 65 участников набрали >= 200 баллов.
11:16 - Кстати, Дима дописал кучу в Дейкстре и у него стало 226. Все российские участники не ниже 9 места (хоть и 9 разделено с местами до 13). Эх, до конца бы так и оставить ;) Кстати, самое обидное, что если бы сейчас давали бы медали, то было бы всё равно два золота и два серебра. Это из-за первого тура так, получается то, о чём я писал ниже - выйти вперёд на этих задачах сложнее, а вот слететь...
11:15 - У Паши 98 по попугаям. Видимо, теперь надо сделать главный ход конём и догадаться до очень неожиданной идеи - в неточной задаче есть точное решение! На самом деле, это реально сложно, это как в шахматах взять предыдущий ход назад.
11:06 - У Паши 90 в попугаях. Всё-таки, он пошёл тем путём. Жаль... надеюсь, за два часа он сообразит про наличие абсолютно точного решения.
10:52 - У Димы сотня по попугаям! При этом уже 31 участник имеет >= 200 баллов, а 145 участников - >= 100 баллов. У наших у всех хотя бы 215 (Паша 281, Саша 248, Егор 224, Дима 215). Насколько этого достаточно, покажет время, но, думаю, будет ещё много подъёмов разных участников.
10:38 - У Паши уже 81 по попугаям. Видимо, это делается за 5 минут. Надеюсь, он не пойдёт дальше этим путём? Очень сбивает то, что эта задача с неточной оценкой, это психологически неожиданно и уводит от мысли искать простое точное решение :( Тем временем, Дима тоже получил 81 балл по этой задаче и имеет 196 баллов за этот тур. Надо бы ещё.
10:32 - У Паши 100 по слонам! Молодец! Не зря он в них сидел. Через минуту присоединился Гена и стал первым из абсолютных победителей. Паше остаются попугаи. Очень надеюсь, что он увидит в них сочетания с повторениями - на мой взгляд, это самый сложный момент в этой задаче. Иначе получается 98.
10:22 - У 17 участников >= 200, у 116 участников >= 100. Россия пока без изменений :(
10:12 - У Паши стало 126. Неужели он всё ещё сидит в слонах? Не пора ли заняться попугаями и сдать их на сотню?
09:58 - У Гены уже 297. Сейчас он чуть-чуть пооптимизирует слонов и станет одним из абсолютных победителей. Тем временем, у 11 участников >= 200 баллов, а у 100 участников >= 100 баллов.
09:54 - Тут же у Саши становится 98 баллов по попугаям (248 всего), и его обгоняет Гена с 250 баллами, у которого по попугаям одно из двух полных решений (другое глубоко внизу, что как бы намекает).
09:53 - Саша сдаёт попугаев на 93 балла и выходит на первое место по туру с 243 баллами. Но что же там за решения не на 100? И не придётся ли потом вместо них писать на сотню?
09:50 - У Егора 224, добавилось ещё 26 баллов по слонам. Что же он будет делать теперь, и что же за проблемы у остальных наших?
09:46 - Почему-то российские участники пока не двигаются (Егор - 198, Саша - 150, Дима - 115, Паша - 110). Очень волнуюсь, в чём же дело. Тем временем шестеро участников имеют >= 200 баллов, а 89 участников - >= 100 баллов.
09:38 - У одного из участников из Китая уже 237 баллов. У Егора тем временем 198 (98 по попугаям). Да, наверно, будет обидно из-за двух баллов писать совсем другое решение...
09:32 - У Паши 10 баллов за слонов. Что бы это значило? Хотя бы 100 баллов уже имеют 68 участников.
09:26 - У Егора 81 по попугаям. Я вообще не понимаю, что там может быть за решение, кроме точного :( Неужели там есть жёсткий ложный след, как в задаче garden первого тура, где можно было вводить состояния не на вершинах, а на рёбрах, что до сотни не доделывается вообще никак?
09:15 - Странно, что сотня по задаче parrots только одна. Зато есть ещё два участника по 98 баллов. Неужели комбинаторика и построение объекта по номеру и номера по объекту - такая сложная вещь? Или не все знают про сочетания с повторенями? При этом хотя бы 100 баллов уже у 52 участников.
09:10 - у Димы 115, у Саши 150. Похоже, пошли в бой разные квадраты в слонах. Тем временем, у лидера из Вьетнама 207 (100 + 26 + 81), а >= 100 уже у 41 участника.
09:00 - у Гены 200. Мой прогноз при виде задач, что у Гены останется 4 часа на задачу elephants, оказался абсолютно точным.
08:49 - уже 28 участников с >= 100. У всех российских участников 100, кроме Димы, у которого 89 (без хипа?).
08:40 - уже 18 участников имеют >= 100. У российских участников 100 баллов у Паши, 89 баллов у Саши (сначала решил послать Дейкстру без хипа?)
08:35 - уже семеро участников имеют полный балл по одной из задач
08:20 - один из польских участников уже сдал задачу про крокодилов. Дейкстра с хипом, однако.
По информации от организаторов, контест начался в 08:00 и закончится в 13:00 (местное время - +3 часа от московского).
---
Условия задач второго тура: http://acm.math.spbu.ru/ioi-2011-day2/
Текущие результаты: http://www.ioi2011.or.th/results
Результаты в приличном виде (спасибо Снарку :): http://sc2.ioi2011.net:8070/contest/
Результаты от Снарка: http://158.250.33.215/~ejudge/player_all.html
Решения всех задач второго тура.
Он мне показался даже проще чем первый. Сколь-нибудь ненулевое время я решал только elephants, остальные две задачи мне вообще показались упражнениями на базовые темы.
1) crocodile
Алгоритм Дейкстры, только нужно хранить в каждой вершине два текущих минимальных ребра, и ответ от вершины - второй из этих минимумов. Доказательство: пусть для каждой вершины посчитан ответ, тогда верно, что D[u] = {второму из чисел D[v] + w[u, v]}, где (u, v) - все рёбра, связанные с u. Теперь пусть, как в Дейкстре, для некоторых вершин уже посчитано D[v]. Тогда если взять вершину u такую, что min {второго из чисел D[v] + w[u, v]} минимально возможен, очевидно, он правильный (так как иначе была бы вершина с меньшим ответом). Включим u в множество уже посчитанных вершин и отрелаксируем. Странно, что за кучу в Дейкстре дают всего 11 баллов...
2) elephants
Самая сложная задача, примерно по сложности как race. Заметим, что в фиксированный момент времени задача решается жадно - возьмём самую левую точку и покроем, и т.д. Теперь, если мы посмотрим на то, какую точку после какой мы покрываем жадным алгоритмом, мы увидим дерево, глубина вершины в котором и является ответом, если решать суффикс нашей задачи, начиная с этой вершины. Если читать это дерево сверху вниз, а внутри уровня слева направо, то мы получим список слонов в порядке справа налево. Осталось научиться поддерживать это дерево и уметь быстро вычислять глубину самой левой вершины. Для этого нужно понять, какие операции делаются с этим деревом. Можно разбить перемещение слона на две операции: удаление и добавление. При удалении берётся поддерево удалённой вершины и подвешивается к соседней на том же уровне, а если на этом уровне вершин нет, то к крайней на более высоком. Если же мы добавляем вершину, она добавляется на некотором уровне, подвешивается к одной из вершин более высокого уровня и у соседа отрезается последовательная часть детей и подвешивается к ней. Структура данных, которая замечательно выполняет такие операции - это декартово дерево
по неявному ключу, если дерево хранить в порядке обхода dfs'ом. Единственное, в нём тяжело искать соседа по уровню, а также искать место, где нужно разрезать последовательность вершин при добавлении. Для этого я предлагаю хранить ещё одно декартово дерево, в котором ключом является координата слона, а также хранится дополнительная информация - ссылка на узел в дереве по неявному ключу. Тогда мы умеем в нём и искать нужную позицию, и переходить к соседу, и вообще делать всё, что нужно.
3) parrots
Видно, что исходное сообщение представляет собой размещение с повторениями (то есть, просто число в некоторой системе счисления), а конечное - сочетание с повторениями (если мы отсортируем все полученные числа, так как информация о порядке всё равно потерялась), число которых, как известно, равно C из n + k - 1 по k. Самый эффективный с точки зрения отсутствия отсутствия потерь информации способ их закодировать - это перевести исходное размещение с повторениями в номер, а потом по номеру построить сочетание с повторениями. Раскодировать, соответственно, обратно. Несложно видеть, что все подзадачи решены (ещё бы они не были решены, если это нельзя сделать таким способом - нельзя сделать никаким другим), например, для подзадачи 5 получается всего на несколько порядков больше сочетаний с повторениями, чем размещений - ограничения подобраны довольно жёстко. Да, несложная длинная арифметика ещё нужна.
В общем, к сожалению, наши шутки на тему того, что второй тур может быть ещё проще, чем первый, оправдались :( И это очень грустно для нашей команды, потому что упасть на таких задачах можно запросто, а вот подняться - почти нереально. Нужно ставить на количество абсолютных. Я ставлю на 6. И остаётся только молиться, чтобы среди них были Паша и Гена.
И мини-баллы за последние подзадачи тоже как минимум спорный ход. Например, в elephants всего 3 балла за то, чтобы уметь обрабатывать в два раза больше запросов. И в условии сказано, что последняя задача может не пройти, если пользоваться C++ и STL.
То есть по замыслу те, кто напишет структуру данных быстрее STL-аналога, получат 300 баллов и займут место типа ~1-7. А те, кто напишет структуру данных медленнее STL-аналога, получат 297 баллов и займут место ~8-14. Зато те, кто хоть что-то не сдал в первом туре, могут уже о Top 10 не мечтать. Нда.
http://158.250.33.215/~ejudge/player_all.html.
Квота мест по медальным зонам в этом году такая же как и в прежние годы?
А то мы тут кроме всех наших братьев-славьян болеем за золото у ещё одного человека: Baris Kaya, а после града 100% результатов первого тура этот вопрос и возник.
Так вот от этого парнишки ожидают первого для страны "золота".
Ну, естественно, мы также в первую очередь болеем за "золото" всех наших (во всяком случае медалей 100%), а что из этого получится - уже недолго ждать осталось - скоро увидим. :)
Грубая прикидка: 25 - золото, 50 серебро и 75 бронза - чтобы можно было как то по текущим местам ориентироваться.
25 золота, 50 серебра, 75 бронзы.
Скорее всего прогноз о 6-ти не подтвердится.
Присоединяюсь ко всем ранее озвученным и тем, что ещё будут звучать далее, поздравлениям!
Гена - МОЛОДЕЦ!
Вообще команды России и Беларуси заслуживают уважения и отдельного поздравления.
Большое спасибо Андрею Лопатину за классную ленту-комментарий с места событий (а какой ещё комментарий мог быть у дважды чемпиона мира? - :) ).
Наблюдая за интересующими меня командами, свёл результаты в одну табличку, вот что получилось:
Золото
Серебро
Бронза
Беларусь
1
3
-
Китай
3
1
-
Польша
2
1
1
Россия
2
2
-
США
3
1
-
Турция
1
1
2
Украина
-
1
2
Хорватия
3
-
1
Комментарии к ней излишни (сортировка в алфавитном порядке).
Ещё раз поздравления всем победителям, призёрам и просто участникам IOI-2011!
Если верить информации от китайских участников IOI, то то, что я утверждал верно с 2006 года.
В составы их команд я, правда, посмотреть поленился.
Например, если n=80, то для кодирования (по сути 640-битного числа) нужна будет последовательность хотя бы из 420 чисел (при R=255), т.е. больше чем 5*80=400.
, урод.Не понял ваше "специально для тебя,
урод" ? Это теперь норма для CF или у вас какая-то претензия лично ко мне?А если по делу, я ведь только спросил, что именно за преобразование. 8n бит превратить в 5n байт (без учёта порядка) в общем случае невозможно.
upd: Суть моего высказывания в том, что (как мне раньше казалось, а теперь я уверен) иногда вместо 5n нужно хотя бы 6n и т.д. При росте n коэффициент перед n нужно увеличивать.
Я не вижу, между каких строк вы читаете, и в чём заключалась моя "провокация" или "наглость".
Когда я решал Parrots я (теоретически) вывел коэф. перед n, который растёт неограниченно с n. Увидев фразу "легко видно преобразование между 8n бит и 5n байт", я просто решил поинтересоваться, что именно это за преобразование, чтобы разобраться, работает ли оно при всех n (тогда моя оценка неверна) или имелось в виду n<=64.
Конкретно у меня получилось
c = 8L / log(combin(L+R,R))
(логарифм по основанию 2)
L - кол-во попугаев
c - (как минимум) во сколько раз n должно быть меньше L
И да, мне не кажется, что я где-то "ляпнул чушь".
Я сделал все чтобы пояснить вам мой подход к решению, если вы и после третьего комментария и выложенного кода не понимаете, то я тоже уже ничего не понимаю. Вы дурак или прикидываетесь? Я не верю что вы не поняли предложенное решение, у вас неплохой рейтинг и вы скорее прикидываетесь. Я не верю в то что вам до сих пор не понятно что коэффициент 5 я взял не с потолка, а из условия задачи. Мой комментарий описывал подход к решению задачи, а она подразумевает коэффициент не более 5 и n <= 64.
Когда я говорю что задача на дп с битовой маской, я вовсе не утверждаю что задача решается так для любого n, ясен пень что я говорю об ограничениях данных в задаче.
И вы не "ланули чушь" вы ляпнули чушь. Которая привела к минусованию моего комментария, описывающего верное решение. В этом то и заключалась "наглость" или "провокация", то, что огорчило меня и заставило ответить вам описав решение. Я не говорю что вы совсем не правы в своем ответе, просто он послужил поводом для кого-то меня минусовать, а возможно вы минусанули, не поняв о чем я сказал.
Ведь по условию задачи в полном решении отношение длин исходной и закодированной последовательности должно быть не больше 5-ти.
Ну смотрите, мы можем передать одну из 2^565 последовательностей, такое сообщение несёт информацию 565 бит. Нам требуется передать 64 * 8 бит 565 / 64 > 8 бит (нам же хватит и 8 бит на каждый кусок из 64). С другой стороны можно 565 поделить на 8 и получить число байт, которые мы можем передать, получиться 70.625, что опять же больше 64 байт. Еще раз, по другому. Мы хотим передать 64 байта, их можно рассматривать как число x, x >= 0 && x < 2^(8*64). 2^(8*64) = 2^(512). мы, умея преобразовывать сортированную последовательность в число и наоборот, можем передать число до 2^565, и таким образом нам не составит труда передать сообщение x, даже еще останется место.
Теперь поясню почему это будет работать и для меньших значений n.
Количество информации в сообщении из 5 * n байт равно 8 * 5 * n битам, что соответсвует 2^(40 * n) возможным сообщениям. Оценивая сверху потери информации при сортировке байт будем считать что все числа различны, и перемена мест любых двух байт меняет сообщение. То есть, информация которая потерялась при сортировке может быть восстановлена с помошью перестановки 5 * n чисел.То есть нижняя оценка для информации, которую мы можем получить передав сообщение (которое потом перемешается и отсортируется) есть log2(( 2^(40 * n) ) / ( (5 * n) ! )) чем больше n, тем больше бит мы теряем с каждым очередным членом в факториале (числа постепенно возрастают) чем меньше n, тем лучше для нашего метода.
UPD: для большей наглядности раскрою скобки, и уберу деление из логарифма.
F(n) = log2(( 2^(40 * n) ) / ( (5 * n) ! )) = 40 * n - log (5 * n)!)
F(n + 1) = F(n) + 40 - log((n * 5) - log(n * 5 - 1) - log(n * 5 - 2) - log(n * 5 - 3) - log(n * 5 - 4)
как видим, при росте n потери информации возрастают. Замечу еще раз что это нижняя оценка для количества информации, и да, она станет отрицательной при устремлении n далеко в бесконечность.
Не хочу ни с кем ссориться, но справедливости ради отмечу, что оценка слишком груба для n=64.
Т.е. F(64) ~= 353 бита, а 353/8 ~= 44<64.
(но 5*64 попугаями всё же можно передать 64 байта исходного сообщения)
Спасибо.
С теорией информации я знаком, просто я не вижу в чем заключается конструктивное решение.
Я понимаю задачу так. Есть сообщение из 64 байт, его надо закодировать не более чем в 320 байт, и, после случайного перемешивания, восстановить исходное сообщение.
На IOI решение на 100 баллов упаковывало 64 -> 262. А у Вас как?
Разборы не добавили, они изначально там были.
Вот, кстати, любопытно. Оказывется, если бы не SnapDragon, то на IOI был бы дележ, как минимум 1-4 места =).
Тут скорее всего проблемы другого характера: причины в разном формате соревнований.
АСМ - это командные турниры, а IOI - личные.
На IOI действует ограничение на максимальное представительство школьников от одной страны - больше 4-х их быть не может.
На АСМ действует ограничение на количество команд от одного ВУЗа, но не действует ограничение на количество команд ВУЗов от одной страны.
Так что доминирование на АСМ говорит, наверное и скорее всего, о высоком уровне преподавания во многих, я бы даже сказал, в большинстве ВУЗов Росии, в то время как в других странах ВУЗов с высоко поставленным уровнем преподавания намного меньше.
Учитывая, что практически во всех странах школьники по окончанию школы стремятся поступать в престижные ВУЗы, то шансов попасть в команду на финал АСМ у бывших призёров IOI или просто талантливых школьников в других странах намного меньше чем в России.
Это, конечно, чисто мой субъективный взгляд со стороны, но кажется мне, что это достаточно близко к истине.
Т.е. существует куча ВУЗов, в которых замечательно преподают, но нет тренера - нет результатов.
Без классного организатора, почти фанатически преданного этому делу, успеха добиться на несколько порядков будет тяжелей.
Кстати, абсолютно аналогичная картина и в школьной олимпиадной информатике.
Т.е. "Кадры решают всё!", ну во всяком случае если не всё, то многое... :)
Ещё один пример в поддержку вышесказанных тезисов на базе украинских ВУЗов: если раньше можно было говорить только о киевской и харьковских студенческих школах и командах на АСМ, то сейчас кроме Киева и Харькова появились Львов, Донецк, Симферополь, Днепропетровск, Винница, подтягиваются и другие - всех не перечислишь, да и в перечисленных городах растёт количество ВУЗов, где занимаются спортивным программированием на более высоком, можно сказать профессиональном уровне. Это всё со стороны хорошо просматривается. Как один из результатов - тот факт, что Украину в этом году выдели в отдельную зону.
Да и перспективные и одарённые школьники, выбрав и поступив в престижный ВУЗ и ощущая там конкуренцию от этой самой конкуренции становятся только сильнее.
Главное тут, что если им в некоторых ВУЗах не помогают в этом, то пусть хоть не мешают... :)
1. В России раньше, чем в среднем по остальным раундам, заканчивается школа. Значит, дети в среднем менее взрослые.
2. У NEERC несравненно большая квота для команд-финалистов. Легче 5 из 13 команд оказаться в медалях, чем, например, 5 из 1.
>мехмат СПбГУ
>Павел Куняев
Я что-то пропустил?
На такое я могу только матом...
Наверняка по политическим мотивам не сказали об этом ;)
Но девчонка заслуживает немного уважения: не въезжая не то, что в тему, а вообще в элементарную терминологию, так уверенно рассказывать обо всем в течении около 10 минут - только за это можно немножко зауважать...
А потом вспомнить, что журналисты - это тоже одна из древнейших профессий и просто улыбнутся - ну не виновата же она в конце концов, что у неё работа такая... :)