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:*

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

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

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? :)

You may use it on your own risk. We will announce official support after we will be sure that everything is OK.

I have the impression that today... tourist, again surpass the 3000 points ... A new range? Something like Intergalactic Grandmaster? LOL

tourist was here 5 days ago.

He is in Italy probably(IOI), so I don't think so :)

i have a dream

Can somebody explain C. I can't understand it :(

why my C got wrong answer at pretest 1? I already same as the sample IO

Anyone search ideas from Google for E(Div 2)/C(Div 1) like me?

We can use fact, that

gcd(Fib_{x},Fib_{y}) =Fib_{gcd(x, y)}. But I have still no correct idea how to get subset with maximal gcd(since binary search is wrong).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.

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.

but i still have not understood the (3^n-1) approach below. what is F(N)?

oops, 3^n-1 is Div2-C/Div1-A

If you want ugly, it's only 11 lines of python:

only four lines implement the algorithm for the fib. index, the rest is i/o (3 lines) and the index-to-fib# function.

and it's faster in python than any div 2 C++ solution, and faster than most of the div 1 C++ solutions.

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?

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:

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

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.See, it's only 80 chars. You don't even need to break the line.

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.

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

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?

The first argument of recfib, namely n, will not affected by m.

2251104 Even shorter(7 lines) with functional style. Accepted.

sweet!

defintion for recursion: see recursion.

A really nice solution Thank you !

In my opinion, these OEIS problems don't add anything to the contest.

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)

Same method but WAed!

Is that not the answer? Ruh ruh.

Edit:How come the font become enlarged? --> WA with 6th pretest case

Use

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

Took me a bit to turn the 2 into a 3-1 though :( I'm out of practice.

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

Indeed, I forgot to write +MOD thing and lock my problem like a fool... 900 points lost will be a real tragedy.

same with me :( lost 1344 points

The fun part is not using OEIS. I think it was a nice problem

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

I can't understand, why my O(8log(10^12)) got TL. Submission #2245668 ?

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.

I just remembered the case k=1. I hope it doesn't get time out

But I meant problem E div2

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.

Congratulations to Velicue for the only contestant to solve E.

How can we solve DIV 2 E ? How can we get the maximum gcd of all the k element subsets between L and R ?

Anyone thinks that A in Div2 is more difficult than B?

Solution in one phrase : cross product. Without that it'll be a bit troublesome.

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

Floating point number is not accurate enough. use integers instead.

Correction — > long because int will overflow :P

I do, but only because I suck in geomtry.

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

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...?Binary search in Div1.C is incorrect :(

l=7, r=14, k=2:

7 — ok

6 — not

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) — 1sorry, but it's not C(Div.2)?

Sorry, I think iTwin say problem C div 2 :D

what is special about test case number 106. why binary search does not work ?

Check test 12345678 7 14 2

mine code is outputting 13 which is right i guess. http://codeforces.com/contest/226/submission/2246243

What about this test 123456789 100000000000 300000000000 3 какой ответ? Right answer is 33025443

Thanks.

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

"

Did his B pass? :D

Using "int" instead of long long caused system test fail (A. div 2) :(

Thats obvoious becuase range was 10^9 .. So int * int will overflow

Screencast

Nice idea to stream video. Streamers usually use 3-minuts delay and stream online.

It is not viable even with delay

Based on the number of people solving, C and D should be exchanged their order in Div 1.

also in Div. 2 , A and B should change their order based on difficulty level or no. of people solved.

No, binary search and sorting are more difficult than school geometry.

I suck at geometry and honestly I don't really like it either. And like me are a lot of Div2 participants.

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.

Но в задаче B не нужно ни то, ни другое=)

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

maybe send a message to Mike M. for something to be added to the FAQs (if it's not already there?).

Yes, i have this problem too, may be someone can solve this problem?

Where can I find English editorial?

I want to see English editorial too, I can't understand Russian...

english editorial

http://codeforces.com/blog/entry/5378

@Mike: I can't understand the solution to problem D Div 2 :Please can you write more elaborate reasoning for your solution