Russian Code Cup 2017 — Elimination Round
By RussianCodeCup, history, 8 years ago, translation, In English

Ready, steady, go!

It's time to find out who the top 50 participants to compete in the Final Round of Russian Code Cup 2017 are. We invite everyone qualified to take part in the Elimination Round this Sunday, May 14, 2017 at 13-00 Moscow Time. Round length is 2 hours. We invite you to russiancodecup.ru, and wish you good luck!

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

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

T-shirts?

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

When you are one of the few people (3 to be exact) who solved F and you didn't get a T-shirt, because you forgot that in Russian Code Cup all problems are worth the same :')

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

What's the intended solution for E? priority_queue for getting subarrays and binary search + hash for merging sequences get TL.

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

    There is a solution for n^2log. You check symbols one by one for nlogn and also keep in mind dp[x] = min{y, you could have finished known prefix with x-prefix of a and y-prefix of b}.

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

      So, you don't fix the number of elements chosen from each array?

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

        No, you just have not to get position (0,y) or (x,0) at the end (to make both subsequences not empty).

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

    I used min segment tree for creating subsequences and O(N * log(N)) suffix array to merge them and it passed.

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

    We just construe answer one by one and for each position in either array keep track of minimal position in the other array such that we can construe prefix of answer we have so far from corresponding prefixes of arrays

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

    My solution is O(N2), but it didn't pass test 9 because of the corner case.

    I greedily construct the answer one by one. I store the set of pairs of prefixes of a and b I used to construct the answer up till now. It has size O(N), because for each prefix of a we're only interested in the shortest prefix of b.

    For the given pair of prefixes, we can take any element, after which there's enough elements to construct the rest. We need the smallest, so we can take RMQ over the next allowed elements in O(1) for each pair, and find minimum over the pairs.

    Now, we need to advance the prefixes to reach the chosen element. To do that, we can just construct arrays of pointers to the next occurrence of this element in both arrays in O(N + M).

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

Got WA#9 in problem E because missed the fact that both subsequences must be non-empty...

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

    Same. Quite atificial condition that we can get rid of just by adding following to the end:

            if (maxElement(answer) < minElement(b)) {
            answer[k - 1] = minElement(b);
        }
        if (maxElement(answer) < minElement(a)) {
            answer[k - 1] = minElement(a);
        }
    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the final round online?

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

What is solution for D?

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

    Just count for every vertex v, number of pairs (u1<u2) ui!=v, such that Ang(u1-v-u2) < 90. Then you just need to subtract 2 * binom_coef(n,3).

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

How to use the checker for problem C on my computer ?

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

    You can try DFS, you just need hash table to check point exists or not and same for visited.

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

      I mean how can I use the checker to check my solution on my computer. I don't see a main function in the checker, and I see a lot of "import ..." that I've never seen before.

      Sorry for my inexperience with Java.

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

Will there be a place to submit solutions after the contest?

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

    vovuh, already mentioned that Codeforces have internal error which not allow add problems to gym. They will be added after problem will be resolved.

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

Sorry for long delay, contest has been added (finally!) to gyms: 2017 Russian Code Cup (RCC 17), Elimination Round

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

    Thank you!

    To RussianCodeCup: I still don't know why I got TLE for E during the contest. My submission is #27152353 of http://codeforces.net/gym/101397/status/E, and it's much faster (2027ms) than genomes_iz_2modules.cpp (2870ms). Is it possible that my code works very slowly on RCC's server?

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

      I got the answer from I_love_natalia. It seems memory allocator/deallocator are slow on RCC. I guess my solution was slow because I used too much vectors/priority_queues.

      → Reply