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.

First \m/

time is no good

best of luck to all

hoooray the contest is coming

Is that you are elder because your name is "eldar" :P (just joke)

Why I can't open "Codeforces.com" in English !? :(

Maybe this will help.

Thanx !

A contest right after witnessing an intense CodeJam Final http://code.google.com/codejam/contest/2437491/scoreboard

"The points distribution will be announced later."

Don't let it happen again, don't let it happen again...

Thanks, I totally forgot about it.

for i:=1 to 1000000 do writeln('Goodluck everybody and high rating');

Problems was so good! They was clear and understandable. Thank you gojira!

And Thanks for rapid SYSTEM TESTING!!!

OMG I did 5 hacks with only one test (in Div2 C) :

`1000000000 1000000000 2`

WTF and my solution got WA 44

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...

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...

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.

it's

`(2^(n + 1)-2)*k`

you can calc it using binpowoO 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.

hi Sir how you get this type of formula and intuition?

Recursion technique comes in. At least for me.

Let

a_{0}= 0 anda_{n + 1}= 2a_{n}+ 2k. Then the result after computingntimes (of the "addktimes 2" part) isa_{n}. (You can try it yourself.) Now we want to solve this recursion.There are now two ways: Guess (

a_{n}= (2^{n}- 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

a_{109 / k}. This is now simply (2^{109 / k}- 1)·2k, which I believe you know how?...it's posted above. But this gives the insight on how to get the result.

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 ;) )

when is the rating updated

I got rank 39 this time and it is my best rank. Thank you!!!

"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!

this contest is wonderfull i hope you take more contests in CF. thank you gojira

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?

Actually they were green!

Maybe that is because of the division...

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-338ESeems usually div1 is base contest and div2 contains "copy problems" but today vice versa. Note problem codes in problemset

In Div1-E Problem's statement, what is written in the picture? what language is it?

Chewa

It is a Georgian fairy tale in Georgian language :)

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 udalenniypotvv poddereve "pod" rebrom (v,u) vkluchayau. Kolichestvo reber 2n-2, dlya kajdogo vizova dfs zapominayetsya memo, t.e. itogo resheniye O(n log(n)). Pochemu to ne prohodit test #6k chemu minusi? eto ved' mesto chto bi zadavat' voprosi po zadacham

Perhaps transliteration is considered poor style.

Perhaps the multiplication

`p*g.size()`

is done in`[u]int32`

.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: 4291930

Williamacm's code for C: 4292531

I 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.

I found yongheng5871 and error202's codes for problem C are the same as sspa.

yongheng5871's code: 4293325

error202's code: 4293287

In Codeforces Round #194 (Div. 1), they four were found cheating already, and they cheated in this contest again!

I'll fix it :) Could you explain me why so many сhinese coders can't take part without cheating?

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.

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 .

I think so, too.

4294295 4295368

My best rank.Thanks to gojira Gerald and Seyaua!

So it seems like in Codeforces , delay time for system testing is inversely proportional to delay time for rating update ....

For div 2 participant already got new rating, why it delayed for Div 1 ?

I think they are handling cases caught in cheating like the one pointed out be yxdb and hence the delay.

why ratings for div1 participant hasn't been updated :|

One more case of copy-paste solution: 4294756 by kartimisin and 4291795 by enesoncu

The only difference is comment /*asgasdgasdg*/, I guess only to make source code look different to a trivial comparison:)

Sorry if this is considered redundant or spam, but nice contest (Y)

Nice problem