Форум DL

Мой профиль

  1. Кулик Сергей             155 - золото
 48. Подтелкин Владислав       55 - серебро 
 58. Сокол Константин          47 - серебро
124. Вильчевский Константин     0

Мой профиль

IOI 2013, 1 тур (глазами Павла Кунявского, Россия)

...
Контест должен был начаться в 8:00, но из-за технических проблем участников только запустили. Обещают начать в 9:00 по местному.
...
Очень похоже, что таблица давно уже не обновляется. Правда говорят, что низ меняется. Очень странно это все.
...
До конца контеста осталось десять минут, и я уже пойду встречать участников. Думаю через несколько часов станет понятнее с результатами.

Немного про задачи

dreaming. В этой задаче дан взвешенный лес. Надо его дополнить до дерева ребрами длины L, так чтобы минимизировать диаметр. Нам кажется, что задача решается жадным приклеиванием центров всех компонент к центру компоненты с самым большим диаметром.

art-class. Эта задача была для нас большой неожиданностью на переводе. Для участников видимо тоже. Хотя по ней уже есть несколько сотен и несколько почти сотен. В этой задаче предлагают классифицировать изображения по 4-ем художественным стилям. Она несколько напоминает language с IOI-2010. Наверное решается достаточно просто. Нам кажется, что надо посмотреть на дискретные производные интенсивности. В разных типах они на вид существенно различаются. У участников в этой задаче есть огромный простор для творчества.

wombats. В этой задаче дана взвешенная решетка дорог (строк много, столбцов мало), по которой можно перемещаться влево, вправо и вниз. Нужно отвечать на много запросов найти кратчайший путь из клетки в первой строке до клетки в последней, и на мало запросов об изменении весов. Видимо предлагается разбивать на части деревом отрезков или корневой и объединять эти части. Это будет где-то на границе времени и памяти, но 20 секунд TL немного намекают...

Официальные условия задач
Русский
English

Мой профиль

Информация об IOI 2013 на Snarknews

Мой профиль

Сокол - 8
Кулик - 14
Вильчевский - 64
Подтелкин - 87
Данные за 10 минут до истечения времени олимпиады. Задачи еще тестируются.
На 1 час задержали олимпиаду, но пол часа продлили.
Участники говорят что backlog [непротесченные задачи] огромный. Фактически, большую половину контеста участники решали задачи адаптированные для full feedback'а (artclass, большие сабтаски) без него.

Мой профиль

Уточнились результаты первого дня IOI 2013

 28. Сокол Константин          237 - серебро
 41. Кулик Сергей              224 - серебро
103. Вильчевский Константин    139 - бронза  
133. Подтелкин Владислав       107 - бронза

Мой профиль

Результаты второго тура

 15. Кулик Сергей             266  =  76 +  90 + 100
 50. Подтелкин Владислав      237  = 100 + 100 +  37
 80. Сокол Константин         190  = 100 +  53 +  37
154. Вильчевский Константин   128  =  63 +  28 +  37

Результаты по сумме двух дней

 
 20. Кулик Сергей             490  = 224 + 266  -  золото
 48. Сокол Константин         427  = 237 + 190  -  серебро
 84. Подтелкин Владислав      344  = 107 + 237  -  бронза 
122. Вильчевский Константин   267  = 139 + 128  -  бронза

Медали по странам

           
                G S B =
   1 China      4 0 0 4 
   2 Russia     3 1 0 4 
 3-4 Korea      2 2 0 4 
 3-4 USA        2 2 0 4 
 5-6 Romania    2 1 1 4 
 5-6 Slovakia   2 1 1 4 
   7 Iran       1 3 0 4 
8-10 Bulgaria   1 2 1 4 
8-10 Israel     1 2 1 4 
8-10 Sweden     1 2 1 4 
  11 Japan      1 2 0 3 
  12 Belarus    1 1 2 4

Мой профиль

IOI 2013, 2 тур (глазами Павла Кунявского, Россия)

... Уже есть 25 и 12 по первой, но они совсем не о чем, я не думаю, что много топа будет их писать
... Быстро появилось достаточно много сотен по первой. Впрочем, она действительно простая. Во второй есть правдоподобная жадность, которая оказывается верной. Вполне вероятно, что большинство участников просто не будет ее доказывать.
Наши пока себя не показали никак. Видимо читают условия. Так тоже можно ...
... Одним словом надо решать game (третью задачу) на сотню. game — это абсолютно стандартная, но достаточно сложная задача. Основная проблема с ней в том, что вчера на GA meeting выяснилось, что в ней заходит тупняк. Поэтому срочно пришлось повышать ограничения, и это делали ночью. Кроме того, для усложнения, в задаче поставили достаточно жесткий ML, который является основной проблемой для последних 20 баллов, по замыслу жюри. Собственно про проблемы с этой задачей я писал, когда говорил про худшие мысли о причинах с задержкой.
... 1:08 К KAN и WJMZBMR присоединились scott_wu и t0nyukuk. Остается вопрос, кто из них умеет писать двумерные динамические структуры данных. В KAN я уверен, вопрос в том, сколько времени это займет.

Подробнее о задачах

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

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

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

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

game. Есть поле 10^9*10^9. Надо отвечать на запросы изменить значение в клетке, и посчитать gcd на прямоугольнике. Изначально везде нули.

В задаче русским по белому написано, что надо сделать какую-то двумерную струтуру данных. Например двумерное неявное дерево отрезков, или дерево отрезков декартовых деревьев. В любом случае надо искать баланс между временем и памятью и прочими радостями жизни. Слава богу, у топа время на написание будет предостаточно.

Официальные условия задач
Русский
English

Мой профиль

Пресс-релиз Snarknews по результатам IOI 2013

Мой профиль

IOI 2013 photos

Мой профиль

If IOI 2013 problems were Codeforces problems

Мой профиль

Some problems discussion?

TIR-OlympicOlimpik:

Hello Codeforces People... IOI 2013 Contest has ended. I dont know solutions about Robots,Wombats and Game... Could you share solutions? Thanks...

Мой профиль

IOI-2013 Tech Report

- подробный технический отчёт по IOI-2013 с детальным разбором причин случившихся в начале первого тура проблем, а также ситуации с заменой задач; является примером открытого и конструктивного подхода к анализу происходивших на турнире неполадок (обычно организаторы упоминают о проблемах в лучшем случае вскользь).

Мой профиль

IOI 2013 - Game

Мой профиль

IOI 2013 problems and solutions