Всем привет!
Совсем скоро, 26 ноября в 19:30 MSK состоится Codeforces Round #215, автором которого являюсь я. Это мой девятый раунд на Codeforces и я надеюсь, что не последний.
Спасибо Геральду Агапову (Gerald), Диме Березину (Berezin), Виталику Аксенову(Aksenov239), Михаилу Мирзаянову (MikeMirzayanov) и Максиму Бевзе(Cenadar) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.
Настоятельно рекомендую прочитать условия ВСЕХ задач.
Разбалловка див1: 500-1000-1500-2000-2000
Разбалловка див2: 500-1000-1500-2000-2500
Gl & hf ! :)
Раунд завершен, спасибо за участие. Извиняюсь за ошибку в задаче A. Надеюсь, что задачи Вам понравились, а нестабильность сегодняшнего соревнования не испортила Вам настроение.
Всем хорошего вечера :)
Так же давайте поздравим rng_58 с достижением 3010 очков рейтинга!
This Contest and previous one from the same street as Berezin said :)
When I read the previous round post I say to myself yea no recommendation for reading all problems But I found this statement
Sergii sends greetings and strongly recommend to read ALL tasks. :)
Странно, что пока никто не выложил известное фото автора.
Why another round for Div1 takes place at Tuesday? Sadly I'm not able to take part in any round at Tuesday, I prefer Saturdays/Sundays and I think I'm not alone with that opinion.
+1
I prefer weekend rounds, too. But it is probably due to NEERC this time.
Although I hate the time (19:30 MSK, means 23:30 Peking time) because it means I cannot go to bed until nearly 2:30 am, I still like taking part in the contest.... I hope more contest starting earlier...How about at noon in MSK?
I think this time is chosen by considering most places in the world.
But 19:30 MSK is not rational enough, because most coders don't like contests between 00:00 am and 13:00 pm, but not just between 00:00 am and 8:00 am.
I agree, are there any other suitable time?
right. for this is a russian website actually. thought that if the round can start a little earlier, only 30min is ok...perhaps i'm a little selfish.having contest after having supper isn't a nice thing, right?
Most probably last round before Dhaka site regional ... :)
I really like your contests than others, thanks a lot.
Project presentation tomorrow ... but sereja's rounds have so interesting questions that I can' leave it :)
I have my last presentation for university :3! In 4 hours... Ahh Codeforces habe become a vicious fot me last week xD!
Ого разбалловка уже определена,РЕДКОСТЬ!!!!
и что оно тебе дало?
Последняя задача несколько проще обычного
GooD Luck!!!!!
Damn!! Cannot participate cause of overtime at work.. Anyway, all the very best to everyone.
I took an exception to participate :)
Wow! almost 3 people participated per second! (in the last 3 minutes before end of registration)
GLGL! c:
Каким образом в пятой задаче решение мождно найти в массиве длиной 1 если по условию задачи в массиве должна быть пара чисел x и y x ≠ y?
Там можно задать вопрос жюри. В то же время, сюда такие вопросы во время контеста задавать совершенно ни к чему.
Я не нашёл как задать вопрос жюри, да и времени особо искать сейчас нету — соревнование идёт :)
Прям на главной странице контеста — большая кнопка "задать вопрос"
P.S. А открыть пост и написать коммент время нашлось? :)
Посмотри, внизу есть "Вопросы жюри". Там рядом есть кнопка "Задать вопрос".
Спасибо!
Hey! Your not using PHP 5.4 as you state in FAQ. Array short syntax [] causes compilation error. Update PHP or your docs.
"К сожалению, его реализация алгоритма работает слишком долго, поэтому Сережа обратился к вам за помощью." и сразу появилась легкая неуверенность))
Какие вырожденные случаи существуют в задаче С 2-го дивизиона?
Если длина подстроки меньше трех, то ответ всегда YES.
тьфу... Обидно.. Спасибо..
строка q длиной менее трех символов
А за взлом жюри +100 не дают, да?
Тогда +300, у нас было 3 решения, все упали.
Ага. Картина маслом: у меня -2 по задаче, у тебя -1, у Petr -1, у Dmitry_Egorov -1. Что нужно делать в такой ситуации? Правильно, такого не бывает, жюри где-то лажануло, надо идти решать другие задачи.
Ну я решил, что надо послать жюри клар "проверьте, что у вас не такая вот бага", и пойти решать другие задачки.
Я сделал так же, но жюри мне ответило "нет, у нас нет такой баги" (ну либо я его не понял), поэтому пришлось дальше баги у себя искать :(
Извиняюсь, просто я был уверен, что если 3 решения верны и обсуждены, то все будет хорошо. Не все так хорошо... :(
Можно было написать совершенно тупой брут, который делает то, что описано в условии (;
Ясно. Мне кажется стоит на первые несколько бревен по любой задаче смотреть глазами, благо задач всего 5 в контесте :)
Спасибо за раунд!
Учту :)
+100 к рейтингу:)
а в чем у жюри ошибка была?
Жюри считало, что ответ NO.
для длины 2 неправильно считали.
I spent lots of time trying to use method mentioned here to hack submission 5246996, but failed to generate the anti-hash sequence in time.
Whats wrong with my code (5256546) for 367A - Сережа и алгоритм? I'counting 10e5 steps, but still get time limit exceeded?
Maybe it's because you used "cout" and "scanf". I think I have read one time that "cout and cin" and "printf and scanf" can have problems when used together...
I tried with only cin and cout, and it is accepted: http://codeforces.com/contest/367/submission/5259184
Actually, its because your solution is O(n^2) and not O(n) as it looks. That's because you're calling strlen(s) in the for loop, for each iteration, which is itself O(n). Call strlen once, keep its value in a variable and use it in the for loop.
А на чем B так активно ломали? Неужели антихештест?
Егор у нас ломал, видимо, на этом:
lastIndex = i + (p — 1) * m; // overflow
if (lastIndex >= n) ...
Да, все 3 взлома таким тестом
Блин. На том же упало.
long long index = i + (p-1) * m;Не до конца подумал, что там лонг лонги.
http://pastebin.com/S4zNh4Em
Некоторые зачем-то перемножали p и m. И иногда получался бред.
У меня в комнате было несколько неправильных, которые не проверяли, что q + (m - 1)·p ≤ n и из-за этого слишком часто добавляли в свою структуру элементы массива b, что приводило к TL на тестах с большими m и p.
Сломал восемь решений разными тестами вида:
где вместо ... подставляются числа 90000, 80000, 70000 и 60000, чтобы добиться разных видов переполнения выражений вида
(m - 1) * p. А кто C на чём ломал?С ломали на неправильных формулах.
У меня все взломы на неправильных формулах для минимального размера. Кажется в претестах нет содержательных четных случаев.
Девять на этом же =) n = 110000.
I can not even imagine how author come up these ideas for problems? Sereja Can you please give us some idea about how did you think about setting about these problems, so that it might be good for upcoming setters ??
Если я правильно понял условие, задачу 367D - Сережа и множества мы с vysheng давали уже почти семь лет назад с ограничением m ≤ 26 (задача G). Широко известным бояном она, видимо, не стала.
Интересно, удалось ли мне её после этого сдать :) .
Прикольно, а как ее делать для 26?
Так же, как недавнюю forbidden-words: векторизацией битовых операций, а основные идеи все те же.
А твоя D у меня не прошла :D . Забавно...
Забавно. Я в итоге свёл эту задачу к чему-то, напоминающему твою же, кстати, задачу с последнего ГП СПб (D отсюда).
Задача С очень похожа на А из этой интернет-олимпиады. Правда, там был цикл, а здесь массив, но это мало что меняет.
Тут уж куда сложнее. В моей задаче всего то нужно просто заметить эйлеров граф. Тут же огромнейшая куча гемора, учитывая условие "равные рядом не стоят".
Тем более тут еще и цикл)
Ну на самом деле это условие там никакой роли не играет. А ответ в той задаче был почти такой же как в этой.
Кажется, настало время выполнять обещания =(
Кстати, кто-нибудь может сказать решение В и, по возможности, объяснить, почему следующая стратегия ведёт к ВА 3: Разобьём a на двумерный массив moduls[i][j], где moduls[i][j]=a[p*i+j], а затем отдельно рассмотрим все строки такого массива и найдём все подстроки оных, которые совпадают с b.
у меня такая же идея, претесты прошло. Может у тебя ошибка, в том, что может быть любая перестановка b, а не именно такой же порядок.
UPD: и полные тесты тоже
Хм... Кажется, понял, в чём моя проблема. Я там вёл переменную кол-ва чисел-отклонений от правильного кол-ва и порой увеличивал её в некоторых неоправданных случаях.
ВА3 — это не сортишь ответ
ВАЗ это Жигули :)
It seems that many people got tricked when solving Problem A,Div.2.I got tricked,too.Although I found it in the last few minutes,I still lost a lot of score.I think it's a good lesson for us who want to solve the easy problems as fast as possible.Nice job,Sereja.
Как решить "B" (div 2) ?
Я решил таким образом: pastebin.com/LvYPHfQm
Но у меня превышен time limit на 11 претесте.
Скажите пожалуйста, в чем у меня ошибка?
TL ты поймал из-за того, что для каждого запроса пересчитываешь ответ. Асимптотика решения получается O(n^2). Можно и нужно её улучшить :)
спасибо, т.е. после того как я посчетал ответ для очередного запроса его записать в массив, а потом уже при следующем запросе проверять, нет ли в массиве еще посчитанного варианта?
или как это делается?
Нужно было предпосчитать ответ для каждого i=1..n,чтобы потом отвечать на запросы за O(1); Предпосчитать можно за линию несколькими способами.
Допустим, у нас есть задача, где мы должны быстро отвечать на запросы о сумме на отрезке от l до r. Возьмем наш изначальный массив и на основе него посчитаем новый массив(этот трюк называется префикс — суммы). Пусть этот массив называется sum, а изначальный массив — a. Тогда i-тый элемент в массиве sum равен сумме первых i элементов в массиве a. Обратите внимание, что массив a[] у нас в 0-индексации, а массив сумм в 1-индексации.
Замечательно, sum[1] = a[0], sum[2] = a[0] + a[1], sum[n] = a[0] + a[1] ... + a[n — 1]. Что это нам дает? Пусть нам поступил запрос найти сумму от l до r, тогда ответ — (сумма от 1 до r — сумма до 1 до l — 1).
Теперь подумай, как на основе этого давать ответы на запросы, которые в задаче В.
Can anybody please tell me how he solved problem C div 1? I tried to count what's the minimum required N to use K different values, so I tried to find the maximum K <= M such that the found N is less than or equal to the given N and pick the largest K costs from input, but I couldn't pass pretests.
The idea is just like that ... Seems you have got the implementation wrong.
Thank you!
F(K) is the minimum required N to use K different values. If k%2=1 => f[k]=k*(k-1)/2 + 1. If k%2=0 => f[k]=k*(k-1)/2 + k/2.
What's the proof?
It's about Euler path in Complete Graph. There are K vertices and a edge is a condition, you want to go through all edges. If k%2=1 => k vertices with even degree. If k%2=0 => k vertices with odd degree. You can think about it that way.
During the contest it looked like a Chinese Postman problem in complete graph to me. In Euler Path edges can't be visited more than once, aren't we allowed to do that here (even in optimal solution) ?
If k%2=1, all vertices have even degree so we can go through all edges and finish in start vertice. That's why f[k]=number of edge + 1 in this case. If k%2=0, we have k vertices with odd degree, so just add an edge between 2 vertices have odd degree, we add in total k/2 new edges. After that we can go through all edge but not finish in start vertice (be cause the last edge is the added edge and we already go through the original edge).So F[k]=total number of edge (new edges and original edges) for this case.
Thanks, nice explanation.
What's the source of the problem with problem div1-A? How is it even possible to have the judge solution for the first problem in the contest fail pretests? Have you tested the problemset at all?
I only saw the announcement around ~30 minutes into the contest (since the popup opens in a random open window of CodeForces, not necessarily the one you're looking at), and spent the whole time "debugging" my A. Then at the end I missed the chance to submit D by seconds :(
We had 3 solutions. All of them were wrong :( Sorry for such situation.
Good thing my D TLEs anyway, I guess ;)
Whole time "debugging" your A ???
you submit it after 12 minute :) :)
Yes, and it was correct, but it got WA on pretest 3 then. 3-7 minutes later, the judge solution was corrected, but I only saw the announcement about this (and that my solution now has pretests-passed) 18 minutes later.
why are most of the nowadays contests in Sundays or in Tuesdays? I count and find that there are about five contests in this month that they were in Sunday or Tuesday. Unfortunately I have a class these days and I lost these contests. Is it fair? I wish next contest will not be in Sunday or in Tuesday. I wish ...:) (I want to write this comment before the contest but I arrive home now!)
Problem B in Div 2: The question defines the sequence as "li, li + 1, ..., ln" but shouldn't this be "li, li + 1, ..., n" according to the second explanation which says "a(li), a(li + 1), ..., an" I got a WA because of this since I assumed it was "li, li+1 , ..., ln"...
what a good contest! :D really cool, good problems
Wow, the system judged very fast today.
Ого, обновление рейтинга просто-таки молниеносное.
Integer overflow on Problem B again ARGHHHHH
Finally 3000! :)
Congratulations!
Thank you!
IT'S OVER 3000! (refer to my template:
#define OVER9000 1234567890:D)Yet another CF target is born.
Congratulation for being second CF TARGET !!! :)
Как решалась C (Div2)/A (Div1)?
Предподсчитаем количество букв (суммарное).
Далее, если r-l < 2, то ответ YES, иначе смотрим на кол-во букв на отрезке (разность предподсчета), если разница максимального и минимального больше 1, то NO, иначе YES
Почему строка yyx это YES?
Задача С div2. Тест 3. Строка 2.
Вы смотрите вывод программы, а не ответ.
Хахаха) Спасибо)
Это у тебя нужно спросить, ответ там NO, это твое решение вывело YES
Да-да, серьёзно туплю сегодня:)
What a good problem A! 7 successful hacks!
witua: 2293 -> 2191 (-102), 278 место.
I_love_Tanya_Romanova: 2291 -> 2189 (-102), 479 место.
Как-то мне оно кажется странным. Или так должно быть?
Похоже на искусственное ограничение. Еще пример: poopi: 2217 -> 2115 (-102), 448 место.
Но готов поспорить, что все равно формул нам никто не скажет.
Мне кажется, или имеет место неправильное вычитание? ;)
Very interesting round, waiting for the tutorial..
Happy being blue : ]]
Удивлён, что раунд rated — вроде же аж 15 минут было неправильное решение жюри?..
К сожалению, в последнее время требования к раунду для признания его рейтинговым сильно упали. Постоянно падающий сайт, 15-минутная очередь тестирования, или, как сейчас, неправильное решение жюри одной из задач (а 15 минут — это очень много для старта контеста) уже давно перестали быть поводом для анрейта. Да и TC в последнее время этим периодически грешит.
Thanks Sereja! It's a nice round: Solutions are short and clear. And the overall difficulty is not too low as I thought (Because it has some tricks in implementation, I failed 2 tasks by it.).
Maybe we can have more rounds like this, do you think so?
It is not so easy to make such rounds :) But I will try.
In problem Sereja and Algorithm, here the constrain is "string q, which doesn't equal to either string "zyx", "xzy", "yxz". If q doesn't contain any such subsequence, terminate the algorithm, otherwise go to step 2." But when I see the testcase then I'm confused, because answer is "YES" when q contains such substring like "zyx", "xzy", "yxz". Why? My code is AC after the contest because in contest time I was confused.
А разбор по ссылке найден. Или это только у меня?
Div1-pB is almost as same as IIUPC 2013 pH which occured on contest of UVa Online Judge today!
I got AC on Sereja ans Anagrams with this code: 5261631. Yet, I am getting WA with this 5261332. This two codes are virtually same except for in one I am using
The reason I am getting WA is because the size of mp changes at the end of the process. But it shouldn't since I am not inserting anything after the beginning. Can somebody explain this bizarre situation? It would suck if I ever have to face such situation during contest time!
When you use map[num], it will add new element in map if num isn't already in it (example). So, if array A has some elements that B dosen't have, size of map will be changed.
Run this code. May b this might help you. int main() { map<int,int>M; int sz=M.size(); cout << sz << " " << M.size() << endl; if(M[5]==1)cout << "i m not gonna print" << endl; sz=M.size(); cout << sz << " " << M.size() << endl; return 0; }
This is my submission of Problems B. Div 2
http://codeforces.com/contest/368/submission/5266990
I confused why the output of test 2 was different from it was on my computer and Ideone.com. Any body can help me ? Tks for all :)
I test your code for test 2 it's WA your program give me 3 2 1 also it's basically seem WA can you explain your solution ?
For each l[i], I put a[l[i]] into a Set in C++, and the set only holds distinct numbers, so I simply print the size of this set
In your solution you're only counting the number of different integers amongst alm, alm - 1, ..., al1. Instead, the problem asks you to find the number of distinct numbers amongst ali, ali + 1, ..., an, for each of li.
On a side note, I would discourage the use of preprocessor directives like these:
Essentially, the main goal for the majority of participants here is to improve their problem solving skills. Even if less typing saves an extra 3 minutes per match for you or me, it is somewhat unlikely to make any difference. Rather than that, it's all about learning to find the solutions for increasingly harder problems in increasingly smaller amount of time. And especially if you're only beginning to practice solving programming contests, writing a clear code (without macros) will only help you to maintain a better clarity of mind.
But that's just my own opinion. I realize some people will disagree, and at some skill level this coding "style" may become more useful.
I like these macros and would recommend them. I think the code is much clearer (for the given participant, at least). Also, you'll never make a mistake like:
which is really hard to find (at least, just by looking at the code).
Hi everybody, sorry to bother, but I don't understand why I get different outputs between the online judge and my computer
http://codeforces.com/contest/368/submission/5275044
That's my solution, and it works fine when I try it... but it doesn't seem to work in the online judge... Any ideas? :(
Aren't you going out of bounds with this line, when your loop enters for the 1st time?
arri[i] = arri[i + 1] + 1;
so arri[i + 1] will have some random value in the memory, since you declared the array localy?
I think Problem C from Div2 Has some problems to be fixed ! Or changes which were made during contest are not being reflected in the practice session !!
I think there is some problem with Problem C in DIV2 to be fixed or the changes which were made during contest are not being reflected in here !!
Everything is good with the problem. Just be more careful while reading as statement can be a bit difficult to understand at first. Cost me 5 WAs before finally getting it AC. Hats off to Sereja for the problems though.
I am confused about a testcase given for Div2-C: Sereja and Algorithm.
q=zyxxxxxxyyz (input string) s=zyxx (query substring)
The explanation for the says — "...you can get string "xzyx" on which the algorithm will terminate" However, the problem states that 'zyx' should not be present in the query string.
In fact, the permutation 'zxyx' would be allowed, but not 'xzyx'.
Am I missing something?
Yes, you're making up additional constraints. There is nothing in the problem statement saying that there can't be 'zyx' present in the input string. It only states that 'zyx' won't be rearranged.
Thanks a lot!