### Malinovsky239's blog

By Malinovsky239, 10 years ago, translation,

Hello everyone!

Today, at 19:30 MSK Codeforces Round #140 will take place. The competition will be held in both divisions.

I'am the author of today's competition. My name is Ilya Malinovsky, I'm student of Saint-Petersburg State University. This is my first Codeforces round.

I want to express my gratitude to Gerald Agapov (Gerald) for his help during the work on the round, Maria Belova (Delinur) for statements' translation from Russian into English, Mikhail Mirzayanov (MikeMirzayanov) for the possibility to prerare contests (and, of course, to compete in them) here, on Codeforces.

As usual, in most of the problems participants will help different characters to cope with their troubles and misfortunes. You will have only two hours to help epical hero, an alien, noble knight and other characters. Also, insidious stone heaps will resist you in one of the problems...

I hope, most of participants will enjoy the tasks.

Good luck!

P.S. Information about score distribution will appear not long before the round starts.

upd. Score distribution is stadart (500-1000-1500-2000-2500) in both divisions.

upd 2 Round is over!

Congratulations for winners!

#### div1:

Winners have from 3 to 4 solved problems. Noone managed to solve E.

#### div2:

1. Velicue (he is the only div2-participant, who got 5 "OK"s)

2. Frommi

3. Aerolight

4. Shahriar_sust

5. bzdbz

Thanks to everyone for participating! I hope, you've enjoeyd the round.

Full editorial.

• +235

 » 10 years ago, # |   +4 I have a question. In round #138 they explicitly said that "D language will not be available on this contest.". In the emails I get I don't ever see it mentioned in the list of available languages. What's up with that? :)
•  » » 10 years ago, # ^ |   +1 You may use it on your own risk. We will announce official support after we will be sure that everything is OK.
 » 10 years ago, # |   -7 I have the impression that today... tourist, again surpass the 3000 points ... A new range? Something like Intergalactic Grandmaster? LOL
•  » » 10 years ago, # ^ |   0 tourist was here 5 days ago.
•  » » 10 years ago, # ^ |   +21 He is in Italy probably(IOI), so I don't think so :)
•  » » 10 years ago, # ^ |   0 i have a dream
 » 10 years ago, # |   -16 Can somebody explain C. I can't understand it :(
 » 10 years ago, # |   -19 why my C got wrong answer at pretest 1? I already same as the sample IO
 » 10 years ago, # |   +9 Anyone search ideas from Google for E(Div 2)/C(Div 1) like me?
•  » » 10 years ago, # ^ | ← Rev. 2 →   +6 We can use fact, that gcd(Fibx, Fiby) = Fibgcd(x, y). But I have still no correct idea how to get subset with maximal gcd(since binary search is wrong).
•  » » » 10 years ago, # ^ | ← Rev. 2 →   +5 def d_down( r,l,k ): d = (r-l)/(k-1) ### 1 below while d > 1: ### 4 below if (1+(r/d)-((l+d-1)/d))>=k: return d ### 2 below N = 1 + (r/d) ### 3.2 below d -= ( ((N*d)-r) + (N-1) ) / N ### 3.4 below return 1 """ basically 1) (r-l)/(k-1) is the maximum possible d, given r, l and k 2) the if...return tests if k d's fit between l and r 3) if not, then d must decrease; can't loop decrement (d-=1) with 1E12 ranges, so 3.1) R = d * (1 + r/d) is a multiple of d greater than r, and 3.2) N = (1 + r/d) is the multiplier of d that gets to that R = N*d, so 3.3) (N*d - r) is how far R has to drop to be <= r, so 3.4) ((N*d-r) + (N-1)) / N is the minimum decrease in d which will drop R to <= r 4) go back to 2) above, with decreased, new d e.g. input m,101,200,2 (answer is 66: *2=132; *3=198) Initial d = 200 - 101 = 99 but only one multiple of 99 between 101 and 200 inclusive, i.e. 198 101 200 ## boundaries r and l 99 198 297 ## multiples of max possible d; R=297; N=3 and if you start decreasing d from 99, then 98 196 294 ## multiples of d-1 97 194 291 ## multiples of d-2 ... so, as d decrements, the numbers on the right (3*d) move faster (3x decrease in d) to get inside 200 than the numbers in the middle (2*d) move to go past 101 (2x decrease in d). the number on the right reaches (or passes) r when 3*d <= 200 i.e. the decrease in d will be the formula in 3.4 above i.e. ( (3*99 — 200) + (3-1) ) / 3 = 33.the only question is whether 2*d has by that time dropped below l (101), but if it has then repeat the loop.
•  » » » » 10 years ago, # ^ |   0 i was one typo (put the modulo on the wrong side of a parenthesis) and about five minutes from modulo-izing my fib(n) routine when time ran out.
•  » » » » 10 years ago, # ^ |   0 but i still have not understood the (3^n-1) approach below. what is F(N)?
•  » » » » » 10 years ago, # ^ |   0 oops, 3^n-1 is Div2-C/Div1-A
•  » » » » 10 years ago, # ^ |   +1 If you want ugly, it's only 11 lines of python: import sys def recfib(n,m): if n==0: return (0,1,) a, b = recfib(n / 2,m) return ( [ a*(((2*b)-a)%m), ((b*b)%m)+((a*a)%m)][n%2], [ ((b*b)%m)+((a*a)%m), b*((2*a+b)%m)][n%2], ) m,l,r,k = map( int, sys.stdin.readline().strip().split()[:4] ) D = (r-l)/(k-1) while D > 1 and (1+(r/D)-((l+D-1)/D))
•  » » » » » 10 years ago, # ^ |   0 and it's faster in python than any div 2 C++ solution, and faster than most of the div 1 C++ solutions.
•  » » » » » 10 years ago, # ^ |   0 Nice solution! Can you explain that the meaning of (a, b) in a, b = recfib(n, m)I guess a is the n(th) fib number. But what's b?
•  » » » » » » 10 years ago, # ^ | ← Rev. 3 →   0 can't say exactly without thinking (under time pressure during the round I just use the code I find: good coders borrow; great coders plagiarize/steal/google), but the second return value is there because it's needed during a recursive approach to the solution.recfib uses recursion to calculate fib numbers. if argument n is not 0, it is divided by two and passed recursively to the next call. There are apparently some well-known formulae:  F(2j) = F(j)^2 + F(j+1)^2 F(2j+1) = (2F(j) + F(j+1))*F(j+1) F(2j-1) = (2F(j+1) - F(j))*F(j) which lends itself to this O(log2(n)) approach (cf. E.W. Djikstra, http://www.cs.utexas.edu/users/EWD/ewd06xx/EWD654.PDF). The two return values are there because the recursed call doesn't know if argument n came from (2n)/2 or (2n+1)/2.ETA: I looked into this some more.The first element of the returned tuple of a call to recfib(n) is FIB(n); the second element is FIB(n+1); from those two you can construct either FIB(2n) or FIB(2n+1), as needed
•  » » » » » 10 years ago, # ^ |   0 Your code cannot pass the tests. You put the '%m' in wrong places. After my modification it passed. And, spliting the long long return statement in recfib using the V1 if C else V2 expression would make the code faster, since that can supress the useless evaluation.  return ((b*b+a*a)%m, b*(2*a+b)%m) if n%2 else (a*((2*b)-a)%m, ((b*b+a*a))%m) See, it's only 80 chars. You don't even need to break the line.
•  » » » » » » 10 years ago, # ^ |   0 Thanks, you are right, I forgot about the ternary operator added in 2.5 that will short-circuit to evaluate just one of the paths. I just read about it the other day, too.And yes, the version I posted is not the one that worked: I added %m's after the [n%2] selectors in the return statement and it passed. Actually, your version may not pass if, for example, (b*b+a*a) overflows. Ihat's why I put so many %m ops in there. And I still think either mine or yours could fail if given the right parameters; using this construct ((VALUE%m)+m)%m) a few times should fix it though. Python may be hiding some of our problems and be more robust here because of automatic type promotion on overflow.Btw, I got it down to 10 lines (raw_input() instead of "import sys" & sys.stdin.readline()). That uses the ugly return construct, but the important thing to note is that the guts of the program, the GCD loop, only takes four lines.
•  » » » » » » » 10 years ago, # ^ |   0 Actually, you don't need so many '%m' in python. For example, it will convert to long for you automatically if a*a+b*b run out of the range of int. And -1 % 5 == 4 in python.Btw, after I copy your code to my editor, the first thing I do is to remove the import line and replace sys.stdin... by raw_input().split().
•  » » » » » » » » 10 years ago, # ^ | ← Rev. 2 →   0 thanks.i know python promotes the type on overflow, i'm just cautious and then i don't have to think about the range of m.and thanks for the raw_input() thing; i know it's there but i think that changes or breaks in V3 so i tend to not use it a lot; again, i'm cautious.i didn't know % alway goes to a positive number; i started doing the extra +m)%m in C++. but since that's the case then even overflows are not a problem.hey, could the %m generate a premature n==0 in the recursive fib routine? would it matter?
•  » » » » » » » » » 10 years ago, # ^ |   0 The first argument of recfib, namely n, will not affected by m.
•  » » » » » 10 years ago, # ^ |   0 2251104 Even shorter(7 lines) with functional style. Accepted. def recfib(n,m): if n == 0: return (0, 1) a, b = recfib(n / 2,m) return ((b*b+a*a)%m, b*(2*a+b)%m) if n%2 else (a*((2*b)-a)%m, ((b*b+a*a))%m) def next_d(D): return D if 1+r/D-(l+D-1)/D>=k else next_d(D-(D-r%D+r/D)/(1+r/D)) m, l, r, k = map(long, raw_input().split()) print recfib(next_d((r-l)/(k-1)), m)[0] # Trick to remove N from the code: N = 1 + r / D # D -= (N*D-r + N - 1)/N # N*D - r = (D + r - r % D - r) = (D - r % D) # N*D - r + N - 1 = D - r % D + r / D 
•  » » » » » » 10 years ago, # ^ |   0 sweet!defintion for recursion: see recursion.
•  » » » » 10 years ago, # ^ |   0 A really nice solution Thank you !
 » 10 years ago, # |   +1 In my opinion, these OEIS problems don't add anything to the contest.
•  » » 10 years ago, # ^ |   0 Well I did it figuring out on paper and still made a noobie mistake.((3^n — 1)+MOD)%MOD is the answer. I guess you never forget to do this once you lose 900points. >_<(I did the 3^n part efficiently and correctly)
•  » » » 10 years ago, # ^ |   0 Same method but WAed!
•  » » » » 10 years ago, # ^ |   0 Is that not the answer? Ruh ruh.
•  » » » » » 10 years ago, # ^ | ← Rev. 2 →   -9 Edit:How come the font become enlarged? --> WA with 6th pretest case
•  » » » » » » 10 years ago, # ^ | ← Rev. 2 →   0 Use long long instead int .
•  » » » 10 years ago, # ^ |   0 Maybe you CAN figure it out on paper but it's so much faster this way... so you have to take the easy way to stay ahead of competition.
•  » » » » 10 years ago, # ^ | ← Rev. 3 →   +3 F(N) = 3*F(N-1) + 2 F(1) = 2 F(2) = 3*F(1) + 2 F(2) = 3*2 + 2 F(2) = 3*2 + 3 - 1 F(2) = 3 (2+1) - 1 F(2) = 3^2 - 1 ... F(N) = 3^N - 1 `Took me a bit to turn the 2 into a 3-1 though :( I'm out of practice.
•  » » » » 10 years ago, # ^ |   +13 I disagree, realizing the solution required a little thinking, and it wasn't some obscure formula or some numbers that are hard to compute. I even think that for some it was even faster thinking about the solution. If you don't try to think the easy problems, how do you expect being able to think the hard ones? That's the way you'll stay ahead, thinking
•  » » » 10 years ago, # ^ |   0 Indeed, I forgot to write +MOD thing and lock my problem like a fool... 900 points lost will be a real tragedy.
•  » » » » 10 years ago, # ^ |   0 same with me :( lost 1344 points
•  » » 10 years ago, # ^ |   0 The fun part is not using OEIS. I think it was a nice problem
•  » » 10 years ago, # ^ |   +1 [PlayLikeNeverB4: In my opinion]See my comment below re normative. I'm not sure if you are referring to Div-2/C or /E, but I thought they were great problems. A bit of knowledge, or maybe a chat with the Google, a little insight, and then coding it right, which was the real challenge in both cases to avoid the TLE, and WA if the modulo operation is not done right.The OEIS is just the turf on which the game i played. Think of yourself as TRON.
 » 10 years ago, # |   0 I can't understand, why my O(8log(10^12)) got TL. Submission #2245668 ?
•  » » 10 years ago, # ^ | ← Rev. 2 →   +3 Well, for Problem B(div1)/D(div2), you will get TLE if you don’t use some technique to remember the answer you printed each time. This is because there exists cases that all k equal to 1. That's how I got TLE for the first time.
•  » » » 10 years ago, # ^ |   0 I just remembered the case k=1. I hope it doesn't get time out
•  » » » 10 years ago, # ^ |   +1 But I meant problem E div2
 » 10 years ago, # |   0 Problem E in div2 is quite tricky...when I realized what i had done wrong it's all too late. congrats to those who solved this problem successfully.
•  » » 10 years ago, # ^ |   0 Congratulations to Velicue for the only contestant to solve E.
 » 10 years ago, # |   0 How can we solve DIV 2 E ? How can we get the maximum gcd of all the k element subsets between L and R ?
 » 10 years ago, # |   0 Anyone thinks that A in Div2 is more difficult than B?
•  » » 10 years ago, # ^ |   0 Solution in one phrase : cross product. Without that it'll be a bit troublesome.
•  » » » 10 years ago, # ^ |   0 I did take out cross products but got WA on test 31 .[code] .. Can anyone tell me what did I do wrong because I cannot see the test case until the system test is over ... And the system test is playing with my patience by being slow
•  » » » » 10 years ago, # ^ |   0 Floating point number is not accurate enough. use integers instead.
•  » » » » » 10 years ago, # ^ |   +1 Correction — > long because int will overflow :P
•  » » 10 years ago, # ^ |   +2 I do, but only because I suck in geomtry.
•  » » 10 years ago, # ^ |   0 Well, I don't know cross product but managed to get AC by writing several ifs. It's easier since it's guaranteed that ABC makes up either right angle or straight line
 » 10 years ago, # | ← Rev. 4 →   +6 The problemsets are good, thanks, Malinovsky239. However, some statement clarifications are wanted. Thanks for any reply.div2(D)/div1(B):"each pile will let you add to it not more than k times (after that it can only be added to another pile)". Assuming adding pile i to pile j, we name i as addend, j as summand, then is the constraint saying which role(addend or summand) can be used at most k times?div2(E)/div1(C): "for each such subset let's find the largest common divisor of Fibonacci numbers with indexes", does this refers to the elements of subsets indexing at 1,2,3,5,8...?
 » 10 years ago, # |   +4 Binary search in Div1.C is incorrect :( l=7, r=14, k=2: 7 — ok 6 — not
•  » » 10 years ago, # ^ | ← Rev. 10 →   0 I think You can try to use dp: Let dp[i] is the minimum step to move n-i+1 alien (i..n) from section 3 to 1 (or section 1 to 3)So dp[i] = dp[i+1] + dp[i+1]*2 + 2 ( because we have to move i th alien from section 3 to 2 move n-i+2 alien (i+1..n) from section 1 to 3 move i th alien from section 3 to 1 move n-i+2 alien (i+1..n) from section 3 to 1 ) **Upd: Sorry, I think you say Problem C div 2.Probielm C div 1, you can use gcd(fibonacci(a), fibonacci(b)) = fibonacci(gcd(a, b)) Then you can try to understand dp[i] = 3^(n-i+1) — 1
•  » » » 10 years ago, # ^ |   +8 sorry, but it's not C(Div.2)?
•  » » » » 10 years ago, # ^ |   0 Sorry, I think iTwin say problem C div 2 :D
•  » » 10 years ago, # ^ |   0 what is special about test case number 106. why binary search does not work ?
•  » » » 10 years ago, # ^ |   +1 Check test 12345678 7 14 2
•  » » » » 10 years ago, # ^ |   +1 mine code is outputting 13 which is right i guess. http://codeforces.com/contest/226/submission/2246243
•  » » » » » 10 years ago, # ^ |   +1 What about this test 123456789 100000000000 300000000000 3 какой ответ? Right answer is 33025443
•  » » » » » » 10 years ago, # ^ |   0 Thanks.
 » 10 years ago, # |   +5 Message received from user "messsi" during todays contest:"send me you code of A please man and i send me code of B ok???? this is my code of B now you send me your code please/* His problem b code here.. */"
•  » » 10 years ago, # ^ |   +7 Did his B pass? :D
 » 10 years ago, # |   0 Using "int" instead of long long caused system test fail (A. div 2) :(
•  » » 10 years ago, # ^ |   +1 Thats obvoious becuase range was 10^9 .. So int * int will overflow
 » 10 years ago, # |   +41
•  » » 10 years ago, # ^ |   +3 Nice idea to stream video. Streamers usually use 3-minuts delay and stream online.
•  » » » 10 years ago, # ^ |   +3 It is not viable even with delay
 » 10 years ago, # |   +2 Based on the number of people solving, C and D should be exchanged their order in Div 1.
 » 10 years ago, # |   +3 also in Div. 2 , A and B should change their order based on difficulty level or no. of people solved.
•  » » 10 years ago, # ^ |   0 No, binary search and sorting are more difficult than school geometry.
•  » » » 10 years ago, # ^ |   +4 I suck at geometry and honestly I don't really like it either. And like me are a lot of Div2 participants.
•  » » » » 10 years ago, # ^ |   +2 maybe, be we all suck at something. i had no idea about the GCD(FIB(N),FIB(M)) = FIB(GCD(N,M)) thing, but a quick google of GCD and fibonacci, plus a bit of number sense, and I was five minutes from being only the second Div-2 participant to solve E during the contest (it was trivially solved in my mind once I talked to the Google). At the same time, I still don't have a clue how to approach the lower-rated Div-2/D (I know it's probably DP from looking at others' code but the application of DP is still somewhat of a black art to me). I know you (Play...B4) have number sense because of your F(N)=3^n-1 derivation for Div-2/C, so you could have been one conversation with the Google away from solving E, too.So what PlayLikeNeverB4 is saying is that PlayLikeNeverB4 is normative — "... and like me are lot of Div2 participants." I am Div2 and have been doing geometry almost daily for at least of couple of dozen years. That was a trivial problem to me, but I understand that not everyone has the same strengths. But if you have been doing this for a number of years and haven't at least spent the time to understand some basic geometry (cross- and dot-product problems are not at all rare), then you will always be Div-2 (like me: DP is my insurmountable hurdle, apparently).And bilbo1 may be saying that bilbo1 is normative. The original posts, "Based on the number of people solving, ..." are probably the closest to stating what is actually normative, but people that do programming contests are self-selecting so even that sampling is suspect.What I would like to say is that Malinovsky239 made up an excellent problem set (with the difficulty ratings based on assuming Malinovsky239 is normative?;-) and second-guessing the difficulty level is a bit impolite without at least complimenting the problemset author on a job well done.Make up your own problem set and then see how you feel when people comment about the ratings.
•  » » » 10 years ago, # ^ |   0 Но в задаче B не нужно ни то, ни другое=)
 » 10 years ago, # |   +4 I always receive mails from codeforces after the contest is over! Can anyone tell me what needs to be done to correct this. And the delay is not of about two hours which is the difference between my and codeforces timezone but instead I receive mails on the next day.Sorry if this does not belong here. Thanks
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 maybe send a message to Mike M. for something to be added to the FAQs (if it's not already there?).
•  » » 10 years ago, # ^ |   0 Yes, i have this problem too, may be someone can solve this problem?
 » 10 years ago, # | ← Rev. 2 →   -9
 » 10 years ago, # |   0 Where can I find English editorial?
•  » » 10 years ago, # ^ |   0 I want to see English editorial too, I can't understand Russian...
•  » » 10 years ago, # ^ |   +3 english editorialhttp://codeforces.com/blog/entry/5378
 » 10 years ago, # |   0 @Mike: I can't understand the solution to problem D Div 2 :Please can you write more elaborate reasoning for your solution
 » 2 years ago, # |   0 Why editorial is not accessible?
•  » » 2 years ago, # ^ |   0