Lewin's blog

Round 1 of Yandex.Algorithm 2018
By Lewin, history, 6 years ago, In English

Hello everybody!

On Mar 3, 10:00 Moscow time, Round 1 of Yandex.Algorithm 2018 competition will take place. I wrote the majority of the problems in this contest, with some additional help from GlebsHP.

I would like to thank GlebsHP for all his help with coordinating this round, MikeMirzayanov for polygon, and of course, everyone who took the time to test this round.

See you in the competition soon!

Editorial here: http://codeforces.com/blog/entry/58135

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

Comments Comments (41)
| Write comment?
»
6 years ago, # |
  Vote: I like it -48 Vote: I do not like it

Is it rated for div.1 or div.2?

And where is it in the Contest list?

→ Reply
»
6 years ago, # |
  Vote: I like it -23 Vote: I do not like it

Where is it in the contest list? I want to join the contest.

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

    If you haven't participated in qualifying or warming-up contests, you can't join the first round. Otherwise, go to the link in the comment above

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

10 am MSK on Saturday? Kinda strange timing if you aim for russian participants.

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

    Why? Because of Friday night drinking? That's only in the West. (In Russia, it's every night drinking.)

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

    10AM on weekend? Seems completely fine.

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

      Saturday might be not a weekend for some students

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

        Seriously? Who has courses on Saturday? Even if there are such cases I believe this is a rare case? Either way, there are many contests between Monday and Friday and I assume all students have courses these days :)

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

          i had classes on Saturday while i was at school

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

          In Russia it is quite common to have classes on Saturday for both high school and university students

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

            Huh, didn't expect it. Maybe that's why Russians are so good ;). Do you have six working days or do you have free Monday or are courses on Saturdays "lighter" or "extracurricular" in some sense?

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

              In high school there are long summer holidays (3 months)

              In Moscow State University we had some random week day marked for “self-studying” (basically day off)

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

In the ruleset it states that if two participants have the same score they will be compared with their lowest rank in the three contests.
Does that mean that if I miss a contest I automatically get a lower position than someone who has the same score but participated in all three contests?

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

    Duh, "lowest" is always confusing when talking about standings. It can be the case that lowest means better and that seems to be more probable case.

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

If I can't participate Round 1 at the exact time mentioned above, does it mean that I'm not able to participate in the contest?

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

How will top 256 participants be decided(for t-shirts)? GP 30 scores are 0 for >30 rank. So will it just be about lowest rank in three contests?

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

How to solve B ?

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

    Generate all permutations for mapping [a,j] to [0,9] and see how many of them satisfy the constraint of having a..j as a subsequence. next_permutation in C++ Standard Library can come in handy

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

    Brute Force...consider all 10! arrangements of 0123456789..

    in any arrangement A[i] corresponds to ith alphabet...

    for every arrangement if sub sequence exists or not can be checked in O(string_length)

    overall complexity is ((10!)*string_length)

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

Is C of elimination round usually this hard? And is sqrt-decomposition required for this problem?

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

    I solved it with sqrt dec, also swap(c,d);

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

      What was the main idea? Partitioning nodes into heavy and light nodes based on whether their degree is > sqrt(m). Then doing manual updates for the light ones and storing the updates for heavy ones and later adding the stored value for heavy neighbors?

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

      What does swap(c, d) mean?

      PS: Can I see your source code for this problem?

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

        Possibly that the setter should have set problem C as the present problem D and vice versa.

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

any hints for D, I know that the stamp must be concatenation between prefix and suffix, but how to check if a certain stamp is valid?

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

    No only prefixes and Suffixes For example aabbaa abba is valid abba.. 1st position ababba 3rd position aabbaa 2nd position

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

vi=0 in problem C :)

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

How to solve E?

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

    Build graph with vertexes(index, changed = 0/1), and edges (k_min, k_max), find path of length n.

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

tourist nails it again!! as usual :p

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

what complexity in D?

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

    The editorial is up. The author has allowed O(n4) to pass.

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

    I have O(N3), but I wrote O(N4) first and didn't find tests where it would be slow. Stamps were either too easy or too hard to cover the string with.

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

To everybody with ~10 bombs on E who still wonders "why isn't it passing?!": there was a missable condition in statement, that you can choose K lower than some numbers from the input, but then you just cannot flip them ;_;

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

    I got WA9 because of n = 1 :(

    40 seconds after the contest end got O(n^2) solution passed in 60ms.

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

Where can I see problems if I didn't register?

→ Reply