Привет всем!
Сегодня состоится Codeforces Round #276, который пройдёт в обоих дивизионах. Время старта — 19:30 по московскому времени (перейдите по ссылке для просмотра времени в других регионах). За помощь в подготовке контеста спасибо Zlobober, за перевод на английский спасибо Delinur, и спасибо MikeMirzayanov за сам проект Codeforces.
Желаю всем удачи, надеюсь, вам понравятся задачи :)
UPD Разбалловка в обоих дивизионах будет динамическая (подробнее об этом можно почитать здесь). Задачи будут упорядочены по возрастанию сложности, тем не менее, не забудьте прочитать все задачи до конца контеста.
UPD Контест окончен! Спасибо всем, кто решал задачи несмотря ни на что. Разбор будет опубликован позднее.
UPD Разбор можно найти здесь. На моё удивление задача div1C оказалась довольно сложной и по количеству посылок сравнялась с div1E, а во втором дивизионе эту задачу вообще никто не сдал за время контеста. Удачи вам в покорении разбора :)
Please short explanation for problems. --> Because read story of problems is too tedious.
Also explanation of sample tests. For better understand problems.
" THANKS FOR READING
Блин , время стандарта изменилась для нас ( Россия же перешла на зимнее время ) :(
Please give me '-' till my contribution reaches 0 and then stop.
Now I know the reason behind late , Bug oversolver
1 hour later is not good for me
Daylight saving time.
I am new to code forces.What is div 1 and div 2 in round #276?I could not register in div 1 so have registered in div 2 .May i know how div 1 and div 2 users are distinguished
Div 1 users must have more than 1700 points
or equal to 1700
MikeMirzayanov's post on Rating System: http://mirror.codeforces.com/blog/entry/102
Div1 is more advanced level than div2
Думал написать контест вместо лекции, а ее отменили:( Как думаете, писать теперь или нет?
Думал написать контест вместо лекции и отменил её.
your last contest(#256) has nice problem.thanks~
What's a good tool to visualise the call graph of my code as it solves a sample test case? And that won't take much time overhead to use during a contest? (For Python or C++.)
so for simple:
you want to see what?
?
In Visual Studio you can see good visualisation (screenshot is in previous edit) Is it what you want?
I cannot see the screenshot (in Rev. 1)...
Something like that. But also a bit different: it should be a graphic so I can take one look at it and know what went wrong. I think I'll have to write my own. It would be easy to parse the output such as what appears in your screenshot or of a profiler for either Python or C++.
Hope short and simple problem description just like the announcement :)
Very bad time for Asian participants
What time it is for you? Because in Europe (let say Central Europe) time was not changed, probably because of summer time...
You are right...It's 0:20 AM in China...
Not in Iran ( 8:00 PM ) :D
Куда ушел Gerald?
not able to wait..
1 hour later is very bad for China. It is 0:30 for us, what a sad story!
I have to move to China, quite good time for me...
And it is 1:30 for Japanese...
It was 3:30am here when the contest started. These coding events remind me how much I like to work in the peace of the night.
I hata the start time, it's too late in our country
Ненавижу voting-систему codeforces, точнее голосующих. И пофиг, что меня заминусуют.
Если фото не загружается
Слабые, зависимые от чужого авторитета личности смотрят исключительно на цвет пишущего. Вот это скорее всего заминусуют:)
I'm Unlucky in dynamic score :(
Please unlike me :) Plz
As you wish
I am always curious to know why do the authors declare the score distributions at the last moments. Has it anything to do with the number of registrants??
I am always curious to know why do the participants care about score distribution before the last moments
Hope to see a nice problem-set and +ve rating growth.. Dynamic-Scoring has always haunted me :P
Server is too busy and can't open any of the problems, is it only me?
Nope.
The server is very busy, it's impossible to submit or even access to the statements !
Server is stuck (
As always when contest is running and lot of participants...
me too
I don't know what happened, but there are more than 1000 submissions waiting for judging.
Nice problems but server is always busy!!! I submitted the code for A-Bits 10 minutes ago and it's still in queue
Nice problems but server is always busy!!! I submitted the code for A-Bits 10 minutes ago and it's still in queue
I can't send any problem. Is the round going to be rated?
Is it rated today?
In my opinion, it shouldn't be...
In queue
It's 11 p.m. I tired to wait. And I'm going to sleep.
Nice set of problems, but the system is making it almost impossible to compete.
Agreed, the last 3 problems look equally challenging.
Yes. 30 minutes to send the solution, waiting the submit page opens..
Good short statements ;)
It's a bit frustating to have busy server when contest are going. Hope for extra time, and fixed system soon.
seems round will be unrated ;( ... anyway, keep solving!
Раунд будет нерейтинговым ??????
unrated :)
"This round will be unrated due to technical issues."
if contest rated , I will up rating, but it is unrated. I am very sad !
How about providing the problems in pdf, as in the gym, along with the online version, so that if server is getting overloaded then people can do with them (download that file initially as a back up)
Open all the problems as soon as the contest starts.. Works for me everytime..
After the contest started I thought, "Awesome problems, awesome statements. I really hope I everything goes well today! :)" An hour later... "Long queue, contest is unrated for technical issues". Now I'm thinking, "Why did I have to jinx it?! :(("
this round is like BAYAN contest ... great problemset but ...
And a buggy round by oversolver :(
Waited long for a DIV2 round and got this :/
I don't think that it's oversolver's fault
No, but the irony in his handle :D
I know it's more like a server fault. But I noticed that Div2A points were changed twice. First it was rated 1000, then 500 and now 1000 again. So, I do suspect that some way or the other, oversolver is at fault, if not majorly.
Update: It's 500 point problem again.
The points are changing only because the score distribution is dynamic. If C is solved by many people by the end of the round, it will probably bring only 500 points.
I know its dynamic. The guy in the top of my room had 900+ point in problem A. Now he has 480 points. The score of an individual changes after correct submission too? I'm sorry, I didnt knew about it.
I don't think you know the correct meaning of dynamic scoring. The scores change based on the number of correct submissions on a problem. The lower correct solutions, the harder the problem is thus higher the score and vice versa.
this is normal to happen in dynamic score, first the score is 1000 then more people solved the problem makes it 500 then more people make wrong submission as a first submission(or solved another problem) which increase number of participants making the points of the problem back to 1000
Oh thanks. I didnt knew about it. I take my criticism back :P
In Soviet Codeforces, you can't take it back.
Aren't you aware of the Russian proverb: "a word ain't a sparrow: once released — it can't be recaptured"!
Such a pain, when there's finally div1 contest where you can participate... and clar says it's unrated :'(
del, всё ясно.
Надеюсь, больше не будет комментариев от тебя.
oversolver, все отлично, задачи классные.
If only I can punch person to death I will punch myself. Such a waste of precious sleeptime.
Стоило Fefer_Ivan уволиться — тут же раунд нерейтинговый. Подозрительно.:)
Дуров, верни Фефера!
Говно контест..... жалко(((((
убейся
Не офигел? Умный что ли?
что-то ты плохо старался
Говорит человек, который не сделал ни одного сабмита в контесте
при чем здесь вообще сабмиты в контесте? вы глупый?
плохо убивался он, говорю
Сколько еще должно пройти таких нерейтинговых раундов из-за сбоев, чтобы можно было перестать обновлять страницу каждую минуту? Когда Codeforces перестанет тормозить, это далеко не самый высоконагруженный в интернете сайт? :\
Я уже тут полгода, и до сих пор сайт не застрахован от наплыва каких-то пяти тысяч человек, его же можно тупо заддосить посещением на контесте!
Не жалко времени было создавать аккаунт для примитивного троллинга? Уходи в свои раковальни, или хотя бы друзей в реале найди
ПОТРАЧЕНО
Она со мной, углепластик, так охладите сервер, я рассматриваю ее пользу!
Лично мое мнение..вам, товарищи, нужно вообще-то радоваться,что кф вообще существует, засирать любой горазд!
contest is unrated . . . keep calm and . . start self mutilation. . . :-"
Solves div2 C in 5 minutes -> unrated round.
Tough luck =(
Is anyone having trouble locking problems? i want to try to hack some solutions, but i can't seem to find the button to lock a problem.
Раунд нереитинговый
правда?
Well, I decided to improve my ranking. Not destiny :)
5th November of 2k14... the day that Codeforces died...
http://i.imgur.com/LN2DJZV.png
"Remember, remember, the fifth of November" Codeforces Edition
Keep calm friends. I know codeforces is not doing well today, but instead of backfiring at it why dont you try to solve the problems, or even go to sleep, than blaming contest writers, platform etc. Remember, the joys the platform has given you, the job you got by practicing at this platform, the money, fame so many things. And one day it is bad and you show this attitude towards it. I am sorry If I sound harsh, but it preety much shows people's character.
It was just a joke m80 (matey)
It was not directed particularly to you mate, but to all such comments above.
Somehow it reminds me about Black Day of Codeforces
Ow God knows when the next contest will be ... :(
In 5 days actually: http://mirror.codeforces.com/contests/486
And in 2 weeks for Div 1: http://mirror.codeforces.com/contests/487
ridam to contest :) tnx
Remember, remember the fifth of November, the Gunpowder treason and plot; I know of no reason why the Gunpowder treason should ever be forgot!
I guess Codeforces system blew up in the spirit of Guy Fawkes Day!
But in serious matter, there were 5000+ competitors and this is the 276th round. One would expect the system to be more stable by now. I personally feel sad for oversolver because that was one good problemset and I think he deserves some credit and I'm quite sure that it wasn't his fault at all. And about changing problem scores mentioned above, scores are dynamic, of course they will change!
Well, anyway I liked the problems so thanks for the good problemset :)
it is my worst contests always "Busy Server" or "in queue"
I`m so sorry but I have to give up this contest for many reasons:-( Expecting next competition ! :)
http://hsin.hr/coci/contest1_tasks.pdf 2 задача и B задача этого контеста, ухх
Мда... Его (автора) посодют, а ты не воруй!
Is hacking disabled due to the contest being unrated? I cannot lock my problems
There are still 40 minutes remaining, but I'm very sleepy. I will sleep now.
Sorry, guys. It seems that it was my fault. I don't know all the reasons why everything happened bad. The main reasons are:
Sorry again about it. I apologize to the writer oversolver he did his job great. Be sure, some sleepless nights are waiting for me!
P.S. Fefer_Ivan, it is hard without you...
I also want to say thank you for those who didn't stop participating just because of contest being unrated and who continued solving nice tasks that oversolver prepared.
I hope that we will see new contests set up by him again!
You didn't answered me personally, but again — where is Gerald ?)
no problem at all
Nothing to sorrow. At least I learned something by trying the problems. Just it will be nice if we have the upcoming contest soon. Thanks! :)
The kernel remounts a filesystem read-only if it encounters an I/O error on the underlying device. If this is what happened, then the kernel log should contain the details.
MikeMirzayanov, can you confirm if what andreyv said is what happened? me curious!
Блин, что-то не оверперформится мне на нерейтинговом раунде)
Хотя если вспомнить мою формулу рейтинга контеста
R = 2^A + Q, гдеA - количество acceptedQ - qualityто все хорошо, можно ложиться спать с хорошим настроением, пока не подоспели систесты)
UPD не смог не дождаться систестов) ABCD сдались впервые) Пусть и не оч честно (D по сложности лишь немного выше С и времени было больше), но мне пофиг, спасибо oversolver :D !!
how to solve div-1 d .
You want to partition the sequence in subsequences each of which will be "going up" or "going down". Solution is a DP where you state is (position, down or up).
My solution (possible solution, I don't know if it's the correct one) was the following: - You can build a DP like dp[i] = min j < i(dp[j] + maxValue(j + 1, i) — minValue(j + 1, i) - The solution above is too slow O(N²), but you can notice that maxValue(j + 1,i) — minValue(j + 1, i) is increasing as we decrease 'j' and that dp[j] is increasing as we decrease 'j'. The sum of one increasing function with one decreasing function is a function that increases and then decreases. - Given that fact we can actually do a ternary search on the maximum 'j', so now we reduced our solution to O(N log N)
"The sum of one increasing function with one decreasing function is a function that increases and then decreases."
Are you sure?
Not so sure, that's why I don't know if my solution is actually right.
My intuition was telling me to assume that dp + max — min is a function that can be ternary searched.
It's actually false: Sum 1 3 7 9 and 9 8 3 2
yields 10 11 10 11 which increases, then decreases and finally increases again.
Yeah, you're right. I guess the lesson is not to trust your gut at all times, they may be wrong!
Nope , you're wrong take this example:
DP. Sequence rises up and down.And the key-point is you will never separate a continuous sub-sequence into more than one sub-sequences if this sub-sequence is straight up or down.For example:
-2 4 5 1 -7 3 6
you should divide them into :
-2 4
5 1
-7 3 6
or
-2 4 5
1 -7
3 6
or something like that.
You can figure out that the only thing you need to handle is which part should the peak and the bottom of the sequence belong. Turns out a DP problem.You can check my code.Hope that helps.:D
Also it has simple O(N) solution:
Could you please explain why this works? I looked at it for a long time, but I can't figure out what x and y represent. Thanks in advance.
In optimal answer any segment that making a group contains their minimum and maximum values on borders. So, we can write following dynamic solution, which find answer on each prefix of array:
or
Therefore it is sufficient to remember and update the maximum values of ansj + aj + 1 (y in my code) and ansj - aj + 1 (x in my code) at each step.
Заметка на будущее — это плохой код.
А я вообще не могу запомнить сколько подчеркиваний во второй строке, поэтому всегда руками.
http://mirror.codeforces.com/blog/entry/13134#comment-178975 :)
потому что нужно
__builtin_popcountll(x);Классные задачки, но почему-то нерейтинговый раунд. Обидно.:( А автору спасибо!
When will system testing begin?
i really loved the C Problem, i'm not sure why, but i just loved it :D
No rating is not bad for mee, round was difficult... waiting system test...
How I solve problem D?
Thanks for the Nice problemset oversolver , I just wanted to tell you that I enjoyed the round despite the technical difficulties that were being caused by codeforces .
PS:If you like what I have said above then give it a '-' .
Is there some tricky case for Div1 A/ Div2 C?
I solved it as follows: let the answer be stored in res. go through the bits of the 2 numbers(from left to right). If the current bit is 1 in both then set that bit in res. If it is 1 in r only then set it to 0 in res and make all next bits 1. In the end count the number of 1s in res and the number of 1s in r. output the one with the max.
What's wrong with that?
So... I have finally seen the test that failed me and it seems to work fine locally but outputs a wrong answer in Custom Test... Can anyone tell me what could've gone wrong here? Submission
i had the same problem but i fixed it, you must think what happens when you have a case like this:
Left = 6 ; Right = 7
6 is written in binary like 110 7 is written in binray like 111
following with your approach you will go to the last bit and set it as 0 then all the remaining bits as 1, but in this case you will return 6 and the correct answer is 7. So, you must care the case when it is the last bit, if they only differ in the last bit you must return Right
Actually not... As I said, at the end I count the number of 1s in r and the number of 1s in res and print the one with more 1s... In this case, I'd print 7 :D
contest had many bugs bugman! :)
All problems are very interesting! Thanks to oversolver.
All problems are very interesting. Thanks to oversolver.
(http://i.imgur.com/nvtu5ZI.png)
still waiting for my first hack attempt :D
(http://i.imgur.com/eDOKpzW.png)
:(
When you are as bad a coder as me then technical difficulties are not such a big problem for you! :P My only submission was Div2 C at 2 hours 7 minutes past the start of the contest and it got tested without any delay.
My only submission was Div1 A at 0 hours 6 minutes past the start of the contest and it got tested without any delay :D
Div1 D:
We can prove that each groups must be increasing or decreasing. So we can solve it in O(N) with using ordinary DP.
Or the problem is just asking to traverse the array from left to right choose some numbers and add to solution and some other numbers and subtract it from solution such that at any time during the traverse number of numbers that you added to solution differs from number of numbers that you subtract from solution by at most 1 but at the end the two numbers should be equal , this can be solved by very simple dp my code 8576807
Lol, how simple. Reminds me of 383D - Antimatter with a long explanation for the official solution and a short one for the one most people found.
(It's not like DEGwer's version is much harder — you just need to think when it's better to split/merge a group and it follows almost immediately.)
I like D , I tried to solve it ( but got TL ) with DP , ternary search and segment trees.
I have seen Div1 B in a Japanese high school programming contest.
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0270
Awesome problems. Variations were really good. Problem A was tricker than usual. Problem D was a very creative one.
За сколько работает этот код???
for(int i = 2; i <= n; i++) { int j = i; while(j <= n) j += (i — 1); }
у меня вроде такая же сложность как у цикла этого, но ТЛ 7 ловлю(B div 1).
за касарь
Ибо работает за
Спасибо, кэп!
Ну вот я тож не пойму, где тогда ТЛ!
I might be mistaken, but that's not quite the code you sent. Here's a snippet from your submission:
The code above is O(n^2).
OMG thx!!! it was BUG!!! the right code is "lf = rg + 2", LOL
Nice problem at all, thanks for the contest. Btw, someone can describe the solution of problem Div2C/Div1A? Please)
greedy will work :). let b = number of bit in R (upper bound).
now start from res = (1<<b)-1. (all the bit 1) now start removing power of 2 from right to left until you have res in the given range.
If removing a power of 2 gives you a number less then lower bound L then do not remove it, try next one...
Thank you man!) I will try to solve it, later.
go from li to ri increasing the number of ones in his binary representation :
for example
li = 0010001 -> 0010011 -> 0010111 -> ...... until it reach some number equal or greater than ri
ri = 1010101
when I say increase number of 1s , I mean add 1s in the 0-positions from right to left, every time you add an 1 digit the result number is the minimun number with 's' 1 digits ( s = current number of 1 digits in the result number ) greater than ri , you can prove it.
Good problems. Bad network.
Как div. 1 C?
How is Div2-D / Div1-B to be solved?
huh!, Codeforces community is busy with up-voting instead helping the guy.Tutorial already published, you know...
Thank you oversolver for this amazing round. I took the best place I ever had, and that gave me faith. My self esteem is in your debt.
Why do we need to run the loop 'm' times in Problem A of Div-2?..
in case we have 65535 65536, Answer is "Yes". so , we must check until m or else we may get a wrong answer in this brute force method .
Thanks oversolver for great problems. I was sad when I read announcement but I was happy after system testing (because my solution A failed) :)
Thank you oversolver for such an awesome problemset! If the servers didn't have issues during the contest and ran smoothly I think it would've been an even better one. I hope we'll see more rounds from you in the future! :)
Quite a nice contest :) My first hack ever! Thank you oversolver.
nice contest and fast editorial
Why rating system is too slow? Or is it a unrated contest??
Yes, due to technical reasons round is unrated.
ohhh..but thanx for an excellent problemset
Just wondering, is this the first time for a contest being unrated? Anyway the div2 problems are as good as your last contest. Thanks, oversolver.
No, unfortunately this is not the first time.
8573331
hint: check the length of s
If check visually, seems that checker printed both string of length 6, no more symbols, spaces or newlines.
Already changed that yesterday, but either way I got TLE :P. Too much copying vectors :(
I don't get it. Why is it WA?
I didn't expect that it can be a reason of WA, but it's caused by zero byte.
My rating didn't change after the contest...
Really? My changed as I expected...
Country wise rankings have been updated for this contest. Although I know many people left the contest half way, including me, but still had to update the site.
I like the link, thanks ;-)
next div 1 contest after two weeks...
when will the ratings be updated?
After the next contest ends XD
fuk u