Russian Code Cup 2017 — First Qualification Round
By RussianCodeCup, 8 years ago, translation, In English

Hi, everyone!

This Sunday, April, 2 at 19-00 Moscow time the First Qualification Round of Russian Code Cup 2017 will take place. 200 top participants will qualify for the Elimination Round, those who wouldn't qualify can still take part in two following qualification rounds.

We have a news for you: we have added Kotlin, Haskell and Free Pascal to our list of programming languages, also you can now submit your Python programs to run in PyPy. Exact versions of compilers and compilation commands are published at the official web site. We are working on adding more programming languages.

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

UPD Editorial is published

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

Comments Comments (47)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope, checking won't last as long as in warm-up.

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

Will there be a mirror contest on Codeforces ?

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

    Why do you need a mirror contest? Everyone can participate in the official contest.

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

      Maybe there are some guys (including me) who want more round which will be rated :)

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

Hello, I see "Qual" word and green tick front of my name in results of warm-up round:

Capture

What does it mean? Am I qualified for elimination round?

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

How to solve E?

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

    The answer is the number of different prefixes times the number of different suffixes in the range minus the sum over all letters of the number of prefixes that end with the given letter times the number of suffixes that have this letter before them in some string (basically, what we do is counting everything, possibly twice, and then subtracting strings that were considered twice).

    Now we need to count the number of different prefixes and suffixes in a range. If we use hashes, it's just a number of different integers in a range. We can compute it using a sweep line with a binary index tree (we also need to keep a binary index tree for each letter in the alphabet to do the subtractions).

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

      We don't really need hashes. Just construct a trie and assign different integers to different nodes.

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

How to solve C?

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

    Optimal order is found by sorting according to the following comparator: (a[i] — b[i]) / x[i]. Then one can do simple DP to find value of savings by using this order.

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

      Been there, done that, gottten WA xD.

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

        Here is my code, it worked for me, hope this is helpful, link:

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

        it was because of precision. I also got WA, but then I did just one division by 1e7 at the end and got AC

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

        The case where a[i] = b[i] or x[i] = 0 can be tricky. I handled them separately.

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

          Yes, you're right. I thought my code worked in that case but now I see that I was wrong. Thanks!

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

      With this method I was getting TLE on test 4. Any optimization in implementation? My code

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

        Well just to double check the sorting part just takes nlog(n). Then the dp for me is two dimensions of size n and 2, and constant amount of transition states. Thus nlog(n) + 2n should work in time I believe, constants are not bad I think?

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

        Can anyone please give working C++ code?

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

        Your comparing function can return x<y and y<x for some triples x,y (e.g. both having a=b) and the sorting enters infinite loop.

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

          ohh Thanks! I removed those two lines, but now it started giving WA in test case 3.

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

            For any x!=y you need the function to return true exactly once for x<y and y<x. Without these two lines it may return false twice if d1=d2. I usually return lexicographical order in such cases like your d1=d2.

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

              But if I have d1 = d2. Then it is like I am assuming x = y. So in that case shouldn't it be alright to return false both the times?

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

                No. You can return twice false only for exactly the same elements. Think of it in the way: would a correct sorting of [x, y] be [x, x]? If not, then you can't treat them as equal. And that's the case here.

                You can check out c++ strict weak ordering for more information about comparators.

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

                  Thanks again! I understood what was the problem. It worked after removing this ambiguity.

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

How to solve D?

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

    for each index find out how far you can go while having K distinct elements , now do dp with segtree

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

      We can actually keep a multiset of available transitions to avoid using any custom data structures.

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

How to solve F?

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

How to solve B?

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

    Check if there exists continuous vertical or horizontal segment of tiles of size more than k. If so, print 'NO', otherwise print 'YES' and ((i + j) % k) + 1 on places where tiles are. (You can check that this answer satisfies the statement).

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

      why ((i + j) % k) + 1 works ?

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

        In the case when answer is "YES" we know that all the segments have length < k. Consider any such segment. Assume that the segment is horizontal. Same argument will work when it is vertical. For this horizontal segment i is constant. So in (i+j)%k will be different for each of those tiles in the segment. As we are incrementing it by 1 modulo k each time while moving along the segment.

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

I wasted more than 1 hour on problem B misunderstanding the definition of "continuous segments of tiles." Please make problem statements clearer next time.

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

    can you please explain it.I m still trying to figure it out.

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

      teja349 it means continuous 1's in array.

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

        Ohh ,I overlooked the word contiguous tiles and was always trying for contiguous segments.

        Can the question be solved for contiguous segments (instead of tiles) or is it NP?

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

          With Bipartite matching.

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

            Can you elaborate?? How with bipartite matching.

            PS: I dint mean adjacent.

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

    Same here.

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

    I didn't understand the statement but managed to guess it from the samples. The explanation for samples would be so useful.

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

Does anyone know where can I submit solution after the contest is over?

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

    It is not possible to submit solution to system after contest, as far as I know, but instead of that you can download tests and check yourself :)

    UPD: It added to gyms, here :)

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

First Qualification round has been added to gyms: 2017 Russian Code Cup (RCC 17), 1st qualification round

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

I downloaded tests, but in russian-code-cup-2017-qual1/b/tests I can onlu see files named "01", "01.a", "02", "02.a",... How can I see the tests? I am using OS X

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

    That's it. Just open that files in any text editor. There are few files, but each contains a lot of internal tests. *.a files are expected answers. Btw, your answers for B can be different, that in .a files, but also correct, because there can be more than one correct answer.

    → Reply