PavelKunyavskiy's blog

By PavelKunyavskiy, 6 months ago, In Russian,

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

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

0:00 Кажется контест начался по расписанию. Как и в прошлый раз после первого успешного сабмита, выложу краткие условия задач (на этот раз с решениями).
0:11 В таблице появились первые баллы. Пока это 7 и 10 по первой. Это переборы в частных случаях. Но это повод выложить задачи.
0:19 Появилось 32 балла по 4-ой. Это разбор случая "нет данных исходно, только длина". Наши пока молчат. Думаю по этой задачи большинство будет сразу писать 100. Ну или хотя бы 80-90, если почему-то получился квадрат.
0:24 Появилось 38 по 5-ой и 4 по 6-ой. 4 это какой-то бессмысленный случай. 38 это осмысленное неоптимальное решние. Его думаю более-менее все сдадут.
0:30 gritukan — первая 100 по 4-ой. Думаю сейчас посыпятся еще много 100.
0:32 Появилось 49 по 5-ой. Это чуть другое неоптимальное решение. (20 дают за что угодно, еще 18 за много записей и совсем много чтений, еще 11 за много чтений и совсем много записей).
0:38 overtroll 32 по 4-ой? Думаю это 100 с багами, иначе совсем на него не похоже.
0:40 josdas 38 по 5-ой. Тоже полезно получить. Но скорее всего, если хочется золото, нужно 100, которое к этому решению имеет мало отношения.
0:41 yutaka1999 100 по 5-ой. От такой задачи логично ждать ранних сотен. Интересно насколько массовыми они будут.
0:43 overtroll исправил баги, получил 100 по 4-ой.
0:45 gritukan 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-ой. С нулем пока сидит adrozdova и super_azbuka. Думаю скоро что-то будет. Асхат тоже не любит писать частичные решения. Саша пишет все аккуратно, но часто медленно. Так что пока не выглядит чем-то страшным.
1:13 josdas 80 по 4-ой. Наверное скоро добьет.
1:16 Тем временем 8 сотен по 5-ой задаче. Причем у участников с достаточно разными результатами в первом туре. А gritukan получил 0 по 6-ой.
1:19 manoprenko 38 по 5-ой. adrozdova 100 по 4-ой. gritukan 12 по 6-ой. Разнообразие. Ждем чего-нибудь от super_azbuka.
1:25 gritukan послыает еще раз 12. Это разбор частного случая, когда все точки на диагонали. Так что возможно это больше баллов с багами, которые он еще найдет. josdas посылает первую то на 0, то на 80.
1:28 Еще три 200. popoffka rudy102 и SpyCheese.
1:31 Уже 15 сотен по 5-ой. Видимо это будет обязательным условием для золота.
1:38 По 6-ой задаче пока лучший результат 41 у gongy. Вроде 41 в итоге должен быть достаточно массовым баллом. А вот 60 звучит как возможность отыгать 7 или 15 баллов потерянных в 3-ей задаче первого дня.
1:41 overtroll присоединился к группе в 200. Думаю он теперь будет долго думать над 6-ой. Надо, чтобы либо смог придумать, либо смог вовремя остановиться, чтобы успеть написать 60. Это тоже не очень быстро.
1:45 koosaga 60 по 6-ой. У него пока 0 по 2-ой. Посмотрим что из этого получится. Вместе с 172 по первому туре, это хорошая заявка на золото.
1:47 gritukan 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 gritukan 16 по 6-ой. Причем именно 16, а не отдельное 4. Что-то нашел видимо, но не достаточно.
2:17 overtroll послал 0 по 6-ой. Зная Влада, это похоже на 60 с багами. Ну или 41 с багами. Ждем.
2:19 Добил до 12. adrozdova получила 4 по 6-ой. Ну посмотрим.
2:21 manoprenko тоже получил 4.
2:25 manoprenko исправил на 25. У adrozdova несколько посылок на 4 и 0.
2:28 waterfalls вышел на первое место по туру с 241. И сдедом получил 260. В 300 я все еще не верю.
2:29 adrozdova получила 16 по 6-ой. А super_azbuka добил первую.
2:36 adrozdova продолжает посылать 16. Видимо хочет больше. Остальные не понятно что делают.
2:45 adrozdova добила 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 koosaga 260. Интересно, как много их будет в итоге.
2:59 Еще одна посылка на 4 от adrozdova по 6-ой. В целом, если пробьет, это будет очень круто. Но так можно потерять очень много времени.
3:06 Еще одно 25 по 6-ой от josdas. Это конечно подстава на этом контесте. Можно убиться об это, а не придумать вторую.
3:08 solonkovda внезапно сдал 70 по 5-ой. Это вообще что?
3:09 I_wanna_be_a_pupil сдал 200. Итого с первым туром 500. Если сможет 60 за оставшиеся два часа — это будет серьезной заявкой на победу. После этого, чтобы его обонать надо либо overtroll либо jcvb либо SpyCheese сдавать на 100 6-ую.
3:17 gritukan после долгого перерыва 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 adrozdova опять посылает 6-ую. Это скорее плохо. Надо уже получить свои баллы по 5-ой. А то так можно и в бронзу вылететь.
3:35 gritukan сдал 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 adrozdova 60 по 6-ой! Не зря потратила 2 часа (или сколько? почти 3). Осталось получить что-то разумное по 2-ой. 38 даст хорошее серебро. 100 может быть даже золото. Если 425 будет не золотом, будет очень обидно.
3:49 gritukan потихоньку вываливается из золота. Осталось 3 человека. Надо сдавать 41, а лучше 60. Посылки регулярные есть. Надеюсь, справится.
3:54 gritukan смог 41. Обычно 60 из этого получается достаточно быстро. 41 может случайно не хватить, 60 уже должно. Надеюсь, остальные 5 человек, таки смогут пересилить вторую в ближайшее время. 4:00 Остался час до конца. Владу и Мише в целом уже мало что надо. Владу неплохо бы получить 60, чтобы его случайно не обонал I_wanna_be_a_pupil. Мишу можно обонать, только сдав на 100 6-ую. Грише надо бы добить 60. Остальным, надо получить баллов за 2-ую. 38 на золото не хватит, нуля тем более. 4:02 josdas послал 2-ую на 0. И следом еще раз на 38.
4:04 4 балла от gritukan по 6-ой. Насколько я понял, 41 можно получить 2 способами — либо за nklogn либо за n^2 (интересно что такое n^2, я не придумал). Если во втором избавиться от log — чисто техническая замена бинпоиска на стек, то с n^2 может случайно быть грустно.
4:10 overtroll 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 от adrozdova. Это видимо частный случай, когда поменялось 2 бита. Не слишком полезно для решения, но 20 баллов пригодятся.
4:21 manoprenko 41 по 6-ой. Но не серебро ему этого не хватит. Надо или 60, или прокачивать 5-ую.
4:22 gritukan получил 23 по 6-ой, но в сумме это дает 60. Прошел какой-то очень странный набор подзадач. Интересно, как это получилось. Впрочем, не так важно. Этого должно хватить на золото.
4:24 manoprenko получил 60 тем же способом, что Гриша. А сам Гриша в это время получил нормальные 60 одной посылкой. Что вообще происходит?
4:27 solonkovda продолжает получать 12 и 16 по 6-ой. В целом, если он пройдет на 60, то может даже зацепиться за конец золота. Но не понятно что он пишет. Может быть это 25 или 41?
4:29 overtroll добил 60. SpyCheese послал на 0. Может тоже скоро сможет 60?
4:31 SpyCheese 60! Теперь интрига ответит ли I_wanna_be_a_pupil. У него за последнее время несколько раз 12 и 0. Миша продолжает посылать.
4:37 adrozdova 38 по 5-ой. Это скорее всего гарантирует серебро.
4:41 Тем временем группа с gritukan занимает с 15 по 20 места. Чтобы было золото, надо захватить 26 место. Должно хватить, иначе совсем жесть. Но во всяком случае, Гриша сделал более-менее все, что мог.
4:43 Таблице опять не очень 4:47 Поднялась. solonkovda сдал на 25 6-ую.
4:49 super_azbuka получает нули по 5-ой. Что интересно он хочет получить. 10 минут до конца. 4:53 Опять табличка упала.
4:54 overtroll несколько раз послал 60, solonkovda несколько раз 25. Видимо по нашим единственная интрига смогут ли Стас или Саша сдать 5-ую на 100. Кстати 417 скоро рискует вывалиться из золота. Это будет очень обидно.
4:58 Опять легла. Интересно это только табличка, или с туром тоже проблемы. Никаких объявлений нет.
4:59 I_wanna_be_a_pupil 60. Обидно, но что ж теперь. Мне сейчас пришел update за 13:55. Видимо есть некоторая очередь. Иду смотреть закончилось ли все.
5:00 В итоге 3 золота, 4 серебра, 1 бронза. И даже несмотря на большие группы после первого тура ни на один отрез не попала ничья.

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

Spoiler

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

Spoiler

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

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

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

Spoiler

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +119
  • Vote: I do not like it  

By PavelKunyavskiy, 6 months ago, In Russian,

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

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

0:00 Судя по таблице контест начался. Условий пока не будет, их просили не выкладывать пока они не появятся на официальном сайте. После первого успешного сабмита напишу про задачи в общих чертах.
0:18 Пока я шел с завтрака появились первые баллы. В частности 100 у SpyCheese и 46 у gritukan и manoprenko.
0:26 Тем временем overtroll сдал первую на 100, josdas и gritukan на 69.
0:30 peto159 получил первые баллы по второй задаче — 11. Это пербор за n! на подсчет ответа.
0:38 manoprenko сдал вторую на 34 (собственно та динамика за 2^n). gritukan и josdas добили первую. А у меня почему-то не автообновляется таблица.
0:40 na2a опять выходит на первое место с 134 баллами.
0:43 Fedosik получил первые баллы по третьей задаче. 23 балла. Кажется это O(n4), но я точно не помню.
0:48 gritukan 11 по второй. Странно. Почему не сразу 34.
0:53 Ну досдал до 34. Может баги какие-то.
0:58 super_azbuka давно уже сдал первую на 100, а я как-то не заметил.
0:59 solonkovda 46 по первой. Ждем еще чего-то от adrozdova.
1:04 Nurbakyt Madibek (cf handle?) got score 46+34+31. Seems, for top contestant contest starts after 100+34+31.
1:08 gritukan написал 3-ю на 23. и вышел на первое место. josdas вторую на 34, и присоединился к большой группе, делящей второе место. А я дописал софтину, которая следит за участниками. Сейчас приведу в приличный вид, и куда-то выложу.
1:11 adrozdova послала первую на 0. Наверное, скоро отдебажит. Интересно сколько это будет. 46, 100 или что-то хитрее? (наврал. Третью, а не первую. Внезапно.)
1:17 Появились несколько 30 баллов по второй. Это решение параллельной ветки задачи. Не перебор, а случай, когда ответ 0. 1:19 Тут какой-то скрипт на питоне. Его можно регулярно запускать, и если у вас linux, будт появлять уведомления про участников, перечисленных в коде. Если кто сделает вариант рабочий для windows, наверное будет хорошо.
1:29 adrozdova 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-ей, присоединился к деленному третьему месту. gritukan уже несколько раз послал 3-ю на 0, видимо написал что-то более умное, но пока баги.
1:51 Еще одно 23 от gritukan. Интересно что это. Куб, но какой-то неудачный, по этому получающий TL? 1:58 manoprenko 31 по первой. Это еще что? 100 с багами? gritukan продолжает спамить посылками на 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 Пока я это писал adrozdova получила 69 по первой, а solonkovda отдебажил 23 по 3-ей.
2:12 Что-то мой скрипт нашел много странных сабмитов, в любом случае не улучшающих баллы (какие-то id поменялись?). А gritukan победил 31 балл по 3-ей.
2:15 Видимо действительно поменялся формат данных в таблице. А adrozdova превратила 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 adrozdova 0 по 2-ой, overtroll 9 по shortcut. Это что-то умное с багами видимо?
2:40 overtroll 38 по 3-ей. Это видимо куб без лишний логарифмов?
2:44 overtroll получил 71 по 3-ей, adrozdova 34 по 2-ой. Ждем, что SpyCheese возьмет пример с Влада?
2:48 Один из Катайцев добил 97 до 100.
2:53 overtroll solonkovda gritukan сабмитят решения по 3-ей на меньше баллов, чем у них есть.
3:03 Тем временем несколько больших групп участников приближаются к границе медалей. Это не очень хорошо, т.к. по правилам, бронзовые медали округляются вниз. То есть, если большая группа захватывает половинное место, то никто из них не получает медаль. А еще сложно все считать, потому что вторая российская команда при этом не учитывается, а они все выше.
3:05 overtroll продолжает посылать нули по 3-ей задаче. Пихает какую-то лажу на больше чем 71 что ли? Он это в целом любит. 3:07 SpyCheese тоже сдал 3-ю на 71. Молодец. Теперь надо все-таки получить 34 по 2-ой, и спокойно думать что делать дальше. Хотя, зная Мишу, скорее всего сейчас тоже начнет пихать 100, либо думать над чем-то больше 34 по 2-ой.
3:13 overtroll 97 по 3-ей. Интересно, затолкал или что-то нормальное. Тем временем можно заметить фейл в разбалловке. 134 получается аж тремя способами, а это очень массовый балл.
3:17 overtroll продолжает пихать 97 до 100. Там ограничения 300000 и 1000000 не понятно речь идет про неассимптотичесие оптимизации или что-то хитрое.
3:18 gritukan взялся за 2-ую. Это хорошо. Может скоро увидим 64 или 100? Впрочем, там на 64 можно придумать много неверных жадностей.
3:19 super_azbuka сдал 3-ю на 23.
3:25 solonkovda присоединился к Асхату на 6-ом месте с разбалловкой 100+64+23. Итого сейчас 6,5 наших участников в золотых медалях. Забавно. Интересно как долго такое продержится. josdas вылетит уже достаточно скоро. adrozdova и gritukan мне кажется к концу контеста, если ничего не сдадут больше. Остальным может и хватить того, что есть. Но большого отрыва, не будет, так что видимо все будет решать второй тур.
3:35 adrozdova и super_azbuka послали 3-ю на 0. К чему бы это?
3:38 SpyCheese 0 по 2-ой. Ждем скоро чего-то интересного.
3:47 gritukan пробил 38. Не знаю насколько это ценно для дальнейшего продвижения, но тоже пригодится.
3:50 josdas смог получить 31 по 3-ей, и вернулся в группу золотых медалей, но не думаю, что на долго, если не сдаст что-то еще. 3:53 Вроде SpyCheese и overtroll обычно начинают писать частичные решения как раз где-то за час до конца, так что может минут через 15 что-то увидим от них.
3:56 josdas сдал 38 по 3-ей. Мне кажется, что группа с 172 будет пересекать границу золотых медлалей после первого тура. Но в любом случае отрыв в обе стороны будет очень маленький.
4:00 30 от SpyCheese по 2-ой. Сделать из этого 64 уже дело техники и 15 минут времени. Вероятно, скоро справится. Если сделает — будет на первом месте с отрывом в 1 балл.
4:11 overtroll 100 по 2-ой. Внезапно, но радостно. Посмотрим чем ответят остальные. И все еще ждем 64 от Миши.
4:15 solonkovda и adrozdova посылают 3-ю на те баллы, которые уже есть. Может что-то из этого получится.
4:17 SpyCheese видимо решил, что 64 это слишком скучно, и полочил 100. Весело.
4:19 31 по 3-ей. Пригодится. Скорее всего это даст ему попадание в золото
4:21 manoprenko ничего не посылал с 3:07. Интересно чем он занимается. 23 то хотя бы надо получить по третьей.
4:27 overtroll потихоньку пихает свои 97 на 100, остальные затихли. Осталось пол часа.
4:28 manoprenko наконец-то сдал 23 по 3-ей. Группы 172 и 165 на границе золотых медалей продолжают расти.
4:34 I_wanna_be_a_pupil 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 с чем-то баллов, динамика за 2n. На еще около 30 баллов проверить, что ответ 0 с большими ограничениями. Это какая-то жадность. На полный балл, как решать я не понял.

Spoiler

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +119
  • Vote: I do not like it  

By PavelKunyavskiy, history, 13 months ago, In English,

Everyone on this site heard about problem preparing tool, maintained by MikeMirzayanov called polygon.

It have a lot of advantages, like automatic checks of everything you can imagine. But also, it have several very annoying things. The main one for me is necessity of synchronizing solutions and generators files by hand, between polygon and your local copy. So I had written a tool, which can do it.

Tool is published on github, with instructions how to install it. You are welcome with any new features/suggestions (I'm not knowing python very well, to be honest).

Known problems:

  • Not tested good enough, probably buggy
  • Installation script working strange. Anyone knowing python better? Any better ways to distribute?
  • Sometimes lost of session is not detected and script fails with strange non-readable errors. relogin helps
  • Parsing html pages can be not stable enough with changing polygon. Waiting for better api from MikeMirzayanov and codeforces team.

Read more »

 
 
 
 
  • Vote: I like it  
  • +192
  • Vote: I do not like it  

By PavelKunyavskiy, 19 months ago, In Russian,

Доброе утро!

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

0:35 тур начался точно по расписанию, но таблица результатов недоступна. Можно почитать условия
0:41 Stefano Maggiolo утверждает в своем twitter, что "у них есть техническая проблема с публичными результатами". Вероятно, с самим контестом все хорошо.
0:46 Появилась таблица. Пока overtroll 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. Интересно, это массовые баги или после первого тура все решили писать частичные решения. У overtroll еще одна посылка на 17.
0:59 cubelover получает 200 за второй тур и выходит на уверенное первое место c суммой 500 за два тура. Третья задачка выглядит сильно сложнее первых двух. Во всяком случае последний subtask.
1:01 Alex_2oo8 получил 100 по horses.
1:03 у BudAlNik тоже еще две посылки на 17 по horses.
1:05 overtroll с 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 overtroll досдал 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 overtroll 100 по sorting и выходит на третье место! Итого сейчас ребята занимают 3,4,7 и 134 место. Ну, тоже неплохо....
2:01 matrix и JeBeK из ирана получили по 200 за второй тур с 115 и 59 за первый. Забавно как-то. #КоляБериПример
2:03 ainta 61 по towns и выходит на 3 место с нулем по sorting. Корея в этом году жжет. Три человека в золоте, 1 и 3 место на текущий момент.
2:06 overtroll 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 overtroll 61 по towns. Молодец. Надеюсь он приятно удивит, добив эту задачу за оставшиеся два часа. (Я все еще не знаю как ее решать на 100, и буду рад, если кто расскажет)
3:00 Ух ты ж. Суровый Владислав добивает ее на 100 сразу! У нас есть первое 300 в туре. Правда кажется формальной гарантии золота это ему все еще не дает, но я посмотрю на 27 человек с 300 на этом туре.
3:04 А у BudAlNik тем временем уже 14 посылок по horses, проходящих какое-то подмножество первых трех подгрупп.
3:09 После трех часов overtroll 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 TooSimple сдал 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. Мише даже может этого хватить на золото, но не понятно, лучше сдать что-то еще. И cubelover сдал 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 не посылает. А cubelover регулярно посылает что-то, но получает 25 и 35. toosimple только что получил 0. Haghani не посылал ничего по этой задачи с начала третьего часа. Больше претендентов на первое место нет.
4:22 SpyCheese 48 баллов по towns. BudAlNik получил еще 36 по sorting. Надо 100. Ну или для начала 74 и что-то по towns.
4:25 И еще раз 36 от BudAlNik.
4:36 300 от ecnerwal и 74 у BudAlNik по sorting.
4:37 Абсолют! Jeehak Yoon cubelover.
4:42 izrak тоже получил 300 за второй день.
4:44 BudAlNik 100 по sorting и это промежуточное серебро. Go Go Go!
5:00 Очереди тестирования нет, контест закончился. Хотя результаты в мониторе называются неофициальными, они наверняка не будут отличаться. Всем спасибо!

Read more »

 
 
 
 
  • Vote: I like it  
  • +77
  • Vote: I do not like it  

By PavelKunyavskiy, 19 months ago, In Russian,

Начался первый тур 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 от overtroll
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. Через небольшое время к нему присоединился CbI4 1:49 overtroll получил 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 Интересно, чем занимаются overtroll и 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 overtroll получил 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 cubelover 300.
4:52 toosimple 300. Кажется что мы все еще получаем сабмиты пятнадцати минутной давности.
11:39 местного времени: в таблице результатов пока что не появились посылки за последние 5 минут, но BudAlNik как и обещал принес еще 15 баллов на boxes.

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +120
  • Vote: I do not like it  

By PavelKunyavskiy, 21 month(s) ago, In English,

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?

Read more »

 
 
 
 
  • Vote: I like it  
  • +19
  • Vote: I do not like it  

By PavelKunyavskiy, 3 years ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it  
  • +47
  • Vote: I do not like it  

By PavelKunyavskiy, 3 years ago, In Russian,

Примерно через 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 по гондолам. dragonic 10. Это выглядит как 20 с багами на самом деле.
0:30 KAN 20 по гондолам. А dragonic еще 10. Бывает.
0:33 cubelover 75 по гондолам. Когда же будут 100? 0:34 Miras321 55 по гондолам. А у dragonic еще 10 :(
0:35 zemen 55 по гондолам. scott_wu 35 по друзьям. Это вроде бы тоже разбор случаев.
0:37 С четвертой попытки у dragonic все-таки 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 Umqra 15 по гондолам. O_o это как? 0:50 KAN 100 по гондолам. Теперь ему придется думать.
0:51 Algiz 47 по holiday. Таких уже достаточно много. Это все кроме собственно задачи.
0:52 dhh1995 выходит на первое место с сотней по гондолам. У dragonic 55. У zemen еще 90.
0:55 zemen 100 по гондолам. Ждем Никит. Кстати, если кому интересно, автор этого треша — misof.
1:00 Xu и Yu закрыли гондолы и теперь три китайца делят первое место с 400. К KAN присоединилось еще два человека с 356.
1:03 dragonic 75 по гондолам. Кстати о Китайцах. Кажется ребята говорили, что после первого тура, команда США учила команду Китая традиционной китайской карточной игре.
1:05 Umqra 10 по гондолам?! Как-то они не пошли.
1:07 zemen разобрал один из частных случаев в друзьях и вышел на первое место по туру со 119.
1:08 Umqra 25 по гондолам. А zemen разобрал еще 2 частных случая. Можно еще написать перебор, паросочетание в двудольном графе (это будет 69 кажется) и начать решать задачи.
1:09 scott_wu решил, что ему не нравятся гондолы и сдал друзей на 100. В целом, это тоже не очень сложно. У dragonic еще одно 75.
1:12 А у Umqra еще 25.
1:14 scott_wu начал заниматься гондолами. 10 это не самое хорошее начало.
1:15 На самом деле, происходящее сейчас имеет не очень много смысла. Я верю, что большая часть участников претендующих на золото получит 100+46+47. Дальше будет не очень большая группа которая из 46 сделает 69. А на оставшихся двух подзадачах все будет решаться. Впрочем, иметь на них 3,5 часа приятнее чем 2.
1:17 А у dragonic еще одно 75.
1:19 scott_wu вышел на первое место по туру с 40 по гондолам и 100 по друзьям. А у Umqra еще 25.
1:21 уже 65. Минут через 15 наверное будет 100. Дальше 47 вообще не проблема. А вот дальше...
1:22 И еще 25 от Umqra. Сколько можно :(
1:23 KAN 0 по друзьям. Вероятно это 100 с багами. Или неправильное решение. Во всяком случае, на вид в частичных ошибаться негде.
1:27 Miras321 пошел набирать частные случае в друзьях.
1:32 Po-En Chen выходит на 2-ое место с 200 за второй тур!
1:33 scott_wu присоединился к 200 за второй тур. 47 думаю будет быстро. Вопрос придумает ли оставшуюся подзадачу.
1:35 dragonic додолбал гондолы. Остался Umqra. Как-то у него не пошло совсем.
1:38 Американцы первые все сдали гондолы.
1:43 Umqra отложил гондолы и получил 46 по друзьям. Сменить деятельность иногда помогает в таких случаях.
1:48 У KAN еще один 0 по друзьям. Кажется самое время получить 11 и стресс-тест.
1:50 ecnerwal кажется первый написал паросочетание в 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 по друзьям, от Umqra 24 по holiday и 35 по гондолам. Пока я писал 24 превратились в 47. А dragonic уснул?
2:58 Umqra 55 по гондолам. Скорее всего 100 по ним ему на золото уже хватит, хотя и впритык. Лучше бы что-то еще.
3:00 Тем временем dragonic вылетел из серебра. Интересно, что он делает последние 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 от dragonic. Ну наконец-то.
3:32 Umqra получил 60 по гондолам. Надеюсь скоро добьет.
3:34 Alex_2oo8 со своим очень странным первым днем поднялся в золото с 247 за второй.
3:36 Кажется табличка сейчас адекватна.
3:40 От Umqra еще одно 60 по гондолам.
3:42 От KAN еще одно 19. Возможно он решил, что золото уже есть, поэтому или 100 или в принципе не важно.
3:44 Я боюсь, что Костя может писать какую-нибудь жесть в holidays. Это может плохо кончится на самом деле. А главное, без сданной friend не поможет.
3:48 И еще одни 60. Интересно, что там не так. 3:52 От Коли 0 по friend. Видимо у него неправильное решение. Ну задача же прекрасно стрессится, почему он этого давно не сделал?
3:53 30 по friends. Прошел первую позадачу. Может наконец-то написал перебор? Или опять слабые тесты?
3:56 Umqra добил гондолы! Похоже, на второе золото. Хотя для безопасности неплохо бы добить еще одну. Ну или хотя бы 69 по friends.
3:58 KAN прошел другие две группы в friends. Интересно, что более кривое, его решение или тесты жюри?
4:01 zemen еще одно 58 по friends. Он серьезно? Ему 0 по последней могут еще простить. не простят.
4:03 Тем временем KAN посылает какой-то треш по друзьям. И появилось еще одно 600.
4:04 О, zemen 69 по друзьям. Этого даже наверное хватит на серебро. Но, блин, что за 0?
4:10 Как-то я совсем не понимаю, что делает dragonic. Это печально. До бронзы ему осталось два места.
4:13 Кажется KAN так и не написал перебор. А делает какой-то треш. Видимо правда сейчас он склеит из него 46. Потому что решения проходящие каждую из подзадач у него уже есть.
4:17 Я считал, что тому, что нули это плохо учат сильно раньше. А у Umqra 23 по holiday. К чему бы это. 4:19 Сдал на 19. Ну слава богу. И zemen на 24. Ну так хоть не так нецензурно. 4:23 Кажется, если не произойдет каких-то чудес, должно быть два золота и два серебра.
4:26 KAN 300! А dragonic сдал на 46 друзей.
4:32 zemen 47 по holidays. Границы на текущий момент 447-330-209.
4:37 Кажется таблице опять плохо.
4:43 Еще 300. Китаец.
4:45 Как бы Umqra не вылетел из золота. У него 5 мест запаса. Лишние 2 балла в первый день могут сыграть. 4:49 Пойду встречать ребят. Думаю, сейчас уже мало интересного произойдет. 4:59 Кажется ничего не случилось. 5:00 OVER. В целом сегодня ребята молодцы. Ниже не опустились. Чтобы Косте с Никитой подняться в золото им нужно было 300. Не делать это странно называть плохо выступили.

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +59
  • Vote: I do not like it  

By PavelKunyavskiy, 3 years ago, In Russian,

Примерно через 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 от Daniyar_7.
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 и dragonic 100 по wall!
1:00 xyz111 200! Может и действительно 300 будет раньше, чем я ожидал.
1:04 scott_wu присоединяется к 200.
1:07 baklazan 200. Кажется 200 это уже не событие.
1:12 У KAN посылка на 0 по game. Вообще это достаточно странно. Реализация решения вроде совсем простая, думаю скоро разберется. 1:34 У Umqra 30 по rail. Видимо тоже не тот порядок задач. Я пока автоматизирую слежку. 1:38 30 от Umqra быстро превратилось в 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, у dragonic 42 по game.
2:01 А вот и первые 300. Поздравляем scott_wu. Даже не пол часа быстрее меня в 11-ом году.
2:07 В соответствующем посте появились фотографии с открытия.
2:23 Miras321 и emachaidze 162, dragonic 142, KAN 130, zemen 108. У остальных за кем я слежу меньше 100. Тем временем 200 сейчас это 5 место. И таких 11 человек.
2:31 Прошла половина контеста. Все американцы сдали game, все китайцы сдали wall. Наши как-то затихли.
2:32 У Umqra 8 по wall.
2:35 И из 8 очень быстро получилось 61. Интересно что это. Скорее всего это надо достаточно сильно доделывать до 100.
2:39 Появились английские условия. Спасибо делегации Армении. А они ведь давно лежат на сайте, да?
2:45 У Umqra еще раз 61 по wall. Видимо он хочет больше.
2:47 dhh1995 300!
2:48 Umqra 8 по wall?!
2:52 Zlobober предположил, что Никита пихает корневую. Это может плохо кончиться.
3:02 KAN zemen dragonic больше часа сидят без посылок. Надеюсь скоро что-то произойдет.
3:15 KAN 100 по game!
3:16 zemen 42 по game. Прогресс. Никиты, присоединяйтесь :)
3:23 Scorpy поднялся на 30 место со 172 баллами.
3:24 От KAN еще одно 30 по rail. Будем ждать больше.
3:25 Umqra 42 по game. Отложить wall это правильное решение в такой ситуации.
3:34 Umqra 100 по game! Интересно, что он будет делать дальше. Видимо у него есть плохое решение по wall и никакого по rail. 3:40 KAN присоединился к большой группе по 256 3:47 dragonic уже сидит без посылок почти два часа. Интересно, что бы это значило? Пишет какой-то ад по rails?
3:53 Тем временем, все еще только два человека имеют 300. И 10 256. Вероятно отсечка золота после первого тура будет проходить по отметке 230. Причем очень сильно деленному 230.
3:58 dragonic послал 8 по rail. Ну хоть что-то за 2 часа.
4:05 Еще одно 300 — Leoyu
4:14 Umqra 30 по rail. Интересно. Видимо он написал что-то другое с багами.
4:23 От zemen как уже больше часа ничего. Интересно, что он сейчас делает? Надеюсь скоро увидеть 100 по game или 56 по rail.
4:34 Привет сборной Казахстана. Miras321 100 по game, NurlashKO 30 по rail с интервалом в 10 секунд.
4:35 Пока писал последний пост dragonic сделал 30 по rail
4:42 Очереди тестирования кажется совсем нет. Ну либо они пишут во времени посылки время, когда она протестирована. Тем временем еще 30 по rail от dragonic.
4:44 Внезапно, 261 от AstroConjecture 4:47 Я ушел ближе к месту проведения, так что видимо это последний пост. Надеюсь кто-то из ребят еще порадует в последние минуты. 4:59 Удачно прошел. Umqra 100 по rail, zemen 30 по rail. 5:00 Контест закончился,возможно еще несколько не протестированных посылок.

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +93
  • Vote: I do not like it  

By PavelKunyavskiy, 3 years ago, In Russian,

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

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

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

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

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

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +94
  • Vote: I do not like it  

By PavelKunyavskiy, 3 years ago, In Russian,

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

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

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +114
  • Vote: I do not like it  

By PavelKunyavskiy, 3 years ago, translation, In English,

Topcoder SRM 600 will be held next Saturday in 21:00 MSK

On round they promise 120 t-shirts for Div.1 and 40 t-shirts for Div.2, half for top ranked, and half the participants randomly chosen among having more zero points.

But that's not all. On Sunday 21:00 MSK there will be held non-rated SRM 600.5 (Special Round Match). Where there will be 40 more t-shits and 600$ prize for first place. Round will have duration of 4 hours and consists of two tasks, which did not give on-sight TCO as too complex and one Div1-Hard level. Besides the top 40 with a nonzero score promise 10 t-shirts for random spectators (people who were logged in the arena more than 3 hours of 4).

UPD: Since this match TL and ML are indicated in the problem. The authors say that they will try to use TL 2 seconds and ML 256 MB for most porblems. (used to be 64MB)

Read more »

 
 
 
 
  • Vote: I like it  
  • +205
  • Vote: I do not like it  

By PavelKunyavskiy, 4 years ago, In Russian,

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. У WJMZBMR 200. Впрочем, резервные задачи по словам жюри еще проще.

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

1:08 К KAN и WJMZBMR присоединились 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 WJMZBMR 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. Есть поле 109 × 109. Надо отвечать на запросы изменить значение в клетке, и посчитать gcd на прямоугольнике. Изначально везде нули. Решение В задаче русским по белому написано, что надо сделать какую-то двумерную струтуру данных. Например двумерное неявное дерево отрезков, или дерево отрезков декартовых деревьев. В любом случае надо искать баланс между временем и памятью и прочими радостями жизни. Слава богу, у топа время на написание будет предостаточно. Конец решения

Read more »

 
 
 
 
  • Vote: I like it  
  • +67
  • Vote: I do not like it  

By PavelKunyavskiy, 4 years ago, In Russian,

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

UPD Scoreboard

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

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 немного намекают...

Read more »

 
 
 
 
  • Vote: I like it  
  • +124
  • Vote: I do not like it  

By PavelKunyavskiy, 4 years ago, In Russian,

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +56
  • Vote: I do not like it  

By PavelKunyavskiy, 4 years ago, In Russian,

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +31
  • Vote: I do not like it  

By PavelKunyavskiy, 4 years ago, In Russian,

Добрый день.

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

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

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

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

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

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

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +30
  • Vote: I do not like it  

By PavelKunyavskiy, 4 years ago, In Russian,

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +45
  • Vote: I do not like it  

By PavelKunyavskiy, 5 years ago, In Russian,

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +10
  • Vote: I do not like it  

By PavelKunyavskiy, 5 years ago, translation, In English,

Hello!

We are happy to invite you to participate in today's round. I hope everyone will find interesting problems for him. And most of the round participants will like it as well as the previous one.

Today's contest was prepared for you by SPb SU 4 team (Alex-Gran (Alexandr Granovskiy), Dmitry_Egorov (Dmitry Egorov), kuniavski (Pavel Kunyavskiy)). After long thoughts you can notice that we present St.Petersburg State University.

Thanks very much for help in the tasks preparation to Artem Rakhov(RAD), Gerald Agapov (Gerald) and Maria Belova (Delinur) for translation statements. Also thanks to Petr Kalinin (KAP) for statements proofreading.

In today's contest there will be seven problems (5 in each division) about the country where wizards live, and this causes many interesting events. Today you have to take part in local meeting, understand the intricacies of writing spells, ride on the magic transport, try to take away magic prizes, play in popular wizards game, help magic government in ruling the country and resolve financial dispute of two famous wizards.

Scoring is standard is standard in both divisions today (500-1000-1500-2000-2500).

UPD: analyse was published.

Good luck!

Read more »

 
 
 
 
  • Vote: I like it  
  • +207
  • Vote: I do not like it  

By PavelKunyavskiy, 5 years ago, In Russian,

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

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

Read more »

 
 
 
 
  • Vote: I like it  
  • +40
  • Vote: I do not like it  

By PavelKunyavskiy, 5 years ago, In Russian,

Появилась информация о Russian Code Cup-2012.

А теперь, внимание вопрос.

Из правил: Вы имеете право участвовать в Russian Code Cup (далее — RCC), если соответствуете следующим требованиям на момент регистрации: Вам 18 и более лет Вы не являетесь сотрудником или близким родственником сотрудника группы компаний Mail.Ru Group Данные ограничения не распространяются на участников онлайн-туров, но в случае несоответствия требованиям такие участники не допускаются до финала.

Правда ли что это означает, что в онлайн раундах можно участвовать всем?

Read more »

 
 
 
 
  • Vote: I like it  
  • +30
  • Vote: I do not like it  

By PavelKunyavskiy, 5 years ago, In Russian,
Опять таки, удивившись что темы до сих пор нет решил создать.

Завтра(а скоро уже сегодня), 20 января 2012 года в 6:00 MSD пройдет SRM530.

Read more »

 
 
 
 
  • Vote: I like it  
  • +35
  • Vote: I do not like it  

By PavelKunyavskiy, 5 years ago, In Russian,

Сегодня в 21:00 MSD состоится Single Round Match 527. Так как темы до сих пор почему-то не было, я решил создать.

Read more »

 
 
 
 
  • Vote: I like it  
  • +39
  • Vote: I do not like it  

By PavelKunyavskiy, 5 years ago, In Russian,

Здравствуйте. Это тема будет не таким уж и оффтопом. Хотя к спортивному программированию имеет не большее отношение, чем висящее сейчас в прямом эфире.


Почему-то не работает предпросмотр, т.е при нажатии соответствующей кнопки появляется пустое окно. Оставляется комментарий нормально.

P.S. Надеюсь что администрация все таки заметит это, не смотря на дурацкое название.
P.P.S. А предпросмотр поста работает.

Read more »

 
 
 
 
  • Vote: I like it  
  • -15
  • Vote: I do not like it