GlebsHP's blog

Yandex.Algorithm 2018
By GlebsHP, history, 7 years ago, translation, In English

Hello everybody!

Yandex.Algorithm 2018 team is glad to announce that the registration for the seventh competitive programming (and even more) championship held by Yandex is open! The championship is a wonderful opportunity to practice with interesting problems, compete against addicted programmers all over the world, and battle for a brand T-shirt. As usual, 25 most successful addicted competitive programmers will be invited to onsite finals that will be held in Saint Petersburg on May, 19.

In case you feel tired of classical competitive programming problems style, or just seek for competitions of any possible kind, you might be interested in new tracks we announce: optimization and ML.

Warm-up round will take place this Sunday!

UPD: link to warm-up round.

UPD2: editorial is here!

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

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

will the statements be in English ?

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

is it rated??????

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

    Good point. They are hosting contest on yandex site, but that is their cheap way to catch you off guard. They will change your cf ratings

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

    Of course it is!

    And I'm not sure if it is the first contest hosted on yandex site.

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

did not understand what is the difference between an open or a blind submission ??

is not the open submission better or what ??

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

    if you send blind submission, then if you solve it correct, then the some amount of time is subtracted from your time .

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

    One of the reasons to conduct a warm-up round is to make it possible for you to become familiar with TCM\Time rules.

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

Why is the start time of the warm up before the end time?

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

    Ok, so I switched my language to russian, and the time says 21:40. I still think the english version needs updating to clarify this though.

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

It's difficult to understand the Russian in the registration form. Why after changing the language is it still in Russian? T_T

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

What happens when the contest starts? A button will appear? I'm not familiar with the system, if anyone could enlighten me, I will be thankful.

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

    Yeah! Pls somebody clarify this ASAP. I'm giving the Yandex contest first time so don't know about how it works...

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

When will the contest link be posted on the Yandex Algorithm site? This is the link ryt?https://contest.yandex.com/algorithm2018/

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

How can I specify the permanent address of residence? There's no field in the registration form to specify that (the field with closest meaning to that is the 'city' field).

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

This year Yandex Algorithm takes place much earlier than before.

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

    :) Looks like Yandex hired some good competitive programming engineers from Facebook.

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

There is some mistake probably, I think this

The Optimization track consists of two rounds.
The first round of the ML track will start on March 05, 2018 at 10:00 and last 7 days.
The second round of the ML track will start on April 02, 2018 at 10:00 and last 7 days.

should be

The Optimization track consists of two rounds.
The first round of the Optimization track will start on March 05, 2018 at 10:00 and last 7 days.
The second round of the Optimization track will start on April 02, 2018 at 10:00 and last 7 days.

since the ML track is mentioned a few lines after that and it says it consists of only one track, starting on March 16.

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

That's why I love e-olymp: https://www.e-olymp.com/en/contests/9371/problems/81900

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

How to solve D?

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

How do you solve C? I checked if all the centers were collinear and then checked if they would split all rectangles along either diagonal or perpendicular, but I think I might have some bug (or could just be 100% wrong)

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

    I was doing the same thing. Were you getting WA on test case 6?

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

      be careful, there can be two objects with the same center

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

        Yep, I used std::sort and then std::unique and std::erase to delete repeating points.

        Must be an extremely dumb bug. At least feels good to know that my approach was correct.

        Thanks!

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

    I did the same and got WA at test 4 .

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

    Checking whether all centers are collinear is enough. Probably you had a bug somewhere in your code.

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

    I was just checking collinearity of the centers, because unless I am completely wrong, any line going through rectangle's center still splits it in two halves. But it didn't work.

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

    Solution is check that all centers of mass* is on one line. But you should be carefull because centres can be same point

    * for circle it is a centre, for rectangle it is { (x1 + x2 + x3 + x4) / 4, (y1 + y2 + y3 + y4) / 4 }

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

Can anyone please share the solution to problem F?

I realized that for a 2x5 block, the best you can do is 3 processors:

1 0 0 0 1

0 0 1 0 0

And for the multiples, you can just tile this 2x5 piece.

But could not figure out what to do with the remainders.

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

    dp[i][mask1][mask2]

    (Note that number of transitions (mask1, mask2) -> (mask2, mask3) for n = 7 is 18320)

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

      dp[i][mask1][mask2] = minimum number of liars among the first i rows such that the last second row has mask1 and last row has mask2

      Is that correct?

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

    I solved with DP and bitmasks.

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

How to solve B?

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

    Check all substrings of size 2 first, if palindromes are found, return lexicographically smallest one.

    If not found, do same for size 3.

    If not found, return -1.

    You can show then for even n>=4, if palindrome exists, a palindrome of size 2 also exists.

    And for odd n>=4, if palindrome exists, a palindrome of size 3 also exists.

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

      Thanks

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

      I think for all n>=4 If the length of the palindrome is even . A palindrome of length 2 exists

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

      What about test case "abba"? The correct answer is "abba", not "bb" (since we have to find lexicographically smallest one).

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

        "Print the shortest substring of the input string that consists of at least two characters and is a palindrome"

        "Do not forget that Arkady want to find lexicographical smallest possible such string"

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

How to solve problem E?

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

    Notice that you can first remove K - 1 sons of the root, which means you can remove their whole subtrees afterwards. The K-th removed son needs to be the last removed vertex overall — the situation for its subtree is the same as for the original subtree, so it can be solved recursively using some tree DP.

    Besides that, there are some other sons of the root. These can't be removed at all, but we can remove K - 1 sons of each of them (with these sons' whole subtrees, just like above); the situation for the remaining sons' subtrees is the same again, so this can be done with another tree DP.

    There are two tree DPs to compute in parallel: the max. number of removable vertices in the current subtree if the root needs to be removed last and if the root mustn't be removed.

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

I solved one problem during the contest will i be qualified for the elimination round

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

I missed it. :( Could I be let into rounds as a finalist of some year?

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

    There are also qualification round

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

    Don't fool yourself, you will definitely miss the ongoing rounds too and end up as a final round tester for the third time :)

    → Reply
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it
  1. Where can i find the editorial for the warm-up round?
  2. Is it possible to see the accepted solutions of other participants?
→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Last year the editorial was published here in Codeforces, and in the schedule page, I think it'll be the same this year.

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

Is there any filter by country or friends in the standings, it'll be really helpful to have those filters!

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

I can't register.

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

I can't enter the qualification round, it says 'You are not registered for Algorithm 2017.' and links to 2017 registration page??

edit: I registered to 2017 contest and can enter now ... nice system

→ Reply