Russian Code Cup 2016 — Announcement. Dates, Prizes, Rules.
By RussianCodeCup, history, 9 years ago, translation, In English

Hello, all!

We are glad to announce the final version of Russian Code Cup 2016 rules! The most important news of this year is that Russian Code Cup goes international, now the problems are available in both Russian and English. Anybody can participate, to enter the competition, please register at http://russiancodecup.ru, participants of previous championships need to confirm their participation in their profile.

This year the prize pool is again 750 000 rub. We have changed the structure of the prizes to give more money prizes away, so top 25 now get cash. The winner gets 150 000 rub, the second place gets 100 000 rub, the third place gets 65 000 rub. Those who take places from 4 to 10 get 30 000 rub, and places from 11 to 25 can account for 15 000 rub. Top 200 in elimination round get branded Russian Code Cup t-shirts.

There are three levels of the championship. First you must qualify in one of the three Qualification Rounds (May 8, May 29 and June 5). Top 200 from each round proceed to Elimination Round (June 19), top 50 from it proceed to Final Round (September 18). If you fail to qualify in a Qualification Round you can still try in the following Qualification Rounds.

We invite you to the Qualification Round 1 on Sunday, May 8, 19-00 Moscow Time, and wish everyone good luck!

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

Comments Comments (21)
| Write comment?
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

What if I have no middle name?

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

    You can fill in your handle.

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

      The question is rather: do you have to fill in your handle? And the answer to it is: no, any visible string, even an almost invisible one like ".", is enough.

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

    Fill in the name of your father with suffix "ovich".

    Example: John Smith, the son of Adam Smith -> John Adamovich Smith.

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

Wow that thing is SLOW...

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

How to solve D?

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

    Precompute the ans for each value of k<=5*10^5 in O(maxn*log(maxn)), where maxn = 500000.

    For query of type 1: find all factors of t[v] and add 1 to those.Update value of t[v].

    For query of type 2: find all factors of t[v]-1 sub 1 from those.Update value of t[v].

    For query of type 3: Output the answer in O(1).

    Overall complexity. O(m*(sqrt(max(t[i]))).I had to use fast I/O and other optimizations to get this AC.

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

What's the intended complexity in D? If it's O((N + Q) * sqrt(max_number)) the constraints look way too high.

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

    I have O((N + Q) * f(max_number)), where f(x) is number of divisors.

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

    Let K = 500000. Complexity of my solution is: Preprocessing O(N + K log K) and O(max_divisor_count(K)) per query.

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

    I got AC with , where C = max_number.

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

    I have a complexity O((N + Q) * sqrt(MAX_NUMBER)) and it's ok :)

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

Choose your favourite C++ compiler:
- slow
- very slow
- as slow as RCC testing system

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

    Compiler is ok, except stdio. I saw such trouble on ROI and NEERC, and it's common trouble for all new enough mingw builds.

    Fix is one of following:
    1. use -D__MINGW_USE_ANSI_STDIO=0 in command line (i'm not sure if it's enough in code)
    2. use -std=gnu++11, instead of -std=c++11.

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

The website is unresponsive. Luckily after the contest!

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

Magical solution for C. Divide all numbers by their common GCD. Now it's easy to see that the answer is no less than 1 and we should check if it's at least 2, and if yes, find it. Let's calculate the following "DP": iterate over numbers, when passing the i-th number keep set of pairs (a, b) where a and b is the pair of gcd values we can achieve by splitting first i numbers into two sets. When passing the number x, we take each pair (a, b) and form two new pairs (gcd(a, x), b) and (a, gcd(b, x)).

It is now working in , but we make a super-observation that we are not interested in pairs where one of the numbers is equal to 1 since we already know that the answer is not less than 1, they provide no information for us. Do not add such pairs and it gets AC. I have no single idea WTH it works. Maybe because I sorted all numbers in increasing order and uniqued them?

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

    Why does it work for in O(n*n*logn)? It looks like there are O(n*logn) pairs (a,b) in the set. How did you estimate this?

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

Why are there less than 50 participants on some of the standings pages? 50 on page 1, 49 on page 2, 50 on page 3, 48 on page 4, etc.

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

What is the correct date and time of the Final Round?

It's written "September 18" here and "September 11" on the website.

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

    The date on the site is corrected. The final round will take place on September 18.

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

      Will there be an onsite round in Moscow for those who wish to come?

      EDIT. Let me phrase the question differently: could you organize an onsite in Moscow like last year? I've already came to Moscow for this :)

      → Reply