Sheldon mode on? :) Ну да, ну да, он там есть, только не участвует и не заходил туда почти 4 года :)

Последние пару лет в составе Unpredictable/Unpretired есть Вася Астахов. Его нет на codeforces/topcoder, и он не пишет код и не участвует в личных соревнованиях. Но при этом он однозначно самый полезный человек в команде :)

Не надо путать комадный и личный спорт. Команды, распадающиеся в прямую сумму сильных индивидуально участников, — далеко не самые сильные.

Кто все эти люди? :) (из всего списка раньше слышал только про Шелдона Купера).

Все эти теории (“модно” и т.п.) выглядят очень притянутыми за уши и странными. Вы видели хоть одного живого человека, который сменил ориентацию из-за моды?

А вообще, хватит в 100500ый раз пережёвывать одни и те же аргументы. На кодфорсес уже был срачъ на эту тему, не надо устраивать ещё один (если он вам показался недостаточно цивилизованным/адекватным — вперёд сюда).

Кстати, а где команды контест пишут? Правда ли, что вот здесь? Т.е. далеко-далеко от гостиницы, зато близко к аэропорту?

По статистике, которая есть у меня (выборка из одного элемента), — отрицательно коррелирует :) Хотя я скорее поддерживаю утверждение “не надо после школы жить дома с родителями”, а не “обязательно надо жить в общаге”.

А кстати, контест по характеру задач для тебя очень подходит. Что ж ты заменой к any_random не пошёл (они ведь вдвоём онсайт писали)? Ну да ладно, в следующем году наверстаешь упущенное :)

Не знаю-не знаю, мне кажется, что если учитывать результаты с фейлами как у Азова — то уж точно без задачи, по которой был фейл (т.е. без E). Я конечно понимаю, что сдавшие ее потратили на это какое-то время, но вот многие из несдавших — потратили гораздо больше времени, т.к. писали/дебагали правильное решение.

Да, это существенно повлияло на действия всех команд, и по-хорошему должен быть незачетный этап. Но тогда в этом сезоне как-то совсем мало этапов получается. Имхо, вариант “добавить и это и Азов” — вполне приемлемый, правда, я бы предложил в этом случае выкидывать 3 худших, а не 2 (1 + 2 полу-незачетных).

И принести с собой бумажку с суфдеревом? :) По правилам распечатывать во время контеста prewritten-code и перебивать его с бумажки нельзя.

Хешами — очень просто, Используем примитив “lcp двух подстрок чего-то из того, что дано на вход, за log length”, с его помощью умеем сравнивать 2 любых суффикса за log их длины. Дальше сортим все суффиксы 2ого набора и ищем там бинпоиском суффиксы первого набора (наверное, можно было его тоже посортить и merge сделать). Итого n log^2.

Мне гораздо более интересно (в очередной раз :) ), как ее все суфдеревом посдавали. Неужели все настолько круты, что суфдерево с такой скоростью по памяти пишут? Чувствую себя неполноценным олимпиадником :(

Почему вы не будете повторять эту операцию вечно, гуляя по циклу?

Подойдёт, конечно, если веса правильно расставить.

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

Собственно, посмотреть, как вы это будете доказывать, гораздо интереснее :) Если для 3х путей ещё можно поверить в “интуитивную очевидность”, то для N — уже сложнее (см. i_love_natalia, который пытался привести контрпример). Если так пугает слово “доказательство” — можете считать, что в задаче просят предъявить пример графа в случае “Yes” :)

Ну так я и говорю, что для 3х это просто. Но если “даже не хочется доказывать” — то почему бы не заставить участников немного подумать.

Не понял примера. “1 2 3” и “3 4 1” противоречивы.

Эх, моя ошибка, надо было в случае “Yes” попросить предъявить граф :)

Работать-то может и работает, а вы докажите. Для 3х путей доказательство тупое, т.к. можно просто все случаи разобрать и графы предъявить. Для произвольного N поинтереснее.

На кодфорсес он редко бывает, так что разве что лично :) (для участников яндекс-тренировок это просто). Если очень интересно и не хочется ждать — могу попробовать вспомнить (там несложно было, по крайней мере, если знать итоговое время работы).

Проблем с точностью тут не может быть, т.к. при переходе к следующему слою динамики ошибка уменьшается в M раз. Ищите багу, 26 тест небольшой :)

Дополнительное упражнение — решить (и доказать!) эту задачу для N путей.

В A, насколько я помню, авторское решение работает за . Автор задачи — Вася Астахов, можно подробнее спросить у него (ну или я вспомню и напишу). Есть также кубическая динамика, но она медленнее работает :)

Нигде снаружи условия вроде не выложены, они пока доступны только в системе. Так что не читеря внаглую (вроде “одолжить условия у друзей”) — не могут.

Ну не знаю, на Java дабловое решение переделывается в “целочисленное” (учитывая, что мы работаем только с числами вида a + sqrt(b), где a, b — рациональные) за 5, максимум 10 минут. А на c++ за конечное время на контесте не переделывается. Так что это задача не на “развитие пространственного воображения”, а на “шаманство с eps” либо “кодирование на джаве” :)

Ну учитывая, что тут всё можно посчитать абсолютно точно в квадратичных иррациональностях с длинкой, то скорее всего у авторов есть такое решение. Если нет — то они не очень правы :)

А как все сдавали G? У нас были какие-то пляски с epsilon’ами и WA на >70 тестах. Или там предполагалось в integer’ах/rational’ах писать?

Who are you, if it is not a secret?

У Unpretired есть как минимум одна вакансия на 7 и на 9. Правда, проблема в том, что вакансий может оказаться >1 :(

Для команд, у которых 5 человек в составе, — не такой уж и перебор :) А вот для остальных — небольшой марафончик получится.

А зачем в A mincost-maxflow? Там потока с нижними ограничениями хватает. И кстати, где можно посмотреть mincost-maxflow твоей библиотеки, который на 100000 вершин работает? Неужели ты закодил cost scaling oO?

Ну так без растягивания/сжатия даже семпл не парсился. Так что вряд ли пролема у Nickolas была в этом.

Ну, мы ту табличку не увидели, т.к. свалили сразу после того, как дописали нашу K. Интересно было бы посмотреть на итоговые результаты (наша стратегия отличалась от вашей только тем, что мы строили не только захватчиков городов, но и разведчиков :) и ещё какими-то глюками в протоколе при общении с сервером).

Несколько дополнений по задачам:

A — задача на поток (вертикальные/горизонтальные непрерывные куски коридора — вершины, клетки — дуги). Видимо, там заходил и тупой поток, но мы написали preflow-push (на макстесте работало сильно меньше секунды).

FGH — у нас никаких помех ближе к концу не было, получались совершенно нормальные картинки :) Может, вы как-то криво парсили? В F мы сдали всё, в G — только первые 2 теста (в последнем там даже склейка кадров infinity работала; 3-4 мы не сдали из-за багов во внутрикомандном взаимодействии :) )

K — а там можно где-то посмотреть итоговый зачёт? Вообще мне показалось, что правила проведения турнира там были довольно странные.

L — а Havka-Papstvo там всё вручную сделали — весь прикол в правильных инструментах для ручного решения.

Да, это общая проблема всех турниров — цели “максимизировать свой результат” и “попасть в топ-50/25” зачастую предполагают совершенно разные стратегии. С другой стороны, если ты по-настоящему крут, ты пройдёшь в эти топ-50 независимо от стратегии (даже если будешь тупо решать задачи подряд). Лично я стремлюсь к этому идеалу :) (хотя мне до него далеко), и тупо всегда действую по стратегии для случая “максимизировать свой результат”.

Нерейтинговыми турниры имхо делать не стоит, т.к. рейтинговых контестов и так мало (особенно в удобное для fulltime-работающих людей время). Можно было бы решить эту проблему, не делая отсечку “топ-50 по одному контесту”, а сделав что-нибудь в стиле “топ-50 в среднем за 5 контестов”. Но это утопия, откуда столько задач для этих контестов взять…

В чём-то вы конечно правы, со спортивной точки зрения это некоторый минус. Но когда я говорил, что раунд хороший, я не претендовал на абсолютную истину, а выражал своё мнение (а я уже довольно давно участвую в контестах не ради спортивных достижений, а for fun; и единственный критерий качества контеста для меня — интересность задач).

Дададада, поддердживаю :) Хотя, честно говоря, по модулю бага с челленджем раунд был очень хорошим. (а я ссзб, забил на перечитывание своего кода перед/после сабмита :( )

Лол, оно походу разрешает ники любой длины, ограничение только на стороне клиента стоит. Security bug :) Upd: нет, не баг, на сервере просто другое ограничение.

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

E — просто зашкаливающе интересная задача, перебор с (!) неасимптотическими оптимизациями. Какая красивая и новая идея, просто rocket science :)

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

Забьёшь на GCJ и TCO? ;)

Ну так кто ж итерациями ФБ делает. По-хорошему, надо вообще писать ФБ-Тарьяна, он мало того что быстрый, так ещё и нахаляву ищет отрицательные циклы.

По поводу C: я писал немного другой поток, с совсем простым графом: сожмём время, пусть все моменты времени — t₁, …, t_k. Они будут вершинами, граф — это цепочка t₁ - … - t_k (все рёбра capacity=k и cost=0) + для каждого задания [l, r] стоимости c ребро из r в l стоимости  - c (и capacity 1). И во всём этом деле надо найти циркуляцию минимальной стоимости. Правда, на контесте у меня оно не зашло, т.к. я разучился писать циркуляцию, а искать prewritten code — неспортивно. Надо будет додебажить и проверить, влезает ли оно в ТЛ…

Ну челленджи-то обычно на простых крайних случаях происходят, а в претестах все крайние случаи были покрыты. Пример: сегодняшняя B, случай “ответ равен длине первой строки”. В этом месте очевидно можно набажить (двигая 2 указателя, сделав полный круг), и этот случай зачем-то был в претестах. Вот не было бы его там — можно было бы от души почелленджить, т.к. народ вполне себе на этом падал.

Просто обычно претесты не слишком отличаются от семплов, и челленджи идут гораздо активнее :)

Кстати, давно (начиная с первого раунда) хотел спросить: а зачем авторы во всех раундах делали такие неприлично сильные претесты? Челленджей за все 3 рауна O(1). Если это такой хак, чтобы превратить правила codeforces во что-то другое — то не проще было это напрямую сделать?

Я уже попробовал этим заняться :) (поискать читеров), но тут есть одна проблема — у многих решения по C очень похожи, но дисквалить на этом основании нельзя, т.к. у них там prewritten code + 5 строчек. Так что вся надежда на то, что кто-нибудь из 17 китайцев откажется.

А тут есть правило про то, что если не все из топ50 поедут на онсайт, то приглашаются следующие участники?.. :(

Рассмотрим цепочку рёбер capacity = k, cost = 0, для каждого отрезка [l, r] — ребро r->l capacity = 1, cost = -c. Только учитывая, как её посдавали, кажется, решение там реализационно проще и наверное баян… :(

В общем, проблема лечится vpn’ом на российский сервер. Но надеюсь, snarknews разберётся с хостером.

А кто ещё 2 разработчика? :)

Кстати, а ты standalone-клиент не хочешь сделать? Если вдруг когда-нибудь будет крутая трёхмерная графика — javascript будет адски тормозить скорее всего.

И opencup.ru, и snarknews.info доступны с очень ограниченного диапазона ip. В частности, из Германии вроде ниоткуда недоступны. Даже vpn не спасает. Похоже, “умный” хостер всё ещё думает, что opencup ддосят, и поэтому блокирует доступ почти отовсюду.

Про ip — ну совсем не аргумент. Что мешает читеру через tor читерить? Имхо, для борьбы со вторыми аккаунтами надо придумывать что-то более интеллектуальное.

А можно подробнее про API полигона? Где про него можно почитать?

Эм, так wildcard же будет. Или всё, что не по правилам acm или codeforces, вы не решаете? :)

А покажи свое решение. Мы пробовали правильное решение написать, но там адовейший адец :(

Мы весь контест паттерны в слоне искали :( Это явный повод для unrated-раунда.

Учитывая одну и ту же страну в профиле людей с таким эффектом, можно предположить, что “доблестные” беларусские провайдеры блокируют vkontakte.ru (но не догадались заблокировать заодно vk.com).

Ага, мне тоже пришло, там ещё отправитель — не рассылка, а какой-то конкретный человек. Так что наверное кто-то просто не ту кнопку в почтовом клиенте нажал.

Ну я упихал тупейший перебор — только на последнем уровне рекурсии вручную всё рассмотрел, а не как в общем случае. На худшем тесте успевало с запасом в 3 раза.

Ещё вопрос — из условия следует, что обязательно надо отдать приказ каждому жуку; из “формата выходного файла” — что необязательно: “Перед обработкой приказов будет проверено, что в каждой клетке (ip; jp) жуков не меньше, чем сумма количеств жуков во всех приказах, исходящих из этой клетки”, т.е. больше может быть. Как правильно?

Что-то никак не пойму из условия — “Тогда с вероятностью a/(a+b) погибает один из жуков второго игрока, а с вероятностью b/(a+b) погибает один из жуков первого” — эти события независимые? Или взаимоисключающие? Т.е. если a = b = 1, то с вероятностью 1/4 умрут все жуки, или с вероятностью 1/2 останется только первый, а с вероятностью 1/2 — только второй?

Ага, ещё в прошлый раз немного опечалило отсутствие комплекта для других ОС. Пожелание ftc — может, лучше делать комплект для локального запуска на чём-нибудь кроссплатформенном, например, на java?

Ну где-то полгода назад они точно были разные. По крайней мере, на одних мой код стабильно влезал в ТЛ, на других — стабильно не влезал. И во время контеста при тестировании на макстесте мне повезло с машинкой, а на систестах — нет. После контеста я поэкспериментировал с добавлением пробелов в программу и обнаружил, что разброс был ~100мс (не помню сейчас точно, но 50мс точно было).

Ну да, 40945109233456 — это 7ая джава.

Ну, “очень нехорошо” уже то, что машинки разные. Остаётся надеяться, что вконтакт проспонсирует на запупку одинаковых :)

Сходится идеально. Логи запусков в правке, первое число — System.nanoTime(). И да, 0 только на 7ой джаве.

А, нет. Вот машинку с 1.6.0_30 нашёл :)

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

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

Ну это пока не опровергает мою гипотезу. Поведение может зависеть не от пробела в коде, а от версии джавы.

Думаю, тут прикол в другом. На codeforces если код скомпилировался — то все его последующие запуски будут на одной и той же машинке. Добавляя пустые строки, вы заставляете его перекомпилироваться и сменить тем самым машинку. А тестирующие машинки разные — я на это уже разок напоролся (в “запуске на сервере” мне повезло с машинкой, а в систестах — нет). Видимо, java там тоже разная :)

Уже не помню, может, и о ней. Там точно были строки :)

А, да, это известный хак. Как-то применяли его, в какой-то задаче надо было сделать O(1) преобразований, а у нас O(1) было слишком большим :) Пришлось упихивать ногами и руками.

А что за учёт вещественности? Округление? :) Да, его всегда приходится писать. Или в чём вопрос?

Ну а я про это и говорю, что проще запомнить magic из нерекурсивного преобразования, чем делать всякие оптимизации/запихивать :)

Потому что vector. Complex всё же побольше памяти занимает и подольше выделяется.

Вполне допускаю, что какая-нибудь рекурсивная реализация порвёт по времени мою нерекурсивную :) Но мне гораздо приятней писать код, не делая кучу преждевременных неасимптотических оптимизаций. Т.е., например, храня многочлены в vector<complex >. И рекурсивная версия на многочлене размера 2 миллиона сделает столько переаллокаций памяти, что в ТЛ уже вряд ли влезет.

Рекурсивный Фурье — да, интуитивный, но он тормозной. А вот “магические” манипуляции в нерекурсивном Фурье проще запомнить (мне, по крайней мере). Если их выводить на контесте с нуля — можно много времени просадить на это занятие.

Какие-то странные утверждения. Вот Петя, например, на последнем opencup’е потерял немало времени на задаче про Фурье, т.к. он в отличие от большинства честный и писал его сам.

Вообще, моё мнение — prewritten code лучше всегда разрешать, соревнования ведь по программированию, а не по заучиванию кусков кода наизусть. Да и в дальнейшей карьере (при реальной работе) изобретать велосипеды крайне противопоказано. Правда, тут возникают всякие проблемы с всевозможными онсайтами вроде GCJ, где интернета нет и преимущество получает тот, кто притащил с собой 100Гб prewritten кода. Но это довольно несущественные проблемы, если problemset нормальный.

Про ограничения сверху, думаю, дело в другом.

Во-первых, одной из (и наиболее вероятно, основной) целей любого контеста, проводимого вконтактами/фсбуками/… (тем более, в который столько денег вкладывают), — набор персонала. Из людей >23 лет большая часть уже где-то работает и место работы будет менять неохотно. Видимо, организаторы выбрали некоторый tradeoff между уроном имиджу соревнования из-за ограничения и количеством потенциальных работников в топе, максимизирующий (с их точки зрения) матожидание набранных людей.

Во-вторых, некоторые считают, что участвовать в контестах ветеранам “не надо”. Ну т.е. что это неправильно и не надо это поощрять. Не знаю, имеет ли это отношение к данной ситуации, просто такое мнение я тоже слышал.

Ну а что касается спортивной составляющей — тут однозначно ограничение будет дискредитировать результаты. Т.е. получится, что какой-нибудь SNWS, который snarknews практически в одиночку проводит, имеет более credible результаты, чем так тщательно организованный чемпионат.

< trololo> Что ж тогда ботоводы не смогли выиграть? :) < /trololo>

Этот “контест” не анонсировался ни на snarknews, ни на codeforces, и задачу взял проверенную временем. Так что можно с чистой совестью обсуждать тут идеи. Если кто в нём вдруг решил участвовать — могу выложить свой код в открытый доступ, feel free to improve :)

Краткая идея в правке.

Мда, внезапно, в итоге моя программа на первом месте… Неожиданно, учитывая, что я забил на этот контест, после того как понял, что моя программа делает полный бред :)

Интересно, а что писали все остальные? Что-то умное, но с багами, так, что оно моему бреду сливало? :)

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

Ну надо перемножить два многочлена, каждый размера 800^2, что меньше миллиона. Фурье конечно приходится делать для 2^21, т.к. результат имеет размер больше миллиона.

Ух ты, а на CF можно только собственноручно написанным prewritten code пользоваться? Я неоднократно видел копипасту с e-maxx.ru решениях участников… Если это правило так хорошо “соблюдается” — наверное, надо либо всех подряд банить, либо убрать это правило.

Трололо. Вы думаете, что такого толстого комментария хватит, чтобы развести тут классический срачъ Овуляшки vs Чайлдфри? :)

Мда, после 5 лет ACM совесть не даёт такое писать :) Надо мне переучиваться :)

Мы — Unpretired (8 место), состав Michael, ilyakor и Вася Астахов.

По поводу впечатлений (расскажу свою личную точку зрения) — весьма своеобразный контест, не очень похож на ACM. Стратегические решения тут возможно даже важнее, чем умение решать задачи. Например, для меня было неожиданностью узнать после контеста, что по задаче B можно было сделать 8 тестов из 10 тупо квадратом, и не надо было писать всякие kd-деревья. Ну или задача про оптимизацию программы — кто ж знал, что они дают кучу баллов за сабмит input’а :) Ну а в целом — прикольный контест, особенно порадовали “4” треугольника в 1 тесте задачи A и комментарии Michael по поводу py-glpk в процессе решения задачи про обмен валюты :)

“Продвинутости” не требуется, нужен человек, который умеет придумывать нетривиальные вещи. У cerealguy в команде как раз с этим всё в порядке :) Наверное, можно запихать и что-то совсем безыдейное, но с математиком она решается быстро и без проблем.

B — прикольная задача, проверяет факт “в команде есть математик”. А в хороших командах всегда нужен математик :)

А что не так с I? Два прямых и один обратный Фурье для многочленов размера миллион — это же очень быстро, укладывается в ТЛ с большим запасом.

Ааа, я понял, что все делали, спасибо. Не знал, что у квадродерева настолько большая константа, что оно тупняку сливать будет…

А чем случаи “A и B маленькие” и “хотя бы одно из чисел большое” особенные? И что у вас за n sqrt(n) log(n), тоже квадродерево?

Вот интересно, а что сдавали в D? Я написал следующее: нумеруем все элементы в соответствии с первой разностью арифметической прогрессии (т.е. 0 получает номер 0, A — номер 1, 2A — номер 2,… kA — номер k, потом 1 — номер k+1, и т.д.) и в соответствии со второй. Получаем у каждого элемента по 2 координаты, строим на них как на точках квадродерево. Нам приходят запросы “+1 в вертикальной полосе” и “сумма в горизонтальной полосе”, они делаются за sqrt(n) обычным способом. Казалось бы, n * sqrt(n), но оно ни в какую не лезет в ТЛ на сервере (видимо, из-за мелкого кеша). У кого-нибудь получилось такое сдать? Или есть более быстрое решение?

Ну она честно решается — предпросчитываем коэффициенты многочленов и отвечаем за O(k) на запрос. Что такого полезного для задачи по приведённой ссылке на wiki (и при этом не выводящегося на бумажке за 5-10 минут) — непонятно.

Зачем в I двумерное Фурье? Одномерного достаточно — нужно произведение sum a{i,j} x^{im+j} и sum b{i,j} x^{mn — (im+j)} (где m — ширина большого поля).

Run id = 39442 (ну или могу сам исходник выслать). Ещё я поставил assert на то, что clock() перед выводом данных — clock() после чтения данных < CLOCKS_PER_SEC * 0.9. Assert не падает, но выдаётся ТЛ. Так что всё же с ТЛем что-то странное.

Что-то не очень она пофиксилась… Зато в процессе нашлась ещё одна проблема. В Visual Studio C++ если кинуть исключение, программа немедленно прибивается, даже если это исключение дальше ловится. Так что у меня возник закономерный вопрос (раз ваш invoker как-то узнаёт про брошенное исключение) — а как вы запускаете программы? Надеюсь, не в debug-режиме? Это бы объяснило все проблемы со временем.

Эм, т.е. это 10 секунд не процессорного времени моего решения, а 10 секунд астрономического времени моего решения + чекера + решения соперника? Это было бы совсем странно. Я clock()’ом замеряю время между моментом, когда я закончил читать данные, и моментом, когда я вывожу ход. Казалось бы, это ровно процессорное время моего решения… Так что странно, буду разбираться, что не так.

Что-то я не понял, а что у вас с ТЛ’ем? Написано 10 секунд на 10 ходов — т.е. секунда на ход? Моё решение упорно ТЛится, даже если отсекать по CLOCKS_PER_SEC/2. Или на вашем сервере clock() не работает?

It is not stated clearly in the rules: what happens if some of the top-25 contestants can not attend to the finals (for example, because of visa issues)? In this case will contestants with places 26+ be invited to the onsite?

Кстати, а кто из прошедших есть на codeforces? Предлагаю составить список.

1. vepifanov
2. ACRush
3. meret
4. RAD
5. e-maxx
6. Petr
7. sdya
8. jacob
9. romanandreev
10. jakubr
11. watashi
12. hos.lyric
13. iwiwi
14. ainu7
15. ploh
16. RAVEman
17. Alexander
18. cerealguy
19. tomekkulczynski
20. ???
21. pparys
22. kelvin
23. gawry
24. ilyakor
25. tomek

Мда, 26-28 места — печалька. Кстати, а по их правилам берут людей после 25ого места, если кто-то из топ20 отказался или не дали визу?

А с чего бы было верно резать по стороне трапеции? :) Я всегда удивляюсь этой стратегии решения задач — написать нечто правдоподобное, даже не пробуя доказывать; “не получается придумать контрпример — значит, правильно”? :)