Hello everyone!
Codeforces Round #258 (Div. 2) will take place on July 24, 19:30 MSK. Traditionally, Div. 1 users can take part out of the competition.
The round was prepared by PraveenDhinwa and me (JuanMata). This is our second Codeforces round, and hopefully not our last.
We have tried our best to make the problem statements as clear and interesting as possible. We hope that everyone will enjoy the round. :)
Special thanks to MikeMirzayanov for creating the wonderful Polygon and Codeforces platforms, Gerald for his extensive help in problem verification and testing, and Delinur for translation of problem statements into Russian. Without their help the contest would never have seen the day.
We wish all the participants good luck and high rating. :)
UPD: It is decided to use the dynamic scoring system.
UPD: Contest is finished. You can find the editorial here. :)
UPD: Congratulations to the winners. Here are the top 8 (the only ones to solve all the problems):
Hey...It's time to make a Div 1 round! :)
don't worry. it will come shortly. :)
Hey algo1, It's time to stop making fake accounts
Second
time fromIndia
andthird
time fromIndian subcontinent
... :)*** Editorail of your last round (Round 251) was awesome... Hope the best for this time, too... :)
Thank you so much for your review. We will try to make it better this time :)
Who is going to be the main character? Devu again? :D
Good Luck
Choosing a Good Name thank you sir.
Why isn't this post on the home page too like all the other contest announcement posts? EDIT:fixed
Thanks, for providing the link of polygon. I was unaware of it.
You could just google it !
I was initially unaware of polygon, I only come to know about it through a blog post. I did not really know that everybody can make problems for even their own contests. polygon is quite nice :)
I know JuanMata personally and I can vouch for two things.
One is clear problem statements.
Another is — expect buttloads of football.
"One is clear problem statements.", this should be correct, let us hope :).
"expect buttloads of football.", no, not really.
Actually he is a bit busy in his google orientation. So the problems statements are written by me. Otherwise you would have been completely right :)
UPD: He has some time free today and tomorrow :) So you might expect both.
i actually wanted this round to happen before the FIFA World Cup ended. but due to other contests in queue this was not possible. otherwise ur second point would have surely been true. :)
I would be expecting use of certain words like "lite" and "ob"... :D
When We See The Problemsetter is JuanMata , Then We automatically expect some soccers ;)
So far I knew, JuanMata is a supporter of Chelsea. But now I've realized about his craziness in football... :)
i am a football fan in general, but my favorite team is Chelsea. :)
Juan Mata is a Player of Chelsea and Spain Football Team ! So He must support them . But , at first he is a supporter of JuanMata ;)
:(
Manchester Rule!
What was your first Codeforces round that you made its problem statemets?
Codeforces Round #251
There was a notification that today codeforces will not be available during some time, can somebody please tell me the exact timings when the site will be down, I forgot to note that down :(
I Think it is 2:30am — 6:30am in IST as far as I remember It was 1:00am — 5:00am in MSK
will Polygon also be down during that time?
yes, it was written that polygon will also be down.
why 258 is BOLD?
so that it is easy for you to choose name of the directory for participating in the contest :P
Wa!So nice!
Wow, such contest, very good, but I'm too young, too simple and sometimes naive. But your contest makes me feel "EXCITED"!
i see u have created another account (SmartLovelyJuanMataAgain) for this contest.
why can't you just compete (maybe unofficially) with your regular account? are u really so pathetic? o.O
Oh, he's just my dear friend!
Good Luck JuanMata!!
why only JuanMata, if not full luck, you can wish some luck to me too :P
Haha yeah sure. He's in same college as I am so I know him
why so :P ???
In this blog, I've found asking you with many WHY... why so many why ??? :P
and scores??
why so many downvotes?
That is most stupid question ever asked.
And there is always someone asking it.
:)
scoring now added to OP. :)
I like the editorials of PraveenDhinwa . They are awesome at codechef and hope here also .
YESSSSSS another JuanMata CONTESSSST!!!!
^_^
Even though the scoring is dynamic Please can you accept my request to sort the problems in increasing order of difficulty(According to you) so that I am atleast sure of solving the first two problems and don't have to click on standings again and again to confirm which problem is the most solvable .
In IOI and ACM-ICPC problems are not in increasing order of difficulty.
UPD: It is decided to use the dynamic scoring system.
WHY??? :(
dynamic scoring = rating drop (in my case)
...but maybe this time finally :-D Never give up!
I think this contest will prove exception to " rating drop (in my case)" :)
If it really prove exception ,it will be my first time to be DIV1 let us play the game till the end and see the results :)
haha, same here, currently I'm a little closer to DIV I, but it can be different after the contest, good luck ;-)
anyway whatever the results I'm happy to solve D ,I think it's my first time ,I need only 6 point for DIV1
same for me, I'm too unlucky in dynamic score
I'm so sad when my points gone down and my name change to be green. I will be more hardly.
i am a new user of codeforces can anyone help me please? what does DIV.1 and DIV.2 mean?
When You are a beginner , you are attending the contest from DIV2 . When performing good in some DIV2 contests and achieving a handsome rating(1700+) , you will be able to attend the contest from DIV1.
the problems of DIV1 are harder than the problems of DIV2. Good Luck :)
Dynamic score is ALWAYS dramatic... Can' t adjust the contest very well... And NO new users-without-any-submissions spoil our fun again...
Dynamic scoring is usually not very good!
In fact,I'm not good at dynamic scoring system.
4255 till now ,seems that we will have a long queue :)
What do you mean?
I mean system test will be slow specially if writer has a strong pretests
I register for the contest but after that i realize i can't participate. very sad. wish all participants high rating!
I didn't see the part of problem D that string is only consisted by 'a' and 'b'. In my opinion you must wrote this important part of statement in problem statement, not only in input.
Btw, great contest, thank you.
oh i got to know it now .... even i missed it .. but the contest was awesome .
I didn't see it too :(
i see "Each character of the string will be either 'a' or 'b'" right now after reading your comments. :))
I didn't notice it too!
I noticed it after 20 minutes. What about bolding these important things ? :))
What was the approach to solve problem D?
Problem statement should be tested more carefully before launch. Hope next time we'll not be bother
Hey guys , I can't see others submission even after locking my problem.This problem is from the beginning. I lock my problem , I go to standings , I double click a submission of my locked problem. then I click the submission number. But nothing happens. After contest it's just fine. But I can see during the contest;. Why?
During the contest, you can only see the codes of people in your ROOM after you lock. The way to do so is in the Room tab.
you must go to the your room, not standing.
You can see and hack only solutions of contestants in your room, so go to your room instead of standings
Awesome contest! Thanks, JuanMata and PraveenDhinwa :)
I suspect that problem B is difficult to hack, and there are small amount of hacks, but some systest fails will apear.
Got WA on Test 74 :(
I solved problem B incorrectly at 35 min. Later I tried to find mistakes, and found that tests like "3\n2 3 1" do not pass, because answer is "no", but program gives "yes\n2 3". I rewrote code, and had 10 minutes to search the same bug in codes of others, but it was difficult to understand whole long codes, and I didn't try to use this or more difficult test.
I got WA on Test 69, because I did not take into account when n is 1 :(((
507 sysfails! Initially 2187 -> later 1680 !
Nice round. Congrats to the authors! How to solve E ?
Use Inclusion Exclusion princicple to solve the equation
a[1] + a[2] + a[3] + .... + a[n] = s
could you please explain more?
How was problem C supposed to be solved?
First, the condition is n%3 == 0. |Solve this system of equations : |x1-x2| = d1, |x2-x3| = d2, x1+x2+x3 = k with x1,x2,x3 is wins of team 1,2,3. Have 4 cases to solve. After check (n-k) is enough to give x1,x2,x3 to X1,X2,X3 satisfy X1=X2=X3=X.
What with sample 5? It's impossible to play only three matches and have differences three won between 1v2 and 2 won between 2v3.
yes, after k = 3 games this situation is impossible.
the information given by our friend is inconsistent (what a bad friend, spoiling the football tournament for you! :P).
so the answer is
no
by default.Thanx for explanation.I have implemented in the same way suggested by you in problem C but I am getting WA on test 4 and I am unable to determine the bug .Would you please take out your valuable time for it.Any help will be appreciated.Thank You. http://codeforces.net/contest/451/submission/7234615
Thanx for explanation.I have implemented in the same way suggested by you in problem C but I am getting WA on test 4 and I am unable to determine the bug .Would you please take out your valuable time for it.Any help will be appreciated.Thank You. http://codeforces.net/contest/451/submission/7234615
test for
d1 = ± d1
d2 = ± d2
, always checking if you can have K games with those differences. doing so, you just have to solve a system of linear equations:
Δ V1 + d1 = Δ V2
Δ V1 + d1 + d2 = Δ V3
Δ V1 + Δ V2 + Δ V3 = N - K
There is no d3.
I used binary search on the winning value of the middle team. Firstly , I have four case ++,-+,+- and --. Now for each case I tried to figure out the configuration that would fit into k. You can see my submission ,7228843.
But it is O(T.log(N)), my algorithm is O(T)
Перед отправкой решения меня выкидывало из аккаунта.У кого ещё была такая же проблема?
Надо поставить галочку "Запомнить на месяц" при входе
Wow, such fast system test which only cost 7 minutes.
System test is so fast! And I am very happy because I solved four problems in Div2 for the first time!
Give us editorial, please
worst contest that i see in my life!!!
I'm sorry
WA on test case 67 :(
I scared I will get down rating
congratulations TankEngineer !
The contest was great! Btw, how to solve problem D ?
Suppose you have found the number of odd and even palindromic substring for the first few characters of the string. For example,
aabaaabb
have8
even palindromic substring and13
odd palindromic substring. At the same time, we maintain the number of 'a's at even and odd positions, and the number of 'b's at odd and even positions respectively. In the above example, we have 2'a's at odd positions and 3'a's at even positions, while we have 2'b's at odd positions and another 'b' at even position.When we append a new character to the end of the string, we can compute the number of palindromic substring which ends with the new character. For example, if the appended character is 'a', the number of odd palindromic substring which ends with the new character will be the number of 'a's at odd positions, and the number of even palindromic substring which ends with the new 'a' will be the number of 'a's at even positions. Hence, the new string
aabaaabba
will have11
(8+3) even palindromic substring and16
(13+2+1) odd palindromic substrings (don't forget to consider the new character as a substring of length 1). There are several cases to consider depending on the parity of the position for the new character, but it is not hard to code them out.Repeat the above steps, each time appending a new character to obtain the final results. Example solution here: 7227422
I didn't notice that the substring between 2 'a' or 'b' is always a good string :( If I did, I would be violet now :(
Anyway, thank you very much :D
too long, update rating
Juanmata, fortunately for you, someone got 258th place, however, no one got 123th place in a round prepared partially by praveen123
If you didn't understand what I am talking about, read this comment
LOL. but atleast OP has got +123 votes (at the time of writing this comment). :)
Did anyone use Hightail for the contest ? How was the experience ?
Nice Round.. Got many fun reading and thinking about the problems.. Still getting fun analyzing the errors of mine... Thank you very much.. Enjoyed the contest.. Hope we will get many more like this..... :D
waaaaaaaaaaaaaaaaat? are you sure?
yeap.. i enjoyed it...
Gave very bad contest but still +11. So sad.:(
I got down rating !
Thank you for the contest :) Very interesting problems.
Unbelievable! TankEngineer solved all problems in less than half an hour!!! Congratulations)
Wow!!!!!! This is unbelievable. Congrats to him.
Problem D was awesome. Loved it :)
me too & it's my first time to solve D
Hii,
In question B test case 26#
5
373362086 994096202 767275079 734424844 515504383
why "yes 2 5" is not an answer?by applying this, the sequence below is now a sorted sequence.
373362086 515504383 734424844 767275079 994096202
Please tell me if I am doing something really foolish.
is the correct answer. u got WA#26 because ur code prints
no
.Ohh, Got my mistake.
thank you :)
In the title, why the font of "258" is Times New Roman, but not Verdana as "Codeforces Round"? :P
Round Stats
hey... in Problem C, initial number of wins for a, b, and c are not coming to be integer values for some test cases like: -> 999999999980 258442058745 258442058715 258442058720.
Please correct me if I am wrong.
If n % 3 != 0, answer is "no". Because each team must have n/3 wins.
Thanks for your reply...but that was not what I asked. -_-