### YuukaKazami's blog

By YuukaKazami, 7 years ago, ,

Hi!

Codeforces Round #146 is going to be here soon. Round is prepared by WJMZBMR, xiaodao. I write problems for Div I and xiaodao 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!

Div1:

1.rng_58

3.bjin

4.Petr

5.Egor

6.tourist

Div2:

1.RiKang

2.Caesar11

3.Gabaum

4.ilona

5.Bidhan

• +253

 » 7 years ago, # |   +19 Orz .. .
 » 7 years ago, # | ← Rev. 2 →   0 sorry for the trouble
 » 7 years ago, # |   +7 Orz WJMZBMR & xiaodao
 » 7 years ago, # | ← Rev. 2 →   +22 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 :-(
 » 7 years ago, # |   +36 made in China... hope i can become yellow...
•  » » 7 years ago, # ^ |   -34 xwlj
 » 7 years ago, # |   -11 Orz
 » 7 years ago, # |   -31 orz
 » 7 years ago, # |   -20 orz！！！！！！！
 » 7 years ago, # |   -26 Orz
 » 7 years ago, # |   +3 why isnt the time again as usual ?
•  » » 7 years ago, # ^ |   +14 Because there is a contest in Codechef tonight, Check here to see more details.
•  » » » 7 years ago, # ^ |   0 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
•  » » » » 7 years ago, # ^ |   +5 Usually, contests end at 1:30 Am in China, as I see. Not good for any day :)
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +54 2500 people think that time is ok.
•  » » » » 7 years ago, # ^ |   0 3:30 AM in FLorida — US, and it is good for me.
 » 7 years ago, # |   +2 despite this there are a lot of contesters !!
 » 7 years ago, # |   -19 Orz
 » 7 years ago, # |   +4 This time is right!
 » 7 years ago, # |   -7 Good luck to everybody. Have a nice exam.
 » 7 years ago, # |   -38 orz
 » 7 years ago, # |   -25 orz!!
 » 7 years ago, # |   +20 What do these mysterious letters mean? Is it a Chinese word?
•  » » 7 years ago, # ^ |   +16
•  » » 7 years ago, # ^ |   +11 Read here.
•  » » 7 years ago, # ^ |   +12 Those characters are to depict the begging man, who is standing on his knees and touching the gound with his head.
•  » » 7 years ago, # ^ |   +8 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.
•  » » 7 years ago, # ^ | ← Rev. 2 →   +3 Thx guys. I found this meaning in wikipedia, but didn't understand. Silly me =DNow I can see a man.
 » 7 years ago, # |   +5 Let the battle begin
 » 7 years ago, # |   -24 Orz
 » 7 years ago, # |   +3 OMG again 10 mins delay :(
•  » » 7 years ago, # ^ |   +10 Hey CodeForces, it's 4AM in Brazil and i've been awake since yesterday. =/
•  » » » 7 years ago, # ^ |   +12 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
•  » » 7 years ago, # ^ |   +4 I suppose it's not so easy to maintain the server. Be patient :)
•  » » » 7 years ago, # ^ |   -9 It is not easy to wait!
•  » » » » 7 years ago, # ^ |   +10 I'm very sorry about it...But everything is fine now
 » 7 years ago, # |   +15 That was Snooze
 » 7 years ago, # |   -16 Hope I can become purple.Good luck everyone!
•  » » 7 years ago, # ^ |   +1 You are purple now.
 » 7 years ago, # |   -17 orz....
 » 7 years ago, # | ← Rev. 4 →   +3 OMG!!1 Is WJMZBMR a girl?
•  » » 7 years ago, # ^ |   +10 IGNORE HER!
•  » » 7 years ago, # ^ |   +3 Sure not.
•  » » 7 years ago, # ^ |   +25 ...Can you see my avatar?...I hope I could be a girl, though...
•  » » » 7 years ago, # ^ |   +8 There are 6 distinct characters in "wjmzbmr". These characters are: "w", "j", "m", "z", "b", "r". So WJMZBMR is a female and you should "CHAT WITH HER!".
•  » » » » 7 years ago, # ^ |   +18 lol...So this guy will be fell in love with me again and see a "thin man" in real world~~~
•  » » » » 7 years ago, # ^ |   +3 it's a trap.. :p
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +14 It's hard to judge whether you're a girl or not through the avatar. ^.^
 » 7 years ago, # |   +25 Too mathy for this morning...
•  » » 7 years ago, # ^ |   +4 Many many many math to night, I am in american here is 5:55 am.
 » 7 years ago, # | ← Rev. 2 →   -18 A, B, C, D — math. E — strings. Very nice problemset, xiaodao, thank you.UPD: It's not a sarcasm :D
•  » » 7 years ago, # ^ |   +3 Before end of contest, it was incorrect when you told even so rough classification...
 » 7 years ago, # |   +187 Looks like Petr and tourist couldn't solve Div 2 problem
•  » » 7 years ago, # ^ |   +4 Maybe they just worked on other high score problems, or challenging.. As a result, they earned more points than anyone who solved C.
 » 7 years ago, # | ← Rev. 4 →   +10 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.
•  » » 7 years ago, # ^ |   0 I love when somebody plays in "Captain Obvious" game for contribution only so much.
 » 7 years ago, # |   +90 Maths Everywhere!
 » 7 years ago, # | ← Rev. 2 →   0 Thank the authors for this intense thinking contest, great work! I wish the editorial would be done soon.
•  » » 7 years ago, # ^ |   +6 It'll come just today.
 » 7 years ago, # |   +3 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.
•  » » 7 years ago, # ^ |   -7 The fastest way is to use Knuth–Morris–Pratt algorithm. Article on Wikipedia
•  » » » 7 years ago, # ^ |   +2 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.
•  » » » » 7 years ago, # ^ |   +3 theogry didn't ask, how to solve this problem. He asked just, how to calculate the number of occurences of one string in another.
•  » » » » » 7 years ago, # ^ |   0 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.
 » 7 years ago, # | ← Rev. 2 →   +16 systest in 3600 .. 3599 .. 3598 .. 3597 .. 3596 .........UPD : 3595 .. 3594 .. 3 .. 2 .. 1 .. 0. Systest!
•  » » 7 years ago, # ^ |   0 it's better than 7200 .. 7199 .. 7198 .. 7197 ..
•  » » » 7 years ago, # ^ |   +13 3.. 2.. 1.. 0.. -1.. -2...
 » 7 years ago, # |   +3 going back to blue again >_<
•  » » 7 years ago, # ^ |   +10 Well, I wish to be blue like you.
•  » » 7 years ago, # ^ |   +1 Me too T_T
 » 7 years ago, # |   -7 When is system testing?I'm worried that my C(Div2) will fail.......
•  » » 7 years ago, # ^ |   0 It seems that your solution is correct, because it's identical to mine and I've proved my solution.
•  » » 7 years ago, # ^ |   0 Here it is!
•  » » 7 years ago, # ^ |   +3 Don't worry . It will pass.
•  » » 7 years ago, # ^ |   0 Thank you,it got an AC.
 » 7 years ago, # | ← Rev. 2 →   0 Well people system test in two hours, american people go to sleep!!!!
 » 7 years ago, # |   0 finally starts
 » 7 years ago, # | ← Rev. 2 →   -12 Seems I just have to wait for the editorial then :D
 » 7 years ago, # |   +22 Is this the slowest systest ever?
•  » » 7 years ago, # ^ |   0 That's because there are 100+ test cases for Div.2 B and C
•  » » » 7 years ago, # ^ |   +5 But the number of test cases in each round before are also 100+.
•  » » 7 years ago, # ^ |   0 It is.(
 » 7 years ago, # |   +4 Very slow judge :(
•  » » 7 years ago, # ^ |   0 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 !
 » 7 years ago, # |   0 Problem D Div 2, I has just read some solution, but i can't understand :( Anyone help me please :D
•  » » 7 years ago, # ^ | ← Rev. 3 →   +11 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: E[i, j] = E[i, k] + E[k + 1, j] + 2 * R[i, k] * L[k+1, j] , 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]: e[j] = E[0, j] = E[0, j-1] + E[j, j] + 2 * R[0, j-1] * L[j,j] = e[j-1] + p[j] + 2 * r[j] * p[j] r[j] = (r[j-1] + 1) * p[j] 
•  » » » 7 years ago, # ^ |   0 What an amazing solution :DThank you :)
•  » » » 7 years ago, # ^ |   +3 what a amazing! I only come up with a O(n*n) dp solution.
•  » » » » 7 years ago, # ^ |   +3 Me too! I try to DP it but failed :(
•  » » » » » 7 years ago, # ^ |   +3 I get a TLE in 68th case :(
•  » » » » » » 7 years ago, # ^ |   +3 Of course :D I have never think like this solution :) It helps me so much, thank Ray again :)
•  » » » » » » » 7 years ago, # ^ |   +3 I got this solution 5 minutes after the contest, saddly. Then I waited hours for the system test to end. Finally I got 1AC.
 » 7 years ago, # |   +2 The evil test case 61 of LCM Challenge :|
 » 7 years ago, # | ← Rev. 2 →   +24 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...
•  » » 7 years ago, # ^ |   +2 Anyway,I think it's a good contest.I would like also thanks to xiaodao for the problems in Div.2.
•  » » 7 years ago, # ^ |   +1 This contest is very valuable, thanks to WJMZBMR and xiaodao. :D
•  » » 7 years ago, # ^ |   +5 Try to refresh the rating as quick as possible.
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +1 I suppose the system is calculating the rating change.
•  » » » » 7 years ago, # ^ |   +2 Then why does it take 30 minutes to recalculate it for 2000 people? The complexity is O(n).
•  » » » » » 7 years ago, # ^ |   +2 good question ! :D
•  » » » » » 7 years ago, # ^ |   +3 You know how it works? 'Cause i don't.
•  » » » » » 7 years ago, # ^ |   +2 How slow is that :( I think it's n^3 :)))))
•  » » » » » » 7 years ago, # ^ |   +1 Even it is n^3, it will be done in just one minute.
•  » » » » » » » 7 years ago, # ^ |   +1 :-? 2000^3 calculations in just one minutesOh yeah, may be n^4 :))))
•  » » » » » » » » 7 years ago, # ^ |   +1 Ha~~~But usually it is done in about ten minutes, I think.
•  » » » » » » » » » 7 years ago, # ^ |   0 Sure it is :D and the rating update has done :D
 » 7 years ago, # | ← Rev. 2 →   +68 Egor — the luckiest man of this contestHis E's submission 2402930 is only 14s to the contest end and runs 16ms to the time limit.
•  » » 7 years ago, # ^ |   +8 Well,He use some interesting strategy to reduce the time, It is just...very good job to do this cool stuff.
•  » » 7 years ago, # ^ |   +31 I optimized my solution until last possible moment. Actually it runs between 2950-3050 ms on server, so I got lucky indeed
 » 7 years ago, # |   +3 Ratings are now updated. Log off and on to see them.
 » 7 years ago, # |   0 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?
•  » » 7 years ago, # ^ |   0 It even shocked me .. The same code run at IDEONE is also throwing Exception http://ideone.com/7efDIa
•  » » » 7 years ago, # ^ |   0 i don't know java but use throws exception will lead u to correct runtime
•  » » » » 7 years ago, # ^ | ← Rev. 2 →   +3 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.
 » 7 years ago, # | ← Rev. 7 →   -16 I am quite shocked. My following simple Brute Force solution for DIV 2 Problem C:LCM Challenge got Accepted.. :D
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 This problem is very easy if you think carefully :)It include 3 cases1: 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 :)
•  » » » 11 months ago, # ^ |   0 nice observation but can you please provide proof of it
 » 7 years ago, # |   -17 Hi A short-solution programming contest will hold on October 24 at gpac.blog.ir
 » 7 years ago, # |   +4 the link for the tutorial is: http://codeforces.ru/blog/entry/5592
 » 7 years ago, # |   0 what does orz mean? and when when will you write editorial? I'm waiting for that :)
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Editorial and orz
•  » » » 7 years ago, # ^ |   +13 orz is used in Japan's net-slang terms. "orz" is used to show when you are in a quick depression and sad or have given up on something. 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?
 » 7 years ago, # |   +3 Orz