Всем привет!
Совсем скоро, 12 января в 19:30 MSK состоится Codeforces Round #223, автором которого являюсь я. Это мой десятый раунд на Codeforces и я надеюсь, что не последний.
Спасибо Геральду Агапову (Gerald) за помощь в подготовке раунда и Марии Беловой (Delinur) за перевод условий на английский.
Настоятельно рекомендую прочитать условия ВСЕХ задач.
Это первый раунд в этом году. Кстати, в прошлом году первый раунд для двух дивизионов тоже был мой(а по статистике +1/-1, оказался самым крутым из тех, что я давал). Надеюсь, что в этот раз задачи окажутся еще более интересными для Вас. Получится ли? Узнаем после окончания раунда :)
Gl & hf ! :)
Разбалловка в обоих дивизионах стандартная.
Sereja, You are savior man, You keep creating good problems regularly :)
Yess! Another Sereja's Round!
9 января в 19:30 MSKПолучится ли? Узнаем после окончания раунда :)Ну как прошло?
Отложили до 12го.
В записи указано 9 января... Чем-то напиминает вечеринку Стивена Хокинга для путешественников во времени.
First Contest of 2014 :) Wish everyone a happy and successful year.. And High rating too :)
Hope it a year, with success, more contests, and faster system test.
According to your first problem in 2014(Sereja and Graph in CodeChef), it is obvious that this contest will be very interesting! :)
Does "Sereja and Graph" interesting problem?)
It was very interesting at least for me. :) It caused me reading some articles and papers and learning new things. :)
could you please tell me something about it when the contest is end?I have no idea how to solve it and got lots of WA.
It does :|
Happy new year to all with this contests.
Sereja u forgot to thank MikeMirzayanov for creating Codeforces. :)
Seems, that everyone knows it :)
*knows
А я каждый твой контест наивно читаю условия ВСЕХ задач, но мне что то не очень это помогает(
Sereja's problems are actually cool( although I only met 2 of them on CodeChef ).I can't wait to see how many AC submissions will fail on "Sereja and graphs" at the end . May it be a great round!
Codechef doesn't work that way. there's no pretests, all tests are system tests. once u get AC, u have solved that problem for sure.
actually, you are not 100% correct. sometimes they update data-set during contest. once i got AC in this problem on January 3, they updated dataset on 6th January. and my code failed, i had to solve that problem again.
But the scores for the 9 non-challenge problems don't change after the end of the contest. That's the point.
A Happy New Year to all, and good luck on the first contest of 2014!
It seems great! This is my first join in the contest of Codeforces Round, I hope I can get good marks~ :>
1st round of 2014, a little late start i think.
Maybe 12th day it's pretty late, but note that there were 3 contests in last week of last year!
Good lucky to everyone!~~
Как только у меня экзамен, модуль/кр, так за день до этого Sereja даёт свой контест((
Как только КФ, так какой-то препод экзамен ставит :(
Я сам школьник, но хотел бы узнать: реально бывает в такое позднее время экзамен?
Экзамен завтра, но ходят слухи, что к нему нужно готовиться сегодня:)
Я вам больше скажу, товарищи. Пару часов назад узнал, что экзамен у меня завтра в 9 утра, а не послезавтра. А приезжаю я завтра в 8.30.
Пожелай мне удачи в бою :)
Really nice New Year's first contest!Good luck to everyone!
In reply to this: http://mirror.codeforces.com/blog/entry/10138#comment-155733 Keep in mind that this will be a historic round, because today for the first time I'll become a yellowcoder from a redcoder :P. But I will try to keep this color :D.
seeing ur previous post, i was like "oh my! what confidence!"
now i am like "not sure if very over-confident, or very under-confident" :D
No,I am kind of saint and I am praying for you that your rating increases today :p
and he didn't make it... top21 and still red
Yesss! 21st place! It looks like my rating will increase even more :D
Impressive work.I've watched you done that twice. Congratulations!
Pretty tight pretests. It seems comparatively there will less hacking this time.
Pretty tight pretests. It seems there will be comparatively less hacking this time.
Как решать С?
Заранее посчитаем для каждой позиции "баланс" (количество "(" левее этой позиции минус количество ")" левее этой позиции). Ответ на отрезке однозначно определяется балансом в начале, балансом в конце, минимальным балансом на отрезке, UPD: и длиной отрезка.
А можно подробнее?
По-моему, в строке "()()()" для подстроки [1,2] и [1,4] все три указанных параметра совпадают, а вот ответы отличаются. Что я не так понял?
Прочитал решение Пети. Еще зависит от длины отрезка.
Так что для примера выше всё норм.
Алгоритмом со стеком найдем для каждой закрывающейся скобки на позиции right парную открывающуюся скобку на позиции left и заполним массив a[left] := right. Теперь в этом массиве нужно отвечать на запросы "на отрезке [L, R] найти количество чисел, меньших R". Это делается деревом отрезков — в каждой вершине нужно хранить все числа на соответствующем отрезке, а при запросе бинарным поиском искать количество нужных чисел.
Жесть. Я свёл к этой же задаче. Только решил попроще scan-line + fenwick tree.
А как это все работает на примере "(())"?
a[1] всегда пустое, так как открывающаяся скобка на позиции 2 всегда ближайшая? Тогда как посчитается ответ для l=1, r=4?
Извиняюсь — я наврал в объяснении. В решении у меня написан стек, а тут написал неправильную жадность:)
Скобки нужно распределять алгоритмом со стеком.
Да ёлки-палки, все поняли, что для закрывающейся открывающуюся. Речь идёт о том, что ближайшую ещё не использованную надо находить, иначе ты для 3 найдёшь 2 и для 4 найдёшь тоже 2.
Я отредактировал коммент, сорри
Можно a[right] = left, и тогда ответ на отрезке [L;R] это количество чисел больших L среди всех, которые левее R. А это равно количеству всех закрывающих скобок левее R минус количество чисел на [0;R] меньших L, т.к. если закрывающая скобка лежит левее L то её пара точно левее. Таким образом надо просто уметь считать сумму на префиксе.
Не совсем же так. Нельзя просто для каждой закрывающейся скобки найти ближайшую открывающуюся, нужно учитывать парность.
Например, для строки "(())" получится массив [undefined, 4, undefined, undefined] и ответ 1, если следовать описанному алгоритму. А вот если разбивать скобки на пары обычным алгоритмом со стеком, то получится правильное решение.
Да. Конечно, надо учитывать парность. Не очень внимательно прочитал и согласился :)
Согласен, я наврал — просто в момент объяснения мне это почему-то показалось эквивалентным.
А я sparse table написал.
У меня такое решение: Для каждой открывающей скобочки найдем следующую за ней закрывающую, пронумеровав их c 1 (обозначим за f(id)). Теперь отвечаем на запрос. Пусть самая левая после L '(' имеет номер s (среди открывающих), самая правая ')' — t (среди закрывающих). Тогда, запустив бинпоиск по ответу, мы проверяем, что существует скобочная последовательность размера X таким образом: f(s) <= t — X + 1 && f(s + 1) <= t — X + 2) && ... (так как всегда нужно брать первые X открывающих и последние X закрывающих). Это запрос на отрезке [s..s+X): (max по i = [0..S) (f(s + i) — i) ) + s <= t — X + 1.
P.s. Ну и разбалловка...
nice contest! thank you Sereja
only 10 successful hacks, of which 7 were on the comparatively difficult problem E.
Sereja, from next time plz try to make hacking more possible, as it is also an important part of contests.
From where can we see all the hacking attempts made in a contest?
u can see all successful hacking attempts in the Status tab, after changing verdict option under the filter to Hacked.
if u want unsuccessful ones also, u can see them in the Hacks tab. but this usually takes a few hours after the round ends to become accessible to all users.
У меня одного решение Div. 1 A на O(nlog2(n)) вышло? =)
у всех по идее. Там либо сложность близкая к линейной, либо на 10м тесте крашится по памяти (если тупо хранить всю сгенерированную последовательность) :P
Ну не знаю, у меня чистый O(nlogn).
А у меня линия. Просто двигаем 2 указателя — один по запросам, а другой по строящейся последовательности.
Красиво. А то я думаю, зачем в возрастающем порядке все дается :)
O(n + m) просто можно.
Ну если уж на то пошло, у меня вообще O(n)
Может O(n+m) все-таки? :)
Ни у одного :)
A contest where faulty point distribution can break one's day, C was solved by 3 times more people than B. Interesting set though.
Maybe C was a well known problem for top coders..
Forgot to delete cerr... Got AC in almost the same code in problem C. I'm going to lose a lot of ratings...
superb speed of system testing today! i think MikeMirzayanov's New Year resolution was to install better testing computers! :D
true... this time system testing was really fast...
and the ratings updated so fast
Спасибо за раунд и отличные задачи!
P.S. Надеюсь поменять цвет :)
NlogN solution for C. Time limit in test case 13 ... , i lost lots of rating points cause of my slow nlogn solution ... pfffff
may be because the author's solution O(n + mlogn)?
Yes my bad...
What does this mean? wrong answer Unexpected EOF in the participants output
Why was E E? OwO
btw very fast system test :)
3 unsuccessful hacks :(
how this code passed test 14 for div2B?
Accessing out-of-bounds arrays in C++ is "undefined behavior", which means anything can happen: the computer might explode, it might corrupt memory, or, in this case, it can appear to work properly. :)
my 3 hacking attempts is about this.
I remember that I got RE in one of the past contests just for 1 more index of array.
I was unlucky at the first contest in new year :(. what will be happen for me??
i think that the algorithm is correct, very strange but correct
did you look at array size of b? it should be at least 10000, see test 14
Привет, див1)
I want to rating under color of my eyes... (red)
Thanks a lot Sereja for another awesome round! :D
I have a problem. I cant'n see the solutions of other participants, neither test cases or hack somebody solution. Because the solution of someone else appears not in other web page, else in the same page, but this not work for me. Mi web browser is Firefox. Even for write this comment I had to use Internet Explorer. What I need to configure in Firefox for that works?
I think you have to install adobe flash player for firefox !
Thanks, but I reset Firefox to it original configuration, and alls works. It seems that some features of firefox like some themes or add-ons were causing troubles.
So easy!