Lewin's blog

By Lewin, history, 21 month(s) 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

»
21 month(s) 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?

»
21 month(s) 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.

  • »
    »
    21 month(s) 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

»
21 month(s) 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.

  • »
    »
    21 month(s) 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.)

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    10AM on weekend? Seems completely fine.

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

      Saturday might be not a weekend for some students

      • »
        »
        »
        »
        21 month(s) 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 :)

        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
          Rev. 2   Vote: I like it +10 Vote: I do not like it

          i had classes on Saturday while i was at school

        • »
          »
          »
          »
          »
          21 month(s) 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

          • »
            »
            »
            »
            »
            »
            21 month(s) 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?

            • »
              »
              »
              »
              »
              »
              »
              21 month(s) 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)

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

mi mi pee pee bigo. now.. is contest rate succ me?

»
21 month(s) ago, # |
  Vote: I like it -63 Vote: I do not like it

this contest will be stupid..... i know it....

»
21 month(s) 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?

  • »
    »
    21 month(s) 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.

»
21 month(s) 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?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

In Kazakhstan today, March 3, a working day, instead of March 9 =(

»
21 month(s) 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?

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B ?

  • »
    »
    21 month(s) 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

  • »
    »
    21 month(s) 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)

    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hah, those brute-force problems always dupe me )

»
21 month(s) 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?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      21 month(s) 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?

    • »
      »
      »
      21 month(s) 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?

      • »
        »
        »
        »
        21 month(s) 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.

»
21 month(s) 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?

  • »
    »
    21 month(s) 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

»
21 month(s) ago, # |
  Vote: I like it +10 Vote: I do not like it

vi=0 in problem C :)

»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve E?

  • »
    »
    21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

tourist nails it again!! as usual :p

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

what complexity in D?

  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    21 month(s) 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.

»
21 month(s) 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 ;_;

  • »
    »
    21 month(s) 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.

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is possible to find an analysis of tasks?