Всем привет!
Уже совсем скоро, в это воскресенье, 2 апреля в 19-00 по московскому времени состоится первый квалификационный раунд Russian Code Cup 2017. Лучшие 200 участников попадут в отборочный раунд, а остальные смогут попытать свои силы еще 2 раза, во втором и третьем квалификационных раундах.
Мы приготовили для вас небольшие новинки: в список языков на раунде будут добавлены Kotlin, Haskell и Free Pascal, а в список интерпретаторов языка Python — интерпретатор PyPy. Точные версии компиляторов и строки компиляции опубликованы в правилах олимпиады на сайте. Мы также работаем над добавлением новых языков в дальнейших раундах.
Желаем всем удачи на раунде и ждем на http://russiancodecup.ru!
UPD Выложен разбор задач
Hope, checking won't last as long as in warm-up.
Хорошо, что работают над добавлением новых языков. А что по поводу тестирующей системы и очереди в полчаса?
Кажется, мы справились ;)
Will there be a mirror contest on Codeforces ?
Why do you need a mirror contest? Everyone can participate in the official contest.
Maybe there are some guys (including me) who want more round which will be rated :)
доступно там?
Hello, I see "Qual" word and green tick front of my name in results of warm-up round:
What does it mean? Am I qualified for elimination round?
Может кто-нибудь задачи скинуть?)
Как решить B ?? почему жадный алгоритм не сработает?
Жадный это выбирать mex? Ну, это не работает на таком тесте:
Ответ
Спасибо, понял. Незнаете, а как решить, тогда?
Upd: Теперь понял и решение. Не думал так просто:
как решить С?
How to solve E?
The answer is the number of different prefixes times the number of different suffixes in the range minus the sum over all letters of the number of prefixes that end with the given letter times the number of suffixes that have this letter before them in some string (basically, what we do is counting everything, possibly twice, and then subtracting strings that were considered twice).
Now we need to count the number of different prefixes and suffixes in a range. If we use hashes, it's just a number of different integers in a range. We can compute it using a sweep line with a binary index tree (we also need to keep a binary index tree for each letter in the alphabet to do the subtractions).
We don't really need hashes. Just construct a trie and assign different integers to different nodes.
Задача С — это игра "угадай компаратор для сортировки". Я угадал с 7 раза, но доказать не могу, почему он работает.
и какой он? я пробовал только самый простой x/a>v.x/v.a
Я вроде как даже доказал, что (a[i] — b[i]) * p[j] < (a[j] — b[j]) * p[i] но что-то не зашло. Какой правильный?
У меня такой
x.X(x.first) — a[i]-b[i]
x.Y(x.second) — p[i]
pii — pair<int,int>
Почему это не работает?
еще влияют уровни, которые между двумя рассматриваемыми
Нужно убрать те, где x[i]==a[i]-b[i]==0. Они всему равны и портят компаратор.
Я проверил глазами, что в этом случае пофиг, а в других все должно быть нормально, а стресс этот тест не поймал. Почему-то мне казалось, что в выпуклой оболочке я делал так же.)
Вот это жесть :-( С 25й минуты до конца контеста пытался понять в чём дело (стресс проходило). Уже даже начал думать, что это из-за вывода long double (раньше на RCC проблемы были с ними).
я с 3ей попытки угадал:)
Зачем угадывать, компаратор это решение задачи при n=2.
How to solve C?
Optimal order is found by sorting according to the following comparator: (a[i] — b[i]) / x[i]. Then one can do simple DP to find value of savings by using this order.
Been there, done that, gottten WA xD.
Here is my code, it worked for me, hope this is helpful, link:
it was because of precision. I also got WA, but then I did just one division by 1e7 at the end and got AC
The case where a[i] = b[i] or x[i] = 0 can be tricky. I handled them separately.
Yes, you're right. I thought my code worked in that case but now I see that I was wrong. Thanks!
With this method I was getting TLE on test 4. Any optimization in implementation? My code
Well just to double check the sorting part just takes nlog(n). Then the dp for me is two dimensions of size n and 2, and constant amount of transition states. Thus nlog(n) + 2n should work in time I believe, constants are not bad I think?
Can anyone please give working C++ code?
Here it is.
Your comparing function can return x<y and y<x for some triples x,y (e.g. both having a=b) and the sorting enters infinite loop.
ohh Thanks! I removed those two lines, but now it started giving WA in test case 3.
For any x!=y you need the function to return true exactly once for x<y and y<x. Without these two lines it may return false twice if d1=d2. I usually return lexicographical order in such cases like your d1=d2.
But if I have d1 = d2. Then it is like I am assuming x = y. So in that case shouldn't it be alright to return false both the times?
No. You can return twice false only for exactly the same elements. Think of it in the way: would a correct sorting of [x, y] be [x, x]? If not, then you can't treat them as equal. And that's the case here.
You can check out c++ strict weak ordering for more information about comparators.
Thanks again! I understood what was the problem. It worked after removing this ambiguity.
Я правильно понял, что задача В — раскраска графа в к цветов, что является NP-полной задачей... как ее тут решать?
В задаче С, у меня зашло такое решение:
1) Сортим все уровни по компаратору
2) Просто идем по отрсортированным уровня и подсчитываем ответ.
Мне кажется, что это не правильное решение, но тесты прошло:)
откуда такой компаратор? в задаче В можно заранее записать табличку вида
1 2 3 1 2 3
2 3 1 2 3 1
3 2 1 3 2 1
... зависит от k. выписал для k=3. Ответ не существует, если есть полоса длиной больше k. Иначе просто выводим те элементы, где стоит 1.
А разве в этом примере будет правильный ответ на задачу? Example: 1 2 3 0 0 0 2 3 1 0 0 0 3 2 1 0 0 0
Во втором столбце два раза встречается цифра 2 и в третьем цифра 1, а так нельзя.
Я думаю, что нужна вот такая таблица:
1 2 3 1 2 3 2 3 1 2 3 1 3 1 2 3 1 2
опечатка) конечно, верная таблица такая
1 2 3 1 2 3
2 3 1 2 3 1
3 1 2 3 1 2
Давай посчитаем длину максимального блока. Если она больше количества цветов — ответа нет. Иначе дадим каждой не лампе цвет (i+j)%k.
Тут граф очень особенный, поэтому задача вполне себе решаема
спасибо:) действительно — очень просто:)
На контестах зачастую появляются NP-полные задачи в некоторых частных случаях и постановках, которые вполне себе разрешимы, так что ничего удивительного вроде :)
How to solve D?
How to solve D?
for each index find out how far you can go while having K distinct elements , now do dp with segtree
We can actually keep a
multisetof available transitions to avoid using any custom data structures.How to solve F?
How to solve B?
Check if there exists continuous vertical or horizontal segment of tiles of size more than k. If so, print 'NO', otherwise print 'YES' and ((i + j) % k) + 1 on places where tiles are. (You can check that this answer satisfies the statement).
why ((i + j) % k) + 1 works ?
In the case when answer is "YES" we know that all the segments have length < k. Consider any such segment. Assume that the segment is horizontal. Same argument will work when it is vertical. For this horizontal segment i is constant. So in (i+j)%k will be different for each of those tiles in the segment. As we are incrementing it by 1 modulo k each time while moving along the segment.
Кто знает, можно ли эти задачи послать на дорешивание?
I wasted more than 1 hour on problem B misunderstanding the definition of "continuous segments of tiles." Please make problem statements clearer next time.
can you please explain it.I m still trying to figure it out.
teja349 it means continuous 1's in array.
Ohh ,I overlooked the word contiguous tiles and was always trying for contiguous segments.
Can the question be solved for contiguous segments (instead of tiles) or is it NP?
With Bipartite matching.
Can you elaborate?? How with bipartite matching.
PS: I dint mean adjacent.
Same here.
I didn't understand the statement but managed to guess it from the samples. The explanation for samples would be so useful.
Does anyone know where can I submit solution after the contest is over?
It is not possible to submit solution to system after contest, as far as I know, but instead of that you can download tests and check yourself :)
UPD: It added to gyms, here :)
Ok, I see, thanks!
А как нужно было понять, что в D правильное понимание условия именно такое? Я решил, что нужно более сильное условие для перехода, а точнее, что мы не можем не пропустить ход, если у нас уже есть нужные индексы.
Если честно, то ты прав.
Петин менеджер умеет мгновенно выдавать данные из любого числа блоков, если на каждый из них указывает хотя бы один указатель. Если же это не так, менеджер сначала переставляет указатели, чтобы условие выполнялось, а затем выдает данные — время выполнения этой операции для i-го запроса составляет si миллисекунд, можно переставить любое число указателей.
А учитывая, что в разборе семпла они специально выбрали индексы так, чтобы по этому правилу их можно было поменять.
Во втором тесте Пете невыгодно выполнять первые два запроса мгновенно (ставя изначально указатели на блоки 1, 2 и 4), потому что потом ему придется потратить 10 миллисекунд, чтобы поставить указатели на другие блоки. Поэтому оптимальная стратегия для Пети — изначально поставить указатели на блоки 1, 2 и 3, перед вторым запросом на блоки 1, 3, 4 за s2 = 1 миллисекунду, а перед последним запросом поставить указатели на блоки 1, 3 и 5 за s4 = 3 миллисекунды. Итого суммарное время ответа на запросы s2 + s4 = 4 миллисекунды.
Это косяк условия.
First Qualification round has been added to gyms: 2017 Russian Code Cup (RCC 17), 1st qualification round
Первый квалификационный раунд добавлен в тренировки: 2017 Russian Code Cup (RCC 17), 1-й квалификационный раунд
Объясните, пожалуйста, для чего эта система с множеством тестов в одном тесте? Я получил WA2 по задаче B, в тесте 2 860+ тестов. Т.е. чтобы найти ошибку, мне нужно написать чекер ответов. При этом сравнение решений (моего и эталонного) ничем не помогло — я решаю точно так же.
Чтобы тестировалось быстрее
Я забыл зарегаться до начала. Зайдя в систему и ужаснвушисть, я всё-таки смог зарегаться, но оно всё-равно отказывалось давать мне посылать решения. Кстати, хочу заметить, что вообще говоря такое поведение противоречит правилам.
Во-первых, в разделе "Правила чемпионата" ничего не написано про то, что участник должен быть зарегистрирован до начала раунда.
Во-вторых в более полных правилах есть два релевантных утверждения:
и
Из первого утверждения можно заключить, что время в головах юристов мейл.ру течёт назад. Из второго утверждения следует, что вообще говоря не должен был бы смочь зарегистрироваться во время раунда. Однако, зарегистрироваться мне удалось, и согласно этим правилам, я должен был получить статус Участника.
Ах, да, обычно в правилах написано, что все участники отказываются от всех претензий к организаторам, тут как-то этого нигде нет. Опрометчиво, опрометчиво...
Регистрация на раунд закрывается, как только начинается сам раунд. Вы зарегистрировались на второй квал (в профиле рядом с кнопкой "Да, я участвую" всегда пишется ближайший открытый квал). Спасибо, что указали на опечатку в правилах, конечно мы её исправим и постараемся сделать процесс регистрации на раунды более очевидным. Пункт про отказ от претензий добавлять всё же не будем :)
Ну вот с Codeforces и TopCoder примерно понятно — им нужно честно распределять участников по комнатам. А для ACM-cистемы зачем вообще эта предварительная регистрация?
I downloaded tests, but in russian-code-cup-2017-qual1/b/tests I can onlu see files named "01", "01.a", "02", "02.a",... How can I see the tests? I am using OS X
That's it. Just open that files in any text editor. There are few files, but each contains a lot of internal tests. *.a files are expected answers. Btw, your answers for B can be different, that in .a files, but also correct, because there can be more than one correct answer.