GlebsHP's blog

By GlebsHP, history, 2 weeks 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  

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

will the statements be in English ?

»
2 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

is it rated??????

  • »
    »
    2 weeks 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

  • »
    »
    13 days 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.

»
2 weeks 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 ??

  • »
    »
    2 weeks 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 .

  • »
    »
    2 weeks 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.

»
2 weeks 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?

  • »
    »
    2 weeks 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.

»
2 weeks 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.

  • »
    »
    2 weeks 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.

»
2 weeks 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

  • »
    »
    2 weeks 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.

»
2 weeks 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.

  • »
    »
    13 days 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...

»
13 days 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.

»
13 days 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/

»
13 days 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).

»
13 days ago, # |
  Vote: I like it +8 Vote: I do not like it

This year Yandex Algorithm takes place much earlier than before.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
13 days 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.

»
13 days ago, # |
  Vote: I like it +33 Vote: I do not like it
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D?

»
13 days 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)

  • »
    »
    13 days 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?

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

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

      • »
        »
        »
        »
        13 days 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!

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the same and got WA at test 4 .

  • »
    »
    13 days 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.

  • »
    »
    13 days 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.

  • »
    »
    13 days 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 }

»
13 days 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.

  • »
    »
    13 days 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)

    • »
      »
      »
      13 days 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?

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved with DP and bitmasks.

»
13 days ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve B?

  • »
    »
    13 days 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.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks

    • »
      »
      »
      13 days 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

    • »
      »
      »
      13 days 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).

      • »
        »
        »
        »
        13 days 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"

        • »
          »
          »
          »
          »
          13 days 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!

»
13 days ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve problem E?

  • »
    »
    13 days 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.

»
13 days 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

»
13 days 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?

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

    There are also qualification round

  • »
    »
    10 days 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 :)

»
13 days 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?
  • »
    »
    12 days 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.

»
12 days 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!

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't register.

»
8 days 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