Доброе время суток!
Совсем скоро начнется Coder-Strike 2014: Раунд 1. Напоминаю, что его официальными участниками будут школьники Москвы и Московской области, решившие на квалификационном раунде хотя бы одну задачу. Все остальные могут поучаствовать в раунде неофициально.
Как обычно, для участия в раунде нужно зарегистрироваться на него на странице.
Раунд будет рейтинговым для всех официальных участников раунда, а также для неофициальных участников из второго дивизиона. Рейтинг по официальным и неофициальным участникам будет считаться отдельно.
Раунд готовили я, HolkinPV и Igor_Kudryashov. Мы очень старались подготовить его как можно лучше. Если есть какие-то вопросы, не стесняйтесь, задавайте их в комментариях.
Надеюсь задачи раунда вам понравятся. Удачи!
UPD 1. Распределение баллов по задачам будет стандартное: 500-1000-1500-2000-2500.
UPD 2. Соревнование перенесено на 10 минут. Все, кто не успели зарегистрироваться, могут попытать счастье еще 5 минут. :]
UPD 3. Из-за сложностей с распределением комнат в этом раунде Div.1 и Div.2 участники будут в одних и тех же комнатах.
UPD 4. Соревнование завершилось, надеюсь вам понравилось. Для официальных участников рейтинг пересчитан. Для остальных он будет пересчитан немного позже.
Is contest like another contests at Codeforces? 5 problems, hacking and ... ?
"The round will be usual rated round for the second division participants." ..so i think yes :D
Yep, you're right! :]
Really easy contest... That was just about speed... And it didnt need neither programming skills nor theory knowledge (Except problem D)...
Why it's not rated for Div1 contestants?
Edit: Just noticed that it's a tournament for high school students.
I think it is because this round is too easy for div1 coder... just like the div2 only contest
А тем кто писал вне конкурса могут участвовать во втором туре??
Видимо, да, если вы о раунде 2.
And what about round 2 ?! rated for Div1 users or not ?!
I cannot tell you such an information right now for sure. Now I think that it will be rated for div1 participants with very low probability.
Для участников Div2 раунд будет рейтинговым? Если да то как будут отделятся в рейтинге оф. участников от участников div 2?
Официальные участники будут состязаться друг с другом и у них подсчет рейтинга отдельный. Другие могут участвовать неофициально, но для первого дивизиона контест будет нерейтинговый, а для второго рейтинг будет считаться отдельно.
As you know, one thing included in rating calculation is rank. In this round div1 and div2 compete together. The whole rank will be included for rating, or div2's separate rank will be included? If we register in this round and we don't submit any code, will our rate decrease? I hope you understood my questions! :D
Div.1 users can take part unofficially and they will not be rated. For official participiants and unofficial Div2 users rating calculation will be separated.
I see. Div1 users will have no part in others rating. They just compete unofficially. Thanks
Also, if you submit nothing, you will not be in the standings and your rating will not change (also, your position will not affect anyone else's rating).
And div1-participants are in different rooms than the div2 ones, so that they can hack only other div1-participants.
very nice :D
users who submit nothing don't even affect rating of participants with negative score in final standings?
Yes. They are not in the standings.
hahaa see UPD 3 :P
I have a more general question. What happens if we register for a contest and because of a bad happening (such as losing internet connection or ...) we won't submit any code? Will our rate decrease or it will be same as before?
Your rate will be changed only if you make at least one submission in the contest
Thanks
It only rate the schoolchildren in Moscow region, right? I was register and I saw "out of competition"
The round will be usual rated round for the second division participants.
how long will it last?
2 hours, as usual.
Извините , а мне интересно официальные участники тоже будут распределены по комнатам и у них тоже будет возможность взламывать задачи ? ну просто нас всего лишь 127 участников.
Да, конечно, все будет как обычно. Просто у вас отдельные комнаты будут.
Again delay..
Nice Start!
First Time to see delay without any problems appears to us
Once the reason was, that official participants were having dinner that time :)
At the end of the day, what's more important than dinner?
Nothing :)
Oh~delay ten minutes. Is it because of the server?
No Error appear it seems like system used to make a 10 min delay even if no problem appear
This 10 minute delay is happening for every round! They should set a default 10 min delay :D
if that happens, then rounds will get delayed by 20 minutes! :D
actually they should set a default advancement of 10 minutes, so that the round will start at regular time! :)
No, it is just to give some additional time for official participants.
OK...just wait for it~GL&&HF
I think it is because of a technical reason: Some people are having dinner :))
so please I need also 10 min extra to have a dinner :)
No, i was late :)
а почему контест перенесли?
Похоже некоторые официальные участники опоздали на контест...
First time div1 and div2 participants will be in same rooms! Looks very interesting! :)
Total: 2279 Contestants: 103 Out of competition: 2176
Can non russian participants win a t-shirt?
no
How will div2 users be rated? The ranking is not separated. Will the mixed rank be putted in the rate calculation formula or first you will separate the ranks of two divisions and then you will calculate according to the new separated ranks?
D = E
E = D
I hope implementations still have some difference.
swap(D,E);
Should have waited for the system tests. Although D did look more difficult.
actually, problem D has a very simple solution (6412648)!
unfortunately i could only get it after the contest finished. :/
EDIT: DemoVersion's explanation about why this approach works.
Как решается D? Просто topsort заходит?
У меня вот такое решение:
Транспонируем граф и выводим его топологическую сортировку. Доказательств не дам, поля снова слишком узки :)
А возможен ответ -1?
В претестах — нет :)
И вообще похоже, что нет, т.к. у нас нет двунаправленных рёбер. Но могу и ошибаться, тогда наверняка кучу людей повалит на систестах)
очевидно же что нет: берем любого сотрудника, всех кому он должен пускаем перед ним, всех кто должны ему пускаем после него. теперь предположим что есть какие то долги между остальными работниками, их можно вычеркнуть так как наш выбранный сотрудник стоит между ними. и если так рекурсивно доказывать, то видно что -1 не бывает
А как хранить граф? Ребер же может быть порядка 10^8, это больше ML (в разы)
ребер максимум 10^5
Блин, ты прав. Эх. Но ничего, до третьей я кажется уже умею условия читать.
Количество ребер не превышает 10 ^ 5.
У меня получилось несложное доказательство, буквально в пару строк — на основании "я больше ничего не умею делать при таких ограничениях", "она должна быть проще Е" и "какая разница, раунд ведь нерейтинговый".
И по поводу -1 — используем лемму "в примерах нету, ну и ладно".
"в примерах нету, ну и ладно"
от создателей "сэмпл проходит, отправляй!" :)
у меня топологическая сортировка прошла претесты
Развернуть граф, найти топологическую сортировку, вывести ее наоборот. Fin.
Я также делал, только в конце еще надо проверять, выполняется ли условие.Если нет — то -1.
Что значит топ-сорт для цикла из трех вершин? В теории он может посортировать так, что ответ не сойдется.
Топсортов для графов с циклами просто несколько же. А как мне кажется, нам любая подойдет, ввиду обхода графа и развернутых ребер.
Это для графа с несколькими компонентами связности их несколько. А для графов с циклами их нет.
Не знаю, зайдет ли. Но претесты прошло. Запустим дфс. Для каждой вершины сначала выведем ее потомков, а затем ее саму.
UPD: зашло
А если потомок А указывает на потомка В, и, вдруг, так окажется, что в Вашем ответе А и В идут подряд?
Всё в порядке. Тогда либо мы сначала выведем потомка не должника, либо попадём в него через дфс и, опять же, выведем его первым.
Возможно, я вас неправильно понял, но в вашем примере А и В вполне могут идти подряд.
Как раз ребро A->B этого не позволяет. Ладно, надо подумать :)
Кажется, это и есть топологическая сортировка :)
Это даже не совсем топсорт. А что-то в духе топсорта. Там ведь граф с циклами. Который формально не получится отсортировать.
А кто-нибудь смог подобрать тест, для которого ответ -1?
У меня конструктивное решение, которое доказывает, что решение всегда есть.
Я решил сортировкой слиянием.
Классный компаратор. Ведь была мысль — раз просто делать swap вершин a,b мало, надо это делать какой нибудь сортировкой. Но ограничения смотреть — для слабаков, дело известное.
В D зашла простая сортировка, где A раньше B тогда, когда B — должник у А. 6408347
Буду очень благодарен любому, кто объяснит, почему это работает.
Такая сортировка исключает абсолютно все пары подряд идущих чисел, где второй — должник первого. Если во время сортировки такая пара находится — она переворачивается и сортировка продолжается.
Да, но мне кажется, что компаратор потенциально не является транзитивным, что может вести к очень странному поведению sort на "anti-qsort тесте" (на нём sort "перескочит" на heapsort, а построение кучи по нетранзитивному компаратору это что-то очень странное).
То есть вопрос состоял в том, почему sort вообще выдаёт что-то разумное.
Под anti-qsort тестом я подразумевал некий легитимный набор ответом на запросы к компаратору при quicksort-е (если он вообще есть), "ломающий" quicksort.
Буду рад услышать более подробные комментарии по этому поводу (если это Вас не затруднит).
Похоже, я недооценил Ваш вопрос :) Вы правы, здесь не соблюдается транзитивность. Я совершенно не думал о переходах в heapsort. Присоединяюсь к Вам. Почему это работает? :) Буду тоже очень рад узнать ответ.
Тут была глупость.
В кои-то веки для решения контестов пригодился bubble sort :-)
What was the indended solution for D? I thought about some bipartite matching, but the number of edges was too high. I suppose that either this or a constructive solution should apply. Is anybody available to give a little hint? (Don't spoil it yet).
Topsort passed pretests.
UPD: it passed full-tests.
This passes pretests : reverse the edges, then find topological sort of this new graph, and output it in reverse order.
But how is one able to topsort a graph which is not guaranteed to be a DAG? I suppose there is a slick trick involved in here. Am I right?
topological sort
Some Hint:
Before we let an employee in, we let all of persons he owes money in then there will be no error ;)
but how this is possible for cyclic graphs (second example)?
Yes its error but your attempting to hack my hint ?! :D he should figure out that himself.
At least for every hint given by now, I took the second exemple from the statement (the length 3 cycle) and said: how can one use such logic on non DAG graphs? (Also mentioned this in my second post up here). Did this approaches also pass SysTests?
My version: it is possible to remove some edge from the cycle without loss for the final structure. So we made DAG.
My code Passed 6412544
There can not be a cycle with 2 node ( Two persons cant both owe each other ).
For cycles with more than 2 node its ok we can write the reverse cycle starts from anywhere.
Ex for test2 lets start from node 1
Thats one of answers. The solution i used at contest was based on the Topological Sort 6407870 but this one was easier to get.
hacking error
What type of error it is?I am not able to post the image so I posted the link.
someone made a test, your program was unable to pass
//link does not work
I used input as file , and it was not hacked by others too.
UPD :I corrected the link
i think it means that when u submitted the hack, another hack was already submitted and in queue before urs. so by the time ur hack was "popped" from queue, the solution was already hacked, therefore ur hack was discarded.
EDIT: however, it looks like u have got points for successful hack of his solution 6409307! not really sure what happened here!
Thanks for answer.I thought the same.So I checked my room and refresh the site again and again but found that it is showing as correct solution.
UPD : My point has been updated after the contest, they gave me it as successful hack.
Is the contest rated for div2 contestant ???
yes
Thank you :D
Is it possible to solve E using RE?
RE?
http://en.wikipedia.org/wiki/Regular_expression
Oh ok.
I tried very slow RE, so TLE...
When will the system testing take place?
Кстати, если кому-то понравилась задача Е.
1835
the ranks of div 2 participants depending on div 1 participants or not ?
the ranks of div 2 participants depending on div 1 participants or not ?
Since the contest is only rated for div2, it's only logical that ratings of div1 participants wouldn't affect that of div2 ratings. Although I'm not sure.
I hope they will judge logically.
I also think so... :)
Yeah, this is what they just did, but since new rating depend of the rank and the expected rank, compete with div1 can only be good for us ;)
Хороший вопрос. Ведь если считать рейтинг для Div2 участников отдельно от Div1, то многие могут занять куда более высокие места, относительно Div2 участников (150, вместо 300, к примеру).
Да, в совмещенных раундах так и бывает. Правда, разница в местах все же не так высока.
450->237
6407031 6407103
i honestly dont know why users try to cheat even in unofficial contests!! -_-
How do you find same solutions?
i hacked one of them, and just ran into the other while checking some Failed System Test solutions. i recognized immediately when i saw
n - (k+2)(i hacked first submission on same mistake).Thanks for the explanation
Or this one 6411312 6406588
His solution was hacked because he wrote stupid "if" in code. ;)
Sorry for my bad English.
but he wrote that purposefully to hack his "fake" account! look at the handles it is clear that one person use both accounts!!
Oh, I didn't noticed that. Then he had cheated.
____________________________________________ Sorry for my bad English.
Sorry for minus in contribution, didn't notice the difference between their handles :(
They are out-of-competition here because only Russian high school students are official competitors, but these guys (guy?) still get rated.
Because this contest was rated for div-2 participants
can someone explain why no test case with output -1 was included for problem D?
is an output of -1 impossible to get and if that's the case why? Thanks.
yes, answer of
-1is impossible.When rating of Div 2 participants will be updated ?
Still not updated :/ UPD: it has been updated
Можете помочь найти ошибку? Задача E 6407792
Комментарий ниже очень кстати. :)
Вот контрпример:
2.y@[email protected][email protected]@[email protected].@@zsmp5@uw8x55@@h3g4azvyy7xb8t@id
Правильный ответ — 8 (столько ответов можно достать только из подстроки "[email protected]"), а ваше решение даёт ответ — 10.
Блин, многим же, наверное, [email protected] какой-нибудь в E кайф обломал)
Теперь я точно знаю, что эта задача делает на месте Е.
Тоже на этом прокололся, если бы один ифец не забыл, прошла бы.. эх, печаль
Для теста [email protected] ответ 0?
да, т.к. между @ и . пустая строка
Да, в условии написано "непустая"
да
Ответ 0, между @ и точкой должна быть непустая строка
Какой хитрый тест, я так до него и не додумался бы
Блин, ребята, не знаю чья вина, но обидно, что письмо с анонсом приходит через час после окончания раунда!
Да если бы только через час)
В правке скрин
У вас хотя бы пришло.
UPD: Время 23:51 по МСК, мне приходит анонс.
oh my god, tourist use 23min to solve all the problems....
too long?
it's not enough for me to even read all the problems ...
First Note that he read problems in Russian his native language.
Second almost he write solution while reading the problems.
Third he is very fast in writing.
Forth if you used all previous features you will solve problem "E" in 23 min.
so you need a core I_7 mind to solve all of them in 23 min.
В чем соль 26 теста задачи Е?
Здесь описано.
может переполнение? 5e5*5e5
Переполнение — это 14 претест.
Попробуйте вот этот тест: http://codeforces.me/blog/entry/11746#comment-165467
Для остальных он будет пересчитан немного позже.
Немного позже — это когда? Завтра, послезавтра, через пару часов?)
уже
А мне оповещение на e-mail о начале раунда пришло через два часа после его окончания, рассылка точно была настроена правильно?
Is there any editorial for this contest. Or can anybody who solved Problem D and E kindly explain the approach for solving those ?
editorial is here.
for D, there is a much easier way than editorial. explanation is here.
системное тестирование за ~1 минуту — это было круто :) чем это было обусловлено?
Can anyone help me with E??? It seemed not very difficult but both during the contest and after that I'm getting WA on test 13. It is a very long string and as a result I don't understand where I went wrong in my code. A very short hack would be appreciated. Thanks.
failed at testcase 26 during contest due to this bug, there's probably more bug in your code
Thanks a lot. Solved cases similar to that and know I'm getting WA on test 23!!! It's driving me crazy!!! I'd appreciate it if you take another look at my code. Thanks.
The substring between
@and.should be a non empty substring consisting only of letters and numbers.Your code check only one occurrence of
_after the first letter.So in a case like :
a_@b_.c... Your code count the substringb_as a valid substring between@and.... while it is not !Thanks both of you:
zeulbandYellowNextYear. I noticed this condition but implemented it in my code wrongly.Будет ли второй раунд рейтинговым для Div.1?
UPD: Все, прошу прощения, вопрос отпал, не будет.