Endagorion's blog

Yandex.Algorithm 2017, third elimination round
By Endagorion, history, 8 years ago, translation, In English

Hi!

It is my pleasure to inform you that today, on June 4 at 15:00 MSK the third and final elimination round of the Yandex.Algorithm 2017 championship will take place. I'm equally pleased to tell that the problems of the round were prepared by me, Mikhail Tikhomirov. I worked for Yandex for three years, and had a great time in a friendly and professional team. Cheers to Yandex!

This round wouldn't take place if not for the work of these great people:

  • Lidia lperovskaya Perovskaya and her team who are responsible for the Yandex.Contest system,

  • Maxim Zlobober Akhmedov, previously a vigilant Codeforces coordinator, and currently a vigilant Yandex.Algorithm coordinator,

  • Mike MikeMirzayanov Mirzayanov and the Codeforces crew who support the Polygon problem preparation system,

  • and finally, all Yandex employees who took part in testing the problems of the round (sadly, the margin of this blog is too narrow to contain all their names).

The round will feature the standard scheme: 6 randomly shuffled problems for 100 minutes with TCM/Time ranking system. The last GP30 points will be distributed judging by the round results, and the final round advancers will be determined at last (find current scoreboard here). You still have the chance to advance even if you missed the previous rounds!

An editorial will be published in a separate blogpost after the round is concluded. We wish good luck to all participants, and hope you enjoy the problems!

UPD: the start is delayed by 15 minutes for technical reasons. Sorry for the inconvenience!

UPD2: the round is finished! Here be editorial.

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

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

Auto comment: topic has been translated by Endagorion (original revision, translated revision, compare)

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

A, D, F -> really nice, especially F

B -> why do such problems even exist? It takes some steel balls to submit it blindly. Took me most time out of problems that I solved xd

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

    Not all problems are always suitable for submitting in blind mode, though. You can actually see that it wasn't necessary to submit it blindly to get high rank.

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

    Solving B with DP was pretty straightforward and had no corner cases. There was no need to solve it greedily.

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

      would you explain DP approache?

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

        dp[i][j][k] = Is it possible to complete the string after placing first i digits so that placed digits are (j=0 — equal to, j=1 — smaller then) corresponding characters of n and (k=0 — not having, k=1 — having) any non-zero digits.

        dp[n][0][1]=dp[n][1][1]=1. Others equal to zero.

        There are two or three ways to move from dp[i][j][k] to some dp[i+1]. We may try placing x, y and (if we don't have any non-zero digits) 0.

        We now only need to restore answer starting from state [0][0][0].

        → Reply