GlebsHP's blog

By GlebsHP, history, 6 months 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  

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

will the statements be in English ?

»
6 months ago, # |
  Vote: I like it -13 Vote: I do not like it

is it rated??????

  • »
    »
    6 months 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

  • »
    »
    6 months 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.

»
6 months 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 ??

  • »
    »
    6 months 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 .

  • »
    »
    6 months 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.

»
6 months 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?

  • »
    »
    6 months 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.

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I always have problems logging into that yandex website -_- . Yesterday I changed the password and today it is not logging in. The same thing happened with me last year.

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

    I've just changed the password, logged out and trying to log in but it says "Wrong Password" as always -_- . Password is just copy&paste.

»
6 months 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

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

    I changed the language during registration and there was only two labels that remained Russian.

    Still you can use Google Chrome to translate the page.

»
6 months 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.

  • »
    »
    6 months 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...

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

google translate is not working on this site. it is always showing in russian and hence i selected each word for translation. But the select options are not available in english. plz fix this.

»
6 months 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/

»
6 months 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).

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

This year Yandex Algorithm takes place much earlier than before.

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

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

»
6 months 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.

»
6 months ago, # |
  Vote: I like it +33 Vote: I do not like it
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

»
6 months 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)

  • »
    »
    6 months 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?

    • »
      »
      »
      6 months ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

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

      • »
        »
        »
        »
        6 months 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!

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

    I did the same and got WA at test 4 .

  • »
    »
    6 months 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.

  • »
    »
    6 months 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.

  • »
    »
    6 months 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 }

»
6 months 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.

  • »
    »
    6 months 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)

    • »
      »
      »
      6 months 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?

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

    I solved with DP and bitmasks.

»
6 months ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve B?

  • »
    »
    6 months 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.

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

      Thanks

    • »
      »
      »
      6 months 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

    • »
      »
      »
      6 months 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).

      • »
        »
        »
        »
        6 months 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"

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

          True, I just did read it in a wrong way – I was finding lexicographical smallest palindrome instead of to find lex smallest among shortest ones. Thanks!

»
6 months ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve problem E?

  • »
    »
    6 months 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.

»
6 months 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

»
6 months 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?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    There are also qualification round

  • »
    »
    6 months 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 :)

»
6 months 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?
  • »
    »
    6 months 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.

»
6 months 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!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't register.

»
6 months 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