Доброго времени суток)
Совсем скоро стартует Раунд 1 Всероссийского Открытого Чемпионата по программированию "КРОК-2013". Из в Раунда 1 в следующий Раунд 2 проходят участники, набравшие не меньше баллов, чем участник на 400-ом месте (при условии положительного числа набранных баллов).
Раунд будет проходить по обычным правилам Codeforces (со взломами и падением стоимостей задач). Во время раунда задачи тестируются системой только на претестах, а системное тестирование состоится после окончания соревнования. Претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы.
До окончания раунда категорически запрещается публиковать где-либо условия задач/решения/какие-либо мысли и соображения о них. Запрещено общаться на тему задач, обсуждать условия, решения и прочее.
Задачи для вас подготовила команда авторов в составе: Павел Холкин (HolkinPV), Геральд Агапов (Gerald) и Михаил Мирзаянов (MikeMirzayanov). Отмечу, что команда в этом же составе провела для вас квалификационный раунд и отвечала на вопросы в течении всего соревнования. Традиционно благодарим Марию Белову (Delinur), которая перевела для вас условия задач.
UPD1: Задачи будут расположены в порядке возрастания предполагаемой сложности. Распределение баллов было решено сделать немного нестандартным: 1000, 1000, 1500, 2000, 2500.
UPD2: в связи с большим количеством участников было решено, что в соревновании нельзя будет участвовать вне конкурса. Для официальных участников соревнование будет рейтинговым.
Всем участникам желаем удачи и успешного прохождения в следующий раунд соревнования.
Уважаемые организаторы чемпионатов. Думаю с данным вопросом к Вам обращались неоднократно. В нашей стране 10 часовых поясов, и логично что не всем удобно московское время. У меня к примеру, во Владивостоке, все турниры начинаются в 2-30. На начало можно попасть, а дальше даже 2-ух часовой контест очень сложно выдержать. Возможно ли как нибудь перенести начало соревнований на более удобное для всех время?
Вы назовите удобно для всех время. Его вроде бы просто не существует.
Вообще на мой взгляд выбрать понедельник под контест не очень удачно для студенческого(в основном) чемпионата.
Будет ли раунд рейтинговым?
Poideie ne dolzhno. Mnogie is div2 porvutsa div1.
А что с внеконкурсным участием? Будет раунд рейтинговым див1/див2/просто возможность принять участие?
Seems like really tough competition.. Did you mean under 400 amongst all Red,orange and purple coders ?
Will the round be rated?
"UPD2: due to the large number of participants, it is decided that it will not be able to participate out the competition. For official contest participants the round will be rated."
So what does a official contest participant mean?
it's rated for both Divisions.
I guess it means all eligible registered participants.
When a Div2 contestant participates in a Div1 contest, he is considered unofficial, because although he registered for the contest, he is non-eligible to participate in a Div1 contest, and vice versa.
In my view, all the participant who read the problem will be rated, as normal CF contests.
You need to submit something to be rated, be it normal CF round or competition one
How would the rating be calculated for both division 1 & division 2 participants ?
how many rounds will this series of contests have，is there any T-shirts to give the winners ?
It seem that there's only one round.
The problems will be more suited for div1, div2 or half way? :)
How to register when registration is private? It seems too private for somebody to enter :)
I have the same problem. I have to register now because I will not have internet acces until the start of the competition
DELETED
I receive an Email tell me that I need to register on Codeforces for Round 1, but it seems that I cannot register because the registration is private. Did I really need to register or it will be done automatically?
"Registration is private", does it mean that all participants who passed qualification round will get registered automatically?
Well, when I click "register now", a message box "The contest does not allow self registration" pops up. So I suppose that the registration will be automatically done.
I hope
I hope so because our dorm cut the wired internet access at 23:00(UTC+8), 30min before the round start, every workdays and it will be very crowded at the public WIFI, which cause it crash frequently.
How am i supposed to register for the contest???
"For official contest participants the round will be rated" ... for only the contestants the round is rated ??? am I misunderstanding ???
it is decided that it will not be able to participate out the competition.if there is no participant out of the competition then all the participants are official so now whats the need of the "For official contest participants the round will be rated" statement ? they can simply say "this round is rated"
haha you quoted that sentence as if it were in correct English :D
If there is problems with the registration I suggest to open the registration durig the contest. Because not all of us can register. I am going to miss school for the competition. I will be home at the 4-5 min from the start. I will mis the competition if i don't register now.
Try to use mobliephone:(
Registration is fixed now.
Сколько будет задач с тегами "кот тапок количество"?
Edit
Why some of you cares so much about the ratings calculations and the score distribution? Every round about ten such messages appear.
What will change if your rating changes will depend on only Div-2 or both Div-1 and Div-2 coders? Won't you participate in one of these cases?
Ну сделайте внеконкурсное участие.
Лень было А на квале написать? :)
Типо 18 нет. Думал будет хоть нерейтинговое внеконкурсное участие.
Ты имеешь ввиду В не более, чем с одним багом?
А где вообще можно было набажить там?
Использовать gets() и не учитывать символ 13 в конце в конце строки, который появляется из-за виндового перевода строки, что я и сделал >:[
Напишите где-нибудь на видном месте, что нужна регистрация на раунд. А лучше автоматически зарегистрируйте всех, кто прошел квалификацию. А то будет куча гневных комментариев в начале раунда как обычно.
Это было в письме и это согласуется с опытом предыдущих соревнований. Просто есть опасение, что многие некоторые не придут — двойные аккаунты, забили и проч. И в результате будет больше неполных комнат.
Сделайте пожалуйста Уайлд-кард раунд в выходные для тех, кто не смог по участвовать.
"Всем участникам желаем удачи и успешного прохождения в следующий раунд соревнования" Жаль, что все не пройдут :( Все равно Всем УДАЧИ!!!
А почему перенесли начало? заранее спасибо!
Единственная причина — чтобы все зарегаться точно успели.
Серьезно или шутка? А то так можно бесконечно переносить, пока все не зарегаются :)
Тем не менее не все успели. Я пытался зарегистрироваться в дополнительные пять минут, но регистрация была уже закрыта. Если внеконкурсное участие запрещено, почему бы просто автоматически не зарегистрировать всех прошедших квалификацию?
я регалась за 5 минут до конца регистрации, мне было сказано, что зарегана, но задачи сейчас сдавать не могу.
Я поискал все HTTP-запросы с вашего хэндла и не нашел запрос от браузера на регистрацию.
Спасибо, значит мне просто не везет. Надеюсь в следующий раз будет не так.
put off 5 minutes?
Lots of hacks specially Problem 4.
Контест окончен... И главная интрига — должен ли проходить квадрат в D?)
Если да — на чем ломают? Если нет — что там можно написать быстро и правильно?
На джаве нет. На плюсах через раз.
Сломали квадратный DSU
Что значит квадратный dsu? Расскажите подробнее, пожалуйста. Может и у меня упадет
Ну каждый запрос отдельно, добавляем в dsu нужные ребра
Вот вам квадратный dsu который прошел.
Нужно оставить 2н ребер.
ИМХО, конечно, но авторы очень неправы — ставить такие ограничения. Вместо нормальной задачи получилось непонятно что, которое вместо +100 даёт -50 нормальным участникам, челенджащим людей с лажей на С++.
Если в итоге эта лажа не пройдет систесты — значит, надо было старательнее челленджить.
Если пройдет — тогда мой вопрос адресован так же и авторам задач. Как было задумано? Это должно было проходить?
Неаккуратные реализации на плюсах все таки падали. Что создает еще больший рандом. На систесте то думаю все попадает, но для челенджей это бред какой-то.
Я писал корневую эвристику для запросов, но думаю на плюсах квадрат зайдёт, если без всяких логарифмов — видел у себя в комнате такое, но оставалось секунд 30.
Я подумал-подумал, решил, что не должен, и все же написал
. Был потом очень разочарован, увидев, что все квадраты посылали.
Квадарты упадут скорее всего. Ну или рандомная половина квадратов упадет. Там есть нормальное за nk.
Да что ж такое. Придумал и написал клевую корневую. И только что понял, что из-за некоторого бага в посланном решении на самом деле тот же самый почти квадрат.
Смотри, давай посмотрим, что мы будем делать, когда будем проходить [0,l): мы какие-то рёбра будем добавлять в дсу, а какие-то ничего делать не будут. Давай такие рёбра сразу выкинем: пройдем от 0 до m-1, если рёбро объединило две компоненты -- хорошее, оставляем, иначе выкидываем. Аналогично от m-1 до 0. При запросе будем итерироваться только по хорошим рёбрам, их максимум 2*N.
Итого O(n+m+k*n), исходник: http://mirror.codeforces.com/contest/292/submission/3544049
Обидно, что заходила всякая фигня, потому что очень клёвая задача же :)
По идее, тут можно разбить список ребер на k кусочков и для каждого a и b предпросчитать dsu, в котором уже есть первые ak ребер и последние bk ребер. И потом на каждом запросе выбирать нужный dsu, копировать и за O(n/k) достраивать до нужного состояния.
Немного похимичить с выбором k и должно пройти (идеально k =
, но боюсь памяти не хватит).
Это я придумал за 10 минут до конца после того, как у меня взломали квадрат. Написать не успел.
А если сначала посчитать дсу на префиксе и на суффиксе. Для каждого запроса нужно слить только два дсу и дать ответ. Похоже на правду?
Да, похоже.
Но я догадался как это быстро делать только сейчас... =_=
У меня в запуске работает 1375 мс. Должно зайти. Тоже не понимаю, зачем такие ограничения поставили.
Сходил за попкорном в ожидании системных тестов...
Попкорн кончился(
Ну все, наверное, расходимся, Burunduk1 получил TLE.
На дорешивании вгоню) У меня в D совсем не оптимально написано. Просто во время контеста была мысль "2*10^8, 2 секунды, все кэшируется... да конечно зайдет!". Забавно, я даже не сомневался в этом.
UPD: O(km) зашло за 1734 мс.
А как же мысль "это же D, авторы должны были позаботиться о том, чтобы тупняк не заходил"? :)
Е должна отметать такое предположение)
Ну так в E ведь O(nm) не заходит, надеюсь? Или я что-то пропустил? :)
Ну, я тоже надеюсь. Просто если Е простая, то почему бы D должна быть сложнее
Ну в E надо было сделать по крайней мере одно логическое умозаключение, чтобы её решить; и оно могло быть сложным по мнению авторов, всякое бывает. Это не повышает вероятности того, что D — "переведите что написано с английского на C++".
Я попросил Gerald-а ответить, но как я понимаю не предполагалось, что решения за такую асимптотику могут проходить. Это авторский фейл, но в самом деле — почти все не проходят. Т.е. в этой задаче предполагалось решение поумнее и проблема не в неправильной оценки, а в неудачных ограничениях.
:) мысль "да конечно зайдет!" была последней. После этого мозг отключился, а руки кодили.
А у меня в комнате нашёлся добрый человек, который захачил моё квадратичное решение. Пришлось писать что-то разумное. Спасибо тебе, KADR =)
Ого, а у меня внезапно зашло O(m ^ 2 + k * n) за 1 секунду на Java.
Инлайн в ДСУ творит чудеса, не верьте e-maxx, разница очень даже заметная: рекурсивный дсу: 3548782, тоже самое с волшебным словом inline 3549312 и нерекурсивный 3548909
Кстати, по поводу DSU. Полезно помнить, что есть 2 разных решения. Первое -- стандартное, а второе -- со списками. Работает решение со списками за O(m + nlogn), где m -- число запросов, n -- число вершин. В нашем случае это 104 + 500*10 с маленькой константой, что должно быть быстрее. Решение со списками: храним color[v] и list[color], когда нужно сделать join, перекрашиваем меньший список и добавляем его к бОльшему.
P.S. Я немного упростил твою реализацию: 3551436.
UPD: Решение со списками работает 0.265 3551644
265 это, конечно, круто. Учитывая, что находим ответы для всех подотрезков.
Could anyone tell me what's wrong with this generating code for problem E? I kept hacking and got "invalid input". Making the right input specification is so tough :(
what is error message?
Looks like you forgot to output request's type in the last
forDid you mean
printf("1 %d %d %d\n", 1, 1, n);in the last line?Oops, I forgot that the 1-typed query needs three parameters. Thanks everyone :). (I need to practice generating input more regularly).
Слишком поздно обратил внимание на задачу C, посмотрел что больше сдают D и думал над ней. Вопрос по задаче C. Зайдёт ли такое решение: обозначим числа в адресе следующим образом: a.b.c.d Переберём всевозможные варианты a и b, следя за тем чтобы не было ведущих нулей, потом аккуратно отразим => получим c и d. Запомним ответ куда-нибудь, например в set, затем возьмём каждый ip из предварительного ответа и первернём его так, чтобы получился валидный ip и положим в тот же set.
Допустим n=3, числа 0,1,2:
0.1.21.0 получится таким образом?
0.1.222.210 такое, как я понимаю, не сгенрится.
Но можно перебрать a,b,c
Не должно — как ваше решение будет обрабатывать варианты типа "1.2.233.221", например?
Правильнее честно перебирать первую половину цифр (длина до 6), затем отражать (2 варианта — одиночная цифра в центре и парная), и потом отдельным перебором пробовать бить это на 4 числа.
делал так, ТЛ на 8, проверка на то, что все цифры использованы и магия с ведущими нулями возможно виноваты, а мб и алгоритм не тот нужен был.
У меня все претесты прошли за 15 мс, так что, видимо, реализация подвела. P.S. Возможно, забыли про хак "если n > 6, то ответ — 0".
UPD: Все тесты тоже прошли за 15 мс
Нет. Зная только a и b нельзя «аккуратно отразив, получить c и d». Например, в адресе: 8.9.121.98
Не совсем так. c и d могут содержать много цифр, a и b — мало, тогда нам не хватит перебора a и b. Например 1.3.2.231.
Авторам большое Φ за ограничения в задаче D. Либо уж ставьте так чтобы квадрат явно не заходил, либо чтобы явно заходил. А то куча челенджей работающих за 1.9+ это какой-то бред.
P.S. спасибо мише.
Большое φ — это вот так: Φ. =)
Just one second to click submit button for problem E. :|
And one second for my C, please :(
Thanks God! Mine was wrong :)
Just one second to click submit button for my 100% corect sources for A, B,C,D,E :/
Ну D, это вообще подстава. Зачем так дразнить ограничениями, на которых обычно заходит квадрат?
Каким образом квадрат все-таки не заходит? Вроде как 2 * 108 легко должно заходить, тем более массив размера 500 помещается в кэш, а по массиву ребер бегаем последовательно.
Может объяснить какой-нибудь мастер оптимизаций, в чем тут дело?
Может дело в том, что каждая операция с дсу — вызов функции?
What is the solution for D? Or is it just a DFS per query?
I use disjoint set, with total complexity O(K * (N + UnionSet cost)).
How do you achieve that complexity? Don't you need to traverse the edges that are not taken? I mean, isn't it O(K * (N + M))?
oh yes, sorry I miss calculation :). N that I wrote first, I mean is M, total edge not total vertex.
Given M = 10000, K = 20000, will 2*10^8 survive?
You can make it faster by pre-computing spanning forests for all edge prefixes [0..i] and all edge suffixes [i..N]. Then you only need to merge two disjoint-set forests for each query.
That brings the total cost down to roughly O(N * (M + K)).
How could one merge 2 DSUs ?
I iterated through every (vertex: root) pair in one forest and merged them in the other forest. It seemed logical, but I have no idea if it's actually correct or not...
OK, it seems to be correct.
It can be done in O(N) by DFS using only edges v — parent[v].
each DSU has O(n) edges, just use them.
DFS per query:
It fails on half of hacks. Probably systest will fail most of them.
I solved in such way. Let's have to sets of edges. First is edges, which connect vertexes, which is not connected by edges with less numbers. Second is edges, which connect vertexes, which is not connected by edges with greater numbers. There sizes is O(n) and other edges is not need. So we can answer query in O(n) time.
It's easy to implement this solution with dsu.
thanks for your response,I am interested why this solution get TLE,I only changed positions and get ac:
TLE41:
ACCEPTED:
why system test is so strictly what is difference ? :(
Consider "if ( A && B ) {}" code. If A is false, then B isn't checked. B is checked only when A is true. So if we know that A is false more often than B is false, it's better to write "if ( A && B) {}", otherwise "if ( B && A ). In our case (g[v][j].ind<l || g[v][j].ind>r) statement is false more often than !used[g[v][j].v] is. Therefore, if ((g[v][j].ind<l || g[v][j].ind>r) && !used[g[v][j].v]) is the best way.
It will be a good lesson for me,thanks
CROC's English is very very difficult and long... I took hard to read even using translation machine.
Very nice problem D. I knew my solution in wrong, but I've locked my code and hacked 7 people!!
Lucky you, I wanted to do the same but tourist hacked me first :(
It can be considered a privilege being hacked by him. :)
Could you tell me what's the tricky case for problem D ?
Just a random test with 500 vertexes and 10000 edges and 20000 queries that all of them are : 1, 10000
if N = 2, M = 2, edge are = {1, 2} {1, 2} and the query is {1, 1} The answer is 1 or 2 ?
I think there could not be any multiple edges.
There could be multiply edges.
"Note that a pair of computers can be connected by multiple cables." But the problem say so. .
Very good! now I think my solution besides time limit, will get wrong answer!! :D
Cool strategy..!
В E вместо легкой и быстрой корнячки жуткое решение с сетом, которое дебагать полчаса. В D вместо честного решения (или даже не совсем честного квадрата) какая-то хрень с DSU, которая почти наверняка не зайдет по времени. В C вместо трех циклов и одной проверки — перебор с отсечениями (тоже повезет, если зайдет).
День офигительных решений просто.
В E ж дерево отрезков с покраской на отрезке просто, зачем там корневая?
А в С перебор должен заходить. С моими отсечениями на тесте 1 2 3 4 5 6 работает 0.2. Казалось бы, это самый сложный тест.
А как же 0 1 2 3 4 5?
Дерево отрезков — тоже вариант, не требующий применения мозга для написания.
Ну, хорошо, если зайдет. Но почему бы не подумать, перед тем, как начать писать. >_<
Вот и я судорожно перечитывал задачу E, но так и не смог понять, почему же она E! Зато задачу C сделали всего-то на 500 баллов дороже, чем дебильную задачу B, которая вообще больше тянет на задачу A второго дивизиона.
Вообще меня поражает то, как представители саратовской школы программирования распределяют задачи по сложности. Каждый гребанный контест они умудряются настолько странно расставить баллы за задачи, что после контеста хочется плеваться желчью. До сих пор помню, как в одном из саратовских раундов задача D была "отсортируйте массив из 20 элементов и пройдитесь по нему за линию с жадником", которую даже серые и зеленые сдавали с плюса в первые двадцать минут.
Ну а особенно порадовали слабые претесты в задаче E. Получилась такая забавная игра — "у кого больше дебилов в комнате, тот и победил". У меня вот в комнате зеленые не стали дерзить и посылать ТЛьное решение. Зато многие мои друзья поналомали туеву хучу таких ТЛьных решений.
Может не стоит называть участников, которые посылали квадрат "дебилами"? Это не очень корректно и не к лицу участнику считающему себя не "дебилом". Если себя так вести, то после каждого раунда Petr должен всех называть дебилами (в том числе и тебя).
Вы наверное квадрат послали? :)
P.S. Я квадрат послал :(
Немного не в тему — но выше речь идет о задаче Е. В которой претесты, как я понял, можно было спокойно пройти с решением за О(N*M).
Упс, я думал D...
Если верить yeputons то иногда еще и вломы макстестом тоже. Если делать memcpy(). Правда у меня взлом на этом успешный.
По поводу сложностей задач — а в чем проблема-то, религия не позволяет решать задачи в порядке, отличном от А-В-С-D-Е?
Если серо-зеленые сдают с плюса за 20 минут, то и желтым, вероятно, это под силу.
Впилюсь-ка я в ветку первого дива.
Объясните, пожалуйста, как это туда лепится =_=
Для каждого запроса i, красим отрезок l[i], r[i], В цвет i, а потом при запросе значения элемента мы сможем за O (logN) найти последний запрос, на котором этот элемент копировали из А, и за O (1) просто вывести.
Для кадог запроса вида "копировать" покрасим в ДО отрезок, [y, y+k) в цвет — номер запроса, и щапомни delta = y -x;
На запрос отвечать так: Смотрим последнее перекрашивание. сдвигаемся на delta Если не было перекрасок — понятно
Заметим, что числа меняются только в массиве B. Каждое число в массиве B на момент запроса второго типа может быть либо исходным, либо "покрашенным" каким-то запросом. Нас интересует последний такой запрос.
Используя основную идею дерева отрезков о том, что любой отрезок можно разбить на логарифм отрезков длины степени двойки, мы красим все такие отрезки в нужный нам цвет (а именно, цвет — это номер запроса), а при запросе второго типа спускаемся по дереву и берем максимум из всех чисел, которые нам встретились (это будет последний запрос, который покрасил данную позицию). Изначальный массив можно считать покрашенным цветом -1.
Я для каждого отрезка в дереве отрезков запоминал левую и правую границы в подмассиве a, который скопипастили в этот отрезок. Ну хотя это то же самое, что и два коммента выше.
Приношу извинения, если вопрос уже неактуален (давно не участвовал) — а системное тестирование скоро будет? Ждать или с работы домой ехать уже? :)
Хорошая работа — решать Codeforces :-)
Системного тестирования долго нет. Скорее всего администрация судорожно добавляет новые тесты и взламывает квадратичные решения по D.
А как их ломать-то? Чем отличается случайный тест, в котором на каждом запросе удаляется 1 ребро от любого другого теста?
Начнем с базового вопроса — что будет работать дольше:
дфс с одной вершины, который веером обходит весь граф
дфс с одной вершины, который цепочкой обходит весь граф
серия дфс, каждый из которых обходит только 1 вершину
Например, какой-нибудь тест против СНМ с только одной из двух эвристик.
Мы тут на досуге с ifsmirnov пытались делать тесты, на которых СНМ с одной эвристикой работает дольше, чем СНМ с двумя. Получалось плохо. Есть какие-нибудь известные способы?
Получалось плохо, потому что ничего принципиально лучше рандома мы в итоге так и не сделали, разве нет? ;)
Ну, там был рандом с претензией на интеллект вроде бы. =)
Ну и вообще, интересно, что люди посоветуют.
Вот тут Burunduk1 утверждает, что на его тесте есть аимптотическая разница
Извините за оффтоп, но Ваша превьюшка напоминает фото Гены Букина :) Или это мне одному так кажется?)
Я помню была какая-то конструкция от Burunduk1 против только сжатия путей. В два-три раза дольше видимо будет на ней.
Собственно вот. Только я не помню что тут происходит. http://pastebin.com/hzeSxBXt
Выложил задачку об этом. Там есть условие, решение, чекер. Решение генерит тест, на котором "СНМ только со сжатием путей" делаем
операций на m запросах.
А кстати, добавляются ли тесты от участников со взломов? Если да, в этом нет необходимости вроде, и так на'challeng'или...
Добавляются, но не все, а вручную по выбору.
What's the solution to C and E? Thanks.
for C the most important thing you should consider is that you can obtain the hole string by determining the length of each of 4 number O(3^4) and the material of the first half of the string O(n^(half of the length <=6)) and then you should check whether it is legal or no for more info see my C++ code : 355108 for E you should use segment tree data structure (read about it here )segmnet tree and keep for each node of the tree that what is the last copy that contains this node and then easily find the answer for each query if you need more info see my C++ code : 3550844 I hope it will be useful for you.
Too strange, why I can't see the system testing? Are they really testing now?
you sure you know what "pending" means? xD
You mean there are some delays and they are just waiting?
Yes and no. the aren't waiting (its pointless isn't it?), they most likely are master basing
посоны, расходимся, систестов сегодня не будет
Ладно, черт с ним, пусть оставляют как есть...
:D
I think systest will run for last 6 hour like on qualification round :D
I think the judge should tells when will the ST begin , if it's too late , I will go to bed now
one does not simply, you mean ?
double translation is evil:)
Actually, you should better hack O(MK)
Oops. I hope everyone understood me :)
Why testing won't start?
please tell me when i can submit my solution for problem 5??? and where i can do that???
my brain is exploding, because i submitted my code 5 seconds before the end, and because of the stress i had, i made a little mistake and 10 seconds after i noticed that!! if i submitted that my score was about 1400 and i would advance to the Round 2.
my brain is exploding now! help please :(
well my story is more tragic. Cause of Iran’s f*** network I wasn’t able to submit my E code in 1:10 when I have already submitted A,B,D. My network re-concocted after the contest. what should I have to do ???
excuse me! i mean 4500(not 1400)! it's because of my brain!
Hey guys, Is there any one to start system test? Mike? Gerald? Pavel?
it seems there is no one to start system test
It will be started soon. Please, a little patience.
Is there any technical problem? I Can't understand this to much delay.
самое интересное, что администрация даже не пытается как-то прокомментировать ситуацию: скоро ли будут систесты, ожидать ли их вообще сегодня, почему происходит такая задержка
Скоро все будет, чуток терпения!
спасибо
Спасибо за информацию! А можно поинтересоваться, почему не используется системное тестирование во время контеста? Есть ли какие-то ограничения, не позволяющие это делать, чтобы после соревнования за минут 5 дотестировать остаток, и просто сделать доступными имеющиеся у администрации результаты?
Я думаю, может получится не очень, если добавится новый тест со взломов, и тогда все протестированные решения нужно на нём ещё потестить.
Казалось бы протестировать на x последних тестах не хуже, чем протестировать на всех. Да и добавлять удачные взломы можно автоматически.
Функциональности тестирования на суффиксе тестов нет. В этом и проблема. Upd: конечно на старых тестах решение не запускается заново, а берется тот вердикт который был раньше.
А почему не очень? Это же не перекрывающиеся задачи.
Вот кстати когда я был одним из авторов раунда, примерно год назад, систесты проходили прямо во время контеста, а после контеста решения прогонялись только на взломах. Разве сейчас не так сделано?
Ну да, в принципе, тоже не вижу особых причин.
Ну, всё равно, это гораздо меньше работы после контеста. Большой вопрос в том, достаточно ли ресурсов, чтобы о чём-то подобном даже начинать думать.
Не хотелось бы видеть длинную очередь решений на претесты, только потому, что система подвешивается полным тестированием предыдущих сабмитов.
Фоновое тестирование на не-претестах может иметь меньший приоритет и не забивать 100% мощностей, чтобы реакция на новые посылки была моментальной. Даже если внезапно нахлынет целая куча посылок, для остановки фонового тестирования нужно всего несколько секунд (время выполнения на одном тесте).
Конечно, это всё работает только тогда, когда детализация заданий на тестирование больше, чем просто «протестируй посылку №1234».
One hour of pending system test should be something unusual. In that case, we contestants all expect some announcements/explanations from admins :(
Edit: ok, just saw Mike's comment :)
Meanwhile in CodeForces HQ:
This one!
Plus this comment to see how many people are waiting for the system test. :D
Okay, keep downrating it :D. I'll take the abs :D
We can minus your comment to see how many people are waiting for the system test. Same result :D
you wanted to say "minus this post to see how many people are waiting for system test"
Ого, системное началось!
Спасибо за оперативность!
Вот теперь пора доставать попкорн))
I'm staying up for the system test! Please get this done ASAP, I want to sleep!!
Чуваки, отбой тривоги, в D тупизна заходит!
а у меня O(m2) не зашло :(
Ну, тут ожидается лотерея, по-моему. Кому-то повезёт, кому-то нет. Ограничения надо было другие, чтобы O(K*N) качественно отличать от O(K*M).
А ведь казалось бы, нужно всего лишь поднять ограничения на m до 105, и все было бы нормально...
Ждём ответа от авторов, их уже в комментах раз 5 спросили. Есть гипотеза, что это была такая разновидность троллинга :)
Что тут сказать?
Мы тщательно старались подгонять ограничения под асимптотику. У нас были наивные решения, которые давали TL на наших тестах. Все (кроме одного, совсем не оптимально написанного) правильные решения проходили с 3х кратным запасом. Отсюда мы сделали вывод, что ограничения отличные.
Здесь надо сказать, что вообще polygon показывает warning, что TL решение укладывается в 2х TL. Я не заметил, что это происходит на всех TL-тестах. В этом моя большая ошибка.
Я искренне прошу прощения за эту недоработку, будем стараться не попадать в такие ситуации впредь.
А, ну тогда ОК, я уж боялся, что оно было осознанно.
Вообще, обычно стоит так подбирать ограничения, чтобы при подстановке их в асимптотику неправильных решений получалось хотя бы 1010 (хотя опыт показывает, что и такое упихивают). Но уж 200 миллионов — это как-то совсем впритык.
Какова сложность авторского решения? Я решал за (N + M) * sqrt(M). Несмотря на то что так и напрашивался бфс, я предпочел написать нормальное решение.
Хм, у меня O(m + k + n^2)
Присоединяюсь к словам, ограничения оказались неудачными, одно из наших решений сбило нас столку, будем внимательнее.
В любом случае, надеемся, придуманные нами задачи вам понравились
В авторском решении из разбора, которое они хотели, чтобы проходило — O(nm) памяти. Видимо, поэтому.
Есть ещё решение за O(N*M+N*K).
Тупизна тупизне рознь)
Заходит)
Да, у тебя читерская функция
залазит на одну глубину меньше, чем копипаста с емакса. Вот в чем фишка!
И это еще не все, такой код получает TL 58, решающая оптимизация — в порядке ветвей if-a:
Будете ржать, но вот мое совсем "тупое" решение, которое получает ОК даже с использованием rand() =)
http://mirror.codeforces.com/contest/292/submission/3547573
Поэтому не думаю, что порядок операций в if() играет какую-то роль
А у меня в комнате посыпались все M*K, в том числе у двух красных. Так что действительно рознь.
Вот, O(m*k) зашло. Куда уж тупее..
Аналогичное решение валится на 93 тесте
Well,I have to thanks all Codeforces team. They taught me what does error 502,504 and server busy means :D . I was kidding but I really expect codeforces to be more faster in this contest :D.
no wonder tourist completed the contest in just 35 minutes.
3000+ on the cards.
haha, in my B i had "unknown toplogy" instead of "unknown topology" in one minor case, WA on 38 :-))
А заблокированная и взломанная задача будет проходить полное тестирование ?
Нет, она же взломана, значит решение неправильное.
in problem D: Why was K limit so low?? some people got AC with O(mk), but some people didn't.
the problems were are implementation and coding and non-algorithmic. and very slow system testing I did not like this contest
More than 1200 contestants, it isn't slow system testing!
it is really slow. just remember last 3 contests, this contest had less contestants than them.
yes it is! most div 2 contests more than 2000 people participate and it takes less than 30 min and i'm not just talking about system testing, it took about an hour for the system testing to start
i think this round should be unrated for these reasons:
the contest was uneven : i see a lot of RED contestants which their ranks is more than 300.
the problem difficulty's were close to a div-2 contest
Problem D is very unfair and they could have set limit of k to 10^5 so people know that the MK soloution would not get AC
I don't see how it's unfair. All had same chances
Because there are participants who got Ac on O(mk) soloution And if the k limit was higher, people would think on another soloution
If the k limit was higher, then many coders would have discarded the O(mk) solution.
But it isn't. The problem statement clearly said k <= 10^4, so, if a coder doesn't realize that the O(mk) solution will work, it's his fault. I don't see how it can be unfair. The constraints were very clear.
agree with your reasons, specially with third one.
Anyway it's too late! The ratings have been updated
I have the same problem, One of my friend's code got acc although his code had to be very slower than mine.
I got back to division 2 and didn't make to the next round because of this So I am completely in agreement with you.
Что значит вердикт "ошибка тестирования" в задаче B? 3542656
А можно будет после тестирования посмотреть решения участников?
да, конечно
ikar выбрал правильный ник)
Эх, буду надеяться, что среди первых 485 участников случайно окажутся 86 читеров.
Ну что, где мои шикарные женщины?
Если вдруг кто забыл...
Блииин... Напомнил бы мне кто-то об этом перед началом контеста — и я бы точно решил Е без багов.
А вот и шикарные женщины подъехали ✔✔✔
This is translation of my russian answer.
We carefully try to make constraints more fair. Our naive solution get TL on our tests. All (except one, that isn't written optimally) our correct solutions passed with 3times reserve. So we decide that our constraints is very good.
Here I should say that polygon shows that all TL solutions fits into 2TL. Buy I didn't notice that thing. That's my great fault.
I truly apologize for this fault. We will try not to make such faults.
Would it be possible to hold the CROC rounds on Sunday instead of Monday? For US competitors who work or are students it's difficult to compete in a round that takes place at 11:30 AM EST on a weekday. I was able to participate in round 1 (and qualify for the next round), but I don't think I will be able to participate in the 2nd round.
I don't think this will conflict with the TopCoder Open, or make competing more difficult for participants in Asia or Europe, so maybe it's possible?
People may already have plans based on published schedule. Also Codechef Cookoff is scheduled for Sunday
My solution to problem D was bfs for each query having a total time complexity of O(Q * (E + N)), why didn't it pass the time limit? M = 10000 N = 500 Q = 20000 Total number of calculations would be around 2*10^8, I have accepted many problems here in codeforces with the same number of calculations? I had the idea of using DSU but it was a little bit harder to implement and to prove, For further contests how can I be sure if the solution will pass or not whit this number of calculations?
I do the same too :(
When you're that near the limit, there's no guarantee it will work in time. It's just your decision if you want to take the risk and go the easy way, or spend some time thinking a faster solution.
You can always use "Custom test" to approximate the running time in worst case. I first submitted a naive solution. Then I used this and figured out it was too slow and resubmitted it later. (Tips: there's a limit for input size in "Custom test", however we only need to measure the running time, so simply assign some random numbers directly in the code itself)
good idea, tnx :-)
Прошли квалификацию — 2018 человек. Зарегистрировались на Раунд 1 — 1558. Сделали хотя бы один сабмит — 1376. Т.е. реальных участников 68% от прошедших. Рассматриваете ли вы уменьшение проходного бала в Раунд 2, к примеру, до 500 человек? :)
Было бы очень круто!
In question D: Can somebody tell me why this submission using dfs worked. 3545286 and mine using bfs is giving TLE. 3551854 Thanks in advance..:) KrK
R_R_ You hacked in during contest. Comments please.
The constant factor in your solution seems to be a little higher. You're using two arrays (color and marks), when you only need one (one that states whether the node has been assigned a component). Try using only the color array and see if you get it AC.
3552076
Still not..I think it doesn't work in time because you are using stl queue, which might allocate memory somehow slower when compared to static array used as queue (see 3552315)
Haha.. That was really awesome..!! Never thought using STL queue will make it this much slower..:P
Thanks a lot. ondrah..:)
ondrah Hey, the one you used in your submission is not BFS. It's is still dfs because you actually implemented a stack using array.:)
Even queue implemented through array is not working. See 3553686
задача D 292D - Компоненты связности
TLE #41 3551866
ACCEPTED 3551867
я всего лишь написал это :
if ((c[now][o]>r || c[now][o]<l) && !fix[g[now][o]])вместо этого :
if (!fix[g[now][o]] && (c[now][o]>r || c[now][o]<l))и решение прошло :(
из за этого , во время контеста мне взломали это решение :( .
Вот уж какая разница? Ну неверный это способ. Согласен, некоторым повезло. Но если в следующий раз ограничения будут подобраны удачнее, то все подобные решения не зайдут. Чего плакаться теперь? Прочитайте лучше разбор и научитесь делать эту задачу правильно. Это «идея». Чем больше вы будете знать «идей», тем лучше будете писать контесты. А причитания, подобные вашим, результата не принесут никакого.
Если решение задачи проходит за 1.3 секунды из отведенных двух — здесь и не пахнет везением... Да, тем, у кого 1.984 или 2.000 — немного "повезло". А тем, у кого на 1-2 тика времени больше — немного "не повезло". Но они знали, на что идут. И то, что они не написали тот же квадрат более оптимально — их проблема, при желании он пишется так, чтоб заходить без проблем. А я считаю, что все, что заходит с вероятностью 1-eps — в случае АСМ является "правильным". Будь то хэш, рэндомизация, или же вот такие "неверные способы".
Более того, если на любом будущем соревновании у меня будет выбор между сдачей "неверного способа" и обдумыванием "правильного" решения, то я выберу первое и абсолютно не буду напрягать себя обдумыванием того, хорошо я поступаю или нет.
Например, если у меня есть граф на 1000 вершин, и надо найти кратчайшие пути от одной из вершин до всех остальных, то я буду писать Флойда. И мне абсолютно плевать, что у него куб, мне плевать, что правильные парни пишут Дейкстру или еще что-то в этом роде. Я пишу решение, которое проходит в пределах ТЛ/МЛ, и при этом требует минимума усилий на написание и содержит минимум мест, опасных в плане возможных багов.
Я согласен, что я неверно расставил акценты в своем сообщении и плохо выразил свою мысль. Что я подразумевал, так это не то, что не надо пытаться сдавать задачу «не лучшим способом», а то, что не надо ныть после того, как это задача не сдалась
Да, если уж ломать то все квадраты. Мне вдвойне обидно, 429 место — если бы все квадраты не прошли, у меня был бы шанс.
А мне втройне — 402 место)
можно как-то посмотреть весь 8-ой тест нзадачи E?
Можно написать генерацию случайных данных, брутфорсное решение, и гонять до первого "!=" :)
У меня падало на 8 тесте из-за того, что я в дереве отрезков при обновлении отрезка, когда заходил в вершину, скидывал текущее значение на потомков, не проверяя, что оно не null и обнулял текущее значение.
Вот посылка с багом: 3545669.
Вот посылка без бага: 3546795.
292D - Connected Components
can anyone tall me why is [ if(!fix[v[i][j].fi] && (v[i][j].se<x || v[i][j].se>y)) ] this wrong and this [ if((v[i][j].se<x || v[i][j].se>y) && !fix[v[i][j].fi]) ] true?????
It isn't wrong — it just exceeds the time limit. The matter was discussed here.
:D :D thanks jimi :D
such a long questions . it was hard to translating specially for persons that their english are not too good .
I made a mistake . It is the participants' duty that have a good English .You can give the questions somehow you want . at last thanks for the contest .
Прошу простить за глупый вопрос, с результатами всё в порядке. Спасибо за хороший контест :-)
Round 2 will be rated for people who did not get in the first 400 in round 1 ? Thanks.
and both for div2 and div1 ? Thanks
Yes , for all the people who participate.
я в кроке 1 раунде занял 386 то бишь прошел.Но при попытке регнуться на крок раунд два мне пишут что рейтинг мой ниже 1700 и посему зарегаться мне нельзя.Как мне быть? P S темы про крок р2 нету решил спросить тут.
Это потому что контест создан с дефолтными див-1 настройками. Думаю, админы увидят твое сообщение и поменяют.
Зарегистрировал вручную. Удачного раунда!
А почему вручную-то?
Тех, кто в показывается в Top 400 по Раунду 1, но сейчас в Div2, как минимум шесть: ultizet, Jace_Beleren, avoit, Wahahalyq, volfram, htkek. Из них сейчас зарегистрирован только Jace_Beleren (что логично). На этот момент остальные должны тоже написать сообщение, чтобы им удалось зарегистрироваться?
И это я посмотрел только тех, кто был в Div2 на момент раунда. А ведь можно было ещё туда свалиться.
Пройти в Раунд 2, и тем не менее, свалиться в div 2? Маловероятно. Вышеупомянутый, например, получил аж +200 к рейтингу, при этом оказавшись почти на границе прохода.
Хотя это не отменяет твоего вопроса, конечно.
Можно было занять примерно 400-е место в КРОК Раунде 1 и затем одно из последних мест в Codeforces Round 180. Этого могло хватить.
А, ещё ж CR 180 был, тогда да.
Сейчас регистрация на него открыта для всех прошедших. Вручную, чтобы не задерживать человека и не заставлять переживать.
OK, понятно, спасибо за ответ!
Похоже, что проблема ещё не устранена.