Всем привет.
В воскресенье, 7 сентября, в 19:30 по московскому времени состоится очередной, 265-ый, раунд Codeforces. Задачи подготовил я, Михаил Тихомиров. Раунд пройдет в обоих дивизионах.
Для раунда будет использована стандартная (не динамическая) разбалловка.
Div. 1: 500-1500-1500-2000-2500
Div. 2: 500-1000-1500-2500-2500
Хочу поблагодарить Геральда Агапова (Gerald) за помощь в подготовке задач, Филиппа Руховича (DPR-pavlin) и Александра Машрабова (map) за тестирование раунда, Марию Белову (Delinur) за перевод условий на английский и Михаила Мирзаянова (MikeMirzayanov) за создание и поддержку проекта Codeforces.
Это мой третий раунд на Codeforces, и я постарался сделать задачи максимально интересными и разнообразными. Желаю получить удовольствие от раунда. Удачи! =)
UPD: раунд завершен. Всем спасибо за участие, надеюсь, вам понравились задачи.
Поздравляю победителей раунда:
Div. 1:
Отдельные поздравления simonlindholm, единственному участнику, кто справился с самой сложной задачей Е!
Div. 2:
Краткость — сестра таланта, да? ;)
Your next contest after Three years....!
I wish to see more Math.:)
I wish to see more Math.:)
I think you'll get what you want.
:)
I hope for no math.
Why both hope for math and not math problems got negative votes?
Because it's spammed on each contest announcement?
Then explain positive votes in this comment Edit: it's no longer up-voted (but it was +13)
Oh, I hadn't downvoted that one. Fixed.
I meant if it's really spam why people in codeforces up voted that comment ? Edit: it's no longer up-voted (but it was +13)
Dunno, I provided a reason for why downvote (there are dozens of short comments like "I hope there'll X" and "GL&HF" and "thanks for X", and I stopped being interested in reading them after the first 100), not why upvote :D
CF voting is really strange, I have no idea why it behaves the way it does. Sometimes I'm thinking the answer could be 42.
@Xellos I will keep that in mind from next contest.:)
Hey man, I just keep repeating that because this site is not named "mathforces", and others keep making "Hope for math!" comments. (!!)
Oh yeah, I forgot that the optimal method to reduce the "Hope for math" spam is to add "Hope for no math" spam.
While speaking about math, have you noticed that the absolute value of your contribution is a perfect cube? Also the absolute value of mine is a 4th power added to 1 :o. It is a very interesting topic :o.
Here , I have made the absolute value of your contribution a 4th power added to 3 now :D
Actually, it is the absolute value of a 4th power added to 3 :D.
Also your contribution is a fourth power :o.
why? I think Math is difficult
Why? I think math is easier than other!
I love Math.:D
Math is beatiful guys and haters shut up xd. If it weren't for math, there won't be competitive programming xd.
I hope I can do better！
265
I m going 2 rise
The green knight rises (poke batman).
I think this announcement sets the record for the shortest announcement for a contest ever. Keep It Short and Simple! :)
Keep it simple, stupid! (the KISS principle!)
I like this simple style,Keep it short so that people don't miss part of important message.
Good way to get more upvotes :D
Wish to learn new concepts ,new tricks and new things :)
...
Это будет мой первый раунд:)
Твой рейтинг после раунда будет в районе 1350-1450
Жаль, что в 8 вечера наши (армяне) против Дании играют.
Why is everyone in a hurry?! Contest's blog 5 days before contest?! Once they posted it a few hours before the contest :D Oh, and no thanks to Gerald or anybody else?! What an unusual contest blog...
It is my first time to compete, I hope i can solve at least once.
Welcome. I hope you can solve all.
Good luck and have fun! scores up, up and up!
How to register for the contest ? I can't find any link for registration
You will be able to register a few hours before the contest.
Long Waiting For this contest
Good luck everyone
Посмотрел на автора и сразу вспомнил ЛКШ!
cheer up!
First time above 1700 and I have a question regarding divisions. My friends take part in Div2 but I can't Register to Div2 due to 1700+ rating.
Will I be able to join as virtual something when Div2 starts without ranking or I must register in Div1?
You can enter virtual Div2 only after the contest is finished
now you can only enter div1
that's bad but thanks.
What type of scoring will be use ?
Good Luck to everyone
why do u combine
Unable to parse markup [type=CF_TEX]
with normal text?I don't know ? 'Cause are different topics ? My question and my wishes ?
Всем удачи на контесте.
Почему кому-то не понравился контест? Уже ведь ради задачи А решать стоило, там ведь такая прикольная идея! Автор картинки наверное просто не умеет решать красивые задачи, ему наверное лишь бы какой-нибудь дфс баянный загнать!
Почему если китайский контест — то это обязательно значит "не понравился"?:) Я согласен с vitux, по ощущениям — контест китайский. Не хороший, не плохой, а именно китайский:)
Кстати, для меня полными боянами были В и С, на идейном уровне — еще и D. А "баянность" задачи сильно коррелирует с оценкой ее красоты?
Буду благодарен, если найдете ссылочки.
Прошу прощения, не хотел, чтобы это прозвучало как какое-то обвинение:)
Если вдруг вспомню/увижу, то дам знать:) Но вряд ли. А пересматривать несколько тысяч задач мне, скажу честно, лень) Да и смысла в этом нету.
Нет, мне правда интересно, где эти задачи могли быть, потому что я их нигде не видел. =)
Из на тему/похожих/с общими чертами — задача "проверьте, образуют ли данные точки куб" более-менее популярная. Хотя и не настолько, как "проверьте, образуют ли квадрат", но эту часть решения В я назвал бы известной и сугубо технической. Конкретно такую не видел — видел задачу, где дано несколько точек, и нужно сказать, можно ли из них выбрать 8 так, чтобы получился куб. Вероятно, на каком-то из зарубежных online judge вроде TJU/POJ/ZOJ/HDU. Идея была та же — перебор проходил.
По поводу С — в голове крутится, что где-то видел даже конкретно такую. Понятия не имею, где именно:) А общая идея "хранить остаток и длину" вроде бы далеко не новая. Только обычно ее дают в виде единичных запросов изменения, или вставки цифры, или еще какой-то такой ереси. На одном из полуфиналов было, в ПЗ когда-то было... Иногда как-то усложняют, и вместо остатка всей строки дают запросы в стиле "сколько подстрок...".
За А спасибо:) Никогда раньше похожих не видел. Ниже пишут, что не новая — надо будет разобрать общий случай в свободное время)
Ну и жду разбор, интересно узнать, вдруг у D есть красивое математическое решение.
То ли я не понимаю, какие идеи следует считать прикольными, то ли эта задача решается не только перебором префикса, который мы не трогаем. Неужто второе?
How to solve C ? Any Idea ?
how to solve Div-1 B?
Bruteforce, I think. There are 6 permutations for each of 7 point (you can fix the first), so it is 6^7 ~ 300k — fast enough.
Or generate all variants for 3 points, build all cube and check points.
How check? Length test&?
How check? Length test?
And how do you check if it's a cube?
I had an idea to calculate all pairwise distances for some fixed permutation (there are 28 segments in total) and sort them. Now, if first 12 of them are equal, next 12 are equal and last 4 are equal, it's a cube. But I didn't have time to code this solution and can't prove it
i'm convinced this idea is correct, but i dont know why my solution 7712723 gives TLE!
Because that's incorrect idea and obviously your solution is wrong. Also, your code-style is very dirty. Learn Math and don't ask stupid questions anymore.
Lol, that's pretty rude. I'd ask you to learn some good manners first.
Oh, I so ashamed...
Один стою в белом пальто красивый.
Map is not so fast thing:) Try to rewrite it without map, it should pass — my solution is basically same, but with vector&sort (7708825), and it works in 0.7 seconds.
my solution 7712723 with the same idea TLEd! :(
Could you please explain how we can fix one point if all of them probably were shuffled?
It would be great if you could write problem A shorter! At the first, I was confused.
Thanks!
How to Solve Div -2 C ?
they key observation is that if we don't have any palindromes of length 2 and 3, then we will have no palindromes at all (other than single characters, ofcourse).
How did you arrive at this conclusion? Have you solved a similar problem before or was it intuition or did you think of this during the contest?
intuition. any palindrome of length n > 2 has a sub-palindrome of length n - 2 as its substring (u can get this by removing the first and last characters).
easy to note that we can build palindrome by add same character to begin and end of another palindrome. just consider the case of odd and even length, so we could just check every 2 and 3 consecutive letters
I made this observation during the contest but do you still have to loop over all possible strings after the input?
Can u explain ur solution !
Suppose you have a palindrome of length at least 4. Delete the start and end characters. Now you still have a palindrome. Thus you only need to consider palindromes of length 2 or 3. Find the rightmost character that you can increment to something satisfying s[i]!=s[i-2] && s[i]!=s[i-1] (within the bound of p of course), then fill the remaining letters with the "smallest" letter possible.
I got my first hack on codeforces! I tried a little different strategy this round. I solved B and A quickly and then tried to solve C within the first hour. But I couldn't. Nevertheless, I spent the whole of the second hour trying to hack but was not very lucky until the last 10 minutes. About 7 minutes before the end of the contest I managed to hack a solution!
Nice problems!
How to solve D? I was struggling for quite a while, but didn't come up with anything faster than 100 FFTs (or 2 FFTs, but for vector with size 107) :(
My solution relied on the fact that we only need 1e-9 precision. Basically, with probability 1-eps we never get to very high levels.
Понравилась задача В. "Пиши, деточка, if'ы, да побольше-побооольше".
Хм, зачем там if'ы? Объявляем одну из вершин началом координат, перебираем единичные векторы-рёбра куба и порядок координат для них (C73 * 3!), дальше просто паросочетание. Или я чего-то не понимаю?
Круто. А я перебирал с отсечением 6^8 вариантов, и те которые выживали, проверял тоже на паросочетания, но кучей if'ов, чтоб понадежней было :)
Честно говоря, я даже не особенно парился об отсечениях или какой-либо оптимизации, просто написал перебор. Этого хватило)
Вот у меня тоже перебора хватило, только после контеста... не поставил одно отсечение... http://mirror.codeforces.com/contest/465/submission/7712967 (на контесте) http://mirror.codeforces.com/contest/465/submission/7714050 (после контеста)
Как альтернатива паросочетанию — если рассмотреть все возможные отрезки между парами вершин этого куба, и принять самый короткий из них за Х, то у нас должно быть ровно 12 отрезков длины Х, ровно 12 отрезков длины 2*Х и ровно 4 отрезка длины 3*Х.
Upd. Cпасибо Lo_R_D за замечание, рассматриваем не длину отрезка, а квадрат длины.
По-правка: у тебя рассматриваются отрезки в квадрате.
Можно не перебирать, а взять 2-4 векторы в порядке длины. Вместо паросочетания можно проверить, что среди векторов есть все попарные суммы трех ребер и сумма всех трех ребер.
Паросочетание здесь можно и за 4! искать, проблем с ТЛ не будет в любом случае.
В теории можно было бы даже два единичных вектора перебирать, а для третьего перебирать только направление. Но на КФ нет __int128, а авторам захотелось координаты до 10^6 :(
I managed to find a suitable algorithm for 464C - Substitutes in Number, yet couldn't solve it because I couldn't read the input properly. I don't know yet what was causing the quite straightforward input code to fail... Here's my last failing submission : 7713194 If I add assert (c >= 0 && c <= 9); after line 43, the assertion fails...
This was a great contest :) Thank you for writing! I liked many of the Div 2 problems.
Первый раз в жизни решение C прошло претесты, но я уже без систестов знаю, почему оно завалится :) Контест великолепен, спасибо большое!
I have a feeling that a lot of A-Div1's will fail.
I see some hacks on div1-C, for example Merlininice has quite a few. How can a solution to div1-C be incorrect? It looks really straightforward.
Are you now scared that yours too is incorrect?! :D
Some people did not take the length by module, some took it by module 109 + 7 instead of 109 + 6.
But why does one need the length at all?..
I guess you're saying that people were computing "length of expansion of digit X" instead of "10 to the power of length of expansion of digit X"?
Exactly.
My solution got hacked also. It was totally a straightforward dp problem. I just couldn't figure out why it was giving incorrect ans. I thought keeping the length and exponent value would do the same thing but totally forgot that if I kept the length, I would have to do modulo 10^9+6 on the length according to FLT. If only I'd kept the exponent value instead :(
10^9+7 instead of 10^9+6 ????
problem statement say 10^9+7
If we store just length, we're computing 10^len at some point. Using FLT, we can just compute 10^(len mod (10^9+6)) instead, so we can just take len mod 10^9+6 instead.
One should use 109 + 6 in order to keep length. Because it is the period of pows (check little Fermat's theorem)
New information for me, thanks :)
do you mean that if I saved the length instead of power of 10 and make it modulo 10^9+6 I will get AC?
Hey Petr, didn't you make a similar mistake (taking different value for MOD) in a past contest? I remember reading about it on your blog!
If I remember correctly he made a missprint (10^9+9 instead of 10^9+7 or sth similar), not a conceptual mistake like the one mentioned above.
so do ztxz16 and Kostroma.
I had this algorithm (which I did not implement) for solving 465C - No to Palindromes!. Is this a good approach?
Treat string as a number in base p.
The function check(x) tells you if x contains no digit > p and that it contains no palindromic substring of length > 1 (both of which can be done in linear time).
Your function check is not monotonic, so binary search won't help you here.
How did you solve it?
Not the contest that I expected and hoped... BTW, Palindromes are AWESOME! Why should somebody be bad with them?!
Потрясающий контест! От души спасибо авторам!
Here's a Brainfuck solution to problem A (reads and outputs as ASCII). The cells are divided into groups of two. The first cell of the group is 1 if the index is in range 0 to n and 0 otherwise. The second one contains input for that index — either 1 or 0.
The code:
>>,- read n [[->>+<<]+>>-]+ prepare cells of the second type [<<] go to start >>[>,>] read input <<[<<]>>> go to first value cell [ <<[->>+<<]>> add values from last index >> go to next cell ] <[-<+>]< if the index cell is 1 add to the result . output resultWeren't E div2 — C div 1 pretests very very weak?
I see naive implementation solutions pass pretests!
Wow, really???
Yes, See those for example 7713065 7710477 7710991
I tried to hack this solution
by this case
2 0 0
but it gives me Unsuccessful hacking attempt
with this case variable pb will be used without initialization
how this solution pass my case ?
pb will have junk value, but that would not contribute to answer, just that "break" will not be called.
How to solve div-2 D ?? I first tried to take all 6 combinations from 24 , that is 24C6 , clearly it isn't suitable !!!
When A,B are too easy and others are hard (div2), this will happen: I can see about 1500 rank difference between 2 users while both of them have solved 2 problems. The rank of the participants which solved 2 problems, starts from 400 and ends after 2000. This is a huge difference! I think this shouldn't happen.
Thanks :)
In this contest, if you can solve only A, B which is common with Specialists and low Experts, your score will depend on your time, which isn't kinda bad. If you succeeded in solving C, or even D, E, those tasks will tremendously increase your rating because they are simply made for coders who has ideas and knowledge.
2:15 ночи (за 15 минут до начала контеста): "Не, бро, извини, мне так фигово, что я не смогу участвовать сегодня". 2:25 ночи (за 5 минут до начала контеста): "Мыться под холодной водой — вот мой выбор" — "Да, это выбор чемпионов". 5:15 ночи (после системного тестирования): "Нифига себе, возможный TL по D зашел, говнокод по C не упал, 16 место ёпт! Впервые решил 4 задачи! А я еще участвовать не хотел!"
Этим комментарием заставил меня задуматься над тем, чтобы все же принять участие в Ice Bucket Challenge:)
просто демон :-)
I misunderstood Div1-C problem statement :-( But problems are very interesting. Thank you for preparing this round :-)
Да ну вас, злые тесты по D div2, куб из одной точки тоже куб) На таком упало...
Нужно внимательнее читать условие:
Понимаю что надо внимательнее. это эмоции, из-за разочарования, что на такой ерунде упало.
For Div2, a and b was easy and c d e was hard. I have solved A and B but I got rank 1100... To many contestants solved just 2 problems and very big difference in same, two problem solvers.
Who else forgot to check if the cube side length is greater than 0? High five!! :'(
High five! :)
I got wrong for DIV 2 D , because I used float instead of integer while printing the cordinates , my programs prints the cordinates in exponent form in one of the test case and is judged wrong.
Did someone else also failed system test in this way before ? Link : 7710844
Предполагались ли в решении задачи D проблемы с денормализованными числами, или это я такой везунчик, что меня это затронуло?
Не думаю, что мое решение предполагалось, но в нем нет никаких операций, кроме умножения даблов при добавлении к ответу.
Я запустил твое решение на макстесте, и оно отработало 2100мс в запуске — видимо, тебе повезло на систестах :) А если сделать ифы, обнуляющие переменные, когда они станут меньше какой-нибудь константы (типа 1e-20), то оно ускоряется в три раза.
Нет, я хорошо проверил на запуске и выставил константу 750 с запасом :) Во время контеста, если сабмит получает ТЛ, то он перепроверяется на отдельном ядре. Если же нет статуса ТЛ, то остается прежнее время выполнения (в таком случае на этом же ядре проверяются еще какие-то решения).
Да, я не прав, я под g++ запускал, под студией, действительно, все хорошо.
Я наоборот думаю, что именно оно и предпогалалось. А денормализованные числа там вылазят как раз из-за умножения чисел, меньших единицы. Добавил ровно одну строку
if (f[j] < 1e-30) f[j] = 0;к твоему решению и оно прошло за 0.2с вместо 1.8с, как на контесте: 7714718.У меня ни в одном из решений такой проблемы не возникло, потому что у меня была единственная динамика — мат. ожидание ответа, а вероятности никак не использовались. Весьма неожиданный эффект.
Как решать Е? Я так понимаю, там нужно что-то быстрее, чем 100000MlogM/32?
Видимо, решается так. Будем хранить числа в персистентном дереве отрезков. В каждой вершине будет хеш соответствующего ей подотрезка. Тогда чтобы сравнить 2 числа, нужно найти первый бит в котором они различаются и сравнить его в двух числах. Еще нужно уметь прибавлять к числу степень двойки. Для этого нужно находить для заданного бита предыдущий, который равен 0. Выходит, мы числа можем сравнивать за O(log(MAX)), где MAX — максимальный показатель степени двойки. Тогда сложность решения O(M * log(M) * log(MAX)).
UPD: Конечно, нужно Дейкстрой искать ответ, просто вместо чисел будут деревья.
Может я неправильно понял условие задачи, но что если предпросчитать 2^(x) динамикой и запомнить для каждого x целую часть и по модулю, а потом алгоритм Дейкстры за m*log(n)(может это не дейкстра, но он на основе set'a), суммировать путь будет не сложно(прибавлять целую часть и по модулю), а потом просто вывести ответ.
UPD: понял ошибку
Если (a + b) % MOD < c % MOD, то отсюда не следует, что a + b < c.
Why ratings update is delayed too much in codeforces after system test is finished? (while it's fast in topcoder)
the relation between system tests and rating update is inverse. i don't know why .
My guesses:
System tests are delayed — because they need to add the newly added hacks to the final tests.
Rating updates are delayed — because they are figuring out the cheaters in the contest.
Задача A сильно смахивает на эту: 196D - Следующая хорошая строка, только ограничения намного меньше. Это было сделано специально?
Нет, случайно получилось. Прошу прощения.
А ведь ты играл тот раунд, я помню :)
Я сейчас скопипастил свое решение, поменяв
'z'на(char) ('a' + p - 1)и проставивd = 2, и получил Accepted.Ты помнишь, что я играл этот раунд два год назад? о_О
Ну вот да, была опасность, что будет много копипаст решений, в том числе, чужих. Но как-то обошлось.
Если быть точным, я помню вот эту ветку обсуждений: /blog/entry/4708#comment-96085
(осторожно, спойлер к одной из задач того контеста)
"Играл" — лол)
Так больше нигде не говорят, что ли? Все пишут и участвуют, и никто не играет?
Я никогда не слышал. Я обычно пишу.
Good question, thanks ^_^ waiting for editorials...
Обновите рейтинг пожалуйста, завтра в школу просплю :(
"Editorial will be up in an hour or two" is a statement for Infinite Loop :P
"Editorial will be up in an hour or two." is a Infinite Loop statement.
Can someone give some hints for Div1 C?
div2 probC
runtime error. changed to
accepted. life sucks :(
1).new char[n]is not supported by standart, it's only gcc feature.2). You need
n+1chars because of extra'\0'character at the end.1) LOLWUT?
1). Sorry, confused it with
char data[n];if you can use
cin, why don't you usestring?Looks like tests in Div1-B are weak — I mean overflow. I have just written an int64 solution, which use values like maxCoord^4 (euclid length of vector product). And it's full solution. Is it difficult to create test to crash this solution?
I think technically you have calculated a hash of the vector's length (have calced it modulo 264) and then you are only interested if two hashed values equal or not, so it seems OK.
These submissions are very much alike, aren't they? This 7704944 and that 7706248 And this 7713468 and that 7713301 too!
I'm a policeman:)
Oh my rating :))
Огромное спасибо за такой прекрасный раунд!
very happy to get 284 point
can somebody explain div-1 C it is not so clear from editorial
Didn't read editorial, but may be can help
First of all, we can notice that after all transformation behind every digit will stay some sequence. Suppose we know these sequences for every digit [0..9], and for digit d sequence has length len[d] and value val[d]. Now, to compute result for input s, go though s and result = result * (10 ^ len[s[i] — '0']) + val[s[i] — '0'].
Now we need to compute len[] and val[]. Let's use DP technique. Consider len[] and val[] calculated for some suffix of transformations queries [k..m-1]. How compute them for suffix [k-1..m-1]? Use similar ideas were used to compute result. Take query d->t, go through t and value = value * (10 ^ len[t[i] — '0']) + val[t[i] — '0']; length += len[t[i] — '0'];
val[d] = value; len[d] = length;
All these formulas come from Horner's method.
Country wise standings are updated. Sorry for the delay.
The contest & Codeforces both are awesome .. :)
Round Stats
Why my submission in queue for so long?