Всем привет!
Сегодня будет проходить второй раунд Открытого чемпионата Москвы и МО по программированию (КРОК). Начало запланировано на 19:00.
Соревнование будет проходить по обычным правилам Codeforces, со взломами и падением баллов со временем. В Раунд 2 допускаются все участники, набравшие в Раунде 1 баллов не меньше участника на 300-ом месте. Все остальные участники могут участвовать в раунде вне конкурса. Специально для участников второго дивизиона подготовлена облегченная версия набора задач. Наборы задач официальной и неофициальной версий раундов частично пересекаются.
Контест будет рейтинговым для всех участников.
Вас ждет несколько задач, упорядоченных примерно по возрастанию сложности. Разбалловка задач как для первого, так и второго дивизиона стандартная (500-1000-1500-2000-2500). Не забывайте, что во время контеста решения будут тестироваться на небольшом наборе претестов. Тестирование на полном наборе тестов будет произведено после окончания раунда. Набор претестов не всегда покрывает все возможные случаи входных данных, поэтому внимательно тестируйте свои решения.
До окончания раунда категорически запрещается публиковать условия/решения задач. Запрещено общаться по теме задач, обсуждать какие либо мысли о возможном их решении. Давайте будем честными! Обсуждать задачи можно после окончания раунда.
В финальный раунд проходит 50 участников, показавших наилучший результат. Все участники, набравшие столько же баллов, сколько и участник на 50-ом месте, также проходят в финал.
Раунд готовили: Ripatti, havaliza, Gerald, RAD, MikeMirzayanov, Delinur.
Всем удачи!
UPD. Напоминаем, что 27 апреля в офисе компании КРОК состоится финал Открытого чемпионата Москвы и МО по программированию (КРОК). Обратите внимание, что компания КРОК не оплачивает дорогу и проживание участников финала. Все участники финала должны прибыть в офис компании КРОК (г. Москва) утром 27 апреля.
После соревнования всем участникам будет предоставлена возможность заполнить форму на согласие участвовать в финале соревнования. В финал будут приглашены первые 50 участников по результатам соревнования, которые подтвердят свое участие в финале. Подтвердить свое участие в финале можно в течение суток после окончания соревнования.
Рекомендуется заполнить форму независимо от ваших результатов в Раунде 2, поскольку отказаться может достаточно большое количество участников.
Обычно бывает необходимо набрать положительное кол-во баллов для прохода(кроме того, что попасть в необходимые места). Верно ли это сегодня?
Ну и более серьезный вопрос: будут ли приглашены участники с местами 51+, в случае отказоы выше?
Да, будут
Опять перенос на 5 минут... Почините там побыстрее, писать уже хочется!
Неужели это Elite!
Скорее "Космические рейнджеры 2: Доминаторы. Перезагрузка"
Решение за k*n в B предполагалось как верное?
Если я правильно решил, то можно за O(n + k).
Быстрые решения я прочитал, меня это и смутило:)
Меня смутит, когда O(N * k) зайдет =)
Зашло:p (940ms)
У меня 300 ms.
Ну я-то не красный)
Я смущён =)
Врядли, я надеюсь что это ТЛ. Потому что решение за O(n + k) очевидно, и будет просто несправедливо если n*k зайдет.
Это 108 операций. На плюсах должно с лёгкостью зайти.
Ах да, забыл что на КФ серверы быстрые. чоооорт, ко всем многочисленнейшим моим фейлам этого раунда добавился еще один...
Это где ж ты в последнее время видел такие сервера, где 108 не заходит?
[ирония] На РОИ. N log N на N=10^5 не зашло. Впритык упало — 1.1 секунды на макстесте. [/ирония]
Я конечно слышал, что там компы отстой, но мне кажется какой-то страшный NlogN был.
Там компы совсем отстой. Приблизительно 2*10^8 простых операций за секунду. И память/кеш "офигеть какие быстрые".
Конечно, вполне возможно, но позагонял прилично. Два запроса к дереву отрезков в цикле по N. Еще считывание 4*10^5 чисел неплохо времени занимало.
На codechef 10^7 со скрипом заходит, и то не всегда.
Codechef — вообще что-то с чем-то. Флойд на 450 за секунду заходит (что, кстати, больше
10^810^7), а решение, по асимптотике лучше, чем авторское, но с деревом отрезков вместо set<> TL'ится в хлам. Там либо лютый рандом, либо какой-то треш с кешем/памятью, других объяснений не знаю.450^3 ~91*10^6, так что все-таки меньше, чем 10^8
Спасибо, 8 --> 7.
Какой тест валит такое решение С : если max(|x1-x2|,|y1-y2|)<=4 выиграл первый, иначе второй ?
При (4, 3) и (4, 4) второй.
а как так получается? передвигаем первую фишку ко второй, и первый выигрывает, нет?
X...
.o..
....
...X
На любой ход первого второй сможет отделить фишки.
P.S. А как сделать с нормальным интервалом строки?
2 пробела + ентер?
Ух ты. 2 пробела это не очевидно, а без них склеивает в строку.
Я всегда [br] пишу(скобки на треугольные заменить)
Второй игрок может заклеить закрашенные клетки. (:
Почему тогда смайлики радостные? :)
Не совсем. (4,4) и (3,4) тоже проигранные разности. Только угадывать константу 3 случайно у меня бы получилось лучше чем думая.
И это всё решение?..
Хоть кто-то решал ее программно?.. Перебор какой-то и т.д.
А то разбор случаев на бумажке — это как-то неинтересно.
Ну на самом деле можно было делать так:
замечаем что при большой разнице каких-то координат выигрывает 2й
для маленьких разниц пишем дп по маскам
Я решал программно и меня взломали. Моя программа на тест где x2 — x1 = 4 y2 — y1 = 3 Говорит что выиграет First. Я на бумажке проверяю и не могу понять, почему First не может выиграть... Может кто-то объяснить?
Тут объяснено
Может быть, твоя программа считает, что нужно всегда лить клей рядом (по стороне) с фишкой противника? Тогда да, 3 x 4 выиграть не получается.
Да, именно такая ошибка :(
Да. Если быть честным, то на мой взгляд такая задача имеет право на существование, но в ACM-формате.
Мда... А ломали ее на чем?
Думаю, на неполном/неправильном наборе случаев
Меня три раза на числе 3. Оно сначала равнялось 4, потом 1, потом 2. 1 это было честно случайно, а вот 4 и 2 действительно баг в доказательстве.
Меня ломали на том, что 3 равнялось 4.
Да, типичная бага))
А вообще да, там ломали почти исключительно на неполном/кривом разборе случаев.
С решалась разбором случаев?
Как решалась B (div 1) ?
После того, как сдал С-шку, хотелось написать fhlasek: "Я хочу, чтобы ты ломал меня. Ты сможешь?".
Сдал
Does anybody thinks that solution for problem C is too nice? :)
P.S. (To not misunderstand) I don't find that solution with 2-3 if/else statements is a nice one
It's up to your own point. Personally, I found it interesting to simulate the game on Microsoft Excel ( sounds weird :) ). Some problems might cost you more time to work without computers, for instance, you can check problem D from last year Google Code Jam qualification round.
P/s: 1590260 is certainly not a solution with 2-3 if/else :)
At least it was solvable by few if/else statements and possibly without full understanding of its rightness.
Спасибо авторам за задачу А. Во время прочтения меня посетила приятная ностальгия по Космическим Рейнджерам.
Оффтопик: что обозначают синие баллы за задачу?
Судя по всему, что сдана не с +.
Значит, что ее взламывали.
Эх, люди добрые, перенесите дату финала :)
Эх, как бы я хотел поставить тебе +100 к комменту! Но только +1
Немного юмора =)
Извините, а не мог бы кто-нибудь выложить ссылку на форму, а то я случайно ее пролюбил?
Можно зайти в соревнование и снизу будут все глобальные оповещения.
спасибо)
В разделе вопросы смотри, там оповещение
интересно, на финал поедут только те, кому ехать на метро? =)
Нет. Мне еще на электричке)
И снова про рейтинг.
Прежде всего, спасибо авторам за проделанную работу =)
В прошлый раз я жаловался,что заняв на VK Cup 2012 Раунд 3 (неофициальная редакция для Div. 2) 4 место еле влез в Див1. Дискуссия закончилась тем, что такова особенность рейтинга, и что в Див 1 дела обстоят лучше.
Сегодня мое ожидаемое место (если сортануть по рейтингу всех бьло 400+). Я занял 214 и получил -8... Поясните, пожалуйста, мне непросвещенному, как так получается ?)
Участников всего 338. Какие 400+ ? У меня вон 242 место и -33 к рейтингу, так что тебе еще повезло фиолетовым остаться.
Участников 463. Или я совсем-совсем не просвещенный?
Считаются только те, кто сделал хоть 1 отправку. 463 — зарегистрировавшиеся.
Не все регистрировавшиеся принимали участие.
Значит совсем-совсем.
Уж не взыщите и простите=)
Обидно просто, результат свой улучшаю уже туров пять...
А в этот раз 4-ое место не влез в див.1 :)
А вообще с рейтингом и правда что-то не то. Мне интересно, как вообще из 2ого дивизиона теперь вылазить. Достаточно посмотреть на ТОП-20 сегодняшнего контеста и на плюсы к рейтингу, что они получили. Дивизион сменили человек 6-7, при чем в основном те, у кого рейтинг был в районе 1690+.
У меня на 35ом месте было 1671, стало +7. Я в целом доволен :)
Даже три первых места, которые решили все (!) задачи и до этого имели неплохой рейтинг, остались за чертой дивизионов. По-моему, это нельзя игнорировать.
Немного нытья: забыл взять ответ по модулю в B, до тестов было 51-ое место... ;_;
Весьма странно, потому что я брал ответ по неправильному модулю и свалился на претестах. По идее, если ты не брал ответ по модулю вообще нигде, ты должен был тоже упасть на претестах.
Вероятно, как всегда DP посчитал с модулем, а вывод — уже без.
Конечно нет, по закону Мерфи я в основном коде везде брал, а вот сам ответ, который я получаю, суммируя много чисел, забыл.
Еще немного нытья — забыл взять ответ по модулю в В, взломали, исправил, в результате вместо, как я подсчитал, 52-го места, — только 98-ое. И рейтинг в минус.
Я занял 60 место и, скорее всего, пройду, т.к. китайцы и другие участники из Азии вряд ли поедут.
Но что это за онсайт такой, куда надо ехать и жить за свои деньги
и куда я прошел? Это печально.А если учитывать, что там призы не самые хорошие, ехать туда — все равно что играть в казино в Лас-Вегасе.
Да, действительно, ужасные призы! 100 штук и маки буквально на каждом переезде раздают, заколебали уже!
100 штук получит 1 человек, мак получит 2 человека. Итого с учетом покупки билета какое матожидание что хотя бы в минус не уйдешь?
Жить там не надо:)
Что, утром приехал — вечером уехал? Но там же обещали еще какой-то игровой тур.
Как бы то ни было, об организации компании КРОК в следующий раз стоит подумать получше.
На Challenge24 надо ехать и жить за свои деньги, а до того еще визу получать, то еще развлечение. И ничего, отличный онсайт получается.
Тут просто не приятно, что даты накладываются на Чемпионат Урала. Я бы поехал бы с радостью за свой счет, но заранее. А не за неделю до онсайта, когда уже билеты на самолет идут по поднебесным ценам, когда Чемпионат Урала на следующий день и хотелось бы там быть, когда есть еще работа и у кого то учеба и вообще планы.
То есть пока ты точно не знаешь, что ты вышел, покупать билеты и писать "Онсайт КРОК" в ежедневник не правильно. Но за неделю, еще и за свой счет... Тут совсем грустно.. Если бы хоть пару недель дали, чтобы можно было подготовить поездку!
С этим согласна, я вообще не представляю, как можно за неделю куда-то сорваться и поехать — работа еще ладно, но домашки в ШАДе распланированы буквально по часам, и такого легкомыслия не прощают :-) Я только к тому, что "поездка за свой счет" != "плохой онсайт".
Ну в общем я буду надеяться, что финал перенесут и здравый смысл восторжествует! :)
Переносить финал сейчас будет максимально некрасиво, потому что
1) кто-то уже берет билеты,
2) кто-то не участвовал в отборе, потому что был уверен, что не сможет поехать.
Соглашусь с Вами, Наталья. Уже действительно не красиво. В принципе у меня лично нет никаких претензий и просьб к организаторам. Контест был объявлен как Чемпионат Москвы и Подмосковья, так что по сути для такой целевой аудитории проблем нет это сделать!
А я уверена, что есть люди, кто это представляет. Например, мне как-то позвонили и сказали: "сегодня идешь, берешь билет на самолет, завтра утром летишь в Москву к президенту". Я отказалась по принципиальным соображениям. Но ведь были люди, которые туда прилетели, в том числе был кто-то вместо меня (кого позвали уже вечером в тот день, когда я отказалась).
Честно, ради такого я бы тоже не поехал, однако, когда у меня стоял вопрос о визе на стажировку, я взял билет в посольство как только узнал, что свободна дата на следующий день, так как сроки поджимали! Так что все зависит от ситуации. Так что не стоит путать ситуации. Поучаствовать в соревновании, где только 3 получат призы, а остальные 47 отменят все свои дела в один час, на мой взгляд не та ситуация :)
Я как раз про то, что в любой ситуации желающие найдутся. У разных людей разные приоритеты. Вот увидишь, 50 человек наберется :)
50 человек-то наберётся, но нужна в кратчайшие сроки точная информация: будет ли онсайт ТОЧНО в запланированное время или есть возможность переноса. Я в онсайт прошёл но билеты на поезд брать не спешу именно по этой причине.
Ещё очень хочется знать расписание онсайта (длительность игрового раунда, например, продолжительность перерыва между игровым туром и финалом, время начала и конца основного тура финала и т.д.), или, хотя бы, время когда всё уже наверняка закончится, чтобы хотя бы примерно знать время на которое планировать пребывание в Москве и возвращение домой.
есть ли такая инфо на codeforces или на сайте КРОКа или ещё где-нибудь?
Интересно, какое место у человека, пройдущего поледним:)
Мы тут с yaro поговорили насчет ML в задаче 176D - Гипер Строка. Никак не можем разобраться, откуда он взялся в наших решениях 1590121 и 1590186.
Вроде бы 26·106 + 20002 + ε int'ов и 106 + ε char'ов не так много, это не больше 150МБ.
Есть у кого идеи, почему ML?
На каждый объект еще сколько-то байт.
Кроме того, на каждый массив(в т.ч на вложенные, т.е для массива a[n][k] — тут n+1 массив) — еще 4 байта на длину вроде бы. Вроде бы это немало увеличит оценку.
Там всего массивов + объектов порядка 10000
Может быть, это поможет? Хотя там, вроде как, какое-то кэпство
Вообще не очень понятно.
===== Использовано: 110 мс, 144076 КБ
===== Использовано: 160 мс, 172920 КБ
Я создал всего 26 массивов, а прирост 28МБ
Откуда берутся 44мб еще можно представить (хоть и непонятно, зачем они нужны), но вот этот прирост на запуске — чудеса какие-то. Any hints?
P. S. А авторы "Крок" второй раз кряду подготовили здоровские задачи, спасибо им!
И еще откуда-то какие-то 44МБ берутся в пустой программе.
Is there a way to check which test cases failed?
go to your submissions and click to submission id
Thank you.
Правда ли, что онсайт
?
Если так, то какой смысл ехать тем, у кого нет шансов в тройку попасть?
Кстати, этот пост забыли запилить на страничку Крока
А что нибудь известно по поводу футболок?
Призы Победители чемпионата получат ценные призы:
100000 рублей — за первое место Apple MacBook Pro 15 — за второе место Apple MacBook Pro 13 — за третье место Участник, занявший первое место в игровом раунде, получит Apple MacBook Air 13.
Я так понимаю никаких футболок не будет.
I seem to see that submissions by a few people are hacked. However they got accepted in the end because they passed system test?
For example: problem C by WJMZBMR, kuniavski and Dmitry_Egorov.
May I know why this is the case?
These solutions were resubmitted after being hacked and got OK
If you are hacked, you can (and should ;) ) resubmit the solution. It is then tested on the pretests and also on the hack case. However, if you had locked the problem and then got hacked, you can no longer resubmit. (But you can still hack others.)
Who can I ask for visa letter to go Russia?
I think u should write a letter to some officials (probably Mike Mirzayanov), but I suppose it's quite impossible to receive a visa in such a short time.
Please explain the logic for solving problem D(HYPER STRING).
Can somebody point to editorial for this round ?
Problem analysis usually appears in one-two days after the contest, don't be so impatient =)
Where can I find the analysis in English
http://mirror.codeforces.com/blog/entry/4372
In Problem C. Why does the second win when the input is “5 5 1 1 5 4”
That was the most important hack case, I think ;) The distance between the pawns is (abs(x1-x2),abs(y1-y2)) = (4,3). If the first player moves so that the distance between the two pawns becomes (4,2), then second wins quite easily. It seems better for the first player to reduce the distance to (3,3). So we have
and now Second moves. The trick is that he should glue this cell:
Then, if the first moves to
the Second should counter with
From here, he can block whatever first responds with. If instead First were to move to:
then Second blocks the upper pawn with
and when first moves to
then second "finishes" with
and the rest is easy.
Thank you very much!
Когда и где будет опубликован список финалистов?
+1. Сутки уже прошли, хотелось бы знать, приглашают меня на онсайт или нет (не то чтобы с моим 88-м местом я на это расчитывала, но хотелось бы определенности).
Апну тему... от отбора до финала и так неделя всего лишь, дак ещё и не больно спешат объявлять финалистов... :(
Разосланы приглашения.
А можно ли увидеть список финалистов?
Sorry for bringing this up again, but how to contact with the contest organizers? Only five days remaining and there's no information for non-Russian coders about how to travel to Russia.
Try contacting with MikeMirzayanov
I've sent email.
Михаил, а точно всё ок? Просто пришло письмо, но я ведь *132-ый.
А что удивительного?
Я насчитал примерно на 115 месте 50-й человек с российским флагом.
Очень немного людей приедут из других городов (и уж тем более других стран) (ибо не оплачивают и времени неделя)
Все нормально. Были выбраны топ-50 из тех, кто подтвердился.
А топ-50 содержал 50 человек, или меньше?
Хотелось бы узнать о конфигурации рабочих мест и о наборе компиляторов на онсайт =)
Да :) и формат было бы неплохо знать :) кф или нет.. и будет ли это на базе кф?