### gojira's blog

By gojira, 7 years ago, translation,

Hello everyone!

Codeforces Round #196 will begin in several hours (August 16, 20:00MSK).

You will mostly have to deal with Manao's problems, which this time range from watching movies and taking quizzes to treebuilding and battling evil undead.

I'd like to thank the following people for their contribution to this round's preparation: the Codeforces problem coordinator Gerald; Seyaua, who tested the problems; Delinur, who translated the problem statements into English; and Aksenov239, who proof-read the statements.

The points distribution in both divisons will be standard.

By the way, Sammarize mentioned he was probably the eldest author of a Codeforces round in the Russian version of his latest round's announcement. Since I'm even older, now I am holding the title ;)

The contest is over, I really hope that enjoyed it. The standings: Div1, Div2. Congratulations to top performers in Div1:

Congratulations to the winner of Div2, Ruthles, too!

The problem analysis is here.

• +263

 » 7 years ago, # |   -36 First \m/
 » 7 years ago, # |   -25 time is no good
 » 7 years ago, # |   +1 best of luck to all
 » 7 years ago, # |   0 hoooray the contest is coming
 » 7 years ago, # | ← Rev. 2 →   +7 Is that you are elder because your name is "eldar" :P (just joke)
 » 7 years ago, # |   0 Why I can't open "Codeforces.com" in English !? :(
•  » » 7 years ago, # ^ |   +1 Maybe this will help.
•  » » » 7 years ago, # ^ |   -7 Thanx !
 » 7 years ago, # |   +3 A contest right after witnessing an intense CodeJam Final http://code.google.com/codejam/contest/2437491/scoreboard
 » 7 years ago, # |   +28 "The points distribution will be announced later."Don't let it happen again, don't let it happen again...
•  » » 7 years ago, # ^ |   +25 Thanks, I totally forgot about it.
 » 7 years ago, # |   0 for i:=1 to 1000000 do writeln('Goodluck everybody and high rating');
 » 7 years ago, # | ← Rev. 3 →   +14 Problems was so good! They was clear and understandable. Thank you gojira!And Thanks for rapid SYSTEM TESTING!!!
 » 7 years ago, # | ← Rev. 2 →   +5 OMG I did 5 hacks with only one test (in Div2 C) : 1000000000 1000000000 2WTF and my solution got WA 44
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 I'm not very surprised: C div 2 / A div 1 was harder than usually, and the pretests didn't contain input with really big integers (only ~= 3 codes had "Limit time excedeed" on pretests after one hour on div 1). Somebody can explain the solution to this problem? I found this one very weird...
•  » » » 7 years ago, # ^ |   0 As we have to minimise the number of times, score get doubled, so we try to make maximum number of "k-1" blocks (k-1 consecutive correct answers), so we can find the maximum number of "k-1" blocks one can have using binary search, and after that, remaining answers will be correct consecutively, we put this block in thw beginning to minimise the score...
•  » » » » 7 years ago, # ^ |   0 Yes, I found this part, but I didn't know how to calculate this first big block: with 10^9 10^9 k, it is ((((k)*2+k)*2+k)*2....) 10^9/k times... With k very low, it can be slow to calculate it from classic maner and I don't see any way to use dynamic, binary search or other thing to calculate it.
•  » » » » » 7 years ago, # ^ |   +4 it's (2^(n + 1)-2)*k you can calc it using binpow
•  » » » » » » 7 years ago, # ^ |   0 oO I don't know why, but during contest, I was thinking that was on the form of something like: 2^(n1)*k+2^(n1-2)+2^(n1-4)*k ... I have been a little blind, the solution was a lot easier than I was thinking.
•  » » » » » 7 years ago, # ^ |   +3 Recursion technique comes in. At least for me.Let a0 = 0 and an + 1 = 2an + 2k. Then the result after computing n times (of the "add k times 2" part) is an. (You can try it yourself.) Now we want to solve this recursion.There are now two ways: Guess (an = (2n - 1)·2k) or use classic technique of solving recursions, characteristic equations. (You can read about the latter part in a lot of places. I'll also gladly explain when I'm awake enough; it's 1.30 am here, so probably later today.)Anyway. It's now simple. Since we want times, we want to find a109 / k. This is now simply (2109 / k - 1)·2k, which I believe you know how?...it's posted above. But this gives the insight on how to get the result.
•  » » 7 years ago, # ^ |   +1 And where I made a mistake was ...I needed to replace res %= MOD; with res = (res%MOD+MOD)%MOD;Today is not my day, today is tourist's day :D (Or maybe mine too ... 5 hacks ;) )
 » 7 years ago, # |   +14 when is the rating updated
 » 7 years ago, # |   +9 I got rank 39 this time and it is my best rank. Thank you!!!
 » 7 years ago, # |   0 "The problem analysis is here, but I did not manage to translate it into English fully yet." the link of 'here' is incorrect! It linked to 8615 entry, but it has to link to 8629 entry!The problem analysis is here!
 » 7 years ago, # |   +20 this contest is wonderfull i hope you take more contests in CF. thank you gojira
 » 7 years ago, # |   +7 Maybe it's not the most appropriate place to ask. But why solved problems from this contest in problemset are not marked green as they always were?
•  » » 7 years ago, # ^ |   0 Actually they were green!
•  » » » 7 years ago, # ^ |   +4 Maybe that is because of the division...
•  » » » » 7 years ago, # ^ |   +7 I think this happened because # of problems, for example:Contest 328, 329 problems: 328A-328B-329A-329B-329C-329D-329EBut this Contest (337, 338): 337A-337B-337C-337D-337E-338D-338E
•  » » 7 years ago, # ^ |   +1 Seems usually div1 is base contest and div2 contains "copy problems" but today vice versa. Note problem codes in problemset
 » 7 years ago, # |   0 In Div1-E Problem's statement, what is written in the picture? what language is it?
•  » » 7 years ago, # ^ |   +1 Chewa
•  » » 7 years ago, # ^ |   +3 It is a Georgian fairy tale in Georgian language :)
 » 7 years ago, # |   -46 Kto nibud' mojet obyasnit' pochemu eto resheniye nepravilnoye? http://codeforces.com/contest/338/submission/4297116. Delayetsya dfs s memoizaciyey. Zapominayetsya dlya kajdogo napravlennogo rebra ( v , u) naibolee udalenniy p ot v v poddereve "pod" rebrom ( v, u) vkluchaya u. Kolichestvo reber 2n-2, dlya kajdogo vizova dfs zapominayetsya memo, t.e. itogo resheniye O(n log(n)). Pochemu to ne prohodit test #6
•  » » 7 years ago, # ^ |   -34 k chemu minusi? eto ved' mesto chto bi zadavat' voprosi po zadacham
•  » » » 7 years ago, # ^ |   +14 Perhaps transliteration is considered poor style.
•  » » 7 years ago, # ^ |   +13 Perhaps the multiplication p*g.size() is done in [u]int32.
 » 7 years ago, # |   +97 sspa and Williamacm are cheating in this contest, AGAIN!their codes for problem C (338C - Divisor Tree) are almost the same, where the only a few differences are some variables' name.sspa's code for C: 4291930Williamacm's code for C: 4292531I found out their cheating last time in Codeforces Round #194 (Div. 1). I think CF team should pay more attention to cheating behaviour in contests.
•  » » 7 years ago, # ^ |   +45 I found yongheng5871 and error202's codes for problem C are the same as sspa.yongheng5871's code: 4293325error202's code: 4293287In Codeforces Round #194 (Div. 1), they four were found cheating already, and they cheated in this contest again!
•  » » » 7 years ago, # ^ |   +11 I'll fix it :) Could you explain me why so many сhinese coders can't take part without cheating?
•  » » » » 7 years ago, # ^ |   +18 Maybe cause we have so large amount of population? I think the percentage of cheating isn't distinctly different among many countries.I feel so ashamed about this.
•  » » » » » 7 years ago, # ^ |   +3 Its interesting that , code of all six cheater is same and all six is from same university/state , may be they all participated from same room in a team and shared each other code and idea .
•  » » » » » » 7 years ago, # ^ |   +3 I think so, too.
•  » » 7 years ago, # ^ |   +11
 » 7 years ago, # |   +23 My best rank.Thanks to gojira Gerald and Seyaua!
 » 7 years ago, # |   +69 So it seems like in Codeforces , delay time for system testing is inversely proportional to delay time for rating update ....
•  » » 7 years ago, # ^ |   +64 For div 2 participant already got new rating, why it delayed for Div 1 ?
•  » » » 7 years ago, # ^ |   +24 I think they are handling cases caught in cheating like the one pointed out be yxdb and hence the delay.
 » 7 years ago, # | ← Rev. 2 →   +44 why ratings for div1 participant hasn't been updated :|
 » 7 years ago, # |   +40 One more case of copy-paste solution: 4294756 by kartimisin and 4291795 by enesoncuThe only difference is comment /*asgasdgasdg*/, I guess only to make source code look different to a trivial comparison:)
 » 7 years ago, # |   +5 Sorry if this is considered redundant or spam, but nice contest (Y)
 » 7 years ago, # |   +5 Nice problem