Блог пользователя GlebsHP

Автор GlebsHP, история, 4 месяца назад, По-русски,

Всем привет!

Команда проведения чемпионата с радостью сообщает вам, что регистрация на седьмой турнир компании Яндекс по спортивному программированию (а теперь и не только по нему) Яндекс.Алгоритм 2018 уже открыта! Чемпионат является прекрасной возможностью порешать интересные задачи, посоревноваться с любителями спортивного программирования со всего мира, и, возможно, выиграть фирменную футболку. Традиционно, 25 наиболее успешных любителей спортивного программирования будут приглашены принять участия в финальном раунде, который в этом году состоится 19 мая в Санкт-Петербурге.

Если вы уже немного устали решать обычные олимпиадные задачи по программированию, или просто ищете соревновательного разнообразия, то вам, возможно, будет интересно принять участие в двух новых треках: оптимизационном и ML.

Разминочный раунд пройдёт уже в это воскресенье!

UPD: ссылка на разминочный раунд.

UPD2: появился разбор задач!

 
 
 
 
  • Проголосовать: нравится  
  • +310
  • Проголосовать: не нравится  

»
4 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

will the statements be in English ?

»
4 месяца назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

is it rated??????

  • »
    »
    4 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится +106 Проголосовать: не нравится

    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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Of course it is!

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

»
4 месяца назад, # |
  Проголосовать: нравится +45 Проголосовать: не нравится

Можно более явно: финал — онсайт или онлайн с возможностью написать в СПб?

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится -27 Проголосовать: не нравится

    Финал конкурса пройдёт 19–20 мая по адресу: Российская Федерация, город Санкт-Петербург, Пискаревский проспект, д. 2, корпус 2, литер Щ. Каждый финалист должен подтвердить свое участие и представить все необходимые документы до 20 апреля. В противном случае он будет дисквалифицирован. Финальный раунд пройдет по правилам TCM/Time, длительность раунда будет между 120 и 180 минутами, объявлена непосредственно перед его началом.

»
4 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

В прошлом году была введена новая фича: оптимизационная задача, результат по которой влиял на итоговый результат. В этом году, как я понял, это считается отдельным контестом? Т.е. результат по каждому треку независим?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Да, в этом году результат по каждому треку независимый.

»
4 месяца назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

is not the open submission better or what ??

  • »
    »
    4 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 месяца назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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).

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

This year Yandex Algorithm takes place much earlier than before.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем GlebsHP (предыдущая версия, новая версия, сравнить).

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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.

»
3 месяца назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится
»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D?

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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)

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        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!

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I did the same and got WA at test 4 .

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    3 месяца назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 }

»
3 месяца назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve E? I got WA 3

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
3 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve B?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        "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"

        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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!

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve problem E?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
  1. Where can i find the editorial for the warm-up round?
  2. Is it possible to see the accepted solutions of other participants?
»
3 месяца назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Автокомментарий: текст был обновлен пользователем GlebsHP (предыдущая версия, новая версия, сравнить).

»
3 месяца назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Господа из Яндекса, насколько для вас сложно сделать линк с главной страницы соревнований (https://contest.yandex.ru/) на текущее (https://contest.yandex.ru/algorithm2018/)? Каждый раз мне приходится искать ссылку на текущее соревнование где-то в гугле или в письмах. На главной же странице ни одного упоминания и все ссылки ведут на какой-то прошлогодний трэш (ну либо я не нашел).

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    В меню выбрать "Соревнования", дальше "Яндекс.Алгоритм-2018".

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      Спасибо! Раньше там был только 2017 год и еще более ранние соревнования.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I can't register.

»
3 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

В форме регистрации нет поля для псевдонима, хотя многие участники (наверно большинство) отображаются под псевдонимами. Как его можно задать?

»
3 месяца назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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