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!
What if I have no middle name?
You can fill in your handle.
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.
Fill in the name of your father with suffix "ovich".
Example: John Smith, the son of Adam Smith -> John Adamovich Smith.
Wow that thing is SLOW...
How to solve D?
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.
What's the intended complexity in D? If it's O((N + Q) * sqrt(max_number)) the constraints look way too high.
I have O((N + Q) * f(max_number)), where f(x) is number of divisors.
Let K = 500000. Complexity of my solution is: Preprocessing O(N + K log K) and O(max_divisor_count(K)) per query.
I got AC with , where C = max_number.
I have a complexity O((N + Q) * sqrt(MAX_NUMBER)) and it's ok :)
Choose your favourite C++ compiler:
- slow
- very slow
- as slow as RCC testing system
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.
The website is unresponsive. Luckily after the contest!
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?
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?
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.
What is the correct date and time of the Final Round?
It's written "September 18" here and "September 11" on the website.
The date on the site is corrected. The final round will take place on September 18.
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 :)