Всем привет!
Скоро, 30 января, 19:30 MSK, состоится очередной Codeforces Round #227 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.
Автором задач являюсь я. Большое спасибо Гере Агапову (Gerald) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.
Главный герой задач этого раунда — кот Георгий.
UPD1: Распределение баллов будет таким: 500, 1000, 1500, 2000, 2500.
UPD2: Соревнование закончилось, поздравляем победителей!
UPD: Разбор на русском
UPD: Статистика
It is Chinese Spring Festival tomorrow- a very large and important event, so Happy Spring Festival to everybody:) Tonight is called Chu Xi in Chinese, means that wait for the coming new year( in lunar calendar), and I hope this contest will make this night better. Good luck to everybody.
边看春晚边比赛Y(^_^)Y
Which means it will be a challenge because of the firecrackers π_π
orzzzzzzzzzzzz literary giant！！！
Happy Chinese New Year, I have received a big red pocket. :)
Sorry, a slip of pen. That is Spring Festival, not Spring Festive.
u don't have to make a new comment for a typo or a grammar mistake. u can click the Edit option on ur old comment and change whatever u want! :)
Yes, thanks for ur notice.
As Chinese people，in this coming New Year's Eve。。。Good luck to everybody
As Chinese people，in this coming New Year's Eve。。。Good luck to everybody
Thank you. I am Vietnamese and I would also like to take this opportunity to wish everyone success for new year.
Happy lunar new year!!! I'll see firework at home and practice this round :))
Today I wish I go to DIV 1 :)
I see you made it... Congratulations :)
Thank you. Now I wish to stay in Div 1, for that I need to practice more!
Китайцы переживают, что в новогоднюю ночь придется помогать коту Георгию, а не Синему Коню -)
шутка года
Ah, the contest will take place at 23:30 in China. That's the Chinese New Year's Eve. And I will come to a new year after I finish my first CodeForces Round. I'd like to share some anecdote with you all. It will be Year of Horse ('马' in Chinese), which has the same pronuciation as Code ('码' in Chinese).What a coincidence! Wish everyone good luck today, especially the chinese coders.
yeeeeeeeeeeees another <3 gridneeeeeev <3 contest
Finally, the main character is a cat! I hope he is fat and orange like Garfield.
No. He is fat, but not orange like Garfield.
We hope problems will be normal ;) ...
Good luck everyone
Registered participants are too many for this contest.(about 3500 till now)
good luck everyone
Когда уже будет динамическая разбалловка?))
Guys, Happy Chinese New Year!!!码年快乐哈。。。。。。
some bugs with hacks . When i press F5 i can hack guys from another room.
when i try to hack it gives Apache Error
i think it should be unrated if it's not only my error
sometimes when i press @hack@ nothing happens
I'm having trouble opening solutions in my room even though I locked both the relevant problems. And sometimes I get redirected to another room (that I'm not in). Has anyone else experienced this?
yes,contest must be unrated!
Thank you for the report. We are investigating the issue. We will do our best to fix it before the next round.
Yes... I faced same problem too... :/
What was "another" room? Was it the 1-st room? Or random? Or not the 1-st but fixed for you?
Room number is shown correct, but users are not. I have seen that room where this user (sayeer_24) was
Very glitchy today! "Room" button does not work very well (puts into random room often) and viewing solutions does not always work even after locking problems.
У меня взломы глючат! не показывается текст кода! UPD англоязычные друзья обогнали((
I don't want to offend anybody (talking about authors of contests), but this round is really interesting. Thanks a lot, gridnevvvit
It's a shame that server problems spoiled an interesting contest. Server was down for much of the contest, room button often redirected into some other room, and hack button rarely worked even if the solutions would finally show up. Very frustrating contest to participate in, but nice problems nonetheless.
кто-то может объяснить второй пример из Е
Удаляем 1: берем подпоследовательность 1 2 3 4 5 6 7 8 9 10, получаем 10 колбасок
Удаляем 3: берем подпоследовательность 3 4 5 6 7 8 9 10, получаем 8 колбасок
Удаляем 5: берем подпоследовательность 5 6 7 8 9 10, получаем 6 колбасок
Удаляем 7: берем подпоследовательность 7 8 9 10, получаем 4 колбаски
Удаляем 9: берем подпоследовательность 9 10, получаем 2 колбаски
суммируем получаем 30.
Надеюсь такие мелочи, как глюки взломов и зависание сервера не повлияют на рейтинговость раунда!
Round duration increased for 10 minutes.can you announce us before 15 minutes say , before the end of the contest , I've really stop coding at last 2 minutes . Very good contest thanks :)Most fun contest i ever participated on CF. Best regards to everybody who helped in creating this round. I think I got the idea at E (after spending 15 minutes to properly understand the statement) — You use anything you want to create a vector prot[i] which tells you whether or not i is protected then you use divide-et-impera solve(a,b) = get the answer for interval [a,b]. You will need quick queries for sum (0/1 if a number has already been eliminated) and minimum value. All these can be acomplished by a segment tree. Didn't have enough time to implement this though. Is this the right solution? Anyway thanks for the round, Gerald, gridnevvvit, Delinur and of course MikeMirzayanov. Keep up the good work!
Is it me or the "room" is buggy today?
On another note: Thanks for the awesome problem set! :)
what a fun bug!! :D
So the winner is vas.and.tor, who made 2 hacks:D
Even I had the same problem. But still managed to hack 1. :D And I had vas.and.tor in my 'buggy' room. But the users he hacked were not shown in that room. What a bug. And regarding ' extended duration' I did not get any notice until after the contest. :( I closed the browser 10 seconds before the end of the competition.
one more great contest, with interesting problems and bugs :)
I managed to make CF show me a standings page full of -1 and -2 where everybody failed all his submissions (even the top 10). A refresh fixed this.
same here in Friends standings
This was happening throughout entire systests. It was a pleasant surprise to see myself in 20th position, but it was quickly revealed to be only a dream :(
Кто решил задачу D, подскажите, пожалуйста, как удалять дуги оптимальным путем?
Хороший контест,спасибо автору!)
As Chinese people，Good luck to everybody。
Да, раунд был классный! Но в задаче Е была маленькая опечатка: кота назвали Григорий в последних абзацах, а не Георгием)) А вообще, спасибо автору!
Спасибо. Да, есть такое. Я сам часто путаю эти имена. Сам иногда называю кота Григорием
Да не за что) И да, все мы люди, все можем ошибаться.
This was a nice round. I especially enjoyed solving E. Keep up the good work !
Хороший набор задач. Мог прорешать гораздо лучше (долго тупил над задачей С, хорошо, что сдал). Спасибо всем, кто готовил раунд.
Can someone please explain the main idea behind problem D? Thank you! I tried to fix my center, delete it from the graph and then see what the solution is (this is the problematic part — I was thinking about maxflow, but n is too large).
The same problem. I think we have to check all vertexes as center and choose the best. But how delete arcs in optimal way?
You should use biparate matching on the graph, where left side is outdegree of vertex, right side is indegree of vertex.
But how to decision which arc delete? If we have 2 indifferent variants?
We will delete all arcs, except that arcs, which is in maximal biparate matching.
Thank you. I have understood.
I didn't understand, Can you please explain it more ?
No, n is not too large at all.
Maxflow algorithm's (good implemented for biparate matching) complexity is O(FLOW * (N + E)) , E is number of edges here. FLOW's limit is N so overall complexity O(N * E).
Не получилось написать раунд. А вот интересно: в D зайдет n запусков Куна для всех возможных центров?
Конечно. Это O(n^2m) по ассимптотике.
Да я понимаю. Ну вот как-то показалось многовато.
Примерно 2 * 108 уже давно не многовато. А учитывая, что это все таки Кун, то меньше будет.
Ну поэтому я эту версию и рассматривал:) Спасибо, классная задача!
How to solve E?
First, a slow (but useful) solution:
In one step, we can remove the minimum of an interval. That means the smallest number (overall) will be removed whenever it's inside the interval picked. If it's supposed to stay, it's clear that we can't ever include it in our interval, and we can just consider our algorithm running on the parts of the original array to the left and right of it.
Otherwise, we have to pick it eventually. If we pick it in the k-th operation, we can get a larger answer just by picking swapping the k-th and k - 1-st operation (think why it works), which means we should pick it in the first operation. And why not with as large w as possible — picking the whole array. Further in the algorithm, we just operate on the same subarray without the deleted element, without doing any splitting (like above).
The slow (O(N2)) solution would now be simulating this algorithm. We can do better, though: we can see that it's all right to remove numbers in increasing order (the order among 2 distinct parts of the array doesn't matter), and we know how much the optimal solution will cost: the number of elements in the subarray on which we're running the algorithm, which haven't been deleted yet.
Splitting subarrays into even smaller parts and checking which one the current element belongs to can be implemented with map<>, counting deleted elements with a Fenwick tree. The implementation is just straightforward now. Complexity:
.
Failed submission:5850238 Time: 2000 ms (MS C++)
Accepted submission:5850920 Time : 872 ms ( GNU C++ )
It shows that
ios::sync_with_stdio(false)inGNU C++does a Miracle!!!!Yes. Input is very large to read input with cin
Having it in your template is a good idea...
rating change reverted after some time... anyone else experiencing it ?
Looks like I'm still blue even though I'm over 1700.
I'm also still green although I'm over 1500. I imagine this is just a small lag between rating change and color change and should be resolved soon though.
The problem is that I oscilate between the 2 colors.
Finally reached blue ^_^ !!
Better than nothing: http://translate.google.com/translate?hl=ro&sl=ru&tl=en&u=http%3A%2F%2Fcodeforces.com%2Fblog%2Fentry%2F10583
Violet "Candidate Master" and blue "amirMD" (1741) ! :D
Sorto supposedly solved C in 3 minutes, has different code templates in his solutions and even different tab settings. And yet he is allowed to take first place.
Also after solving D, submited E in 2 minutes which has just a bug : 5843619.
He have to explain this situation i think...
Can't find what's wrong, with this code: 5847679.Can someone help me?
try with 120200 correct o/p — 1
And other stuff
For the problem B:
10010111
Can somebody tell me how to merge 100,10,1,1,1 into 10010111 ?
I try but fail.
So I think this data's answer is 4 ..
Sorry, problem C..
I have tested some Accepted code,all their answers are 5.
I got confused now.
After test data '111',I believe the system test data is not strong enough.
You can do it with this operations (I hope my notation is clear):
100 + 10 -> 10010, 1, 1, 1
10010 + 1 -> 100101, 1, 1
100101 + 1 -> 1001011, 1
1001011 + 1 -> 10010111
Sorry,I misunderstand the Description。。 thanks ：）
{100, 10, 1, 1, 1} → {1, 1, 1, 10010} → {1, 1, 100101} → {1, 1001011} → {10010111}
Oh.sorry,I mistake 'i!=j' to 'i<j',thanks ^-^