Всем привет!
Авторы сегодняшнего раунда — craus и dalex. Мы не могли просто так пропустить раунд с таким красивым номером, поэтому в 19.30 MSK вам придется решать задачи, которые Павел для вас придумал, а я подготовил.
Благодарим Gerald и Delinur за помощь в подготовке соревнования и MikeMirzayanov за то, что у нас есть Codeforces.
Систему подсчета баллов и их распределение вы узнаете вместе с началом раунда. Все равно эта информация не несет особого смысла, пока контест не начался.
Полных решений и успешных взломов!
UPD. Контест завершился, поздравляем победителей!
Div. 1:
1. Petr
2. tourist
3. Egor
Div. 2:
1. k3e18
2. tongcx1988
3. LeMieux
UPD. 2 Опубликован разбор задач.
Does that mean there will be some problems have tricks, and there will be a chance to hack for getting higher scores?:D
That was a great contest! Good problems! New ideas!
Thank You!
Удачи всем!
"Scoring system and score distribution will be published when the round starts. Anyway this information makes no sense unless the round begins."
lol, I guess the setters are fed up with comments like "Only 10min/5min/30sec left before contest and there is still no updates!!"
Ждём раундов с "Систему подсчета баллов и их распределение вы узнаете вместе с концом раунда. Все равно эта информация не несет особого смысла, пока контест не закончился." :D
Best wishes to every one!!
Don' t have time to take part, what a pity. Anyway, wish everyone a high rating [By the way, this is the 222ed round, so I guess there will be some prblems about twos. So try to search for some information ~ . Well,just kidding ]:):)
Keep in mind that this will be a historic round, because today for the first time I'll become a redcoder :P.
Aha, Good luck to you. I'll pay attention to your performance on this round. :D
may the (code)force be with you ;)
I hate starwars.
You Sith !!
Now I hate it more!
Good Luck Swistakk:) May God with you today :)
Congratulations =)
Did it :D!
Wow... Congrats! You barely made it, but I would like to have your confidence. Because I have lost it competing here :D
congratulation :D Swistakk
By 1 point :D Happy New Year :)
Congratulations!!!
Astonishedseeing your confidence !!!! Great !!! :)and you really made it!!! congratulations man :)
challenge succeed!!!.... what a confidence!!! congratulation....
Всем удачи! Желаю всем проводить 2013 год хорошим кодом на последнем рейтинговом раунде!
А Good Bye — что за турнир?
Я просто не знаю, что за турнир Good Bye. Он не обсчитывается?
Скорее всего будет нерейтинговым. Обычно рейтинговые только "Codeforces Round ..."
Например, ABBYY CUP или КРОК были рейтинговыми. Если он будет проходить по нормалньым правилам, а не как, например, Unknown Language Round, то скорее всего будет рейтинговым.
You can't wish us accepted solutions and successful hacks! That's a paradox. :D
Or maybe after we get hacked a few times we'll finally reach the good solution / program?
thats always the case with wishing 'high ratings' also as it is designed in such a way that if one gains someone else loses.
Please vote "I like it".
Is this the new trend or something? Seems like there is always somebody asking for upvote or downvote in every contest. I am kind of curious now to see how long this will continue :p
I did not read related comments before, therefore I do not know that others ask for up-vote or down-vote. Just do it for fun, nothing more.
Yep. Good luck to me and everyone else ~
We wish you accepted solutions and
successful hacks!(Y)
"Костя — профессиональный киберспортсмен, специализирующийся на дисциплине Dota 2"
а, как сказал?
What's the idea behind putting STRONG pretests?! Hacking is almost impossible!
Well, when hacking is "I know one tricky case, and I'll check if all solutions works on it" It's not very interesting too.
Pretests aren't strong today BTW at least in Div1.C. My solution is absolutely wrong but passed them.
Well, it's not even like this. Even the extreme cases (big input) were present in the pretests! Some people in div2 got TLE because their algorithms were not to run in time under the problem constraints, I'm amazed that such cases were included in the pretests!
Possible, in Div2 A, there is no test when a = b ;)
I hacked three submissions with a==b test. ^_^ .. Happy today.
Maybe they wanted to make a more classic contest, but Codeforces is neither a classic type of contest nor an ACM type. So there is no point in very strong pretests. Problem C on Div2 could have had some cases not included in the pretests (like the case with all the matrix full, when the DFS should not be called at all).
I didn't use dfs at all, my solution is kLogn + kLogm using segment tree, some people used sqrt segmentation.
PS: failed sys test
Увидев авторов, сразу подумал — хотя бы одна задача про Доту будет :)
Хм... С действительно проще В или сейчас она полетит на систестах?..
Ну, если маски какие-то перебирать, то должно быть нормально. Если считать, что надо банить лучшего — неверно. Да и всё-таки B сдали больше же.
Ну я банил не лучшего вообще, но лучшего из тех, что останутся оппоненту к его следующему пику (или к концу очереди действий) с учётом того, сколько до этого будет банов у оппонента и сколько пиков ещё будет у нас.
Претесты прошло по крайней мере Оо
Тут нужно банить 99. (нули запрещены, но можно добавить ко всем 1)
И тут я понял, что сейчас ну ооочень много решений посыпется.
Ну янаписал это, потом понял, что трешак, решил, что не придумаю нормального и пошел ломать. Только 1 такого заметил в комнате:(
Действительно. Печально =(
It's fun to see a problem about Dota 2 :P
"C" решалась кучей, в которой храним пару <количество_свободных_соседей, номер_вершины> и на каждом шаге зачеркиваем клетку с наименьшим кол-вом свободных соседей или как-то иначе?
пишем bfs или dfs. Зачеркиваем вершины, которые позже всего посетили.
А стартуем с какой клетки? С любой?
да.
Считаем сколько клеток должно остаться в ответе — k. Пишем bfs/dfs из любой клетки с точкой на k шагов, все остальные клетки с точкой помечаем как X.
Можно ещё выбрать любые связные s-k вершин и зачеркнуть все остальные.
Это делается всё тем же dfs/bfs из любой клетки, да?
Да.
Считаем сколько пустых клеток изначально (пусть t) Забиваем все пустые клетки липовыми стенами и ломаем t-k рядом-стоящих липовых стен
the second last codeforces round of this year and nice one..
Just got a popup message there is another round on 30th, which will be rated for both Divisions
Incredibly simple A (and impossible to hack as I've seen), simple DFS on C, hard to understand the statement on B (the explained sample though saved the day), not so hard solution (here the intuition on why it works was more important than the proof itself). Nice round for the 2nd last contest of this year. "Authors of today's round are craus and dalex" — keep up the good work.
Three succesful hacks on A. :P
Well, at least in my room, most solutions to A had the case a==b included in them (I tried at least 10 submissions).
I was able to hack on A LOL :D
In Div2 B, I forgot to make size of my array which contains merged a and b to 2 * 105. Instead the size was 105. I wonder, will it fail or not? :|
Probably it will fail, but, as all of us know, everything is possible. Tell us if it failed or not.
I tested my code on "custom test". I thought it would get AC or RTE but not WA. As in "custom test" there were no RTE, I gave up resubmitting. And now I got WA 37. :)
FAILED T_T
Забавный раунд. Я бы оценил все три из B, C и D по сложности как C.
А в D есть какая-то халява? Я ее не решил, то, что после раунда рассказал Петр тоже халявой не выглядит...
События + дерево отрезков для максимума, в котором надо делать операции плюс-минус на отрезке
Ну, халява уровня C точно.
Давай предположим, что самый хреновый чувак имеет уровень x, самый крутой — уровень y. Когда мы знаем точное значение пары (x, y), мы можем однозначно восстановить ответ: это количество таких i, что L[i] ≤ x ≤ V[i] ≤ y ≤ R[i]. Давай обозначим это количество как ans(x, y).
Давай уменьшать значение x сверху вниз, поддерживая при этом дерево отрезков, в котором в ячейке y держится число, равное ans(x, y). Какие бывают события?
Во-первых, у нас чувак может влезть в допустимые, т. е. когда V[i] = x, мы начиная с этого момента, можем чувака добавить в множество. Более конкретно, мы можем добавить в множество его только если V[i] ≤ y ≤ R[i], значит к ответам на отрезке [V[i], R[i]] надо прибавить 1.
Во-вторых, у нас чувак может стать слишком крутым для нашего множества (в предположении, что у нас действительно окажется чувак уровня x или ниже!). Это происходит, когда x = L[i] - 1. Тогда мы должны откатить его вклад в ответ, то есть уменьшить на 1 в дереве отрезков на отрезке [V[i], R[i]].
Так как в любой момент времени у нас поддерживается актуальная структура данных с ans(x, y), то ответ это тупо максимум по всевозможным значениям максимума дерева отрезков (т. е. значения корня). Ответ восстанавливается нетрудно по такому решению.
Ну да, но я бы не стал сравнивать это с тупой динамикой за O(n22n) (которую да, пришлось из рекурсии развернуть в прямую)
Ну может быть. Кстати, посоны говорят, что она на самом деле за O(n2n), потому что всегда выгодно кого-нибудь да банить, а значит каждая маска имеет смысл только на одном уровне. Но я тоже до этого не допёр.
Кстати, почему O(n2·2n)? O(n·2n) же..
UPD: Это так, потому что не банить никого равносильно забанить самого трешового
I am interested is problem D Solvable by (Binay Search of Answer)+(Data structure)?
Let's find the amount of days we need to fix bugs with binary search. Now, let's check that k days is enough to do it. First of all sort the bugs. Then iterate through them and for each of them find a student with the minimal c that can fix(b >= a[i]) the bug using set<pair<int,int> >. And he also will fix next k — 1 bugs. If every time we have a student to do it(set is not empty) and the sum of all c is less or equals to s then we can do it. P.S for some reason my solution gets TLE on 9 test :(
Как надо было решать В,С?
С решаем так:
нам нужны только m самых сильных героев
забить на пропуски хода, никогда их не будем делать
динамика по маске, которая означает свободных на данный момент героев
переходы: либо баним кого-нибудь, либо берем в команду к себе
B: сперва бинпоиск. Как проверить, можно ли за m дней? Перебираем блоками по M заданий, начиная со сложных. Берем каждый раз самого дешевого чувака, который может их все сделать.
Код
can't submit in the last 10s ? I submit my solution in the last 10s,but failed to submit
Wow! Amazing strong-willed victory by Petr!
Congratulations :)
Failed Div2 Problem D because my program output N0 instead of NO ...
In Div 2 A all different possible test cases is 6*6 = 36 but there is 38 test cases LOL :)
Thank you for the nice contest! I've enjoyed it :). By the way, I got RE on problem B div1. But I've correct output at CF server (and on my local machine), and I can't see why it got RE. Can somebody tell me what I've done?
My submission is here. => http://mirror.codeforces.com/contest/377/submission/5561801
(UPD) I've submitted same code at practice, and got AC. http://mirror.codeforces.com/contest/377/submission/5562952
It seems to depends on the version of glibc.
Using glibc with version 2.15, I got RE.
I hope this information is useful.
Using the GNU C++ library debug mode, I get
/usr/include/c++/4.8.2/bits/stl_queue.h:483:error: attempt to access an element in an empty container. Objects involved in the operation: sequence "this" @ 0x0xffd9f148 { type = St14priority_queueISt4pairIiiENSt7__debug6vectorIS1_SaIS1_EEESt7greaterIS1_EE; }on that test, which means that you attempt to access an empty priority queue.
It seems you had undefined behavior as mentioned by andreyv. But New Year will be soon, so it's time for miracles. Usually I do not do it, I rejudged your solution and got OK. Ratings will be updated soon. Happy New Year!
To : numa and andreyv
Thank you for investigating environments and my code! I'll be careful from now on. I'm glad to know the reasons :).
To : MikeMirzayanov
Thanks for the rejudging! It seems that I was very lucky!
And again, thanks for all whom tried to help me, and craus and dalex for helding a wonderful contest. Happy New Year for all!
Very Fast system test. Loved it :)
Таргет =) Спасибо авторам за раунд!
Why am I Expert with rating 1703 !?
and I am Specialist with 1501!
And I am Pupil with rating 1504 !!
Thanks :D...I do on ideone without making it private.Have to take care from next time :(
Maybe your solution and another one's solution were same.
Div. 1
Div. 2
More info
Hi If you visit my profile, KiAsaGibona my rating is 1504. And when I take my mouse at the graph, it says EXPERT , But I am still Pupil . As far I know 1501-1700 is Expert range. But I am 1504 and still Pupil . I want to be blue :( :(
I saw this bug in other profiles too. I think it will be fixed soon.
Its not a bug. Let the system alone it is working hard coloring coders :D
Let's hope so, As I am going to be Blue for first time. Yayyy :)
[1500,1699] is Expert range not [1501,1700] . :)
I have the same problem. My rating has changed BUT the title and color is still NOT updated yet... Hope someone could help? Thanks!
У tourist второе место и плюс 0 к рейтингу. Хорошо, что не упал :)
I took part in this contest but my rating hasn't changed (I submitted for problem A, div 2). I noticed that the ratings of other Div 2 participants has changed, but mine not. Could someone tell me why this happened?
Same here. For a moment, I thought that my rating remained constant, which is rare :P
Are you sure you registered for the contest?
I'm sure. the submission during the contest: http://mirror.codeforces.com/contest/378/submission/5553767
and the registered participants: http://mirror.codeforces.com/contestRegistrants/378/page/10?order=BY_RATING_DESC #2316
My rating didn't change too
My rating is the same
Не знаю, баг это, или фича, но у меня уже более месяца висит оптимистично-удручающее сообщение "Да! У вас +100500 к рейтингу!", хотя я уже пару контестов после этого слила...
Можно это как то убрать?
Эм, прочитать его? У меня оно пропало после того как я открыл это сообщение.
Таки да, помогло)
Спасибо)
Can someone explain why DFS works for Div2 C?
flood fill s-k cells, that will remain empty. Mark the rest as 'X'.
@dbaluta As given graph is connected & consists of s empty cells, so, Run DFS from any empty cells & mark only (s-k) cells visited. Then, simply print the solution writing empty unmarked cell X . Thats all :)
For any cell, i can delete it if i am sure it won't block the path to any other "not deleted" node.
So from every cell (x) ,we run dfs to delete cells reachable from (x).
After deleting them, if i want to delete more cells, then it is safe to delete cell (x).
--> Consider all the blocks where you have '.' as nodes..
--> Now as you can read in the problem description , all the '.' are initially connected..
--> So now you have a connected component with you..
--> You have to now turn K '.' cells into WALL so that the component is still CONNECTED..
--> Now , the Picture of DFS comes into the mind.. DFS will traverse all the nodes and will backtrack as soon as it reaches 'LEAF' node.. If you turn those leaf nodes into WALL your graph will still be a connected one!!
Hope it helped!! :-)
Thanks a lot guys! Now is all clear :).
i got wa on test 89 :( I had done bfs and marked levels.Then removed k nodes which have the highest levels.
Actually BFS should work : 5554249
почему у див.2 у второй половины до сих пор не обновился рейтинг?
Now tourist really have to be ranked FIRST if he wants to increase his rating :o
Думаю он может подняться со 2, если первым будет rng (судя по тому как считается рейтинг)
if his rank will be 2,and rng_58 rank 1,his rating will increase ;)
See these solutions : 5560186 5560332
Hey my raiting chnged to 1501 but y i am still graded as pupil?
did they made the contest unrated or what ? why are the ratings constant ?
As noone has already done it, I will present solution to Div1 C, because in my opinion it is pretty funny and short.
We just have to completely forget about n-m weakest heros and bruteforce remaining ones in O(2^m * m) using simple dp on masks. Why it is correct?
In short, if we pick — we pick strongest one and if we ban a "bad" hero it doesn't matter which one (from the "bad" ones) we ban. It is obvious that if someone have to pick a hero, the best choice is to pick the strongest hero from remaining ones. So in a fixed moment of the game, if players will have to make k decisions, all picks will be among k actual best heros. Let us call that other heros are bad. Bad heros will never be picked. Since that, there is no point in missing a ban, because we can ban the weakest from remaining heros and that won't affect our solution, because noone will ever want to pick it. So if we consider an optimal sequence S1 of decisions for both players we can create another sequence S2 which will be still optimal for both players and chooses heros only from those m strongest ones. If there occurs missing a ban or banning a hero which can't be banned in S2, we ban the weakest remaining hero in S2 and there is no difference between those 2 choices in future picks, so these two states are equivalent.
Learn Russian, there are lots of comments with discussions of solutions after each round in our language =)
If I'm not mistaken E is fairly easy. I will describe a solution with assumption that everything is continuous, not like in the problem statement (it's essentially the same problem, but easier to describe). Think about a whole process in a coordinate system OX — time axis and OY — cookies axis. Firstly sort buildings due to cookies per second (= possible slopes of our cookie graph) and process them in this order. After adding each building we want to maintain a graph of "maximum number of cookies we can achieve in a time t" — this graph consists of consecutive segments of lines with ascending slopes. It can be kept in a vector. When adding a building, we have to find first moment T (by binary search) when we can afford building it and update our graph (that means, finding an intersection of our graph and line passing through (T, 0) with slope corresponding to this building production. Just pop a few last elements of vector and push_back a new one. If we won't process buildings b such that there exists a building c such that c is cheaper and has bigger production, we can achieve O(n) time not O(n log n) by omiting binary search.
This is convex hull optimization right? I didn't do contest because it was too late and I was tired, but I looked at questions and that is what I thought, but I wasn't sure because it was E and I thought it must be more complicated :P
Edit: Actually I think I was wrong.
Can anyone explain me how to solve Div2 C/Div1 A?
Can any one tell me about Good Bye — 2013 contest in detail? :)
Well , my solution in Div2C is based on BFS , then there has a BFS tree when we run BFS then we can disconect their leaves( this are the nodes more farthest) .
My submission. Code
please can any one explain how good bye round will be for both divisions !? and how the rating system will be ?
You can see here :)
Wow, Zlobober became the new International Grandmaster, Congratulations! :)
How do you solve Div 1 Developing Game?
I think there is a much simpler Greedy solution to Div 2 C. For each row note the number of empty cells in that row. Now if we have to delete k of the cells then we can completely convert the initial rows to X,such that the no of cells left in the row (which u have just processed ) is more than the number of cells left to convert to X. Now if there are some cells still left to convert ,except the cells which are connected to the row just immediately down u can convert into X. This algo works since when we convert entire intial rows to X the remaining is still connected.
In the problem B div 1, can anyone tell me why my JAVA solution got TLE (I do it in O(nlogn^2) : (.
(http://mirror.codeforces.com/contest/377/submission/5559914)
After the contest, I tried to rewrite it in C++ and got AC in 156 ms : (
Try to use classes with ints instead of Pairs of Integers and PriorityQueue instead of TreeSet.
Thanks, I tried to use classes with ints instead of Pairs of Integers and got Accepted @_@.
The objected data is so slow @_@
Screencast
I think the test data of Div.1 E (Cookie Clicker) is not so strong for a Div.1 E problem. A simple O(n2) solution passes all the tests. In 5604868 I just deleted all the buildings which cannot be used in the optimal answer, using the method mentioned on the top of the editorial, and then used simple O(n2) dynamic programming.
Thank you! It seems that in random tests this condition:
if(a[q[qe-1]].v<a[i].v)is false very often.You have TL now.
I've rejudged all accepted solutions that were submitted after the contest. Contest submissions are OK.