Всем привет!
В воскресенье, 29 мая 2016 года, в 12-00 состоится второй квалификационный раунд Russian Code Cup! Мы будем рады видеть на нем всех, кто не прошел в отборочный раунд в первом квале. Ну а те, кто и завтра не сможет пройти в отборочный раунд, смогут принять участие в третьем квалификационном раунде 5 июня. Всем удачи и до встречи на раунде, не забудьте зарегистрироваться на чемпионат на сайте http://russiancodecup.ru
How many contestants in each qualification round advance to the elimination round? I advanced from the first round, can I take part in the second round?
200 from each round
I finished in top 200 in the first round, can I take part in this round?
Сколько нужно программистов, чтобы написать без ошибок одно письмо-анонс? :)
так в Майл.ру нет нормальных программистов:)
И вновь баг с отображением решенных задач — я решил задачи A и D на прошлом раунде.
Такая же история, но успел только первую решить... Перед отправкой заметил, что что-то не так, хорошо, что успел вернуться во второй раунд и решить 4 задачи.
Я не пишу раунд, тем не менее, зашёл посмотреть на задачи. Первые секунд пятнадцать показывались задачи с первого квалификационного раунда, а не со второго, это может многих сбить с толку. Сейчас уже показываются новые задачи.
UPD Почему у всех место 3? :)
Ага, я вот заметил что решал не то когда уже пошел засылать первую задачу.
15 минут решал первую задачу из первого раунда = +час штрафа >_<
Аналогично. Заметил это только когда дописал А и её некуда было отправить. В итоге потерял 11 минут, которых как раз был хватило чтобы исправить тупой баг в последней задаче(
Нас таких много, тоже решал задачку с 1 квала. Еще иногда при отправке пишет "неправильно заполнена форма"
Начал решать задачу В, оказалось очень много частных случаев (по крайней мере в моем решении). Убил на нее целый час, зато хорошо потестил, захотел отправить — смотрю, нет кнопки послать решение.
И тут я понял, в чем прикол...
Почему нельзя участвовать неофициально если уже прошел?
Подскажите, как зарегистрироваться на раунд. Нажимаю на сайте кнопку "Зарегистрироваться", меня переводит в мой профиль.
Как отправить решение?? Нажимаешь отправить — пишет неправильно заполнена форма) UPD Если понажимать это раз 10 то отправится)
After I logged in at 12:00 AM, the web site was showing the tasks of the 1nd qualification round to me. I've clicked "2nd qualification round" in the header and started solving. As it turned out later, this had no effect, so I've wasted some time on tasks from the 1st round. Confused and infuriated, I stopped participating in the round.
Please, move previous rounds to some kind of archive so that it would be impossible to mix those up with the current round.
The same for me. Wasted some time solving task A from the 1st qual.
I wasted 50 minutes solving problems from 1st round. So the contest was during 1:10 for me.
Did we have to register before the round to participate in it? I registered just now and can't submit :(
Yes, same thing happened to me in the 1st qualification round.
Условие задачи Е совсем непонятное.
Не могу найти себя в таблице. В поиске по никнейму — 61 место, но на 61 позиции другой человек :)
Может быть несколько человек на 61 месте одновременно, там штрафник с точностью до минуты считается
P.S. Впрочем, сам только что воспроизвёл этот баг — в поиске я 147, в таблице 145.
will there be system testing after contest or the pretests contain everything?
Я правильно понимаю, что RCC — единственное личное онлайн-соревнование, в котором семплы принципиально никогда не поясняются?
Upd: а нет, еще SN?S/Яндекс.Алгоритм, извиняюсь.
На Яндекс.Алгоритме совсем недавно в задаче E квала было пояснение.
Зависит от авторов задач, а не от платформы. Даже если нет специального поля для пояснений — всегда можно их написать в основном условии, было бы желание.
Уважаемые организаторы, сайтом вообще невозможно пользоваться. В начале раунда всплывает окошко навроде "Раунд начался, посмотреть задачи". При клике — задачи прошлого раунда, и лишь где-то в уголке написано, что это первый квал, заметить невозможно. КАК так можно было сделать? Хорошо хоть, их нельзя отправить — только так я понял, что что-то не так, спустя n минут контеста.
Далее, при попытке отправить — неправильно заполнена форма. Из одного поля! Причем проблема известна.
Про то, что показ задач неудобный, и говорить нечего:
Каждый год одни и те же проблемы (и новые).
At first, I started reading a problem from the 1-st round too.
And one other issue. I submitted E and was waiting for feedback. I was chatting with someone and he also was refreshing standings. He saw my WA first and told me about it, but for 1-2 more minutes I wasn't able to see it by myself. I tried refreshing (and hard-refreshing using ctrl+F5) the standings and the page with problems (where I can see my own submissions).
The participants are not allowed to communicate with each other or anybody else regarding any topics related to the tasks. http://www.russiancodecup.ru/en/rules/
Poor-poor Errichto is gonna be disqualified...
Shouldn't you hide this for trolling purpose?
If you think like a troll, maybe you are one of them...
Nice one. So, the question is: is my status (AC/WA) related to the tasks? I would say that it is related indeed ;_;
Nice sorting.
Как решить вторую задачу?
Жадный алгоритм. Всегда принимаем деньги у тех, кто нам больше всего их отдаст. Отдаем тем, кому меньше всего надо. Если в какой-то момент не можем отдать, то заменяем его тем, кому больше всего денег надо отдать. Лучше сливать тех, кто больше всего просит. Всё как в жизни.
Странно, у меня тоже была такая идея . но у меня не прошло
если не можешь расплатиться, то не надо переходить к следующему продавцу. нам выгоднее не платить тем, кто просит больше.
вместо
должно быть
p2++; — вот тут ошибка, двигать позицию нужно только если мы оплатили (из вышеизложенного объяснения — "Если в какой-то момент не можем отдать, то заменяем его тем, кому больше всего денег надо отдать", а у тебя пропускается тот кому меньше всего надо отдавать)
Нет. Ты увеличиваешь p2, если не получилось отдать ему деньги. Но это не оптимально. Лучше оставить как есть, а посчитать, что деньги не отдали тому, кто больше всего их требует.
Жадно. Сортируем покупателей так, что бы сначала шли те, которые дают больше денег, а продавцов наоборот, сначала те, которые требуют меньше денег. А дальше просто симулируем.
Как решать Е?
как решать D?
How to solve D. T-shirts ?
Bitmask DP , let dp(mask , turn) denote the remaining tshirt if mask is the bitmask of all removed tshirts . answer is dp(0 , 0) (assuming 0 is player 1) . Now in each turn player chooses to remove an existing tshirt such that the result of dp is up in the ranks of that player .
You don't even need to include turn into DP state, because turn = bitCount(mask) % 3.
In fact, no need for the 'turn' register, the number of remaining tshirts determines the current player.
We can get rid of turn because it will always equal n — number of bits in the mask % 3 :P
Well, you exactly know, whose turn is it now, but it doesn't really matter, of course.
It can be done greedy with the same complexity as input reading (and actually for any number of people in the team). Let's consider all turns people do in the reverse order. Then for every turn the guy currently making turn will have to cross out the t-shirt with lowest priority in his chart. This can be proven by induction, but it is quite intuitive in a sense that his teammates can leave this shirt out knowing the last guy will HAVE to cross is out. Putting down the main part of my code to clarify (turn is in reverse order, so as p (priority)):
How to solve B and E. Btw I found C and D much easier than B.
if current element is a '+' choose the largest value to add . if its a '-' , consider 2 cases , if the minimum value is <= our current money , then take that else if all values are > current money , take the largest value and sacrifise that.
Woow I am really stupid. I did the same thing but firstly I wrote a brute force which was slow. So I decided to see if it will not get TL if I change all ints to shorts. So I did it with "#define int short". It got WA. Then I came up with your solution but didn't realize that the sum of the numbers can overflow short ...
Are shorts faster than ints (more than by ~0.01)? It's a serious question, I don't know the answer.
No
Once I solved a problem on Timus archive and submissions with unsigned shorts were a bit faster than submissions with ints. Link to list of submissions (submissions with ints used about 60 Mb memory, with unsigned shorts — about 33 Mb memory).
Maybe when you copy large arrays.
For B: Sort receive request in descending order and sort send request in ascending order. Then process the value. Then maintain balance and increase balance on receiving and decrease if sending is possible.
Problem E. First, we need to find an intersection of two paths. Its endpoints are found among LCAs of 4 points in the input. If it's empty, the answer is NO. Next, there are 2 cases.
If testers go in the same direction, the answer is YES if abs(e0 — e1) < longest edge in the intersection, where e0 and e1 — times of entrance into the first node of the intersection.
If testers go in different directions, we need to check that their time intervals spent at the intersection have a common point and they don't meet in a graph node.
Everything above can be implemented using binary ascent.
Как решать С? Я писал перебор с отсечением.
Пиши перебор когда length(S) < k * (k + 1) / 2 а иначе раздели строку на k строк длины 1, 2, .., k - 1, length(S) - k * (k - 1) / 2.
если длина строки больше k * (k + 1) / 2, то ответ всегда есть: берем делаем различные длины.
иначе перебор с возвратом.
Тьфу блин, эту простую мысль то я как-то и упустил :-\
Кажись я перемудрил со своим перебором и бором всех суффиксов :) http://pastebin.com/80x5Q3C7
Если длина строки больше или равна sum(1..k), то можно просто взять строки различных длин. В противном случае строка получается очень короткой — делаем перебор.
Перебор и без отсечений будет заходить)
I really can't believe I wrote this code on E without any single bugs, compiled in first time, and got accepted in first time. (I got one WA but I submitted incomplete code for to check my code)
https://ideone.com/bEGBmq
can you explain your logic?
Divide paths two pieces, going up and going down, and check all 4 pairs. When checking one pair,
If they're going same way and if there will be collision, there will be collision on the longest common edge, too. So we can simply check longest common edge.
If they're not going same way, there can be at most one collision, find where it is. If it's on a node, there won't be collision, if it's on edge, there will be collision.
EDIT: By "collision", I mean "both testers were going along that bridge during some non-zero time interval"
I don't get why you "submitted incomplete code for to check your code". What did you expect? You don't know the order of tests so you still can't be sure after getting e.g. TLE (if you were afraid about WA/RTE).
I couldn't believe that I can solve it, there are just 5 minutes, penalty won't be matter, and I'm sure there have to be some bugs so I submitted without checking "collision on node or on edge". Then I submitted it, I realised it's easy to check it, added it to my code and submit again, got accepted. And I got WA on test 5 at first attempt, so I was pretty sure it's because of "collision on node or edge". BTW it's so stupid to do that.
Как обычно. Оформление сайта, его функциональность и работа тестирующей системы затмили шикарный набор в задач. На котором участники из топ-20 решили столько же задач, сколько и у тех, кто не вышел в следующий раунд.
А что не так с набором задач? Вы хотите, чтобы обязательно человек на 200 месте решил больше задач, чем на 201? По-моему, очень даже неплохо получилось: 212 человек с 4мя, то есть, 4 задачи почти гарантировали проход. И Е несложная, хотя, конечно, могла бы быть ещё немного попроще.
Думаю, Павел имел в виду, что хотя бы у человека на 20 месте должно быть больше задач, чем на 201.
Кстати, никто не заметил, что условие задачи E было изменено после начала контеста?
Исходная версия:
Изменённая версия:
То есть, если открываешь условия в начале контеста и не обновляешь их, о таких вещах нужно догадываться.
Английская версия вообще неадекватная:
Let's call a bridge tested on i-th day if both testers were going along that bridge during some non-zero time interval.
И все.
This contest in Gym: 2016 Russian Code Cup (RCC 16), 2nd qualification round.
Ghosts are from 1st qual.
Thanks
, I'll fix it ASAPfixed!How to sort an array of ints (not Integers) in descending order in Java?
I sorted it and reversed then.
First time for me — getting AC on the first attempt at Andrew Stankevich organized contest. All previous ones were 3-4 tries at best :)
A went in smooth, B smooth. On C I stumbled — I've got the idea about largest difficult string being 14 letters long. But I still hesitated thinking that 1000 testcases of the same 14 letters long "AAAAAAAAAAAAAA" might be too much for brute force. It wasn't, but I lost lots of time trying to come up with some suffix array / trie / or something else based solution. Stupid of me. With 5 minutes left I read Problem D and it was the easiest problem of the round (in my perception because I like this type of problems). Again I had great opportunity to qualify and missed it (287 place). This is my ... 9th qualification round in RCC, usually placed between 201 and 300 :)
In my local time this contest was at 4:00 am and I went to sleep around 0:00 after re-watching last weeks episode of Game of Thrones :)
When you have a string of length = 15, and K = 5, you have about 15*14*13*12 decompositions, and for 1000 test cases about 33 * 1e6 operations, so it's ≈ 30 times less than 1 sec (≈ 1e9 operations)
That doesn't matter, but your value ( 15 * 14 * 13 * 12 ) is far from true number.
The actual value is
which is 1001. ( 32 times smaller than your value)
Пришло на почту:
Выходит вы будете рады видеть всех.
Тех кто прошел — приглашают, но им будут не рады
Учитывая, что участвовать внеконкурса нельзя — очень не рады.