Zlobober's blog

Russian Code Cup, 1st qualification round
By Zlobober, history, 8 years ago, In English

Hi everybody! FYI, 1st Qualification Round of RCC starts in less than an hour. I still don't see any kind of announcement on CF, so let it be here.

Good luck!

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

»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

http://www.russiancodecup.ru/en/

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

How to solve D faster than , where n = 5 * 105?

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

    I didn't submit it during the contest, not sure if it would fit the TL, but an O(n*sqrt(n)) solution would be to maintain an array of answers for all k; initially it can be built in O(n*sqrt(n)), then updated in O(#divisors(T[v])) for each query of type 1 and 2.

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

    It may be solved in O(n * sqrt(MAX) + m * numberofdivisors(MAX)) where n = m = 1e5

    Maintain all answers, changes are O(divisors), queries are O(1), precalc is O(n * sqrt(MAX)): for each problem you have O(sqrt(MAX)) ranges to add fixed value. It may be done offline without log

    PS: had to spend much time to fit in TL anyway:(

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

How to solve B?

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

    First and last carriage should be lit

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

    we should make the procces using deque. If we can we push the carriage to the tunnel. If we can't we delete first carriage from tunnel. And we should keep the amount of lights. If current lights is zero. We make the last carriage lighting. And in the end we should delete all the carriage from the deque.

    Here is my code

    Sorry for my english

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

    Greedily + check first and last carriage for light http://pastie.org/10829451

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

Has anyone solved C faster than O(n * maxdivisor * logn)?

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

    Well, I don't know an actual complexity of my solution, but I couldn't come up with a test to make it work at least observably long.

    (Copy-Paste from another thread on CF):

    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
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I also don't know the complexity of my solution. I came to idea that first element in any case will be in one of two group. So we can go through all of his divisor and iterate though other elements if element also has this divisor we put him in one group with first, else we put him in another group and keep the gcd. This solution got TL

    I decrease the time, using one if. if current gcd of second group is smaller than our current maximum we break;

    Here is my code

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

Is it possible to upsolve the problems?

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

Solution for this round Tutorial

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

Can someone pls make a training for it here? :)

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it -10 Vote: I do not like it
→ Reply