Вот-вот начнется второй тур 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 — большой вопрос.