Ripatti's blog

Codeforces Beta Round #70 (Div. 2)
By Ripatti, 14 years ago, translation, In English
Good evening.

I'm glad to welcome you on this Codeforces beta round.

Authors of today problemset are Ripatti (it is me) and Lepetrandr. it4.kp, MikeMirzayanov, RAD, Nerevar and dlevshunov helped in preparing the round. Delinur translated statements into English.

Good luck for all!

UPD
Winner is Neverauskas.
Editorial.
  • Vote: I like it
  • +64
  • Vote: I do not like it

14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Hope the problems be interesting as usual! =)
→ Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
мой последний контест перед олимпиадой! удачи всем и мне!
→ Reply
14 years ago, # |
  Vote: I like it -13 Vote: I do not like it
I do not like this contest, problem statement two is not clear. And C is to difficult.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Stop complaining please. The statements on both languages are OK. 

    And C is not very difficuilt I think.
    → Reply
14 years ago, # |
  Vote: I like it -18 Vote: I do not like it
I did get an answer after one hour, i think it should not be rated.
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Do not you think that downtime in the last quarter of contest could cause some problems for participants?

May be you should make this contest longer.
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it
The problems are nice but I think these problems should have been put into a division 1 contest (Especially: C, D and E). What do you think?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it
    I think so too.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    Well, last contest problems C-E for Div.2 was A-C for Div.1
    May be you are right, I think that problems are quiet harder that usual.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I agree with you, the problems are quite hard today.

    But I'm on 19th place, on the first page! *YAHOO*
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    I think C,D is not so hard.
    E maybe hard for div2 but it is E :)
    → Reply
14 years ago, # |
  Vote: I like it +4 Vote: I do not like it
Problems c,d,e were tough. Problem a,b didn't have any special tests (or pretests were good) so no hack :(.
→ Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
When I tried to hack problem A, I got an invalid input error said "FAIL Expected EOLN (stdin)", what does this mean?
Missing eol at the last line?
→ Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
how u guys hackin? Teach me PLS :D i'm newbie

→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    1)Solve any problem
    2)Open problemlist
    3)Click "Lock"-icon
    4)Open your room
    5)Ctrl+Click to any cell(problem you lock only) and see  others solution.
    6)Write test or generator and submit hack
    → Reply
14 years ago, # |
  Vote: I like it +19 Vote: I do not like it
Fast System test :)
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anybody explain me how to solve Problem C?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Let's find divisors of m.

    We can notice, that if m / mindivisor < k  - therefore u can not split any log, so Marsel wins.

    Ok, let m / mindivisor be  >= k.
    Then, optimal strategy for both players is to split every log into mindivisor logs. 
    And now we can find the answer - if  n is odd, the last log will be splitted by Timur, and Timur wins. 
    Otherwise - Marsel wins.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      "Then, optimal strategy for both players is to split every log into mindivisor logs." Can you please explain/proof this?
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it
        If N is even Marsel win anyway because he can repeat Timur's turns.
        else if Timur can split one log to mindivisors logs, He win as Second witn even N
        → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      "Then, optimal strategy for both players is to split every log into mindivisor logs."
      It gives the correct result, but it's not obvious, and, I suppose, not true.

      One of possible winning strategies here is symmetric strategy. If n is even, Marcel has symmetric strategy, so he wins. Otherwise, if Timur can make a turn (m / mindivisor >= k), then he splits one log, so that it parts can't be splited again, and so he gets symmetric strategy for remaining logs.

      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What was the main idea for C   ?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Consider the situation where N is even. Pair up the logs. Then the opponent can always copy your move for another pair, so you always lose. What if N is odd? You can deduce from the even case that it is equivalent to play on a single log with length M. 

    Now the rule goes as follows. When you play on a single log with length L, you always try to split it into logs with length L' ≥ K such that is even. By the above argument opponent always loses. If none of the allowed divisions leads your opponent into even case, try to recur on each possible splitting and see if you can win. It runs pretty fast.

    Be careful to handle the case when N = K = 1.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    If Timur can't move at first, then Marsel will obviously win.

    Otherwise, we have two cases:

    - N is even, Marsel will win by imitating Timur's actions since at that time, logs are paired up.

    - N is odd, Timur simply destroys a log of length M and puts Marsel into the an even position, at which who moves second will win (it is Timur then!). You can see there is always a way to divide the log so that you can not make any move on the newly formed logs (repeatedly divide M by its divisors while this does not make M less than K).
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
it used Sprague-Grundy function.
→ Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Nice problem set! Even a little bit harder than usual :D
And I love the fast system test :x
→ Reply
14 years ago, # |
← Rev. 6   Vote: I like it +1 Vote: I do not like it
I kind of doubt if test 23 for problem A is a valid input(I can't see the whole data because of ellipsis at the last line). According to the input constraint, every line contains 100 characters at most, so I used char str[3][101];  during the contest and failed unexpectedly, but char str[3][102]; got AC.
So how to explain this? 
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    May you say your position in standigs .
    It helps to see your code
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it
    Input
    aaa
    aa


    #include <iostream>
    #include <stdio.h>
    #include <string.h>
    using namespace std;

    int main () {
        freopen("input","r",stdin);
        char a[2][4];
        for(int j=0;j<2;++j)
            fgets(a[j], 4, stdin);
    //a[0] is "aaa\0"
    //a[1] is "\n\0[trash]"

    //so strlen(a[1]=1)
    //and your loop is uncorrect

    //tested with g++
        return 0;
    }

    → Reply
    • 14 years ago, # ^ |
      ← Rev. 4   Vote: I like it +2 Vote: I do not like it
      Update: 
      It turned out I didn't grasp fgets until now. Your code snippet helps, thanks. 
      The testcases for problem A are OK. 
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it
        I was test smth and add it to post(tested in my local machine witt \n instead of \r\n [Linux])
        → Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
I don't usually comment, but I really liked the problems, especially E.
→ Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
discussion and sample solutions should have been given by now.
→ Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Can anyone explain D?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Guys can i post A,B,C problems in my site? :D is it illegal? 
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
i liked E , however it confused me , because of this part of Problem :
"Any scientist in a minute can move down the corridor to the next lab" .
→ Reply