### gridnevvvit's blog

By gridnevvvit, 8 years ago, translation,

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 (ai9128429340875). 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:

• +164

 » 8 years ago, # |   +41 Can't wait, hopefully it won't be too much maths :D
 » 8 years ago, # | ← Rev. 2 →   -7 a
 » 8 years ago, # |   +5 I think it will be interesting.
 » 8 years ago, # |   -9 Good Luck ^_^
 » 8 years ago, # |   -24 I hope the system testing starts soon after the contest not like the last contests.
•  » » 8 years ago, # ^ |   -20 System testing after contest starts when authors of task check all hacks.
•  » » » 8 years ago, # ^ |   +5 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.
 » 8 years ago, # |   -23 it will be better that there will be input and output files
 » 8 years ago, # |   -18 Welcome ! New authors always have interesting problems I think today it will be too :)
 » 8 years ago, # |   -24 One of the best announcements I ever read !!
 » 8 years ago, # | ← Rev. 2 →   -13 Wow! It's my first Codeforces round and authors too, what a coincidence! It should be stunning round as I think. I wish you good luck and high ratings!!))))
 » 8 years ago, # |   0 i hope today will be my day :))
•  » » 8 years ago, # ^ |   0 oh oh oh, abo's day its unbelievable :D :D
•  » » » 8 years ago, # ^ |   -40 fuck you nikalosaberidze
 » 8 years ago, # |   -11 gl & hf all! :)
 » 8 years ago, # |   -6 This is my first contest in codeforces, hope i can solve some problems in the contest
•  » » 8 years ago, # ^ |   +10 best of luck, buddy.....:)
•  » » » 8 years ago, # ^ |   0 thanks , pray for me , best of luck to you also
 » 8 years ago, # |   0 Good luck everybody. I hope today will be lucky contest for all
 » 8 years ago, # |   -11 Hello, I'm Commander Sheppard and this is my first contest on Codeforces!
 » 8 years ago, # |   +3 Hope to solve at least 3 problems :)
 » 8 years ago, # |   0 i had registered.now when i am trying to submit its telling me to submit u have to be registered :(
 » 8 years ago, # |   0 what'er pity not joinning this contest= =..dynamic scoring could be really exciting and fun T____T...hope to reach 1700 T_T
 » 8 years ago, # | ← Rev. 3 →   +12 WTF??? UPD: he has already -179 hacks... 
•  » » 8 years ago, # ^ |   +13 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..."
•  » » 8 years ago, # ^ |   -7 Now he has 215 unsuccessful hacks
•  » » 8 years ago, # ^ |   +9 Психанул!)
•  » » 8 years ago, # ^ |   0 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:)
•  » » 8 years ago, # ^ |   0 우리의 위대한 지도자 김 장군의 명예에, 나는 미국 제국주의를 정복 할 수있을만큼 우리 민족 강하게 만들기 위하여 열심히 컴퓨터 과학을 공부합니다!
•  » » » 8 years ago, # ^ |   0 Your letters are so cute :)
 » 8 years ago, # |   -12 what is the 5th test in B problem??? "@
 » 8 years ago, # |   +2 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 equationN = 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
•  » » 8 years ago, # ^ |   +2 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.
•  » » 8 years ago, # ^ |   0 n!/(x!*y!) — number of different numbers of length n and containing x of "a" digits and y of "b" digits.
•  » » » 8 years ago, # ^ |   +9 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
•  » » » » 8 years ago, # ^ |   0 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 )
•  » » » » » 8 years ago, # ^ |   +6 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 ) .
•  » » » » » » 8 years ago, # ^ |   +1 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.
•  » » » » » » » 8 years ago, # ^ | ← Rev. 3 →   +1 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.
•  » » » » » » » » 8 years ago, # ^ |   0 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 : // ax + by = gcd(a,b) = d void eea(int a, int b, int& x, int& y, int& d) { if (!b) {x = 1; y = 0; d = a; return; } eea(b, a % b, x, y, d); int x1 = y, y1 = x - (a / b) * y; x = x1, y = y1; } int divide(int a, int b) { int d, x, y; eea(b, MOD, x, y, d); // if(a%d==0) return ((x+MOD)*(a/d)) % (MOD/d); // else "no quotient" } both run in O(logn) time. however, pow(k,mod-2) is a lot easier... ;)
•  » » » » » » » » » 8 years ago, # ^ |   0 so that was my fault, I misunderstood you. :)
•  » » » » 8 years ago, # ^ |   0 "from the "Number Theory" : (1 / b) % mod == ( b^(mod-2) ) % mod , because mod is a prime number !"Could you provide references to this proof?
•  » » » » » 8 years ago, # ^ |   0 from "fermet's little theorem" : a^(p-1) % p = 1thus 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) % pfinally : (1/a) % p == a^(p-2) % p
•  » » 8 years ago, # ^ |   0 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.
•  » » 8 years ago, # ^ |   0 I did something similar except I did:(N-i)*a + (N-j)*bStarted with i = 0 and b = N and as I incremented one, I decremented the other...Then i checked if the number resulting was good or not and if it was then I thought about using some sort of combinations trick... As it worked for the 2nd example case 10C8 + 10C7 where 8 and 7 were the highest values of pair (i,j) for every case, but, I got lost in the middle of it... Can anyone help?
 » 8 years ago, # |   0 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. :(
 » 8 years ago, # |   -7 I think the problem more difficult than before.. a lot of counter testcase..
 » 8 years ago, # |   0 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!
 » 8 years ago, # |   0 When is the rating come out??
 » 8 years ago, # |   0 Nice contest, keep up the good work.
 » 8 years ago, # |   -26 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 zerowhere as your pretext 3 test case is : Input 5 -1 -2 1 2 0 Output 1 -2 3 -1 1 2 1 0This is incorrect. List 2 doesn't have a positive product. -1 * 1 * 2 = -2 is NEGATIVE. WRONG TEST CASE.
•  » » 8 years ago, # ^ |   +5 It's your output, not jury's.
•  » » 8 years ago, # ^ |   0 The test case is correct only. The correct output is 1 -1 2 1 2 2 -2 0
•  » » 8 years ago, # ^ |   +3 ohh.. sorry.. got it now. i read it in the incorrect order... thanks.
 » 8 years ago, # |   0 what's the idea of problem D
 » 8 years ago, # | ← Rev. 2 →   0 UPD :
 » 8 years ago, # |   +2 Hey a newbie question but I can't seem to find it in the FAQ or anywhereHow 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.
•  » » 8 years ago, # ^ |   0 It takes around 2 or 3 hours to update your rank.
 » 8 years ago, # |   -11 my first contest still rating is not updated ? why always me ?
•  » » 8 years ago, # ^ |   0 Your rating will be updated soon..it takes little time to update ratings. Happy coding :)
 » 8 years ago, # |   +2 Problems were quite interesting.Hope to see you again soon.
 » 8 years ago, # |   0 this round was better than I expect !