Codeforces Round #146 is going to be here soon. Round is prepared by YuukaKazami, MinakoKojima. I write problems for Div I and MinakoKojima write for Div II. Gerald did a great job in coordinating round preparing, and he also give some pretty good advise about problems. I'd like to express my gratitude to him. Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for perfect Codeforces system and Polygon system as well and Mary Belova (Delinur) for translating problems. Also thanks to donehl for testing the problems and making his comments about the problems.
Score distribution is 500-1000-1500-2000-2500 in both divisions.
Hope you enjoy the problems! =)
I apologize for the 10 minutes delay.I'm very sorry for the inconvenience I caused. So I'm writing a good editorial for compensation :)
The Editorial is here: Editorial
Congrats to winners!
Orz .. .
sorry for the trouble
Orz WJMZBMR & xiaodao
That would be interesting to participate in contest made by you but unfortunately we have our Moscow ACM ICPC Quarterfinal today at the same time :-(
made in China... hope i can become yellow...
why isnt the time again as usual ?
Because there is a contest in Codechef tonight, Check here to see more details.
i guess you are right but its a little hard to attend contest in this timing i wish they run in in another day but in the usual time
Usually, contests end at 1:30 Am in China, as I see. Not good for any day :)
2500 people think that time is ok.
3:30 AM in FLorida — US, and it is good for me.
despite this there are a lot of contesters !!
This time is right!
Good luck to everybody. Have a nice exam.
What do these mysterious letters mean? Is it a Chinese word?
Those characters are to depict the begging man, who is standing on his knees and touching the gound with his head.
There are a group of hieroglyph chracters, means "admiration". It is popullar and have been general used in BBS or Microblog around Japan and China.
Thx guys. I found this meaning in wikipedia, but didn't understand. Silly me =D
Now I can see a man.
Let the battle begin
OMG again 10 mins delay :(
Hey CodeForces, it's 4AM in Brazil and i've been awake since yesterday. =/
I made an alarm to wake up, coz here is morning, if I knew I would'we made it 10 mins later, it would mean a lot to me :D
I suppose it's not so easy to maintain the server. Be patient :)
It is not easy to wait!
I'm very sorry about it...But everything is fine now
That was Snooze
Hope I can become purple.Good luck everyone!
You are purple now.
OMG!!1 Is YuukaKazami a girl?
...Can you see my avatar?...I hope I could be a girl, though...
There are 6 distinct characters in "wjmzbmr". These characters are: "w", "j", "m", "z", "b", "r". So YuukaKazami is a female and you should "CHAT WITH HER!".
lol...So this guy will be fell in love with me again and see a "thin man" in real world~~~
it's a trap.. :p
It's hard to judge whether you're a girl or not through the avatar. ^.^
Too mathy for this morning...
Many many many math to night, I am in american here is 5:55 am.
A, B, C, D — math. E — strings. Very nice problemset, xiaodao, thank you.
UPD: It's not a sarcasm :D
Before end of contest, it was incorrect when you told even so rough classification...
Looks like Petr and tourist couldn't solve Div 2 problem
Maybe they just worked on other high score problems, or challenging.. As a result, they earned more points than anyone who solved C.
It seems that system testing hasn't started now.When will it start?
UPD: It has started.
UPD: It seems systest today is very slow.
I love when somebody plays in "Captain Obvious" game for contribution only so much.
Thank the authors for this intense thinking contest, great work! I wish the editorial would be done soon.
It'll come just today.
Anyone can teach me how to solve "how many times does a string x occur in a string s" as mentioned in the description of Div2 E?I sucked at that point already.
The fastest way is to use Knuth–Morris–Pratt algorithm. Article on Wikipedia
In this problem KMP wouldn't run in time (if you get 10^5 "a" queries on a 10^6 string your running time is 10^11). You need an Aho-Corasick automaton or a suffix array. Or something using hashing.
Nezzar didn't ask, how to solve this problem. He asked just, how to calculate the number of occurences of one string in another.
Just saying that either Aho-Corasick or a suffix array is an out-of-the-box solution for the problem as stated, but without the cyclic rearrangements. To find one string in one other string just once you could certainly use KMP.
systest in 3600 .. 3599 .. 3598 .. 3597 .. 3596 .........
UPD : 3595 .. 3594 .. 3 .. 2 .. 1 .. 0. Systest!
it's better than 7200 .. 7199 .. 7198 .. 7197 ..
3.. 2.. 1.. 0.. -1.. -2...
going back to blue again >_<
Well, I wish to be blue like you.
Me too T_T
When is system testing?I'm worried that my C(Div2) will fail.......
It seems that your solution is correct, because it's identical to mine and I've proved my solution.
Here it is!
Don't worry . It will pass.
Thank you,it got an AC.
Well people system test in two hours, american people go to sleep!!!!
Seems I just have to wait for the editorial then :D
Is this the slowest systest ever?
That's because there are 100+ test cases for Div.2 B and C
But the number of test cases in each round before are also 100+.
Very slow judge :(
it's good that problem E & D had less than 3 AC ,so we can imagine there is an end time for this slow system testing !
Problem D Div 2, I has just read some solution, but i can't understand :( Anyone help me please :D
Let E[i, j] be the excepted score for clicks from i to j(inclusive). Let L[i, j] be the excepted 'o' s starts from left, of clicks from i to j. Let R[i, j] be something like L[i, j]. Then we have:
, for any i < k < j.
Think about: If we got x 'o's in clicks [i..k], y 'o's in clicks [k+1..j], then score x^2 is calculated in E[i, k], y^2 in E[k+1, j], and we actually need (x+y)^2 = x^2+y^2+2xy. And since R[i, k] and L[k+1, j] are independent, the 2xy part is calculated as 2 * R[i, k] * L[k+1, j].
Now we take k = j — 1, i = 0, and let e[j] = E[0, j], r[j] = R[0, j]:
What an amazing solution :D
Thank you :)
what a amazing! I only come up with a O(n*n) dp solution.
Me too! I try to DP it but failed :(
I get a TLE in 68th case :(
Of course :D
I have never think like this solution :)
It helps me so much, thank Ray again :)
I got this solution 5 minutes after the contest, saddly. Then I waited hours for the system test to end. Finally I got 1AC.
The evil test case 61 of LCM Challenge :|
sorry for the slow judging...I put too many test in Div2B and Div1A...I didn't expect some solution are too slow T_T...anyway...the judging is done now...
Anyway,I think it's a good contest.I would like also thanks to MinakoKojima for the problems in Div.2.
This contest is very valuable, thanks to YuukaKazami and MinakoKojima. :D
Try to refresh the rating as quick as possible.
I suppose the system is calculating the rating change.
Then why does it take 30 minutes to recalculate it for 2000 people? The complexity is O(n).
good question ! :D
You know how it works? 'Cause i don't.
How slow is that :( I think it's n^3 :)))))
Even it is n^3, it will be done in just one minute.
:-? 2000^3 calculations in just one minutes
Oh yeah, may be n^4 :))))
But usually it is done in about ten minutes, I think.
Sure it is :D and the rating update has done :D
Egor — the luckiest man of this contest
His E's submission 2402930 is only 14s to the contest end and runs 16ms to the time limit.
Well,He use some interesting strategy to reduce the time, It is just...very good job to do this cool stuff.
I optimized my solution until last possible moment. Actually it runs between 2950-3050 ms on server, so I got lucky indeed
Ratings are now updated. Log off and on to see them.
Can anybody tell me why Div2.C 2398837 is Runtime error on pretest 1. exit code: 13131313 It is at least not throwing any exception in my system. I suspect BigInteger#isProbablePrime but don't know why?
It even shocked me .. The same code run at IDEONE is also throwing Exception http://ideone.com/7efDIa
i don't know java but use throws exception will lead u to correct runtime
you mean main method throws exception like this 2405543 it didn't help ... still same issue. I don't know want is wrong. java experts please help.
I am quite shocked. My following simple Brute Force solution for DIV 2 Problem C:LCM Challenge got Accepted.. :D
This problem is very easy if you think carefully :)
It include 3 cases
1: n odd => result = n * ( n — 1 ) * ( n — 2 );
2: n is not odd and ( n mod 3 = 0 ) => result = ( n — 1 ) * ( n — 2 ) * ( n — 3 );
3: n is not odd and ( n mod 3 <> 0 ) => result = n * ( n — 1 ) * ( n — 3 );
Brute force is quiet "buffalo" for this problem :)
nice observation but can you please provide proof of it
Hi A short-solution programming contest will hold on October 24 at gpac.blog.ir
the link for the tutorial is: http://codeforces.com/blog/entry/5592
what does orz mean? and when when will you write editorial? I'm waiting for that :)
Editorial and orz
Before, thinking by myself what could it mean, I realized that orz denotes admiration and they thank the author in this way. But I was wrong, and now I still cannot understand why they are in a quick depression because of the round. Can anybody explain it?