Hello!

A few hours later, 25 апреля в 19:30 MSK, you are lucky to participate in Codeforces Round #181 for Div. 2 participants. Traditionally, Div. 1 participants can take part out of the competition.

Problems have been prepared by: Gridnev Vitaliy (gridnevvvit), Ignatyev Alexander (aiMR). We want to thank Gerald Agapov(Gerald) for help in preparation of this round, Michael Mirzayanov(MikeMirzayanov) for marvelous Codeforces and Polygon systems, Mary Belova(Delinur) for translating the problems.

About authors: me and Alexander are third year students of Mathematics Department, Saratov State University. It’s our first round and I hope not last.

We hope you will like these problems, and that it will be fun to solve them.

Also we strongly recommend you to read all the problems.

We wish everyone good luck and high rating!

**UPD: Scoring will be dynamic. Problems are sorted by increasing order of difficulty**.

**UPD1**: Editorial here

**UPD2**: Contest finished. Congratulations to winners:

Can't wait, hopefully it won't be too much maths :D

a

I think it will be interesting.

Good Luck ^_^

I hope the system testing starts soon after the contest not like the last contests.

System testing after contest starts when authors of task check all hacks.

I think it's not true because all hacks are checked automatically by validator.

I suppose that main reason of our waitin' is that validator checks all the hacks.

Welcome ! New authors always have interesting problems I think today it will be too :)

One of the best announcements I ever read !!

i hope today will be my day :))

oh oh oh, abo's day its unbelievable :D :D

gl & hf all! :)

This is my first contest in codeforces, hope i can solve some problems in the contest

best of luck, buddy.....:)

thanks , pray for me , best of luck to you also

Hello, I'm Commander Sheppard and this is my first contest on Codeforces!

Hope to solve at least 3 problems :)

what'er pity not joinning this contest= =..dynamic scoring could be really exciting and fun T____T...hope to reach 1700 T_T

Codeforces was down. But how could lrb know about it? He was sure that the solution was incorrect. He pressed and pressed the button

`Hack!`

but nothing was happening. "Ok, I'm going to count how many times I pressed that damned button!", he thought: "66, 67, 68! Codeforces is available again! Let's see where my +100 points are..."Now he has 215 unsuccessful hacks

Психанул!)

When I saw that lrb wanted to hack my code my heart started boom boom boom:)I thought that my solution is wrong:)but when i saw that he has more than 100 unsuccessful hacks i understood that he want to break record and i calmed down:)

우리의 위대한 지도자 김 장군의 명예에, 나는 미국 제국주의를 정복 할 수있을만큼 우리 민족 강하게 만들기 위하여 열심히 컴퓨터 과학을 공부합니다!Your letters are so cute :)

what is the 5th test in B problem??? "@

Hey, really enjoyed this competition, but i got a little problem with problem C. So im asking you for little help.

Here is what i came up with: We generate all possible sums ( highest possible sum has 6 digits ) and make equation

N = x*a + y*b, where N is our sum ( we do this with every generated sum ).

And we find number of solutions to this equation that: x>0, y>0 and a+b<=N ( it's pretty

clear ).

For most of my time i was trying to come up with some nice dp solution, but it turned

out to be impossible for me... If it's one right solution desribed above, then please explain to me how to calculate

those all solutions nicely?? Because for me it got too messy and i finished with only 2

first tasks :(

:) Thanks in advance

I think that answer is sum(C(n, x)) if N = x*a +y*b is good, but there is small problem for me, how fast and correct calc C) Sorry for my bad english.

n!/(x!*y!) — number of different numbers of length n and containing x of "a" digits and y of "b" digits.

You can use this : C( n , k ) = n! * pow( (n-k)! * k! , mod-2 )

from the "Number Theory" : (1 / b) % mod == ( b^(mod-2) ) % mod , because mod is a prime number !

Sorry for my bad english

i knew there is must be using some number theory, but, sadly after knowing a and b value, i cant compute C(n,a)

could you explain more with n = 14215 and k = 13517 ?

thx (taken from test 3 )

only pre-calculate every factorials module 1000000007 and store this numbers in an array .( for example fact array ) this step takes O(N) time and space .

then C( n , k ) = fact[n] * power( fact[k] , mod-2 ) * power( fact[n-k] , mod-2 ) . this step takes O( Log N ) .

or calculating c(n,k) using c(n,k-1) c(n,k) = c(n,k-1)*(n-k+1)/(k)

but as Reza said, we have to pre-caculate them.

actually this wont work !

because there is no necessity that c(n,k-1)%MOD or (n-k+1) is divisible by k.

this will lead you to WA.

of course!

i didn't mention that for dividing u need to use modular division, i just said that this is another way tu calculate c(n,k)...

for dividing u can use pow(k, mod-2)(as Reza said) or use Extended Euclid algorithm :

both run in O(logn) time. however, pow(k,mod-2) is a lot easier... ;)

so that was my fault, I misunderstood you. :)

"from the "Number Theory" : (1 / b) % mod == ( b^(mod-2) ) % mod , because mod is a prime number !"

Could you provide references to this proof?

from "fermet's little theorem" : a^(p-1) % p = 1

thus a * a^(p-2) % p = 1 and a % p == a^(p-2) % p from other view a * ( 1/a ) % p = 1 and a % p == (1/a) % p

finally : (1/a) % p == a^(p-2) % p

the same idea, but a little bit differences. x is the number of digits a still have sum=a*x+b*(n-x) (a,b from input), for each single value of x, i check whether sum is a good number. if yes, calculate number of numbers you can create with that.

the only problem that i had is the final step.

I can't believe that my B is going to fail because I forgot to check if the "connected-team" size is less than or equal to 3, submitted and locked it. Just after I locked it I remembered that. :(

I think the problem more difficult than before.. a lot of counter testcase..

I loved the contest, especially C, got it accepted at the last minute (stupid overflow mistake :(). This is when you have to love the dynamic scoring :)

Thanks!

When is the rating come out??

Nice contest, keep up the good work.

The problem A — Array in the description it guarantees a correct solution: 1st list -product should be negative 2nd list — product should be positive 3rd list — product should be zero

where as your pretext 3 test case is : Input 5 -1 -2 1 2 0 Output 1 -2 3 -1 1 2 1 0

This is incorrect. List 2 doesn't have a positive product. -1 * 1 * 2 = -2 is NEGATIVE. WRONG TEST CASE.

It's your output, not jury's.

ohh.. sorry.. got it now. i read it in the incorrect order... thanks.

what's the idea of problem D

UPD :

Hey a newbie question but I can't seem to find it in the FAQ or anywhere

How long does it take for ratings to change after a competition?

I go back to sleep right after matches (I'm in Austrlia) so I don't find out.

It takes around 2 or 3 hours to update your rank.

my first contest still rating is not updated ? why always me ?

Your rating will be updated soon..it takes little time to update ratings. Happy coding :)

Problems were quite interesting.Hope to see you again soon.

this round was better than I expect !