Hello, codeforces.

To unveil the full power of Kotlin and JetBrains tools, as well as their advantages in algorithmic problem-solving, we’ve invited two competitive programming stars to match their skills in solving Kotlin problems on stage at the ICPC World Finals.

Andrew ecnerwala He, one of the top competitive programmers in the world, will compete in a match against Kamil Errichto Debowski, Codeforces "Legendary Grandmaster" and Topcoder "Target." The match will be commentated by none other than Roman elizarov Elizarov, Kotlin Lead Language Designer.

You can join the stream on Kotlin by JetBrains youtube channel at Nov/07/2022 07:17 (Moscow time) and view submissions in the special Codeforces round Ecnerwala vs Errichto Kotlin Match. Only ecnerwala and Errichto can participate in the round, while you will be able to join as spectators.

We will reuse some problems from previous Div3 rounds. We mostly used round #748. And also, one problem was from round #627. A lot of thanks to MikeMirzayanov vovuh and MrPaul_TUser.

Good luck to both participants, and thanks to MikeMirzayanov for the great codeforces platform.

The International Olympiad in Informatics 2022 is scheduled to start in a month. To help you prepare today, we announce an online judge with IOI problems. Right here, on codeforces.

Available now

On https://ioi.contest.codeforces.com/ you can find a contest for each day of each IOI contest since 2002. Participate virtually in a 5-hour contest or simply upsolve problems there! Virtual participants will appear in separate scoreboards for each year as well as in an upsolving scoreboard. Don’t forget to disable coach mode to appear in the upsolving scoreboard.

Future work

We have at least some problem materials for contests since 1998, but IOI has had competitive programming problems since 1994. Even if these problems are not very useful for training, they have significant historical value. Unfortunately, early-year materials on ioinformatics.org are incredibly bad, so if you have something (e.g., solutions, interactor, checkers, library sources), please contact me right away!

I am also considering adding original contest results as ghost participants to the scoreboards.

Let me know in the comments, what else would you like to see in the IOI archive?

How to help?

I'm sure some problems are misconfigured. The most probable errors are tests in wrong subtasks or changes in grader not mentioned in the problem statements. Let’s find them in upsolving mode, to avoid ruining the training process for contestants. If you have solutions (preferably partial solutions), please, become an early tester. Report issues via github repo. Pull requests to problem statements and validators are also always welcome there!

Please, contribute with contest materials for earlier IOI!

If you are a member of an IOI committee, help the project a lot by enforcing a better archival process for the future contests. In particular, it would be great to have as part of the public archive:

• Statements in markdown
• Any kind of non-English statements
• Test data generators and tests generation command lines
• Any description of solutions intended behavior or score
• no new archive format every year :)

Special thanks

• MikeMirzayanov and geranazavr555 for implementing a lot of stuff in Codeforces and Polygon
• ligaydima , Dimitrys and especially Masha237 for help converting problem statements to polygon format.
• lperovskaya for maintaining archive on contest.yandex.ru/ioi, which become a great material source, as well as for proofreading this text
• Petr for solutions and other materials of IOI2002 (and IOI2000, and IOI2001 I hope to publish later).
• eduardische for showing me the old IOI site with problem materials, and Martins Opmanis for maintaining it.
• yeputons for original archive resources and idea back in 2011
• Mazaalai for better than original one solutions of IOI2003-reverse

Updates

10.08.2022: IOI 2022 day 1 is available.
13.08.2022: IOI 2022 day 2 is available.
30.08.2023: IOI 2023 day 1 is available.
01.09.2023: IOI 2023 day 2 is available.
03.09.2024: IOI 2024 day 1 is available (no statements now) 05.09.2024: IOI 2024 day 2 is available (no statements now)

Важный день!

Сегодня мы узнаем победителей трека Engine VK Cup 2019–2020. Лучшие участники сезона, прошедшие отбор в феврале, к сожалению, не соберутся вместе на Новой сцене Александринского театра в Санкт-Петербурге, но в 17:05 начнут бороться за звание чемпиона VK Cup и призовой фонд:

• 1 место — 524 288 рублей,
• 2 местo — 131 072 рубля,
• 3 местo — 32 768 рублей.

Болеть за финалистов можно по ссылке.

А уже в 02.11.2020 17:35 (Московское время) вас ждут Div1 и Div2 раунды по мотивам задач финала VK Cup.

Задачи для финального раунда VK Cup подготовлены сотрудниками ВКонтакте PavelKunyavskiy, izban, YakutovDmitriy и Kurpilyansky, .tx, а также неповторимым 300iq. Дополнительные задачи для Codeforces раунда подготовлены Supermagzzz, Stepavly и MikeMirzayanov.

В подготовке и тестировании этого раунда помогали MikeMirzayanov, ecnerwala, Egor, hos.lyric, yosupo, lperovskaya, Stepavly, Supermagzzz, HIR180, qwerty787788.

Спасибо большое!

Удачи!

UPD И победителями VK Cup 2019-2020 становятся:

1. tourist
2. Endagorion
3. Merkurev

Поздравляем! Полная таблица результатов доступна по ссылке.

UPD:

Div.1 Scoring: 500 1000 1500 1750 1750 2500

Div.2 Scoring: 500 1000 1500 2000 2500 3000

UPD: Разбор

Вот-вот начнется второй тур IOI.

Результаты
Таблица от снарка

0:00 Кажется контест начался по расписанию. Как и в прошлый раз после первого успешного сабмита, выложу краткие условия задач (на этот раз с решениями).
0:11 В таблице появились первые баллы. Пока это 7 и 10 по первой. Это переборы в частных случаях. Но это повод выложить задачи.
0:19 Появилось 32 балла по 4-ой. Это разбор случая "нет данных исходно, только длина". Наши пока молчат. Думаю по этой задачи большинство будет сразу писать 100. Ну или хотя бы 80-90, если почему-то получился квадрат.
0:24 Появилось 38 по 5-ой и 4 по 6-ой. 4 это какой-то бессмысленный случай. 38 это осмысленное неоптимальное решние. Его думаю более-менее все сдадут.
0:30 vintage_Vlad_Makeev — первая 100 по 4-ой. Думаю сейчас посыпятся еще много 100.
0:32 Появилось 49 по 5-ой. Это чуть другое неоптимальное решение. (20 дают за что угодно, еще 18 за много записей и совсем много чтений, еще 11 за много чтений и совсем много записей).
0:38 V--o_o--V 32 по 4-ой? Думаю это 100 с багами, иначе совсем на него не похоже.
0:40 josdas 38 по 5-ой. Тоже полезно получить. Но скорее всего, если хочется золото, нужно 100, которое к этому решению имеет мало отношения.
0:41 yutaka1999 100 по 5-ой. От такой задачи логично ждать ранних сотен. Интересно насколько массовыми они будут.
0:43 V--o_o--V исправил баги, получил 100 по 4-ой.
0:45 vintage_Vlad_Makeev 0 по 5-ой. Интересно что это?
0:50 Исправил. Теперь 38. И появилась еще одна 100 по 5-ой. На этот раз у Ирана.
0:53 solonkovda 100 по 4-ой. SpyCheese 59 по 4-ой. Миша думаю скоро исправит, звучит 100 с багами. Думаю первую все наши все-таки сдадут. Вопрос в том, сколько времени потеряют.
0:57 Собственно исправил.
1:01 jcvb 100 по 5-ой. Итого 497. Думаю 557 будет в течении часа. А вот дальше интереснее.
1:02 solonkovda 38 по 5-ой.
1:09 manoprenko 80 по 4-ой. Уже два раза. Видимо все-таки это 100, которое почему-то получает TL.
1:10 josdas 59 по 4-ой. С нулем пока сидит demon1999 и super_azbuka. Думаю скоро что-то будет. Асхат тоже не любит писать частичные решения. Саша пишет все аккуратно, но часто медленно. Так что пока не выглядит чем-то страшным.
1:13 josdas 80 по 4-ой. Наверное скоро добьет.
1:16 Тем временем 8 сотен по 5-ой задаче. Причем у участников с достаточно разными результатами в первом туре. А vintage_Vlad_Makeev получил 0 по 6-ой.
1:19 manoprenko 38 по 5-ой. demon1999 100 по 4-ой. vintage_Vlad_Makeev 12 по 6-ой. Разнообразие. Ждем чего-нибудь от super_azbuka.
1:25 vintage_Vlad_Makeev послыает еще раз 12. Это разбор частного случая, когда все точки на диагонали. Так что возможно это больше баллов с багами, которые он еще найдет. josdas посылает первую то на 0, то на 80.
1:28 Еще три 200. popoffka yarek и SpyCheese.
1:31 Уже 15 сотен по 5-ой. Видимо это будет обязательным условием для золота.
1:38 По 6-ой задаче пока лучший результат 41 у gongy. Вроде 41 в итоге должен быть достаточно массовым баллом. А вот 60 звучит как возможность отыгать 7 или 15 баллов потерянных в 3-ей задаче первого дня.
1:41 V--o_o--V присоединился к группе в 200. Думаю он теперь будет долго думать над 6-ой. Надо, чтобы либо смог придумать, либо смог вовремя остановиться, чтобы успеть написать 60. Это тоже не очень быстро.
1:45 ko_osaga 60 по 6-ой. У него пока 0 по 2-ой. Посмотрим что из этого получится. Вместе с 172 по первому туре, это хорошая заявка на золото.
1:47 vintage_Vlad_Makeev 100 по 5-ой. И вышел на первое место по туру. Думаю 60 ему по силам, и он скорее всего их получит, когда придумает сразу. Пока из первой сборной отстает только Стас, который закопался в первой задаче. Надеюсь скоро разбрется.
1:52 super_azbuka 7 по 4-ой. Это либо эпичные баги, либо решил проверить понимание условия.
1:53 josdas 90 по 4-ой. Видимо действительно получает какой-то странный TL. Ну, надеюсь разберется. По первой 100 точно нужно.
1:54 jcvb 225. Новое первое место по туру. Гриша продолжает засылать 12 по 6-ей, Стас нули по 4-ой.
1:58 josdas добил 4-ую. Это хорошо. Это позволит успокоиться и заняться другими задачами. А то, с не 100 по первой, наверное было достаточно некомфортно.
2:00 Мы вот поняли, что 12 баллов, можно получать, если не учитывать, что перекрытия квадратов учитываются один раз, потому что в этой подзадаче это не важно. Это может быть обидно. Хотя, раз он получает еще и нули, вероятно все-таки баги.
2:06 solonkovda 12 по 6-ой.
2:10 super_azbuka сдал 59 по 4-ой. Ну, это уже не 0. Продолжает посылать. На этот раз 0.
2:14 vintage_Vlad_Makeev 16 по 6-ой. Причем именно 16, а не отдельное 4. Что-то нашел видимо, но не достаточно.
2:17 V--o_o--V послал 0 по 6-ой. Зная Влада, это похоже на 60 с багами. Ну или 41 с багами. Ждем.
2:19 Добил до 12. demon1999 получила 4 по 6-ой. Ну посмотрим.
2:21 manoprenko тоже получил 4.
2:25 manoprenko исправил на 25. У demon1999 несколько посылок на 4 и 0.
2:28 waterfalls вышел на первое место по туру с 241. И сдедом получил 260. В 300 я все еще не верю.
2:29 demon1999 получила 16 по 6-ой. А super_azbuka добил первую.
2:36 demon1999 продолжает посылать 16. Видимо хочет больше. Остальные не понятно что делают.
2:45 demon1999 добила 25. Влад и Миша посылают то, что уже есть. josdas получил 4 по 6-ой.
2:47 Саша продолжает посылать 6-ую. Хочет 41?
2:49 josdas получил 25 по 6-ой. Надо сделать что-то с 5-ой, и все будет хорошо.
2:51 jcvb 260. Чтобы его обгонять надо или сдать на 100 6-ую, или иметь 300 на 1 туре. Но у человека у которого 300, пока 170 и не понятно, что с ним будет дальше.
2:54 ko_osaga 260. Интересно, как много их будет в итоге.
2:59 Еще одна посылка на 4 от demon1999 по 6-ой. В целом, если пробьет, это будет очень круто. Но так можно потерять очень много времени.
3:06 Еще одно 25 по 6-ой от josdas. Это конечно подстава на этом контесте. Можно убиться об это, а не придумать вторую.
3:08 solonkovda внезапно сдал 70 по 5-ой. Это вообще что?
3:09 brandnewnode сдал 200. Итого с первым туром 500. Если сможет 60 за оставшиеся два часа — это будет серьезной заявкой на победу. После этого, чтобы его обонать надо либо V--o_o--V либо jcvb либо SpyCheese сдавать на 100 6-ую.
3:17 vintage_Vlad_Makeev после долгого перерыва 0 по 6-ой. Возможно написал что-то более умное и дебажит.
3:18 SpyCheese не посылал ничего уже почти два часа. Видимо думает. По 6-ой даже мелкие баллы набираются не очень просто. Уже скоро стоит начать писать то, что есть. Интересно он это понимает? Впрочем, 8-ое место ему почти гарантировано (я все еще считаю, что максбалл за тур будет 260).
3:19 Ага. jcvb 300. Он либо очень суров, либо слабые тесты.
3:28 SpyCheese 12 по 6-ой. Я все еще не понимаю как можно получить 12, а не 16, кроме как багами. Но почему-то очень много кто справляется. Остальные молчат, кроме Влада, посылающего нули.
3:31 josdas 41 по 6-ой, SpyCheese 25 по 6-ой. Это радует. Мише в целом 25 хватит для всего, чего надо и он может рашать дальше в свое удовольствие. Стас думаю скоро сможет 60 (если только не начать пихать nklog). Но ему все еще нужно сдавать вторую.
3:32 demon1999 опять посылает 6-ую. Это скорее плохо. Надо уже получить свои баллы по 5-ой. А то так можно и в бронзу вылететь.
3:35 vintage_Vlad_Makeev сдал 25 по 6-ой. Но видимо ему этого все равно не хватит. Следом посылка на 4. Так что наверное хочет больше.
3:36 josdas 60 по 6-ой. Надеюсь, он теперь отвлечется на 5-ую. Сейчас это еще не золото.
3:37 solonkovda 16 по 6-ой. Тоже пригодится. 70 + 60 наверное даже может хватит, с учетом первого тура. Но что-то еще сдавать точно надо.
3:43 Проснулся super_azbuka и получил 0 по 6-ой. Наверное что-то скоро поправит. Но почему все вторая сборная так не смогла в 5-ую задачу?
3:45 demon1999 60 по 6-ой! Не зря потратила 2 часа (или сколько? почти 3). Осталось получить что-то разумное по 2-ой. 38 даст хорошее серебро. 100 может быть даже золото. Если 425 будет не золотом, будет очень обидно.
3:49 vintage_Vlad_Makeev потихоньку вываливается из золота. Осталось 3 человека. Надо сдавать 41, а лучше 60. Посылки регулярные есть. Надеюсь, справится.
3:54 vintage_Vlad_Makeev смог 41. Обычно 60 из этого получается достаточно быстро. 41 может случайно не хватить, 60 уже должно. Надеюсь, остальные 5 человек, таки смогут пересилить вторую в ближайшее время. 4:00 Остался час до конца. Владу и Мише в целом уже мало что надо. Владу неплохо бы получить 60, чтобы его случайно не обонал brandnewnode. Мишу можно обонать, только сдав на 100 6-ую. Грише надо бы добить 60. Остальным, надо получить баллов за 2-ую. 38 на золото не хватит, нуля тем более. 4:02 josdas послал 2-ую на 0. И следом еще раз на 38.
4:04 4 балла от vintage_Vlad_Makeev по 6-ой. Насколько я понял, 41 можно получить 2 способами — либо за nklogn либо за n^2 (интересно что такое n^2, я не придумал). Если во втором избавиться от log — чисто техническая замена бинпоиска на стек, то с n^2 может случайно быть грустно.
4:10 V--o_o--V 41 по 6-ой. Кажется это защищает его от того, что его обгонит Миша с 60-ю.
4:12 super_azbuka 4 по 6-ой. Это конечно больше, чем 0...
4:15 super_azbuka 25 по 6-ой. Отдебажил таки. Теперь надо что-то по 5-ой.
4:18 Продолжает посылать 6-ую. Не 0 по 5-ой это не модно?
4:19 20 по messy от demon1999. Это видимо частный случай, когда поменялось 2 бита. Не слишком полезно для решения, но 20 баллов пригодятся.
4:21 manoprenko 41 по 6-ой. Но не серебро ему этого не хватит. Надо или 60, или прокачивать 5-ую.
4:22 vintage_Vlad_Makeev получил 23 по 6-ой, но в сумме это дает 60. Прошел какой-то очень странный набор подзадач. Интересно, как это получилось. Впрочем, не так важно. Этого должно хватить на золото.
4:24 manoprenko получил 60 тем же способом, что Гриша. А сам Гриша в это время получил нормальные 60 одной посылкой. Что вообще происходит?
4:27 solonkovda продолжает получать 12 и 16 по 6-ой. В целом, если он пройдет на 60, то может даже зацепиться за конец золота. Но не понятно что он пишет. Может быть это 25 или 41?
4:29 V--o_o--V добил 60. SpyCheese послал на 0. Может тоже скоро сможет 60?
4:31 SpyCheese 60! Теперь интрига ответит ли brandnewnode. У него за последнее время несколько раз 12 и 0. Миша продолжает посылать.
4:37 demon1999 38 по 5-ой. Это скорее всего гарантирует серебро.
4:41 Тем временем группа с vintage_Vlad_Makeev занимает с 15 по 20 места. Чтобы было золото, надо захватить 26 место. Должно хватить, иначе совсем жесть. Но во всяком случае, Гриша сделал более-менее все, что мог.
4:43 Таблице опять не очень 4:47 Поднялась. solonkovda сдал на 25 6-ую.
4:49 super_azbuka получает нули по 5-ой. Что интересно он хочет получить. 10 минут до конца. 4:53 Опять табличка упала.
4:54 V--o_o--V несколько раз послал 60, solonkovda несколько раз 25. Видимо по нашим единственная интрига смогут ли Стас или Саша сдать 5-ую на 100. Кстати 417 скоро рискует вывалиться из золота. Это будет очень обидно.
4:58 Опять легла. Интересно это только табличка, или с туром тоже проблемы. Никаких объявлений нет.
4:59 brandnewnode 60. Обидно, но что ж теперь. Мне сейчас пришел update за 13:55. Видимо есть некоторая очередь. Иду смотреть закончилось ли все.
5:00 В итоге 3 золота, 4 серебра, 1 бронза. И даже несмотря на большие группы после первого тура ни на один отрез не попала ничья.

4 Дан одномерный японский кроссворд с некоторыми уже покрашенными клетками. И даже наверное уже хватит на бронзу. Докрасить то, что однозначно. С этой задачей есть забавная проблема, что жюри вчера нашло ее на тимусе с ограничениями соответствующими подгруппе на 80 баллов. В итоге решили забить, т.к. на тимусе за последние 2 года ее сдали 11 человек, да и задача не слишком сложная, и если ты настолько суров, что решал ее там, то явно решил бы и так.

5 Дана реализация структуры данных, в которую можно сначала много раз добавить число, потом сделать некоторый предподсчет, потом много раз проверить есть ли в ней какое-то число. В результате бага, биты в добавленных числах перемешались одной и той же перестановкой. Надо с помощью запросов к структуре (nlogn на чтение и nlogn на запись, n — точная степень двойки), найти эту перестановку.

Писать тут нечего, насколько тривиально это придумать — не знаю. У меня ушло минут 15-20. Есть подозрение, что на золото может случайно понадобиться ее решать на 100.

6 Дано квадратное поле, в котором есть интересные точки. Нужно сфотографировать все интересные точки не более чем k квадратами, с противоположными углами на главной диагонали. Стоимость — количество клеток покрытых хотя бы одним квдаратом.

Если я праивльно помню разбалловку, то за n^2k можно получить 41 балл, за nk 60, на 100 надо избавиться от k в ассимптотике (я знаю решение, но считаю, что это нельзя придумать). Эти 40 баллов дают шанс в борьбе за 1 место топ-4 по результатам первого тура (в 260 у топа я уверен).

Про тур есть подозрение, что он может оказаться слишком простым. В частности, думаю 260 у топа будет за 2 или 2,5 часа. А вот будет ли вообще 300 — большой вопрос.

Вот-вот начнется первый тур IOI.

Результаты
Таблица от снарка

0:00 Судя по таблице контест начался. Условий пока не будет, их просили не выкладывать пока они не появятся на официальном сайте. После первого успешного сабмита напишу про задачи в общих чертах.
0:18 Пока я шел с завтрака появились первые баллы. В частности 100 у SpyCheese и 46 у vintage_Vlad_Makeev и manoprenko.
0:26 Тем временем V--o_o--V сдал первую на 100, josdas и vintage_Vlad_Makeev на 69.
0:30 peto159 получил первые баллы по второй задаче — 11. Это пербор за n! на подсчет ответа.
0:38 manoprenko сдал вторую на 34 (собственно та динамика за 2^n). vintage_Vlad_Makeev и josdas добили первую. А у меня почему-то не автообновляется таблица.
0:40 Na2a опять выходит на первое место с 134 баллами.
0:43 Mediocrity получил первые баллы по третьей задаче. 23 балла. Кажется это O(n⁴), но я точно не помню.
0:48 vintage_Vlad_Makeev 11 по второй. Странно. Почему не сразу 34.
0:53 Ну досдал до 34. Может баги какие-то.
0:58 super_azbuka давно уже сдал первую на 100, а я как-то не заметил.
0:59 solonkovda 46 по первой. Ждем еще чего-то от demon1999.
1:04 Nurbakyt Madibek (cf handle?) got score 46+34+31. Seems, for top contestant contest starts after 100+34+31.
1:08 vintage_Vlad_Makeev написал 3-ю на 23. и вышел на первое место. josdas вторую на 34, и присоединился к большой группе, делящей второе место. А я дописал софтину, которая следит за участниками. Сейчас приведу в приличный вид, и куда-то выложу.
1:11 demon1999 послала первую на 0. Наверное, скоро отдебажит. Интересно сколько это будет. 46, 100 или что-то хитрее? (наврал. Третью, а не первую. Внезапно.)
1:17 Появились несколько 30 баллов по второй. Это решение параллельной ветки задачи. Не перебор, а случай, когда ответ 0. 1:19 Тут какой-то скрипт на питоне. Его можно регулярно запускать, и если у вас linux, будт появлять уведомления про участников, перечисленных в коде. Если кто сделает вариант рабочий для windows, наверное будет хорошо.
1:29 demon1999 31 по третьей. Ну почему бы не начать так.
1:31 Положил скрипт на github. Не знаю ценно ли это кому-то.
1:32 DBradac выходит на первое место, сдав 2 задачу на 64.
1:34. У меня однго каждый раз отваливается автообновление таблицы постоянно?
1:36 solonkovda сдал первую на 100. Хотя бы 100 баллов есть уже у 108 людей, при этом больше 100 всего у 33.
1:42 Как-то ничего не происходит. Причем такое ощущение, что не только у наших. С таблицей все хорошо?
1:44 Ладно, что-то произошло. super_azbuka 30 по 2. 30 это на самом деле круче чем 34. Во всяком случае перспективнее для получения 64.
1:47 Stilwell 71 по 3-ей! Это квадрат, который я пока не придумал.
1:49 josdas получил 23 по 3-ей, присоединился к деленному третьему месту. vintage_Vlad_Makeev уже несколько раз послал 3-ю на 0, видимо написал что-то более умное, но пока баги.
1:51 Еще одно 23 от vintage_Vlad_Makeev. Интересно что это. Куб, но какой-то неудачный, по этому получающий TL? 1:58 manoprenko 31 по первой. Это еще что? 100 с багами? vintage_Vlad_Makeev продолжает спамить посылками на 0, 9 и 23 по 3-ей.
2:00 super_azbuka написал динамику по 2-ой. Получил 64. подгруппа на 30, выглядит как неплохое приемущество сегодня.
2:05 Еще одно 31 от manoprenko. Пора написать стресс-тест? Или это какое-то странно 69, которое почему-то получает TL?
2:06 Получил 69, поднялся выше группы с одной сотней. Возможно эти три балла разницы могут быть ценны в итоге. solonkovda 0 по 3-ей. Видимо баги, надеюсь скоро найдет.
2:08 Итого, за 2 часа Гриша и Стас видимо сдали обязательный минимум и разбираются что делать дальше. У Гриши видимо есть что-то по третьей, но пока не получается превратить это в баллы. Асхат вырвался вперед засчет решенной группы на 30 во второй, надо сейчас собрать быллы в третьей, и думать что дальше. Денис дебажит третью. Что делают Миша Путилин с Владом не очень понятно. Видимо думают над решениями, они часто любят собирать баллы в последний момент. И иногда из-за этого огребают. Миша Анопренко потихоньку собирает баллы. Что делает Саша я тоже пока не очень понял. Обычно она вначале собирает все простые баллы все-таки.
2:10 Пока я это писал demon1999 получила 69 по первой, а solonkovda отдебажил 23 по 3-ей.
2:12 Что-то мой скрипт нашел много странных сабмитов, в любом случае не улучшающих баллы (какие-то id поменялись?). А vintage_Vlad_Makeev победил 31 балл по 3-ей.
2:15 Видимо действительно поменялся формат данных в таблице. А demon1999 превратила 69 в 100. Ждем 34 по второй? Это вроде достаточно быстро.
2:17 А команда Китая резко вырывается вперед. Еще одним человеком сдавшим третью на 71, и еще одним аж на 97! 97 это видимо недостаточно оптимально написанное полное решение. Ну либо жюри решило отсечь линию от nlogn или еще что-то такое же странное.
2:23 Еще одно 97 по 3-ей от Китая.
2:24 solonkovda 34 по 2-ой. Собрал обязательные баллы, посмотрим что будет дальше.
2:27 manoprenko сдал первую на 100. Теперь первую задачу сдали все 8 российских участников.
2:32 demon1999 0 по 2-ой, V--o_o--V 9 по shortcut. Это что-то умное с багами видимо?
2:40 V--o_o--V 38 по 3-ей. Это видимо куб без лишний логарифмов?
2:44 V--o_o--V получил 71 по 3-ей, demon1999 34 по 2-ой. Ждем, что SpyCheese возьмет пример с Влада?
2:48 Один из Катайцев добил 97 до 100.
2:53 V--o_o--V solonkovda vintage_Vlad_Makeev сабмитят решения по 3-ей на меньше баллов, чем у них есть.
3:03 Тем временем несколько больших групп участников приближаются к границе медалей. Это не очень хорошо, т.к. по правилам, бронзовые медали округляются вниз. То есть, если большая группа захватывает половинное место, то никто из них не получает медаль. А еще сложно все считать, потому что вторая российская команда при этом не учитывается, а они все выше.
3:05 V--o_o--V продолжает посылать нули по 3-ей задаче. Пихает какую-то лажу на больше чем 71 что ли? Он это в целом любит. 3:07 SpyCheese тоже сдал 3-ю на 71. Молодец. Теперь надо все-таки получить 34 по 2-ой, и спокойно думать что делать дальше. Хотя, зная Мишу, скорее всего сейчас тоже начнет пихать 100, либо думать над чем-то больше 34 по 2-ой.
3:13 V--o_o--V 97 по 3-ей. Интересно, затолкал или что-то нормальное. Тем временем можно заметить фейл в разбалловке. 134 получается аж тремя способами, а это очень массовый балл.
3:17 V--o_o--V продолжает пихать 97 до 100. Там ограничения 300000 и 1000000 не понятно речь идет про неассимптотичесие оптимизации или что-то хитрое.
3:18 vintage_Vlad_Makeev взялся за 2-ую. Это хорошо. Может скоро увидим 64 или 100? Впрочем, там на 64 можно придумать много неверных жадностей.
3:19 super_azbuka сдал 3-ю на 23.
3:25 solonkovda присоединился к Асхату на 6-ом месте с разбалловкой 100+64+23. Итого сейчас 6,5 наших участников в золотых медалях. Забавно. Интересно как долго такое продержится. josdas вылетит уже достаточно скоро. demon1999 и vintage_Vlad_Makeev мне кажется к концу контеста, если ничего не сдадут больше. Остальным может и хватить того, что есть. Но большого отрыва, не будет, так что видимо все будет решать второй тур.
3:35 demon1999 и super_azbuka послали 3-ю на 0. К чему бы это?
3:38 SpyCheese 0 по 2-ой. Ждем скоро чего-то интересного.
3:47 vintage_Vlad_Makeev пробил 38. Не знаю насколько это ценно для дальнейшего продвижения, но тоже пригодится.
3:50 josdas смог получить 31 по 3-ей, и вернулся в группу золотых медалей, но не думаю, что на долго, если не сдаст что-то еще. 3:53 Вроде SpyCheese и V--o_o--V обычно начинают писать частичные решения как раз где-то за час до конца, так что может минут через 15 что-то увидим от них.
3:56 josdas сдал 38 по 3-ей. Мне кажется, что группа с 172 будет пересекать границу золотых медлалей после первого тура. Но в любом случае отрыв в обе стороны будет очень маленький.
4:00 30 от SpyCheese по 2-ой. Сделать из этого 64 уже дело техники и 15 минут времени. Вероятно, скоро справится. Если сделает — будет на первом месте с отрывом в 1 балл.
4:11 V--o_o--V 100 по 2-ой. Внезапно, но радостно. Посмотрим чем ответят остальные. И все еще ждем 64 от Миши.
4:15 solonkovda и demon1999 посылают 3-ю на те баллы, которые уже есть. Может что-то из этого получится.
4:17 SpyCheese видимо решил, что 64 это слишком скучно, и полочил 100. Весело.
4:19 31 по 3-ей. Пригодится. Скорее всего это даст ему попадание в золото
4:21 manoprenko ничего не посылал с 3:07. Интересно чем он занимается. 23 то хотя бы надо получить по третьей.
4:27 V--o_o--V потихоньку пихает свои 97 на 100, остальные затихли. Осталось пол часа.
4:28 manoprenko наконец-то сдал 23 по 3-ей. Группы 172 и 165 на границе золотых медалей продолжают расти.
4:34 brandnewnode 300! 4:37 Через 8 минут будет отменено правило про посылку раз в минуту. Скорее всего после этого таблица может начать сильно отставать. От наших ничего ценного не слышно. Влад и Денис продолжают пихать третью. От резницова была одна посылка по 2-ой, на 0. Остальные давно не посылали.
4:40 А еще большая группа 111 баллов, дошла до границы бронзы. И не очень высоко над ней еще более большая группа 134. Очень нужна размазывающая задача во второй тур. Причем размазывающая всех, а не топ.
4:43 Табличка прилегла. Это такая заморозка?
4:44 Вроде вернулась.
4:49 Хм, а может я и слишком оптимистичен про границы. Сейчас большая группа с 172 баллами начинается на 21 месте (2 участника из второй российской команды не влияют). Всего золотых медалей 27. Может 6 человек и найдется кто их обгонит. Но смысл это меняет мало. Отрыв между грницей золота и даже группой с 157, почти на нижней границе серебра очень маленький. Все будет решать второй тур.
4:55 SpyCheese послал 0 по 3-ей. Что-то написал и баги? Денис и Влад продожают пихать, но пока безуспешно. 4:56 Интресно какого размера сейчас очередь?
4:57 Табличке явно плохо. Интересно как всему остальному в системе.
5:00 Табличка как-то все. И теперь отдает там вход в pcms??? Но не думаю, что за последние пару минут что-то кардинально поменялось

Краткие условия задач.
1 Решить рюкзак с большими ограничениями и весами. Нужно попасть суммарным весом в интервал. Дополнительное ограничние — интервал длиннее, чем разность макисмального и минимального веса. В задаче нужно придумать правильную жадность.
2 Дано множество пар (s, t) Нужно расположить их в некотором порядке. Стоимость — . На 40 с чем-то баллов, динамика за 2ⁿ. На еще около 30 баллов проверить, что ответ 0 с большими ограничениями. Это какая-то жадность. На полный балл, как решать я не понял.

3 Дан взвешенный граф в форме бамбука, у которого от каждой вершины которого отходит максимум еще одно ребро. Надо провести еще одно ребро фиксированной длины между вершинами самого бамбука, чтобы минимизировать диаметр. Вроде понятно как делать за куб, за это будет где-то 40 баллов. Дальше случается квадрат, линия (или nlogn), и еще 7 баллов на попихать. Как решать что-то быстрее куба я пока тоже не понял.

Всем доброго дня и здравия. Думаю, многие на этом сайте слышали про инструмент для подготовки задач, разработкой которого занимается MikeMirzayanov. Имя ему — polygon.

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

Утилита опубликована на github вместе с инструкциями по установке. Буду рад любым новым фичам и предложениям.

Известные проблемы:

• Код протестирован не достаточно хорошо, могут быть баги.
• Устанавливающий скрипт иногда ведет себя странно. Буду рад советам всех тех, кто лучше меня знает питон. Также вызывает интерес, какие бывают более удобные способы распространения.
• Иногда потеря сессии не обнаруживается и скрипт падает со странными ошибками, relogin помогает излечить эту проблему.
• Парсинг html страниц может быть недостаточно устойчив к изменениям в полигоне. С нетерпением ждем более хорошего api от MikeMirzayanov и команды Сodeforces.

Доброе утро!

Условия
Результаты
Результаты от снарка

0:35 тур начался точно по расписанию, но таблица результатов недоступна. Можно почитать условия
0:41 Stefano Maggiolo утверждает в своем twitter, что "у них есть техническая проблема с публичными результатами". Вероятно, с самим контестом все хорошо.
0:46 Появилась таблица. Пока V--o_o--V 17 по horses (видимо проверил понимание условия, или 100 с багами), SpyCheese получил 36 по soring. Это какой-то разбор частных случаев.
0:50 Судя по тому, что SpyCheese сразу же перепослал на 36 еще раз, возможно он пишет что-то более интересное.
0:52 На текущий момент есть несколько сотен по horces, две 54 и много 36 по sorting и одна 25 по towns.
0:56 netman тоже получил 100 по horses.
0:57 budalnik и SpyCheese тоже получили 17 по A. Интересно, это массовые баги или после первого тура все решили писать частичные решения. У V--o_o--V еще одна посылка на 17.
0:59 HYPERHYPERHYPERCUBELOVER получает 200 за второй тур и выходит на уверенное первое место c суммой 500 за два тура. Третья задачка выглядит сильно сложнее первых двух. Во всяком случае последний subtask.
1:01 Alex_2oo8 получил 100 по horses.
1:03 у budalnik тоже еще две посылки на 17 по horses.
1:05 V--o_o--V с 6-ой попытки 34 по horses. Решение за квадрат на стресс-тест?
1:06 И еще раз 17 от Влада. Ну да, он же не любить стресс-тесты, я вспомнил.
1:09 А вообще, полный feedback на все послыки развращает. Когда были токены, хотя бы участник пинался их отсутствием начиная делать фигню. Тем временем у Влада уже 8 посылок по horse.
1:13 SpyCheese 54 по horses. Это дополнительно разобранный случай. Однако он существенен в задаче. Довести ее после него — чисто дело техники.
1:15 У budalnik получил 34 по horses. Неужели у них нет решения в основном?
1:17 У Ruchiose 0 100 35. Это неплохая заявка на выход на первое место по туру в скором времени. За первый тур у него 205.42
1:20 Кажется с очередью пока получще чем вчера. Посылки появляются в таблице в течение минуты.
1:21 Тем временем LHiC подбирается к границе золота с гордым нулем за второй тур. Пока это мало что значит, на само м деле. Он пишет частичные решение очень поздно, но стабильно.
1:25 V--o_o--V досдал horses на 100. Молодец.
1:35 У SpyCheese загадочная посылка, прошла 1 и 3 подзадачу по horse. К чему бы это.
1:40 Появилось первое 51 по towns. Я умею 61. Кстати, кто-нибудь расскажите как решать последнюю подзадачу.
1:43 LHiC получил 37 по horses (тоже 1 + 3 подзадачи). Похоже на 100 с багом или разбор случаев. И то, и то, неплохо, потому что случай третьей подзадачи ключевой.
1:46 SpyCheese 100 по horses, выходит на 5 место.
1:49 На месте budalnik кажется полезным получить 34 36 25. Чтобы иметь запас, проверить понимание условий и улучшить нервое состояние. Интересно, что он делает сейчас. Посылок давно как-то нет.
1:50 LHiC 100 по horse и выходит на третье место!
1:55 V--o_o--V 100 по sorting и выходит на третье место! Итого сейчас ребята занимают 3,4,7 и 134 место. Ну, тоже неплохо....
2:01 matrix и JeBeK из ирана получили по 200 за второй тур с 115 и 59 за первый. Забавно как-то. #КоляБериПример
2:03 ainta 61 по towns и выходит на 3 место с нулем по sorting. Корея в этом году жжет. Три человека в золоте, 1 и 3 место на текущий момент.
2:06 V--o_o--V 25 по towns. Тоже полезно, но содержательная часть задачи еще впереди.
2:09 У budalnik две посылки на 17 по horses. Видимо написал полное решение и дебагает? Не должно быть долго с уже написанным квадратом.
2:13 SpyCheese пишет что-то по towns. Пока получил 0.
2:23 budalnik 36 по sorting. horses видимо решил отложить. Тоже подход.
2:25 budalnik 54 по horses. Ключевая 3 подзадача пройдена. #КоляДавай
2:33 SpyCheese добил towns на 25. Кажется все простые баллы Миша теперь собрал. Ждем, что будет дальше.
2:36 LHiC получает 100 по sorting, и выходит на второе место. Получить 25 просто, но врядли Миша это будет скоро делать. Видимо первое место будет решаться на том, кто решит towns на 100. Ну или 61 будет достаточно для деленного. Хоть кто-то из троих с 300 в прошлом туре сделает же 261. Еще конечно может быть 572.02 от Haghani но мне кажтеся маловероятным, что он сможет 300, а остальные нет. Ну и если так получится, то первое место будет вполне заслуженным.
2:40 SpyCheese продолжает посылать towns. Видимо он умеет лучше, чем 25.
2:42 budalnik продолжает долбить horse. Интересно, что такое было 34, если он до сих пор не поймал все стресс-тестом.
2:44 SpyCheese 35 по towns. Это хорошо. еще бы 100 по scoring написал.
2:47 Haghani сдал sorting на 100, и вышел на второе место. Кстати, он уже гарантированно получает золотую медаль. Для этого надо набрать строго больше, чем 506.91. Хотя на практике конечно сильно меньше. Я думаю граница золота будет где-то 440. 2:51 LHiC получил 25 баллов по towns, чем также гарантировал себе золотую медаль.
2:58 V--o_o--V 61 по towns. Молодец. Надеюсь он приятно удивит, добив эту задачу за оставшиеся два часа. (Я все еще не знаю как ее решать на 100, и буду рад, если кто расскажет)
3:00 Ух ты ж. Суровый Владислав добивает ее на 100 сразу! У нас есть первое 300 в туре. Правда кажется формальной гарантии золота это ему все еще не дает, но я посмотрю на 27 человек с 300 на этом туре.
3:04 А у budalnik тем временем уже 14 посылок по horses, проходящих какое-то подмножество первых трех подгрупп.
3:09 После трех часов V--o_o--V 300 (505.42), LHiC 225 (525), Meirambek 179 (368.9), Nik_Storm_2010 174 (379.42), bekzhan29 174 (363.55), SpyCheese 171 (421.51), Na2a 154 (343.55), BigBag 136 (325.72), Maestr0 136 (325.55), netman 120 (224.45), Ferathorn 108 (282.73).
3:29 jqdai0815 сдал sorting на 100 и подключается к борьбе на towns.
3:32 SpyCheese потихоньку сползает к границе серебра и золота. Того, что есть сейчас явно не хватит, надо сдавать что-то еще. Ждем 100 по sorting или 61 по towns. Ну или 100 сразу по towns, мало ли. 3:33 LHiC сдал towns на 35 и вышел на деленное первое место. Хотя это мало что меняет в реальности.
3:34 budalnik продолжает долбить horse. Уже 18 попыток.
3:49 Пока я отошел budalnik 13 по towns, SpyCheese 74 по soring. Мише даже может этого хватить на золото, но не понятно, лучше сдать что-то еще. И HYPERHYPERHYPERCUBELOVER сдал towns на 48 и обогнал LHiC. Ждем ответа.
3:55 budalnik еще три попытки на 17 по horse. Нучоза :(
3:57 Додолбил! Отставание от границы серебра сейчас 36 баллов. Это достаточно много и еще увеличится. Но таки досданная задачка, может дать хороший моральный подъем.
4:02 LHiC 61 по town! Теперь, чтобы его обогнать нужно 300 на втором туре (и быть в топ-4 на первом).
4:05 SpyCheese 100 по sorting! Молодец.
4:06 Появилось второе 300 на туре. В этот раз yutaka1999. Теперь делят с Владом 7-ое место.
4:13 LHiC после своих 61 не посылает. А HYPERHYPERHYPERCUBELOVER регулярно посылает что-то, но получает 25 и 35. jqdai0815 только что получил 0. Haghani не посылал ничего по этой задачи с начала третьего часа. Больше претендентов на первое место нет.
4:22 SpyCheese 48 баллов по towns. budalnik получил еще 36 по sorting. Надо 100. Ну или для начала 74 и что-то по towns.
4:25 И еще раз 36 от budalnik.
4:36 300 от ecnerwala и 74 у budalnik по sorting.
4:37 Абсолют! Jeehak Yoon HYPERHYPERHYPERCUBELOVER.
4:42 JoeyWheeler тоже получил 300 за второй день.
4:44 budalnik 100 по sorting и это промежуточное серебро. Go Go Go!
5:00 Очереди тестирования нет, контест закончился. Хотя результаты в мониторе называются неофициальными, они наверняка не будут отличаться. Всем спасибо!

Начался первый тур IOI2015

Результаты
Результаты от снарка
Условия

0:19 Кажется я наконец-то поборол проблемы с сетью, и попытаюсь начать рассказывать о происходящем. На тукущий момет есть баллы по самой простой задаче тура (boxes). Четыре сотни, и много раз по 10. 10 это что-то простое, не очень имеющее отношение к задаче. Первые 100 были за 13 минут у Alex_2oo8.
0:24 45.45 по второй задаче от Maestr0. По системе оценки задачи не особо понятно что это. (Да, балл по этой задаче не целый). 0:27 Несколько по 34 балла, по третьей. Это жадность без струтуры, на 100 нужно добавить какое-то двумерное дерево (условия уже на подходе)
0:31 Число сотен по boxes растет. Больше ничего особо интересного не происходит.
0:33 Первые баллы от российских участников. 100 по boxes от V--o_o--V
0:40 100 по scales от Žiga Željko. Хм. Сотни по двум задачам за 40 минут немного пугают.
0:52 Начали появляться массовые 45.45 и 55.55. Вероятно скоро на первом месте будет 100 55.55 34. А вот дальше начнется самое инетресное. Еще бы из российских ребят кто-нибудь что-нибудь сдал.
1:14 На текущий момент 23 человека полуичли хотя бы 100. Ничего интересного пока не происходит.
1:21 Судя по тому, когда сделаны сабмиты, всплывающие сейчас, очередь тестирования где-то 15 минут. Это как-то грустно.
1:24 У нас сменился лидер. IvL обогнал предыдущего лидера на 0.2 балла!
1:25 Тем временем, у LHiC 100 по boxes, у SpyCheese 71.42 по scales.
1:34 jasonyik выходит на 1 место, получив 100 45.45 34. Через небольшое время к нему присоединился AllCatsAreBeautiful 1:49 V--o_o--V получил 55.55 по scales, jasonyik 71.42 по scales и вышел на первое место. А у меня опять отвалился интернет.
1:50 У budalnik были 2 посылки на 0 по teams. Интересно что бы это значило. Видимо пишет решение больше, чем на 34.
1:53 34 по teams думаю еще долго надо будет ждать от всех 4-ех. Все не любят писать частичные решения в начале. 1:56 Еще одна посылка Коли на 0. Да что же такое. (А еще большое фи, авторам CMS, у которых не все посылки попадают в history)
2:01 SpyCheese сдал boxes на 50. Это решение за квадрат. вроде бы, сделать из него линию не очень сложно.
2:02 Takahiro Masuda сдал teams на 77. Это может быть либо лишний лог в решении, либо просто неоптимально написанное. 2:06 budalnik сдал teams на 34. Решил написать стресс-тест?
2:07 Takahiro Masuda досдал teams на 100. Это серьезная заявка. Тем временем открыты все задачи.
2:08 А SpyCheese сдал boxes на 70. Интересно что это. NlogN вместо линии?
2:14 SpyCheese досдал boxes.
2:15 А Белорусы, Украинцы и Казахи как-то кучкуются около 36 место. 7 подряд.
2:20 Пропала 100 по задаче scales. Кто-нибудь заметил еще проблемы? Интересно, массовое что-то или просто у этого человека что-то странное?
2:24 Барбара Кускова kuskova вырывается на четвертое место, получив 100 по boxes.
2:31 Прошла половина контеста. Через часик ребята начнут посылать частичные решения. Не очень приятно, для наблюдающих за ними.
2:34 Появилась 100 по scales у Hristo Venev. 0 100 34. Кажется для него делать что-то пободное типично.
2:37 budalnik послал scales на 0. Думаю скоро будет что-то более разумное.
2:38 bekzhan29 теперь делит 6 место с 100 55.55 34. 55.55 баллов за scales становятся популярны.
2:41 И снова смена лидера, теперь на первом месте Haghani с солидным отрывом в 43 балла.
2:45 LHiC получил 21 по teams. Это даже похоже на жадность без структуры.
2:46 А budalnik получил 10.35 по scales. Молодец.
2:47 Hristo Venev решил не отпускать Haghani слишком далеко, досдал boxes на 100 и теперь занимает второе место с отставанием в 14.42 балла. 100 100 34.
2:58 LHiC получил 100 по teams. Видимо дописал или добебагал структуру.
3:06 budalnik получили 10 по первой. Я все же надеюсь, что это 100 с багами.
3:09 Интересно, чем занимаются V--o_o--V и SpyCheese? Уже больше часа нет посылок.
3:17 На второе место выходит Nonthakit Chaiwong получив 45.45 по scales. Отставание от первого места меньше трех баллов, а 100 по teams это серьезная заявка на успех.
3:24 budalnik прошел только 3-ий subtask по boxes. Что, простите?
3:38 Как-то уже долго ничего не происходит.
3:45 Кажется опять образовалась очередь. Во всяком случае в табличке всплывают сабмиты 20-и минутной давности.
3:46 LHiC получил 71.42 и вышел на деленое первое место.
3:47 budalnik начал чтоли мерджить посылки по boxes??
3:48 LHiC получил 73.51 по scales. Это даже может быть залогом первого места на туре, но непонятно насколько даст приемущество в сумме. SpyCheese получил 21 по teams. По крайней мере, вероятно у него есть праивльная жадность.
3:50 V--o_o--V получил 71.42 по scales. А получить не 0 по teams?
3:52 Задача scales с переменным успехом выполняет свою роль по разнообразию количества баллов. Достаточно много участников набрали 71.42, 55.55, 45.45. А вот 73.51 набрали только SpyCheese и LHiC. Совпадение? Не думаю.
4:04 У SpyCheese 77 по teams, 34 по teams. А budalnik похоже мерджит boxes. Получил 45.
4:08 Кажется пока что, чтобы хорошо писать этот тур, в сборной России надо быть Мишей.
4:09 budalnik 38.78 по scales. Это уже даже похоже на бронзу!
4:37 Ничего не происходит, мы перемещаемся в место проведения соревнований.
4:46 LHiC 300 зпт умничка тчк
4:47 HYPERHYPERHYPERCUBELOVER 300.
4:52 jqdai0815 300. Кажется что мы все еще получаем сабмиты пятнадцати минутной давности.
11:39 местного времени: в таблице результатов пока что не появились посылки за последние 5 минут, но budalnik как и обещал принес еще 15 баллов на boxes.

Вкратце о задачах.
boxes. Есть 10^7 команд на круге размера 10^9. Надо каждой команде разнести по сувениру. Сдвиг на один в любую сторону занимает секунду. Все сувениры лежат в 0. Разнести все и вернуться в 0 за минимальное время.
scales. Есть 6 монет разного веса. Расположить их по возрастанию веса с помощью как можно меньше запросов "самая легкая/тяжелая/средняя монет из трех", а также "самая легкая из трех, которая тяжелее четвертой, или самая легкая, если таких нет".
teams. Есть N человек. У каждого есть ограничения с двух сторон на размер команды в которой он может участовать. Есть Q дней. В каждый день есть сколько-то задач, для которых нужны команды известного размера. Узнать в какие дни, можно сформировать комнады, а в какие нет.

Two years ago (or something like that) GCJ problemsetters announced commandline-tool, which can download input, make submissions, and view current contest state. It support was not very long, but before last contest it worked as is (at least downloading and submitting).

Before last contest I discovered, it can't login to google account because it get HTTP 404 error. Any ideas what got wrong and how to fix it?

Also I'm interested if anyone else, except me, use it?

Good time of the day.

As some of you know, yeputons and I have an archive of IOI-tasks. While preparing it, we had understood, that we have no resources to prepare graders for all languages,so we want to find a way to write a grader only for C, and to link other languages to it.. Also, I think it's better to have one grader and adapters to avoid code duplicating, which can cause errors.

There were some problems with linking Pascal, but they were mostly solved. I'll write about one unsolved problem further. It would be very good if someone have ideas how to solve it.

Next year Java will be available on IOI. So I tried to write Java adapter for graders. Here is one for the problem 2010.cluedo. I think this one works well.

I publish this because I think someone else can be interested in it. Also I have some problems, which I don't know how to solve. Probably someone here can solve them.

First of all, we need to include jni.h. But it doesn't belong to gcc library path. So we need to set path, which depends on computer settings (path to java, to be more precise).
Also this way is quite complicated to compile. I don't know how to do this in some IDE, which is probably used by participant using java. And participant probably don't know what is jni, and how to do something like this.
The same problem happens to pascal. Also there is one extra problem. FPC needs libc to link this. And I don't know way to find libc on windows. libmsvcrt.a from MinGW is ok. But how to find it on participants computer? And what to do, if he is using some other compiler? Also, participant needs C-compiler to use Pascal, and that is not very good.

All this problems are not really important on competition (as we know settings of participants computers), but if we use on-line judge for it we will face the above-mentioned problems.

I hope there is someone from ISC or some other IOI structures, who can help with it, who is reading Codeforces. Anyway, if you have some ideas how to make this better, or any comments, I will be very interested in it.

Примерно через 5 минут по плану должен начаться второй тур IOI 2014.

Полезные ссылки:
Результаты
Результаты от снарка
Видеотрансляция
Таблица по странам от Снарка
Блог про первый день

Меня попросили не выкладывать условие, пока не будет официальной версии на сайте олимпиады, но обещали сделать ее существенно быстрее, чем на первом туре. Увидим.

Для тех кто не следил за первым туром напоминаю: есть 6 полных баллов, 1 261, и 19 256. Количество золотых медалей — то ли 26, то ли 27. То есть борьба за них будет достаточно суровой.

0:00 Ух ты. И правда быстро выложили.
0:05 Пока ничего не произошло. Я пока пишу какие-то мысли про задачи.
0:12 Еще какое-то количество 10 и 20 по гондолам.
0:17 По гондолам появились 25. Кажется это уже не только первая из трех задач, которые там есть. Впрочем, кажется что две из трех тривиальны совсем.
0:26 zemen 20 по гондолам. emachaidze 23 по holidays. Видимо это разбор случая, когда начало в нуле. Или что-то большее с багами (например забытый long long).
0:27 fabik 27 по friends. Это кажется разбор частных случаев.
0:29 Po-En Chen 55 по гондолам. -imc- 10. Это выглядит как 20 с багами на самом деле.
0:30 KAN 20 по гондолам. А -imc- еще 10. Бывает.
0:33 HYPERHYPERHYPERCUBELOVER 75 по гондолам. Когда же будут 100? 0:34 Miras321 55 по гондолам. А у -imc- еще 10 :(
0:35 zemen 55 по гондолам. scott_wu 35 по друзьям. Это вроде бы тоже разбор случаев.
0:37 С четвертой попытки у -imc- все-таки 20 по гондолам. Интересно, что это было.
0:38 Po-En Chen 90 по гондолам.
0:40 Добил до 100. В целом, эту задачу все должны добить. Вопрос в том, сколько времени на это уйдет. У zemen вот уже 75.
0:42 AstroConjecture выходит на первое место в 55 по гондолам. KAN 75.
0:44 Появилось несколько 47 по holiday. Это разбор частных случаев + перебор. На самом деле первые 5 подгрупп в ней имеют мало отношения к полному решению.
0:45 Miras321 100 по гондолам. zemen 90. Если цель этой задачи была скушать время, она с ней справляется.
0:47 sivukhin 15 по гондолам. O_o это как? 0:50 KAN 100 по гондолам. Теперь ему придется думать.
0:51 Algiz 47 по holiday. Таких уже достаточно много. Это все кроме собственно задачи.
0:52 dhh1995 выходит на первое место с сотней по гондолам. У -imc- 55. У zemen еще 90.
0:55 zemen 100 по гондолам. Ждем Никит. Кстати, если кому интересно, автор этого треша — misof.
1:00 Xu и Yu закрыли гондолы и теперь три китайца делят первое место с 400. К KAN присоединилось еще два человека с 356.
1:03 -imc- 75 по гондолам. Кстати о Китайцах. Кажется ребята говорили, что после первого тура, команда США учила команду Китая традиционной китайской карточной игре.
1:05 sivukhin 10 по гондолам?! Как-то они не пошли.
1:07 zemen разобрал один из частных случаев в друзьях и вышел на первое место по туру со 119.
1:08 sivukhin 25 по гондолам. А zemen разобрал еще 2 частных случая. Можно еще написать перебор, паросочетание в двудольном графе (это будет 69 кажется) и начать решать задачи.
1:09 scott_wu решил, что ему не нравятся гондолы и сдал друзей на 100. В целом, это тоже не очень сложно. У -imc- еще одно 75.
1:12 А у sivukhin еще 25.
1:14 scott_wu начал заниматься гондолами. 10 это не самое хорошее начало.
1:15 На самом деле, происходящее сейчас имеет не очень много смысла. Я верю, что большая часть участников претендующих на золото получит 100+46+47. Дальше будет не очень большая группа которая из 46 сделает 69. А на оставшихся двух подзадачах все будет решаться. Впрочем, иметь на них 3,5 часа приятнее чем 2.
1:17 А у -imc- еще одно 75.
1:19 scott_wu вышел на первое место по туру с 40 по гондолам и 100 по друзьям. А у sivukhin еще 25.
1:21 уже 65. Минут через 15 наверное будет 100. Дальше 47 вообще не проблема. А вот дальше...
1:22 И еще 25 от sivukhin. Сколько можно :(
1:23 KAN 0 по друзьям. Вероятно это 100 с багами. Или неправильное решение. Во всяком случае, на вид в частичных ошибаться негде.
1:27 Miras321 пошел набирать частные случае в друзьях.
1:32 Po-En Chen выходит на 2-ое место с 200 за второй тур!
1:33 scott_wu присоединился к 200 за второй тур. 47 думаю будет быстро. Вопрос придумает ли оставшуюся подзадачу.
1:35 -imc- додолбал гондолы. Остался sivukhin. Как-то у него не пошло совсем.
1:38 Американцы первые все сдали гондолы.
1:43 sivukhin отложил гондолы и получил 46 по друзьям. Сменить деятельность иногда помогает в таких случаях.
1:48 У KAN еще один 0 по друзьям. Кажется самое время получить 11 и стресс-тест.
1:50 ecnerwala кажется первый написал паросочетание в friends. Кажется получить 100 это не поможет.
1:51 А у KAN еще один 0.
2:00 Спустя два часа отсечки медалей 350-245-139. Думаю к концу отсечкой золота будет примерно 449.
2:01 Baklazan третьим получил 200 за второй тур.
2:11 Как-то все наши затихли. Опять до конца третьего часа?
2:13 Кстати scott_wu тоже не спешит получить 47. А вот Po-En Chen уже набрал 24
2:15 KAN прошел только третий subtask в holiday. Это как интересно? Мне казалось они вкладывают тесты, а первая подгруппа подмножество. Ладно, похоже на мелкие баги, скоро поправит.
2:17 Miras321 сдал паросочетание в friends.
2:21 Ух ты. Там 4 по 100 по holiday. Или эти ребята очень суровы, или тесты отстой. Я боюсь, что все-таки второе. В таком случае вероятно 300 будет. В том числе 100 есть у svanidz1
2:29 zemen тоже разобрал двудольный граф в друзьях.
2:31 У KAN 24 по holiday. Забавно, я не умею решать третью не решив вместе с ней вторую, хотя формально по ограничениям они не вложены.
2:33 Еще одна сотня по holiday. Видя монитор, все бы понеслись пихать. А так...
2:38 Кажется отвалился scoreboard. Надеюсь, это единственное, что сломалось.
2:45 Судя по таблице, первый тур потерялся, а второй перетестируют :)
2:46 Ну вот, теперь ничего не понятно. Интересно, а там откуда я выкачиваю список сабмитов тоже треш?
2:49 Кажется все починили. За этого время случилось 550. От наших вроде ничего.
2:54 А, нет. От Кости еще 56 по друзьям, от sivukhin 24 по holiday и 35 по гондолам. Пока я писал 24 превратились в 47. А -imc- уснул?
2:58 sivukhin 55 по гондолам. Скорее всего 100 по ним ему на золото уже хватит, хотя и впритык. Лучше бы что-то еще.
3:00 Тем временем -imc- вылетел из серебра. Интересно, что он делает последние 1.5 часа.
3:03 И у нас есть первый total! Поздравляем scott_wu. А в тесты в holiday я все-таки не верю.
3:05 Все-таки с табличкой что-то не то. После Ctrl+F5 total исчез.
3:07 О. Вернулось. Ну ладно. Ерунда какая-то. А от наших все ничего.
3:09 KAN подтвердил предположение, что тесты полный отстой. Все подзадачи, кроме второй. Думаю ее он сейчас просто заглушит.
3:20 Надеюсь тестирующей системе не так плохо, как табличке.
3:21 Кажется табличка не обновляется с 3:08
3:29 В json с сабмитами мне пришло 100 от KAN по holiday. Надеюсь, он разберется что у него там с друзьями.
3:31 Еще пришло 19 по friends от KAN и 47 по holyday от -imc-. Ну наконец-то.
3:32 sivukhin получил 60 по гондолам. Надеюсь скоро добьет.
3:34 Alex_2oo8 со своим очень странным первым днем поднялся в золото с 247 за второй.
3:36 Кажется табличка сейчас адекватна.
3:40 От sivukhin еще одно 60 по гондолам.
3:42 От KAN еще одно 19. Возможно он решил, что золото уже есть, поэтому или 100 или в принципе не важно.
3:44 Я боюсь, что Костя может писать какую-нибудь жесть в holidays. Это может плохо кончится на самом деле. А главное, без сданной friend не поможет.
3:48 И еще одни 60. Интересно, что там не так. 3:52 От Коли 0 по friend. Видимо у него неправильное решение. Ну задача же прекрасно стрессится, почему он этого давно не сделал?
3:53 30 по friends. Прошел первую позадачу. Может наконец-то написал перебор? Или опять слабые тесты?
3:56 sivukhin добил гондолы! Похоже, на второе золото. Хотя для безопасности неплохо бы добить еще одну. Ну или хотя бы 69 по friends.
3:58 KAN прошел другие две группы в friends. Интересно, что более кривое, его решение или тесты жюри?
4:01 zemen еще одно 58 по friends. Он серьезно? Ему 0 по последней могут еще простить. draconic не простят.
4:03 Тем временем KAN посылает какой-то треш по друзьям. И появилось еще одно 600.
4:04 О, zemen 69 по друзьям. Этого даже наверное хватит на серебро. Но, блин, что за 0?
4:10 Как-то я совсем не понимаю, что делает -imc-. Это печально. До бронзы ему осталось два места.
4:13 Кажется KAN так и не написал перебор. А делает какой-то треш. Видимо правда сейчас он склеит из него 46. Потому что решения проходящие каждую из подзадач у него уже есть.
4:17 Я считал, что тому, что нули это плохо учат сильно раньше. А у sivukhin 23 по holiday. К чему бы это. 4:19 Сдал на 19. Ну слава богу. И zemen на 24. Ну так хоть не так нецензурно. 4:23 Кажется, если не произойдет каких-то чудес, должно быть два золота и два серебра.
4:26 KAN 300! А -imc- сдал на 46 друзей.
4:32 zemen 47 по holidays. Границы на текущий момент 447-330-209.
4:37 Кажется таблице опять плохо.
4:43 Еще 300. Китаец.
4:45 Как бы sivukhin не вылетел из золота. У него 5 мест запаса. Лишние 2 балла в первый день могут сыграть. 4:49 Пойду встречать ребят. Думаю, сейчас уже мало интересного произойдет. 4:59 Кажется ничего не случилось. 5:00 OVER. В целом сегодня ребята молодцы. Ниже не опустились. Чтобы Косте с Никитой подняться в золото им нужно было 300. Не делать это странно называть плохо выступили.

Краткий разбор задач (разбор белым шрифтом, если выделить станет виден)

gondola Условие en
Достаточно простая но мутроная задача. Точнее даже три задачи. Разбор на GA выглядел как "Первые две подзадачи тривиальны, в третьей нужно немного комбинаторики". Пожалуй, я не пойду дальше
friend Условие en
Введем для человека стоимость за то, чтобы его не взять. Тогда людей можно удалять с конца пересчитывая эти стоимости. Стоимость будет меняться только для человека, который позвал. Как меняется достаточно несложно разбирается для всех трех способов.
holidayУсловие en
Это выглядит как жесть. Какие-то мысли. Если зафиксируем отрезок, то ответ на нем — это сумма нескольких максимальных. Это можно считать какой-нибудь двумерной структурой, или персистентным деревом. Кто-то из казахов рассказывал мне, как довести это до nlogn запросов к такой структуре, но я если честно не готов был это ни аккуратно проверить ночью, ни воспроизвести сейчас. Жюри обещает какой-то красивый devide-and-conqure.

Комментарий. Тур выглядит в целом сложнее первого. Для наших ребят это скорее хорошо. Если придумать holiday на 100, это может помочь неплохо отыграться.

Примерно через 15 минут по плану должен начаться первый тур IOI 2014.

Результаты
Результаты от снарка
Видеотрансляция
Таблица по странам от Снарка

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

0:03 Судя по таблице контест начался по расписанию. Чтобы быть в этом уверенным, я дождусь появления первых баллов, после чего выложу условия.
0:04 У них что-то кешируется слишком злобно, так что если у вас все еще "подождите" Ctrl+F5 должно помочь.
0:12 На IOI-Conference подтвердили, что тур начался по расписанию.
0:13 Первые баллы! 42 от stevenkplus
0:17 Первые баллы по rail. 8 от Conor Griffin из Ирландии. Пока я это писал появились еще одни 8.
0:21 Так же быстро появилось много 8 по wall. Это простое моделирование того, что описано в условии.
0:26 dhh1995 получает 100 по game! Решение пишется достаточно просто, если его быстро придумать. При этом с придумать бывают проблемы. Вроде бы, она пробивается как-то еще с использованием мощных структур.
0:30 Еще одна сотня по game от участника их тайлайнда, и 30 по railes от уже известного Conor Griffin. У нескольких участников из Казахстана и Украины 8, остальные пока молчат.
0:31 И еще 3 сотни по game. У scott_wu xyz111 Baklazan и участника 0:38 24 по wall от stevenkplus. Это разбор частного случая, который видимо не очень поможет для полного решения.
0:39 30 по race от LeMieux.
0:42 61 по wall от Dominik Smrž из Чехии.
0:43 56 по rail от akshatb. Как видите участники пошли совсем в разнобой.
0:45 Scorpy 30 по rail 0:46 stevenkplus and Jacob Jackson 100 по walls!
0:49 KAN 30 по rails. По текущей статистике это не правильный выбор задачи. Впрочем,на IOI-контесте порядок задач не особо важен. Сегодня надо сдавать все.
0:52 Еще одна 100 по wall. От yutaka1999.
0:53 zemen и -imc- 100 по wall!
1:00 xyz111 200! Может и действительно 300 будет раньше, чем я ожидал.
1:04 scott_wu присоединяется к 200.
1:07 Baklazan 200. Кажется 200 это уже не событие.
1:12 У KAN посылка на 0 по game. Вообще это достаточно странно. Реализация решения вроде совсем простая, думаю скоро разберется. 1:34 У sivukhin 30 по rail. Видимо тоже не тот порядок задач. Я пока автоматизирую слежку. 1:38 30 от sivukhin быстро превратилось в 56.
1:48 230 у dhh1995.
1:51 У KAN посылка на 0 по walls. К чему бы это.
1:55 100 по rail от asterius. Итого все задачи открыты в 1:49.
1:58 256 у dhh1995.
2:00 Наши активизировались. У KAN 100 по wall, у zemen 8 по rail, у -imc- 42 по game.
2:01 А вот и первые 300. Поздравляем scott_wu. Даже не пол часа быстрее меня в 11-ом году.
2:07 В соответствующем посте появились фотографии с открытия.
2:23 Miras321 и emachaidze 162, -imc- 142, KAN 130, zemen 108. У остальных за кем я слежу меньше 100. Тем временем 200 сейчас это 5 место. И таких 11 человек.
2:31 Прошла половина контеста. Все американцы сдали game, все китайцы сдали wall. Наши как-то затихли.
2:32 У sivukhin 8 по wall.
2:35 И из 8 очень быстро получилось 61. Интересно что это. Скорее всего это надо достаточно сильно доделывать до 100.
2:39 Появились английские условия. Спасибо делегации Армении. А они ведь давно лежат на сайте, да?
2:45 У sivukhin еще раз 61 по wall. Видимо он хочет больше.
2:47 dhh1995 300!
2:48 sivukhin 8 по wall?!
2:52 Zlobober предположил, что Никита пихает корневую. Это может плохо кончиться.
3:02 KAN zemen -imc- больше часа сидят без посылок. Надеюсь скоро что-то произойдет.
3:15 KAN 100 по game!
3:16 zemen 42 по game. Прогресс. Никиты, присоединяйтесь :)
3:23 Scorpy поднялся на 30 место со 172 баллами.
3:24 От KAN еще одно 30 по rail. Будем ждать больше.
3:25 sivukhin 42 по game. Отложить wall это правильное решение в такой ситуации.
3:34 sivukhin 100 по game! Интересно, что он будет делать дальше. Видимо у него есть плохое решение по wall и никакого по rail. 3:40 KAN присоединился к большой группе по 256 3:47 -imc- уже сидит без посылок почти два часа. Интересно, что бы это значило? Пишет какой-то ад по rails?
3:53 Тем временем, все еще только два человека имеют 300. И 10 256. Вероятно отсечка золота после первого тура будет проходить по отметке 230. Причем очень сильно деленному 230.
3:58 -imc- послал 8 по rail. Ну хоть что-то за 2 часа.
4:05 Еще одно 300 — Leoyu
4:14 sivukhin 30 по rail. Интересно. Видимо он написал что-то другое с багами.
4:23 От zemen как уже больше часа ничего. Интересно, что он сейчас делает? Надеюсь скоро увидеть 100 по game или 56 по rail.
4:34 Привет сборной Казахстана. Miras321 100 по game, NurlashKO 30 по rail с интервалом в 10 секунд.
4:35 Пока писал последний пост -imc- сделал 30 по rail
4:42 Очереди тестирования кажется совсем нет. Ну либо они пишут во времени посылки время, когда она протестирована. Тем временем еще 30 по rail от -imc-.
4:44 Внезапно, 261 от AstroConjecture 4:47 Я ушел ближе к месту проведения, так что видимо это последний пост. Надеюсь кто-то из ребят еще порадует в последние минуты. 4:59 Удачно прошел. sivukhin 100 по rail, zemen 30 по rail. 5:00 Контест закончился,возможно еще несколько не протестированных посылок.

Краткий разбор задач (разбор белым шрифтом, если выделить станет виден) (Условия только русские, официальные я вчера забыл скачать)

rails. Условие (EN). Говорят, что если отсортировать все станции по расстоянию от нулевой, то можно определять их положение и тип по очереди, делая два дополнительных запроса. Если честно, я не пока не разбирался в деталях.

wall. Условие (EN). Будем хранить наш массив в дереве отрезков. Опрецией обновления в нем будем считать "загнать числа в отрезок [l, r]". Последовательное применение таких операций, является операцией такого типа, поэтому можно стандартный способ делать груповые опрерации будет работать. Надо быть осторожным с тем, что операция некомутативна.

game. Условие (EN). Будем поддерживать инвариант: внутри компонент связности нет ребер, про которые еще не задан вопрос. При этом всегда, когда можно ответить да, с сохранением инварианта будем отвечать да. Это не сложно реализовать за квадратичное время, при этом легко доказать, что граф в итоге окажется связным. При этом в первый момент когда это будет так, не будет неизвестных ребер внутри компоненты, а значит вообще.

Комментарий. Задачи выглядят достаточно простыми по отедльности, однако во всех трех надо придумать некоторую идею, с которой могут быть сложности. При чем скорее всего у разных людей в разных местах. Так что мой прогноз — все задачи будут решены на 100 достаточно быстро разными людьми. Полные баллы будут но ближе к концу контеста и не очень много. Увидим насколько он оправдается

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

На пробном туре было на удивление мало проблем по сравнению с прошлыми годами. Кажется даже сразу работали принтеры (видимо в этот раз одинаковые?). Их мелких проблем — положили не актуальную версию одной из задач, мышка очень плохо работает на поверхности стола, система выдает неадекватный вердикт в случае ML. Но с ними всеми достаточно быстро поборолись. Например, обещали на туре выдать больше бумаги, чтобы использовать ее в качестве коврика для мышки.

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

Также меня просили немного рассказать о членах сборной

KAN (Николай Калинин) — выпускник 40 лицея Нижнего Новгорода, абитуриент ННГУ. Абсолютный победитель Всероссийской олимпиады 2013 года, двукратный абсолютный победитель ВКОШП, победитель Zepto Code Rush 2014, 10-ое место в рейтинге codeforces на текущий момент, 3-е место IOI-2013. Несмотря на не самое удачное выступление на РОИ этого года (аж 4-ое место!), выиграл три из четырех отборочных туров на сборах.

-imc- (Никита Уваров) — выпускник московского лицея "Вторая школа", абитуриент ФУПМа. Третье место Всероссийской олимпиады 2014 года, победитель Coder-Strike 2014 - Finals. Никита первый раз побывал на сборах в 9-ом классе, однако после не очень удачного выступления в 10-ом классе не был приглашен на сборы снова. Уверенными выступлениями в течении всего последнего года, он доказал, что это было ошибкой и, заняв второе место на сборах, прошел на международную олимпиаду.

zemen (Константин Семенов) — выпускник 41 лицея города Ижевска, абитуриент ФИВТа. Абсолютной победитель Всероссийской олимпиады 2014 года, а также открытой олимпиады 2014. Золотой медалист IOI 2013 (12 место). Если проход на IOI в прошлом году, как и 4-ое место на Всероссийской олимпиаде было для всех неожиданностью, в этом году Костя наравне с Колей был фаворитом всех российских школьных сореванований и выиграл многие из них.

sivukhin (Никита Сивухин) — выпускник СУНЦ УрФУ, абитуриент УрФУ. 4-ое место ВКОШПа, участник Петрозаводских сборов в составе команды UrFU 3. Автор Codeforces Round 231 (Div. 2). Никита — первый участник сборной из Екатеринбурга (правда, были участники из Свердловска). И это в год, когда Екатеринбург проводил РОИ и финал.

Достаточно скоро начинается утверждение проблемсета и перевод задач на национальные языки. Первый тур завтра в 9 утра по местному времени.

Фотографии от pashka в полной версии

Уже по традиции я буду писать что-то про поездку сборной России на IOI.

В этом году от России в Тайбей приехала большая делегация из 18 человек. Вместе с 4 участниками приехало 10 наблюдателей из Казани (как проводящей стороны 2016 года), а также руководители сборной, pashka (член ISC) и я.

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

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

Ссылки на тему:

Официальный сайт олимпиады.
Список участников и разная статистика
Здесь скоро будет проект от Снарка

В полной версии есть фотографии.

Topcoder SRM 600 пройдет в ближайшую субботу в 21:00 MSK

На раунде обещают 120 футболок для Div.1 и 40 футболок для Div.2, из которых половина раздается топу, а половина случайным участникам набравшим больше нуля баллов.

Но это еще не все. В воскресенье в 21:00 MSK будет нерейтинговый SRM 600.5 (Special Round Match). На котором раздадут еще 40 футболок и приз в 600$ для первого места. Раунд обещают веселым - с длительностью в 4 часа и состоящим из двух задач, которые не дали на онсайт TCO как слишком сложные и одной уровня Div1-Hard. Кроме топ-40 с ненулевым счетом обещают 10 футболок для случайных болельщиков (людей, кто был залогинен в арену больше 3 часов из 4-ех, но не открывал задачи).

Так же напоминаю про этап OpenCup утром в воскресенье и очередной раунд FaceBook Hacker Cup ночью с субботы на воскресенье. Всем удачных выходных :)

UPD: Также появилось новость, что начиная с этого матча TL и ML будут явно указаны в условии. Авторы говорят, что будут стараться во всех задачах использовать TL 2 секунды и ML 256 MB. (раньше было 64MB)

8:15 По текущим данным, тур отложен на 45 минут. На улице прошел дождик. Сейчас он вроде почти кончился, но тем кто сегодня поедет на пляж будет весело.

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

8:42 Трансляция. Кстати у них пока не работает сервер с табличкой, и еще некоторые другие. Может быть это причины задержки? Зато солнце выглянуло...

8:50 Интернет работает как-то совсем печально. Или это все смотрят трансляцию.

8:51 Следующее заявленное время начала — 9, т.е с задержкой в час.

8:57 Участников пустили в зал. Тем временем один из ISC Member опроверг мои самые страшные мысли о причинах задержки. Это радует, но детали после начала контеста.

9:03 Если я правильно понял, то в зал забежал опоссум. Ну ок.. Тем временем ко мне присоединился eduardische

Контест начался.

0:14 Контест предположительно начался в 9:15. Уже есть 25 и 12 по первой, но они совсем не о чем, я не думаю, что много топа будет их писать. Условия будут, когда я поборюсь с интернетом. Scoreboard

0:29 Поборолся. русское английское Тем временем есть три сотни по первой задаче и одна по второй. Похоже, что все будет решаться на третьей.

0:37 Быстро появилось достаточно много сотен по первой. Впрочем, она действительно простая. Во второй есть правдоподобная жадность, которая оказывается верной. Вполне вероятно, что большинство участников просто не будет ее доказывать. Наши пока себя не показали никак. Видимо читают условия. Так тоже можно.

0:46 От KAN и tunyash 100 по caves. От malcolm 51. Только пока я это писал, случился rejudge.

0:50 100 по caves от zemen. А у остальных не сложилось. И опять никто не говорит что происходит.

0:58 У наших три сотни и 51 от malcolm. У YuukaKazami 200. Впрочем, резервные задачи по словам жюри еще проще.

1:00 KAN присоединился к YuukaKazami Одним словом надо решать game на сотню. game — это абсолютно стандартная, но достаточно сложная задача. Основная проблема с ней в том, что вчера на GA meeting выяснилось, что в ней заходит тупняк. Поэтому срочно пришлось повышать ограничения, и это делали ночью. Кроме того, для усложнения, в задаче поставили достаточно жесткий ML, который является основной проблемой для последних 20 баллов, по замыслу жюри. Собственно про проблемы с этой задачей я писал, когда говорил про худшие мысли о причинах с задержкой.

1:08 К KAN и YuukaKazami присоединились scott_wu и t0nyukuk. Остается вопрос, кто из них умеет писать двумерные динамические структуры данных. В KAN я уверен, вопрос в том, сколько времени это займет.

1:12 Уточнение: у scott_wu 210. Но понятно, что это делается за совсем моментально. Тем временем у malcolm 76 по cave. Мы с eduardische получать такой score, кроме как специально попортив 100 не умеем.

1:22 У KAN 10 по game. У tunyash 39 по robots. Я думаю это первый и третий subtask. Значит скорее всего у него есть правильная жадность, в которую надо добавить какую-нибудь структуру.

1:30 У malcolm 14 баллов по robots. Это похоже на вторую подгруппу, которая является частным случаем, и не является большим продвижением к решению.

1:33 А теперь у malcolm 76. Это похоже либо на безумный набор подгрупп из-за багов и слабых тестов. Либо на правильное решение с TL, написанное аккуратнее, чем у tunyash.

1:39 У zemen 14, у tunyash 53. Видимо Артур отдельно разобрал вторую подзадачу. Тем временем у Украинцев контест не задался — единственная 100 на команду сave у fedimser. У vlad107 200, у kostya_by 100, у двух других белорусских участников 100 нет.

1:46 У участника из Бразилии(Renato_Ferreira) 0-0-80. Неожиданное начало.

1:50 У zemen 90. Интересно, что бы это могло быть? TL на последней группе, из-за неаккуратной реализации?

2:00 У zemen и tunyash 90 по robots, у malcolm 100. KAN видимо пишет что-то крупное по game. А у меня 7% заряда на ноутбуке :(

2:07. Китаец, выигравший первый тур, закончил издеваться, и за 4 сабмита получил 100 баллов по cave. Этим он себе обеспечил место не хуже 4-го.

-2:20 Осталось меньше половины контеста. Последнее время ничего интересного не произошло. У Украинцев все еще одна сотня на команду. У белорусов дела получше. Три человека вверху серебра.

-2:08 tunyash сдал game на 27. Это кажется просто много одномерных деревьев. Или двумерное с багами?

-2:07 И у нас есть 100 по game от участника из Болгарии (Hristo Venev). Думаю скоро будет 300, но этого недостаточно для того, чтобы обогнать ACMonster.

-1:58 Еще 100 по game от Siarhei Kulik. Правда 46-53 по двум другим. Немного про задачи.

-1:56 tunyash сделал 37 по game. А что такое было 27?

-1:54 А эта табличка оказывается умеет показывать детали посылок.. У KAN за последний час три посылки на 0 по game. У остальных более-менее посылок кроме того, что в таблице нет.

-?:?? А если таблицу увеличить, потом уменьшить, то поедет верстка и часы в частности.

-1:35 У KAN еще 0 по games. Не пора ли написать стресс-тест. Мне два года назад в аналогичной ситуации с elephants помогло.

-1:32 malcolm сдал game на 37. Интересно чего они ждут, прежде чем сделать 37?

-1:30 zemen 63! Правда 63 от 80 отличается практически полностью.

-1:25, а KAN 80 по game!

-1:21 Тем временем Кулик 46-90-100.

-1:07 Тут случился обед, и две посылки по cave от malcolm. У KAN есть еще одно 80.

-1:00 У KAN и zemen уже почти однозначно золото. Двум остальным надо что-то сдавать. От tunyash нет посылок уже час. Видимо он решил писать game, а не получать 10 баллов по robots. У malcolm сабмиты по двум задачам. К чему бы это?

-0:57 YuukaKazami 300! Что ответит другой китаец?

-0:51 80 по третьей от Димы. Интересно, он теперь пойдет ее заталкивать на 100 или подумает над первой?

-0:48 У tunyash сабмит на 10 баллов по games. Ждем в 8 раз больше. А лучше в 10...

-0:45 Интересно, какой сейчас размер очереди тестирования?

-0:38 21 по cave от malcolm. Хм...

-0:28 Две посылки по 51 от malcolm 0 от zemen еще несколько 80 от KAN и уже пол часа ничего от tunyash.

-0:20 Кулик 76. У Артура остался запас в 2 места. Нужно сдавать 63 или 80.

-0:14 Запас кончился. Надо сдавать. А лучше еще и Диме сдавать.

-0:13 Дима 100 по game. И все еще 76 по cave.

-0:09 Есть сабмит от tunyash. 37. Очередь похоже где-то 7-8 минут. То есть вердикты по новым посылкам скорее всего уже не придут.

-0:08 zemen 80 по game!

OVER

Мы пошли к детям. Увидим, что получится.

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

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

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

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

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

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

Первый тур никак не может начаться :( Сейчас уже доступна видео-трансляция (говорят зацикленная) Мы надеемся, что с началом контеста появятся результаты. Через некоторое время после начала контеста, мы выложим условия и будем рады их обсудить.

UPD Scoreboard

За происходящим будем следить мы с meshanya.

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

9.01 Участников куда массово повели. Что там вообще происходит?

9.02 Вроде все вернулись. У одного из участников мы заметили 4 минуты да начала контеста на мониторе.

9.11 Видимо отложили еще. Или не отложили. Никто ничего не говорит.

9.25 На трансляции наконец-то показали участников. Контест уже идет. Интересно, когда он начался?

9.31 Вроде обещают сделать табличку в ближайшее время. Тем временем KOTEHOK сообщает, что гостей привезли к 9 на экскурсию в музей, который открывается в 10.

9.35 Пришел вопрос от участника из Греции(?). Контест однозначно начался, что уже радует.

10.11 Так как ничего непонятно, давайте посмотрим условия задач более удобно, чем в видео-трансляции. русское, английское

10.27 Они ее сделали! По последним данным прошло 1:28. Максимальный результат 100+0+55. Есть несколько сотен по задаче art-class про машинное обучение. Много сотен по dreamig, в том числе у zemen. tunyash и KAN пока написали частичные решения по ней. malcolm пока получил 55 по wombats. У прошлогоднего чемпиона random.johnnyh сотня по dreaming.

10.39 В задаче dreaming 18 баллов дают за случай когда исходный граф это паросочетание. Еще 47 дают за случай, когда две компоненты. Так что 18 баллов от KAN очень похожи на 100 с багами.

10.54 Очень похоже, что таблица давно уже не обновляется. Правда говорят, что низ меняется. Очень странно это все.

11.04 Говорят у SC все работает. Мы за них очень рады.

11.13 За это время к нам присоединился eduardische а табличка все еще не обновляется. SC официально заявило в twitter, что у них проблемы с таблицей. Да ладно?

11.30 Она уто^Wсломалась.

11.41 В табличке появилось больше флагов. Видимо их отсутствие сейчас наибольшая проблема, с точки зрения жюри.

11.48 Один из руководителей команд, сказал, что слышал, что участников проблемы с получением результатов. Если это так, то все совсем грустно.

11.56 Появились флаги. Может сейчас появится что-то еще?

12.04 Появились результаты топа. Там есть KAN с 158 и malcolm с 155. Больше чем 55 по wombats пока ни у кого нет. Так что видимо надо делать что-то с классификацией.

12.24 Какие-то еще результаты Говорят, что контест продлили на пол часа. Все очень плохо :(

12.35 Говорят, что жюри остановило тестирование, чтобы все были в равных условиях. Что там вообще происходит?

13.26 Тем временем ничего нового не происходит. До конца соревнования остался примерно час, если его еще не продлят. Видимо подробности того, что происходило будут только потом и уже от участников.

13.30 В трансляции есть какие-то неофициальные результаты. Там KAN делит с участником из Италии первое место с 255.

13.33 Если верить трансляции у zemen 212.

13.36 Говорят у malcolm все еще 155 :( Видимо art совсем не пошел.

13.41 По просьбам: Кулик 224, Сокол 233, Furko 215.

13.45 Вроде у какого-то китайца 100 по wombats. Это сильна заявка на 300 в туре.

13.51 Говорят тестирование более-менее заработало, но очень медленно. До конца контеста 39 минут.

13.56 А кто-нибудь слышал что-нибудь про Хо?

14.01 Furko получил 233. А мы нашли Хо. У него 100+0+76. Это интересный вариант.

14.13 Китаец с сотней по wombats начинает получать баллы по art. У него есть примерно 17 минут. This is very exciting. :)

14.21 До конца контеста осталось десять минут, и я уже пойду встречать участников. Думаю через несколько часов станет понятнее с результатами.

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

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

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

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

В тренировки добавлен VI Открытый Кубок мат-меха среди школьников Санкт-Петербурга и Ленинградской области.

Этот контест проводится каждый год авторским коллективом, состоящим из студентов и выпускников СПбГУ. В этот раз, кроме соревнования в Питере, была проведена трансляция на учебно-тренировочных сборах школьников, поэтому контест достаточно сложный, и мы решили, что он будет интересен широкой публике.

Задачи готовили PavelKunyavskiy, nk.karpov, Malinovsky239 и Ольга Бурсиан (не знаю ее handle). Также спасибо Gerald, yaro, yeputons, romanandreev, Gassa, I-juice за прорешивание и вычитывание условий.

Ссылка на тренировку. Соревнование личное и длится 4 часа.

PS По ряду причин, в таблице результатов как призраки есть только участники, показавшие достаточно хороший результат — сдавшие хотя бы 6 задач.

Кто-нибудь знает хоть какую-то информацию про то будет он завтра(12 мая) или нет?

Добрый день.

Некоторое время назад мы наткнулись на интересный баг. Я был бы рад, если бы кто-то мог мне его объяснить.

Посмотрим на такой код

int main(){
    for(;;);
    return 0;
}

Скомпилируем его с помощью обычного g++. При запуске, он ожидаемо зависает. Прервем процесс.

Теперь попробуем сделать немного по-другому. Добавим в строку компиляции -Wl,--stack=925000001. Запустим процесс, он снова зависнет(неожиданно правда?). Однако, при нажатии Ctrl+C, он полностью занимает ядро процессора и не собирается завершаться.

Константа 925000001 найдена бинпоиском, на границе эффект воспроизводится не очень стабильно, иногда не убивается один из 2-3 запусков. Воспроизвелось на нескольких Win7.

Проблема не у gcc, потому что у MSVS2010 происходит тоже самое, только начиная с 9400000001 стека.

Так же было бы интересно воспроизводится ли под другими версиями windows.

Посты последнее время появляются совсем незадолго до раунда, что при утреннем почти бесполезно.

TopCoder SRM 573 будет сегодня15 марта в 5:00 MSK (в других временных зонах).

За последнее время часто понадобилось хранить файлы не в 1251, которую по умолчанию ставит Far, а в UTF-8. В принципе, обычно получалось по методу, вспомнил хорошо, не вспомнил — кто-то заметил, поправил, или сказал поправить. Но со временем надоедает.

Кто-нибудь умеет менять кодировку по умолчанию? Чтобы он сразу ставил UTF-8. Гугл не помогает. Потыкаться тоже.

Здравствуйте!

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

Сегодняшний контест для вас подготовила команда SPb SU 4 (Alex-Gran (Александр Грановский), Dmitry_Egorov (Дмитрий Егоров), PavelKunyavskiy (Павел Кунявский)). После долгих раздумий из названия команды можно догадаться, что мы представляем Санкт-Петербургский Государственный Университет. Куда более очевидно, что мы все трое учимся на первом курсе математико-механического факультета.

Большое спасибо за помощь в подготовке задач Артёму Рахову (RAD), Геральду Агапову (Gerald) и Марии Беловой (Delinur) за перевод задач. Также большое спасибо Пете Калинину (KAP) за вычитку условий.

В сегодняшем контесте вас ждет 7 задач (по 5 в каждом дивизионе) про страну, в которой живут волшебники, и, как следствие, происходит много интересных событий. Вам предстоит поучаствовать в местных митингах, разобраться в тонкостях написания заклинаний, прокатиться на волшебных видах транспорта, попытаться унести магические призы, поиграть в любимую игру волшебников, помочь магическому правительству в управлении страной, а также свернуть шизофреническую сумму разрешить финансовый спор двух прославленных магов.

Разбалловка задач сегодня стандартная в обоих дивизионах. Хочу заметить, что стандартная — это 500-1000-1500-2000-2500, а не как обычно :).

UPD: Опубликован разбор.

Поздравляем победителей!

Div. 1
rng_58

tourist

SergeiFedorov

Endagorion

Справившихся с 4 задачами, на этом непростом контесте. Отдельные поздравления от меня Endagorion al13n справившимся с задачей D.

Div. 2

handojo1

mastersobg

bdepwgjqet

Всем удачи!

Разбираясь со скриптом от yak_ex и настраивая его под себя, подумал о том что было бы удобно различать в таблице визуально уже просмотренные посылки от еще не просмотренных.

Хранится ли в необходимая информация и доступна ли она в каком-либо виде? Так же была бы полезна подсветка последней просмотренной посылки, а то бывает, что пишут "время истекло", закрываешь, а кого смотрел вспомнить не можешь.