Slamur's blog

Codeforces Gyms: VIII Samara Regional Intercollegiate Team Contest
By Slamur, 9 years ago, translation, In English

About two months ago we ran another regional intercollegiate team contest. The corresponding gym contest on Codeforces will be held on Sunday, June 7, 2015, at 13:00 UTC +3:00.

Contest was prepared by Sinner, dalex, Slamur. Also special thanks to craus, Shlakoblock and I_love_natalia.

Contest will be available on this page: Codeforces Gyms

The list of our previous contests:

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

Comments Comments (17)
| Write comment?
»
9 years ago, # |
← Rev. 8   Vote: I like it -43 Vote: I do not like it

I have some question(I am new in CF & it is my first GYM contest):

  1. Can anyone participate(Div.1/Div.2)?
  2. Is rating change?
  3. Is there any registration process?

Sorry for my poor English. Thanks in advance.

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

    It will be gym contest, so:

    1. Anyone can participate.
    2. It will be unrated.
    3. Registration will be opened during all contest.
    → Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Reminder: the contest starts soon, the registration is opened.

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

What is the idea for L ?

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

    K + 1 rings can be moved in 2K + 1 turns:

    • move K rings on K additional towers
    • move last ring on needed tower
    • move K rings from additional to needed tower

    So you can use next algo to move N rings:

    • move recursively N — (K + 1) rings on medium tower
    • move (K + 1) rings on needed tower in 2K + 1 turns
    • move recursively N — (K + 1) rings from medium to needed tower

    F(N) = F(N — K — 1) + (2K + 1) + F(N — K — 1)
    F(N) = 2F(N — K — 1) + (2K + 1)

    If you enumerate groups of (K + 1) rings, this fotmula will be:

    G(i) = 2G(i-1) + (2K + 1)
    G(0) = if (M = N mod (K + 1)) == 0 then 0 else (2(M — 1) + 1)

    It can be solved with matrix exponentation or even with deriving of formula.

    → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it +23 Vote: I do not like it

I was asked to write quick one-line hints for all problems. They are in the first revision.

There are also some typos but it's difficult to edit and make another spoiler, so I'll leave it as is.

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

    Anotyer way to solve B in the first revision.

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

      Can you provide the explanation for M? I dint get what dalex wants to say here.

      Thanks.

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

        Detailed M (see 1st revision)

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

          Where can I find the 1st revision you are talking about, please ?

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

            Above a comment, there is an option saying <-- Rev x.(x is some positive integer)

            Pressing that gets you to previous versions of the comment.

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

Any hint on question K please??

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

    Hints are in the comment above by dalex. Just go back to revision 1 of the comment to see the hint.

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

Can someone who has solved problem A post the 13th test-case here. I am getting WA and I can't figure out my mistake. Thanks. This is my code http://ideone.com/hPM1Ud Problem A

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

Problem C can also be found in Algorithm Design by Kleinberg and Tardos (here)

→ Reply