Russian Code Cup 2017 — Second Qualification Round
By RussianCodeCup, 7 years ago, translation, In English

Hello everyone!

Top 200 from the First Qualification Round have already advanced to the Elimination Round, but the other paricipants still strive to get there. If you haven't qualified yet, we invite you to take part in the Second Qualification Round that will take place this Sunday, April 16, at 12-00 Moscow Time. Best 200 participants will advance to the Elimination Round, other participants can try again in the Third Qualification Round.

Good luck to everyone, see you at http://russiancodecup.ru!

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

Comments Comments (22)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

If I qualified to the elimination round, how can I receive the certificate and I'm live in Egypt ?!

→ Reply
»
7 years ago, # |
← Rev. 7   Vote: I like it +18 Vote: I do not like it

Has anybody received their shirts from last year?

EDIT: oops... that was an unfortunate typo!

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

I qualified in the previous round. Can I take part in this round unofficially?

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

How to solve C?

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

    Minimize the number of cycles.

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

    The answer to the fully given array = N — number of cycles. So you collect all cycle segments (e.g. ? -> 1 -> 4 -> 5 -> ?) where ? is controlled by you. If you have one segment — you have no choice (just put one element you have). Otherwise you can connect all segments into a one cycle (e.g. end0 -> start1, end1 ->start2, ... endI->start0), thus maximizing the answer.

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

I have a feeling that E can be solved using MO's Algorithm but I don't know how xD So Can Someone Help Me ?

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

    Yes, it does. I solved it by MO.

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

    I tried to, but got TLE :(

    First, transform array into prefix sums + lift it up by 100000 to avoid negative values. So our goal is to find longest interval such that arr[l] = arr[r] inside the quered interval.

    We start MO's algorithm and check intervals. We maintain:

    • for each value: a deque of indices of this value in our current interval (easy to add/remove index from any side);
    • a multiset of maximal lengths for each value (that is multiset of all deque[val].front() - deque[val].back()). The multiset is also easy to update since we can compute the length for the value from the deque. The answer for current query is then the largest value in the multiset.

    At the end of block check, we can clear the multiset directly, and clean the deque's by collapsing the current interval.

    PS: I used map<int,int> instead of multiset.

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

      My solution is similar to hellman_'s one, except a trick to avoid log factor in the complexity :). Maintain two array a[], b[]. When adding/removing a segment of leng d we add/substract one from a[d / sqrt(N)] and b[d]. To find the maximal len, we need only O(sqrt(N)).

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

Will the problems get added to Gym like Qualification Round 1?

→ Reply