IOI
Начался 2-й тур 22-й IOI...
Начался он в 16:30 по московскому времени.
http://www.ioi2010.org/scoreboard2/scoreboard.html
Условия задач на русском: http://acm.spbgu.ru/ioi-2010-day2/
Со стандартной задачей-незадачей наша сборная справилась за первые 10-20 минут.
16:53
Гена Короткевич сдал "мегасложную" задачу номер 2.
В чем же заключалась эта вторая задача? Задача-незадача hard-version :) Проще рассказать не условие (2 страницы), а решение: найдите очередной центр дерева (вершину такую, что max размеров ее поддеревьев минимален). На замечание "Эта задача 100 раз была! Она абсолютно стандартная!" автор заметил, что это не бага, а фича и "Так и задумывалось". Так что, мое ему полное o_O.
P.S. Гене за скорость респект :)
17:01
Следуя народной мудрости "какая бы задача простая ни была, напиши тупое решение", Глеб получает 50 баллов по динамике по дереву (Задача 2). Это хорошо) А еще лучше, что в 17:03 следует resubmit на 100-ню :-) Тем временем всего сотен по задаче уже 19.
17:11
Рома тоже молодец :-)
В таблице http://www.ioi2010.org/scoreboard/scoreboard.html красивой зеленой стрелочкой с числом 45 намекают, что сотня по DP по дереву подняла его на 45 мест вверх. Сейчас Рома на 12-м. (Теперь ожидается плавный спуск вниз на некоторое время, ибо остальные догоняют).
P.S. Сотен по 2-й уже 38 (из них 2 наши)
17:20
Миша и Серега подтянулись (играем в лесенку =)
Итого - У всех по 2 сотни! Незадачи для наших кончились :-(((
3-я задача с открытыми тестами. 1-й и 6-й я умею делать руками :-) Тесты можно скачать здесь: http://acm.spbgu.ru/maze.rar
17:39
Начался тур! В смысле, простые задачи закончились и удачные сабмиты теперь будут радовать нас раз в полчаса-час, а не каждые 5 минут, как раньше. На первом месте сейчас Гена с 50+24+100+100. И 50, и 24 - это несложные заглушки, со временем как минимум такие баллы должны появиться у всех ;-) Наша сборная все еще имеет 4x200 баллов.
18:02
Rumen Hristov из Болгарии жжет! 58 баллов по maze-у. Лучший результат. Временно обошел Гену на 34 балла... А наши, как говорит Андрей "Пишут что-то умное".
Первая тройка по странам: Bolgaria (Rumen) - Belarus (Гена) - Belarus (Алексей)
18:15
Андрей ищет ответ на простой вопрос "Что они делают уже целый час?". Собственно стратегии развития сейчас, наверное, 4:
1) Думать. Сидеть и думать.
2) Получить 50 баллов по saveit.
3) Сделать пару тестов руками по maze-у и получить хотя бы баллов 30.
4) Писать злой перебор по maze-у. Или даже (так не надо делать!!!) DP по профилю для маленьких тестов.
P.S. На этот вопрос предельно простой ответ только что дал Рома, получив стандартные 50 баллов по saveit.
P.P.S. Можно порадоваться за сборную Белоруссии: 274+269+200+200
18:22
Тем временем новости из верхней части таблицы:
Гена догнал Rumen-а. 50+58+100+100.
18:26
А вот новости из USA: Сборная USA жжет!
Жжет Neal Wu. У него сейчас 0+40+0+0.
Жжет Brian Hamrick. 50+48+0+0.
По-моему, они что-то затевают ;)
18:31
Пару слов про Казахстан: самым сильным участником я считаю Мадияра. На первом туре он надежды вполне оправдал... а вот сейчас, сейчас у Казахстана 219, 200, 175, 125 = Мадияр. Надеюсь, просто переволновался в начале тура. Ждем взлета! :)
20:07
Извиняюсь, за длинный перерыв. Опыт проведения трансляций почти нулевой, поэтому подумать о подзарядке ноутбука я не догадался =( Сейчас все ОК, я сижу на 220. Новостей и мыслей накопилось много, сейчас все они тут появятся.
(1) Гена получил 100 по saveit! Это круто =) По поводу идей решения, у меня их было 2, про одну из них Андрей успел переговорить с местным научным комитетом, они сказали, что по сути близко к авторскому решению и корректность они умеют доказывать. Итак, идея: возьмем все 36 деревьев кратчайших деревьев. Вершины все помеченные. Деревья подвешенные. А теперь заметим, что многие поддеревья будут повторяться. Кодировать повторяющиеся второй раз, естественно не нужно, достаточно пометки, что такое дерево уже было. Реализация предлагается такая: разобьем все поддеревья на классы эквивалентности за линейное время и каждый класс закодируем 1 раз (количество детей и номера их классов). Далее запишем 36 корневых классов.
(2) По задаче maze я, не перенапрягшись, получил ручками 45 баллов на 5 тестах + 5 за "ничего" (читай условие) = 50. Т.е. всех их сборной, кто получит меньше, ждет легкая казнь :-)
(3) Андрей, сказав "Хватит. Пойду, поберегу нервы.", пошел в ближайший магазин за сувенирным кленовым сиропом. Минуты через 3 резы нашей сборной из 320, 250, 250, 217 превратились в 321, 321, 294, 239. Не так уж плохо =)
(4) Ответ на вопрос "Почему 239?!", почему у Глеба 0 по saveit? Говорят, он задал жюри такой вопрос "Я получаю Illegal Library Call. Я отправил пустое решение, получил тоже самое. Я отправил тупое решение, которое нам выдали, получил тоже самое... и т.д.", и получил "No comments". Получать по всем, тем более, самым тупым решениям "Illegal Library Call", безусловно должно бесить. Жюри ответ "No comments" объясняет тем, что в проге правда ошибка, а их "тупое" решение и должно получать такой вердикт, ибо оно не полное. Посовещавшись с Андреем, мы вынуждены с ответом жюри согласиться, а Глебу можем только посочувствовать. Ну и понадеяться, что законные 50 баллов его еще ждут в конце контеста ;-)
(5) http://www.ioi2010.org/scoreboard/scoreboard.html Не смотря на то, что наши сейчас на 8, 14, 17 местах, есть мнение, что для золота нужно будет как минимум 690-700 баллов. Т.е. нужно еще, еще больше баллов!
PS: Мысли кончились, F5 можно уже не жать
20:35
До конца чуть меньше часа.
Россия = 321, 321, 297, 239 (все по-прежнему)
Белоруссия = 377, 297, 291, 269 (у всех есть стандартный набор 50+eps+100+100)
Украина = 288, 250, 215, 201 (2 человека еще не достигли просветления)
Казахстан = 297, 250, 243, 225 (сзади как и раньше Мадияр, медленно-медленно ползет)
Болгария = 380, 318, 309, 308 (Rumen стабильно жжет! У лучше знакомого нам Владислава пока 309...)
20:45
Вопросы и ответы:
От Паши Кунявского: "Как считаешь Миша досдаст оставшиеся 5 тестов?". Я считаю, что все будет хорошо ))
Сколько нужно на серебро? По-моему, 100+55+75+100 + 50+50+100+100 = 630.
Сколько нужно на золото? 100+90+80+100 + 120+100+100 = 690
Т.е. сейчас есть ощущение, что вопрос золото-серебро решался на первом туре =( А сейчас задача всех "не слить".
PS: Я хочу закодить кое-что по maze, так что какое-то время меня не будет (since 20:50)
21:12
Эксперимент закончен. Тупой жадный dfs, запущенный из всех клеток границы (написанный минут за 15) получает сам по себе 62 балла, если его спарить с резами, полученными руками, все 70.
70 баллов на халяву по задаче maze! Я в расстройстве =(
21:24
Даешь +20 Мише за maze и +50 Глебу за saveit!!!
Рома, Серега, что приятного вы приготовили нам за последние 2 часа? Время посылать! :-)
Начался он в 16:30 по московскому времени.
http://www.ioi2010.org/scoreboard2/scoreboard.html
Условия задач на русском: http://acm.spbgu.ru/ioi-2010-day2/
Со стандартной задачей-незадачей наша сборная справилась за первые 10-20 минут.
16:53
Гена Короткевич сдал "мегасложную" задачу номер 2.
В чем же заключалась эта вторая задача? Задача-незадача hard-version :) Проще рассказать не условие (2 страницы), а решение: найдите очередной центр дерева (вершину такую, что max размеров ее поддеревьев минимален). На замечание "Эта задача 100 раз была! Она абсолютно стандартная!" автор заметил, что это не бага, а фича и "Так и задумывалось". Так что, мое ему полное o_O.
P.S. Гене за скорость респект :)
17:01
Следуя народной мудрости "какая бы задача простая ни была, напиши тупое решение", Глеб получает 50 баллов по динамике по дереву (Задача 2). Это хорошо) А еще лучше, что в 17:03 следует resubmit на 100-ню :-) Тем временем всего сотен по задаче уже 19.
17:11
Рома тоже молодец :-)
В таблице http://www.ioi2010.org/scoreboard/scoreboard.html красивой зеленой стрелочкой с числом 45 намекают, что сотня по DP по дереву подняла его на 45 мест вверх. Сейчас Рома на 12-м. (Теперь ожидается плавный спуск вниз на некоторое время, ибо остальные догоняют).
P.S. Сотен по 2-й уже 38 (из них 2 наши)
17:20
Миша и Серега подтянулись (играем в лесенку =)
Итого - У всех по 2 сотни! Незадачи для наших кончились :-(((
3-я задача с открытыми тестами. 1-й и 6-й я умею делать руками :-) Тесты можно скачать здесь: http://acm.spbgu.ru/maze.rar
17:39
Начался тур! В смысле, простые задачи закончились и удачные сабмиты теперь будут радовать нас раз в полчаса-час, а не каждые 5 минут, как раньше. На первом месте сейчас Гена с 50+24+100+100. И 50, и 24 - это несложные заглушки, со временем как минимум такие баллы должны появиться у всех ;-) Наша сборная все еще имеет 4x200 баллов.
18:02
Rumen Hristov из Болгарии жжет! 58 баллов по maze-у. Лучший результат. Временно обошел Гену на 34 балла... А наши, как говорит Андрей "Пишут что-то умное".
Первая тройка по странам: Bolgaria (Rumen) - Belarus (Гена) - Belarus (Алексей)
18:15
Андрей ищет ответ на простой вопрос "Что они делают уже целый час?". Собственно стратегии развития сейчас, наверное, 4:
1) Думать. Сидеть и думать.
2) Получить 50 баллов по saveit.
3) Сделать пару тестов руками по maze-у и получить хотя бы баллов 30.
4) Писать злой перебор по maze-у. Или даже (так не надо делать!!!) DP по профилю для маленьких тестов.
P.S. На этот вопрос предельно простой ответ только что дал Рома, получив стандартные 50 баллов по saveit.
P.P.S. Можно порадоваться за сборную Белоруссии: 274+269+200+200
18:22
Тем временем новости из верхней части таблицы:
Гена догнал Rumen-а. 50+58+100+100.
18:26
А вот новости из USA: Сборная USA жжет!
Жжет Neal Wu. У него сейчас 0+40+0+0.
Жжет Brian Hamrick. 50+48+0+0.
По-моему, они что-то затевают ;)
18:31
Пару слов про Казахстан: самым сильным участником я считаю Мадияра. На первом туре он надежды вполне оправдал... а вот сейчас, сейчас у Казахстана 219, 200, 175, 125 = Мадияр. Надеюсь, просто переволновался в начале тура. Ждем взлета! :)
20:07
Извиняюсь, за длинный перерыв. Опыт проведения трансляций почти нулевой, поэтому подумать о подзарядке ноутбука я не догадался =( Сейчас все ОК, я сижу на 220. Новостей и мыслей накопилось много, сейчас все они тут появятся.
(1) Гена получил 100 по saveit! Это круто =) По поводу идей решения, у меня их было 2, про одну из них Андрей успел переговорить с местным научным комитетом, они сказали, что по сути близко к авторскому решению и корректность они умеют доказывать. Итак, идея: возьмем все 36 деревьев кратчайших деревьев. Вершины все помеченные. Деревья подвешенные. А теперь заметим, что многие поддеревья будут повторяться. Кодировать повторяющиеся второй раз, естественно не нужно, достаточно пометки, что такое дерево уже было. Реализация предлагается такая: разобьем все поддеревья на классы эквивалентности за линейное время и каждый класс закодируем 1 раз (количество детей и номера их классов). Далее запишем 36 корневых классов.
(2) По задаче maze я, не перенапрягшись, получил ручками 45 баллов на 5 тестах + 5 за "ничего" (читай условие) = 50. Т.е. всех их сборной, кто получит меньше, ждет легкая казнь :-)
(3) Андрей, сказав "Хватит. Пойду, поберегу нервы.", пошел в ближайший магазин за сувенирным кленовым сиропом. Минуты через 3 резы нашей сборной из 320, 250, 250, 217 превратились в 321, 321, 294, 239. Не так уж плохо =)
(4) Ответ на вопрос "Почему 239?!", почему у Глеба 0 по saveit? Говорят, он задал жюри такой вопрос "Я получаю Illegal Library Call. Я отправил пустое решение, получил тоже самое. Я отправил тупое решение, которое нам выдали, получил тоже самое... и т.д.", и получил "No comments". Получать по всем, тем более, самым тупым решениям "Illegal Library Call", безусловно должно бесить. Жюри ответ "No comments" объясняет тем, что в проге правда ошибка, а их "тупое" решение и должно получать такой вердикт, ибо оно не полное. Посовещавшись с Андреем, мы вынуждены с ответом жюри согласиться, а Глебу можем только посочувствовать. Ну и понадеяться, что законные 50 баллов его еще ждут в конце контеста ;-)
(5) http://www.ioi2010.org/scoreboard/scoreboard.html Не смотря на то, что наши сейчас на 8, 14, 17 местах, есть мнение, что для золота нужно будет как минимум 690-700 баллов. Т.е. нужно еще, еще больше баллов!
PS: Мысли кончились, F5 можно уже не жать
20:35
До конца чуть меньше часа.
Россия = 321, 321, 297, 239 (все по-прежнему)
Белоруссия = 377, 297, 291, 269 (у всех есть стандартный набор 50+eps+100+100)
Украина = 288, 250, 215, 201 (2 человека еще не достигли просветления)
Казахстан = 297, 250, 243, 225 (сзади как и раньше Мадияр, медленно-медленно ползет)
Болгария = 380, 318, 309, 308 (Rumen стабильно жжет! У лучше знакомого нам Владислава пока 309...)
20:45
Вопросы и ответы:
От Паши Кунявского: "Как считаешь Миша досдаст оставшиеся 5 тестов?". Я считаю, что все будет хорошо ))
Сколько нужно на серебро? По-моему, 100+55+75+100 + 50+50+100+100 = 630.
Сколько нужно на золото? 100+90+80+100 + 120+100+100 = 690
Т.е. сейчас есть ощущение, что вопрос золото-серебро решался на первом туре =( А сейчас задача всех "не слить".
PS: Я хочу закодить кое-что по maze, так что какое-то время меня не будет (since 20:50)
21:12
Эксперимент закончен. Тупой жадный dfs, запущенный из всех клеток границы (написанный минут за 15) получает сам по себе 62 балла, если его спарить с резами, полученными руками, все 70.
70 баллов на халяву по задаче maze! Я в расстройстве =(
21:24
Даешь +20 Мише за maze и +50 Глебу за saveit!!!
Рома, Серега, что приятного вы приготовили нам за последние 2 часа? Время посылать! :-)