Hello!
Tomorrow (the 3rd of November) will held the Nothern Subregion Quarterfinal 2012 in the Northeastern European Region.
I think, it will be very interesting to watch the "battle" between teams, because in our quarterfinal participate 3 persons from the top10 in Codeforces rating. And jury made all to make this quaterfinal very interesting and unpredictable.
Also, don't forget, that you can participate in Yandex.Contest.
Who are participants from CF top10? Dmitry Egorov, yeputons and ... ?
tourist
did not he participated in ioi? how is it possible?
Also two world champions!
Really?But students who had participated in two ACM-ICPC world finals aren't eligible to participate again.(as far as I know)So a student who won two world champions can't take part.
Зеркало будет?
The problem statements will be only in russian language?
There will be only English problem statements.
Delay for the second time :(
Кто-то знает, где можно будет смотреть борд онсайта?
http://neerc.ifmo.ru/information/northern-2012.html
Это не команду SPb SU 3 Taken случаем дисквалифицировали?
Это провал года.
А о чём речь можно узнать? Что за дисквалификация?
Судя по твиттеру парни заныкали на машине вовремя пробного тура суффиксное дерево. Хотя между турами админы чистят рабочие машины видимо чтобы никакого prewritten code
Получается, дисквал они получили за то, что админы недобросовестно выполнили свою работу?
Хочу больше подробностей об этом инциденте. Напишите кто-нибудь, кто в курсе.
Их подискваили за попытку сохранить код между пробником и основным туром в неположенном месте.
А почему бы просто не запретить писать во все директории, кроме рабочей? Кто может гарантировать, что на своем компьютере на основном туре я не найду заранее подготовленный недоброжелателем файлик с олимпиадным кодом?
Там все чистят. А запретить писать в мои документы не стоит потому что могут начать тупить среды и не только. В общем там какая-то дебильная ситуация получилась. Они вроде даже утверждают что сохранили по ошибке.
с физическим запретом нормально не будет работать ни одна современная IDE со своей любовью писать много всего куда-то в %USERPROFILE%
поэтому запрет существует лишь в правилах в виде вот такой строчки:
During the practice session teams may not store any source code anywhere except working directory.
в случае с обсуждаемой командой запрет был очевидно нарушен записью prewritten code в дебри того самого %USERPROFILE% отдельно от настроек любых IDE, что мало похоже на случайную ошибку.
ловится ли это автоматически или вручную — вопрос, не имеющий отношения к теме.
(все написанное есть личное мнение свидетеля этих событий; я не являюсь представителем жюри)
Может быть, стоит давать более содержательные задачи на пробный тур, чтобы участникам некогда было заниматься ерундой?
Пробный тур для этого и нужен :)
Ерунда — это когда команды сдают две халявки и уходят с пробного тура. Здесь же вполне целенаправленное нарушение правил.
Свечку держал?
А какие-нибудь ссылки есть?
Официальных нет, а так чуваки в твиттере с места событий писали: https://twitter.com/karlicoss
Как можно было сдать задачу С за 11 минут не используя OEIS (я говорю про трансляцию контеста на Yandex.Contest)?
Судя по фразе отсюда "Правила отдельных раундов совпадают с правилами официальных четвертьфиналов", гуглить ответы нельзя, поскольку на официальных четвертьфиналах это запрещено. Или я не прав?
А где в правилах написано, что нельзя использовать OEIS?
Во-первых, ссылка на правила вот. Во-вторых, на онсайтах интернета просто нет, а приносить с собой всякие материалы и общаться с другими людьми запрещено по тем же правилам:
Но то, что интернета там нет, не означает, что им запрещено пользоваться, не так ли? :)
Конечно не означает. Правда, запрещено пользоваться computing devices (handhelds, portable PCs, notebooks, calculators), mobile phones or any other communication devices.
Но, если Вы умеете выходить в интернет без всего этого, то, пожалуйста, пользуйтесь.
Чип в мозг с вайфаем разрешен?
Полагаю, запрещено пользоваться лишь принесёнными с собой вычислительными устройствами — ведь компьютером, предоставляемым жюри, пользоваться можно. Полагаю также, что я могу свободно использовать и свой домашний компьютер на онлайн-аналоге контеста.
Разумеется, большинство решений с OK там — константные массивы. А чего ещё ожидать от такой задачи? Если давать на онлайн-контест такой баян, большинство участников не справится с соблазном загуглить это за 15 секунд.
Ну давали-то ее изначально не на онлайн контест. Авторы знали, что у участников не будет инета, так что почему бы не дать? Я когда писал онлайн, специально не копипастил с OEIS, чтобы быть на равне с теми, кто пишет без интернета. Тем более, что контест проводился по правилам онсайта. Видимо, другие участники так не думают.
После 100500 OpenCup'ов, на которых куча команд гуглила задачи, веры в абсолютную честность большинства участников не очень много :) К авторам конечно претензий мало (разве что, эта задача — баян, а нетривиальные баяны сильно хуже тривиальных). Я только хотел сказать, что ничего неожиданного в такой ботве на онлайн-контесте нет.
А в Армении сдают задачу на 1:00. Это при том, что включить компьютер, залогиниться в систему, набрать в блокноте A+B и отослать занимает в лучшем случае 1:20 — 1:30.
В Узбекистане же это отнимает 1:54, что тоже не похоже на честную игру: задача там все-таки не A+B, и надо было немножко подумать.
Я говорю про конкретную задачу, которая без готовых ответов совсем не очевидная. Это сильно запутывает, когда задачу, которая по сложности в контесте как минимум седьмая (по крайней мере, мне так кажется), сдают на 11 минуте второй по счету. И после этого ты начинаешь над ней думать, а она так просто не решается.
И если в приведенных тобой примерах могли просто начать кодить на 3-5 минут раньше, то здесь это не поможет.
Мои примеры вообще доказывают нарушения регламента в официальных контестах и не имеют отношения к задаче C.
С которой, в общем-то, понятно, кто как ее решал и на какие сайты при этом заходил :) Можно было, например, открыть официальный монитор и убедиться в этом.
Собственно, мы тоже зашли куда надо под конец контеста; если бы играли на онсайте, реальное наше место — 21-ое с 7 задачами и 964 минутами штрафа.
Да, мы (в Армении) начали 5 минут пораньше, но не думаю, что этот факт каким то образом повлиял на общий монитор.
fuck the system
Мне кажется, или действительно результаты команды SPb SU 4 (Egorov, Kunyavskiy, Suvorov) появляются с какой-то задержкой. Задача С сдана на 215мин, а в таблице появилась определенно позже. Только что появилось ?6 по J, хотя контест уж давно кончился. Может они как-то отдельно от других решают?
UPD. Выяснил. У них были какие-то проблемы, им чуток контест продлили.
У нас у компьютера были проблемы с памятью и при попытке скомпилировать решение комп перезагружался. В результате нас пересадили на другое место, компенсировали 15 минут. Отсюда и задержка.
Как решать Н ?
Расскажу про самую сложную часть задачи — нахождение пар "специализированных" медсестер, не имеющих возможности одновременно уйти в отпуск.
В-общем, построим граф по условию, с раздвоением всех вершин (входящие ребра входят в одну вершину, исходящие выходят из другой, и между ними ребро). Вершины, соответствующие "обычным" медсестрам я буду называть белыми, соответствующие "специализированным" медсестрам — черными. Переберем первую черную вершину, найдем любой путь из ее первой половинки во вторую половинку любой белой вершины и развернем все ребра на этом пути. Теперь в полученном графе проверим достижимость вторых половинок белых вершин из первых половинок черных вершин (один ДФС). Если из какой-то черной вершины мы не сможем дойти до белой вершины — значит, мы нашли пару, которая войдет в ответ.
P.S. Я сегодня на собственной шкуре узнал, что можно выиграть четвертьфинал, и при этом быть ужасно недовольным своим выступлением. G, H, I — те три задачи, которые были нами придуманы, и при этом ни одна из них не была до конца реализована...
UPD. Кто расскажет, как решается I с питерскими ограничениями?
Я решал так: Вычислим значение формулы для всех 212 наборов значений переменных. Будем делать это обычным рекурсивным разбором выражения, только ответом будет не одно число (0 или 1), а битовая маска из 212 битов (кстати, для маски очень просто делать все логические операции, которые есть в условии (~ x, x&y, x|y, ~ x|y, ~(x^y))).
Теперь допустим, что наборов значений переменных, где формула принимает истинное значение (cnt), не больше половины. Тогда для каждого такого набора заведём вершину в первом слое и пустим в неё по одному ребру из A, B, ..., L, ставя отрицание там, где соответствующая переменная равна 0. И добавим ещё 11 рёбер из 0-й вершины.
Теперь в вершину второго слоя пустим cnt рёбер из 0 с отрицанием.
Для случая cnt > 211 в первый слой ставим вершины, на которых значение формулы — 0. А в вершину второго слоя пускаем рёбра из вершин первого слоя с отрицаниями. И ещё (212 - cnt - 1) ребро из 0.
Возможно, что понадобится отдельно разобрать случаи, когда исходная формула тождественно равна 0 или 1.
На contest.yandex.ru такое решение укладывается в 1 секунду на всех тестах.
а размораживать когда будут?
There's official video translation at http://www.ifmo.ru/online/online.htm
Ой. Сейчас прочитал условие L и понял его неправильно (подумал, что количество операций '+' и '-' не превышает 10000). Написал решение за квадрат и оно зашло. Так и предполагалось?
Когда я включил трансляцию под конец разбора, там обсуждали дерамиду.
Нет, предполагалось, что должно заходить что угодно быстрее квадрата, но не квадрат. Я вот почти на 2 часа увяз в дебаге корневой, в результате только при помощи стресса отловил все баги.
n*log(n) с большой константой не входил. Поделили константу на 30 — прошло.
n*log(n) в этой задаче — это около полумиллиона, я честно говоря плохо себе представляю что надо такое написать, чтобы константа была около тысячи. Почти наверняка имела место неверная реализация или неправильно оцененная асимптотика.
У меня тоже tnlog(n) (t — количество типов, 26) не зашло. Я слишком много раз делал операции с декартовым деревом (например, чтобы узнать ответ на запрос, я подразбивал дерево на три, чтобы среднее ровно соответствовало запрашиваемому интервалу).
А разве узнать ответ на запрос можно быстрее, чем разбив его на три? Не подскажете, как?)
у нас тоже не заходило одно декартовое дерево. Правда мы написали свой рандом и мелкие оптимизации... но там при каждом сплите количество вершин могло увеличиться на одну. Но мы в афиге были когда нам это пришлось оптимизить.
Ну стоит уточнить что большая константа это 26, т.е. хранили сумму для каждой буквы. По сути каждый раз делалось 26*log n * примерно 3 операции с Декартовым деревом, но всё равно выходит не так уж и много. А n*log n с одним декартовым деревом и битмасками зашёл за 0.04, так что всё ок.
Where can I find the Official Final Standing?
http://neerc.ifmo.ru/information/northern-2012.html
http://contest.yandex.ru/contest/Contest.html?contestId=98&tab=monitor&ignoreUpsolving=false
Oh, I found that in Standing
В задаче K могут встречаться нулевые площади:(
Oh, it was a hard and amazing contest. Congratulations for the winners.
Офтоп.
Со snarknews.info:
"**Поздравляем команду MIT Unpredictable (Илья Разенштейн, Рати Гелашвили, Sepideh MahAbadi) с победой в Northeastern North America Regional Contest и выходом в финал ACM ICPC 2013!**".
Меня почему-то улыбнуло...
Меня улыбнуло тоже. Присоединяюсь к позлравлениям!
Are the top-ers ( Dmitry_Egorov , yeputons , tourist ) on the same team ?
UPD: Now I know why I get downvotes . I didn't take a look at Standings.
I wonder why do people down vote ? If you have downvoted for the comment above can you please explain why?
I didn't down vote you, but maybe you got down votes because from the standing you can see that Dmitry_Egorov and tourist are from different team?
From the ranking I think that tourist is on the same team with cerealguy and niyaznigmatul.
Oh , thanx . How stupid of me? :D I did notice standings but didn't look at it. I read comments and skipped them cause I didn't understand them. I'm just 9th grade student so I just now that ACM-ICPC is a team contest .
Как надо было решать G, J и C?
Задача J.
Мы так делали: заметим (написав перебор за 5 минут), что для n >= 7 решение всегда существует. Для n < 7 считаем перебором, иначе прекалькаем (прямо в исходник) ответы для n = 7, а ответы для n > 7 получаются добавлением в конец перестановки чего-то типа n, n-1, n-2, ... 8.
Еще надо быть осторожным с тем, что четвертая функция может из-за этого преобразования поменяться, так что надо выбрать правильный ответ для n = 7, который будет прекалькаться в исходник :)
Кто-нибудь может сказать тесты для H ? Моя программа получает WA6, но она работает верна на всех моих тестах.
6 4
1 3
1 3
1 4
2 5 6
The contest is in Codeforces::Gym now: 2012-2013 ACM-ICPC, NEERC, Northern Subregional Contest
Is Codeforces::Gym available during Codeforces rated events?
Does anyone know if there will be an online version of the coming NEERC regional (not subregional)?
I think no. There was no online version in the past. But they always publish tests and solutions, so it definitely will be uploaded to Codeforces gyms 1-2 days after the contest.