Malinovsky239's blog

Codeforces Round #140
By Malinovsky239, 12 years ago, translation, In English

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:

  1. peter50216

  2. Dmitry_Egorov

  3. Egor

  4. RAVEman

  5. bmerry

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.

  • Vote: I like it
  • +235
  • Vote: I do not like it

Comments Comments (76)
| Write comment?
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it -19 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it 
      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.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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))<k:
  N = 1 + (r/D)
  D -= ( ((N*D)-r) + (N-1) ) / N
print( recfib( D, m)[0] )

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

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                12 years ago, # ^ |
                ← Rev. 2   Vote: I like it 0 Vote: I do not like it

                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?

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

                  → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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
          → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        A really nice solution Thank you !

        → Reply
»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Same method but WAed!

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is that not the answer? Ruh ruh.

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
          ← Rev. 2   Vote: I like it -9 Vote: I do not like it

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

          → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 3   Vote: I like it +3 Vote: I do not like it 
        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.

        → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        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

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      But I meant problem E div2

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Correction — > long because int will overflow :P

          → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I do, but only because I suck in geomtry.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
12 years ago, # |
← Rev. 4   Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Binary search in Div1.C is incorrect :(
l=7, r=14, k=2:
7 — ok
6 — not

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 10   Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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

"

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Screencast

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      It is not viable even with delay

      → Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
»
12 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        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.

        → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I find English editorial?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply