Hello everybody!
Today will be Codeforces Round #276, which take place in both divisions. Start time is 19:30 in moscow time (follow this link to see time in others zones). For preparing contest i say thanks to Zlobober, for translating to Delinur, and to MikeMirzayanov for project Codeforces.
Good luck to all, hope you will enjoy problems :)
UPD Score distribution will be dynamic (see more information here). Problems will be sorted in increasing order of difficulty, however, do not forget to read all problems before the end of the contest.
UPD The contest is over! Thanks to everyone who solved the problems despite everything. Analysis will be published later.
UPD Editorial can be found here.
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://codeforces.net/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
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
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
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 ;)
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 :'(
If only I can punch person to death I will punch myself. Such a waste of precious sleeptime.
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://codeforces.net/contests/486
And in 2 weeks for Div 1: http://codeforces.net/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 ! :)
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!
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.
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.
(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
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.
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