Автор Zlobober, 9 лет назад, По-русски

В пятницу, 17-го апреля, в 19:00 начнётся Раунд 2 чемпионата по программированию VK Cup 2015! Не забудьте зарегистрировать вашу команду на раунд, регистрация закроется за пять минут до его старта.

В этом раунде могут принять участие все те команды, которые отобрались в Раунде 1 или в Уайлд-кард раунде 1. Напомним, что из первого раунда допущены все те команды, что набрали не менее 796 баллов. В уайлд-кард раунде было достаточно решить не менее шести задач, либо решить пять задач со штрафным временем не более 415 минут. Таким образом, принять участие в Раунде 2 могут 400 + 50 = 450 команд!

Участников ждет соревнование по правилам классических раундов Codeforces. По сравнению с Раундом 1 вас ждут некоторые изменения. Во-первых, одновременно с основным раундом будет проведена интернет-трансляция, которая представляет из себя обычный рейтинговый div1-раунд по правилам Codeforces. В трансляции может участвовать любой div1-участник, не зарегистрированный на основной раунд в составе отобравшейся команды.

Во-вторых, вас, как и ранее, ждёт плавная динамическая система оценки задач, но сами задачи будут расположены в случайном порядке. Участникам будет предложено 6 задач.

Раунд подготовлен силами команды Codeforces, команды VK и пользователя Errichto, который предложил свою неоценимую помощь в рамках кампании "5 лет Codeforces". Большую помощь в тестировании задач оказал winger.

Напомним, что в Раунд 3 пройдут все те команды, которые наберут положительный балл, не меньший, чем у команды на 100-м месте. Также обращаем ваше внимание, что все команды, проходящие в Раунд 3, получат фирменную футболку Чемпионата. Помимо этого, фирменной футболкой будут награждены топ-50 участников интернет-трансляции Раунда 3.

Желаем удачи и интересной борьбы!

UPD: Благодарим всех за участие! Появился разбор задач. Ждём вас на Уайлд-кард раунде 2 и Раунде 3!

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

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

Shuffled Randomly.. this will be interesting :D

»
9 лет назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится

Футболочку бы..)

»
9 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

Is it a rated event?

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

    For all unofficial participants there will be an online mirror that is a usual rated div1-round

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -32 Проголосовать: не нравится

      Is that an official statement? Could you please point to the source?

      EDIT: Thank you very much. I thought the text was the same as the one sent by email, but it isn't.

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

        Just read this topic...This Friday, April 17th, 19:00 there will be Round 2 of VK Cup 2015! For all unofficial participants there will be an online mirror that is a usual rated div1-round. Any div1 contestant that does not participate in official Round 2 is able to compete in this mirror.

        Here is the official statement

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

I hope that pro A will be the easist one, not pro E like last time.

»
9 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Why I can't register for the round. Div1 participants can take part in only div2 rounds why we div2 participants can't take part in only div1 rounds unofficially ?!

»
9 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

The time is not so good for Chinese Coder... Because such a challenge contest will happen at 0:00 a.m. CST and until 2:30 a.m. CST. Maybe waiting for rating updated until 3:00 .. and 9:00 a.m. CST there is a google code jam Round 1A. I don't want to miss any one...

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

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

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

    Думаю не так будет... Все задачи будет на русском. Удачи всем!

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

    Вы можете читать и английские условия, но надо помнить следующее: на Финале будут только русские условия, официальными с точки зрения VK Cup являются русские условия (например, возможная ошибка в английских не будет влиять на подведение результатов этапа Чемпионата). Удачи!

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

А сможет ли прошедшая на раунд 2 команда участвовать в следующем wild-card, если не зарегистрируется на этот самый раунд 2?

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

А я правильно понимаю, что регистрация на этот раунд доступна тем и только тем, кто прошел после раунда1/уайлд-кард1?

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

    Если это не так, то зачем тогда раунд1/уайлд-кард1?

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

      Просто я, например, могу зарегистрироваться. Но вроде бы не прошел раньше. Вот и не могу понять: мне радоваться, что пускают, писать и молчать в тряпочку — или накалякать багрепорт? =)

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

        А вы уверены, что вы действительно можете зарегистрироваться? Форма регистрации предполагает жесткую валидацию в конце процесса.

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

If the team takes place in top 100, will they receive 2 t-shirts?

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

Случайный порядок только для официального соревнования? Или для зеркала тоже?

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

    В обоих местах. Казалось бы, в чём тогда смысл случайного порядка в официальном соревновании, если порядок по сложности можно подглядеть в зеркале...

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

А где будет трансляция??

»
9 лет назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

I just read two random problems and decided that don't want to compete in this match :(

»
9 лет назад, # |
  Проголосовать: нравится -34 Проголосовать: не нравится

Our team advanced to round 2 and I have no idea where is the original round 2.

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

    I had to turn language to Russian. You could write the same post on English language. Nobody told me anything. You could email for example. What is the mean of turning off the registration? please at least turn it on!

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

      >What is the mean of turning off the registration?

      Allocation of participants to rooms.

      You got to round 2 and only noticed that the official round is visible only there just now? How did you open the qualification round and round 1, then?

      Yeah, there's probably no point in putting the Russian-only round to the English part of the site other than wanting to see blogs "I can't register in the official round, help!".

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

    It is Russian-speaking only Championship and the rounds are visible in Russian interface only. The schedule has been published in the day of Chanpionship announcement ~7 weeks ago and never changed.

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

So hard! I will get down rating !

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится -6 Проголосовать: не нравится

E хешами решается или это у меня руки такие кривые, что ТЛится (тест 22)?

Сабмит 10754440 Пока что код недоступен, http://paste.ubuntu.com/10840126/

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

    Там всего 2 сравнения строк нужно сделать, хэши нужны разве что на антихэш-тест попасть.

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

      Тем не менее я не понимаю, почему этот код, а также все его оптимайзы получают ТЛ22.

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

        Так может как раз антихеш-тест? Не даром же Zlobober статью писал.

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

          Так там кажется по модулю

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

          Ну у меня стоит модуль 1e9+9, а антихештест вообще на WA ловит ведь.

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

          Самое смешное, что я сам стараюсь подобный тест в тестсет без специальной надобности не добавлять, но вот сегодня посреди тура решение одной команды было почелленджено именно строчкой Туэ, поэтому в итоговом тестсете она всё-таки оказалась.

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

            Я бы челенджил и решения с константным выбором точки в которой считаем хэш... :)

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

    Складывать в set 5000000 записей — плохая идея.

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

      Спасибо, понял, где собака зарыта.

      P.S. unordered_set, где элемент это (h1 << 32) | h2 тоже не прошел :(

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

How to solve E? I wasted all the time on it but my hashing+unordered_map solution didn't pass pretest 22...

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

    Answer can either be 0, 1, or 2. Take the substring from the the first occurrence of different characters to the last occurrence and check to see how many original strings you could have had.

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

      It's not true. If we have two equals strings the answer is not 0, 1 or 2.

      Edit. Ouch, reading the statement twice don't help =)

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

        and we can't have tho equal string according to statement.

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

        That's what I was solving but the 'Input' section mentions that given strings are distinct. I noticed that only after trying to hack with similar strings.

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

          And I don't understand why such essential information was only given in the input format.

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

            Yeah, was going to whine about it. Turned out that I spent quite a lot of time solving a bit different problem. I agree, it should have been mentioned in the problem statement as well as in the input.

            Same is true for B as well, the only part that confirms that the graph is indeed a tree is the input section where it says that pi < i

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

            "Implement a program that can, given two distinct words S and T..."

            That's main part of the statement.

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

        It's guaranteed that two string are different. :P

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

        S and T will not be same strings. Even if they could have been then it would be really hard to express the answer without modular arithmetic.

        Takeaway: It's OK to take part in contest at 2:00 AM — 4:30 AM but shouldn't have written comment at 4:30AM in the morning.

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

          If the strings are equal, the answer is 25 * n + 26

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

          I don't think the answer may exceed O(len) * 26

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

          Why? Even if they are same max answer is approximately 26 * N since we care only about distinct original strings.

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

            wouldn't in that case ans be 26 * (N + 1) ?

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

              No, consider the case "aab". If you insert 'a' before the first char and before the second char, you'll get the same strings. The answer is 25 * N + 26, as I mentioned above.

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

              In this case it depends on the string. For example

              2
              aa
              aa
              

              The answer here will be 25 + 25 + 26.

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

    So you may not use hashes, just find first mismatch in the strings and define in which of them a symbol was deleted exactly in this position (e.x. s[i+1]==t[i] if a symbol from S was deleted, next I will consider this case).

    Then create two copies T1 and T2 of T with erased symbol inserted before and after position of deleting.

    Finally, you need just to check if erasing a symbol from the second position of mismatching will lead to a string which is equal to S. If both T1 and T2 may be equal — ans=2, if one of them — ans=1, if no one — ans=0.

    I hope it will pass system testing! :)

»
9 лет назад, # |
  Проголосовать: нравится +67 Проголосовать: не нравится

Отличный контест от вк, теперь пойду в вк посижу :D

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

Effect of shuffling and tricky questions: Only half out of all registered people submitted their solutions :/

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

My teammates message(20 min before end): "როდის იწყება ეს დედანატირები მე-2 რაუნდი" ("When vk cup 2nd round will be held?"), Fuck Him -_-

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

How to solve F?

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

    For each possible position and each letter present in t find the candidate letter for the replacement (it might be the same letter). Change s so that these two letters will be swapped and the remaining characters will be replaced with some separate symbol ('*' for example) , it will be kind of mask. Then for each such pair and the possible position you need to check whether this mask from s matches similarly masked t. In valid positions masks for all letters should match. In order to check masks I computed z-function for each possible pair of characters in advance.

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

In prob -B what is the ans of 7 -1 3 1 2 1 1 1 4 4 2 4 3 5 5

»
9 лет назад, # |
  Проголосовать: нравится +43 Проголосовать: не нравится

То самое чувство, когда исправляешь баг в F, смотришь на часы, а там меняется 21:29 на 21:30 >_<

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

I can't seem to submit offline. When will we be able to do this?

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

Is there anything special about test case #35 in problem F? Seems like quite a lot of people failed on it.

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

    Anti-hash?

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

      Seems no. Our solution based on Z function also got WA on this test.

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

    My guess is that it's for errors in pairing logic check, e.g. I add only one "edge" in letters map (forgot to add reversed one). But can't check it until the problem is opened for practicing..

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

      You are right. I was just not completely clearing some array. Seems that everyone has it's own bug, and the 35-th test is just a good one.

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

    For example my code failed on #35, and also fails on this simple test:

    2 2 bc ab

    (answer 0)

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

      Almost all possible compilable codes fail both on #35 and your simple test :D.

»
9 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

System Testing is over . why cant we submit in practice.

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

My solution of F:

  • if we fix the substring of S (its first letter) to match T to, we can recover the pairing of letters: just remember one occurence of each letter (a-z) in T, look at the letters that are matched to them and here it is!

  • we can check if the given substring of S has the same hash (easily computable using polynomial hashes of prefixes) as T after the pairs of letters are swapped — the hash of T is just , where ki is a constant dependent only on the letter i; specifically, if (letters s[i] are numbered from 1 to 26), then over all i such that s[i] = c.

  • for better accuracy, do it for two polynomial hashes

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

    Same solution, just used big module instead of two hashes 10759121

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

    We had similar solution, but from a bit different angle. For a string, let's assign a number to each character — the distance between the nearest same character on the left (or 0 if this character is the first occurrence in the string now). For T it will be constant, for S it's easy to see that we can modify the hash as we're sliding the window — potentially subtract some power if it becomes 0 after the window slides, and add new character (we do not have to remove old character since it's the first occurrence and it's 0 anyway).

    Now, if the hashes match, we have a valid permutation in this position and only then we have to take first occurrences of 26 letters and check whether our permutation forms pairs.

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

По моему, давать С и Е в один контест была плохая идея. Какие-то случаи, что-то там разбирать.

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

    Ну в Е динамику можно было написать.

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

    Так а зачем разбирать?

    В Е пишем полный перебор хешами, в С жадность — второй пытается идти к цели, первый пытается идти к диагонали, на которой стоит второй (чтобы заблочить его).

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

    В Е красивая идея, по-моему. Ищем первый несовпадающий символ в обеих строках (s1[i] ≠ s2[i]). Понятно, что в одной из двух строк символ с индексом i пропущен. Рассмотреть эти два случая, и все.

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

Я так хотел футболку, что до систестов, попав на 51-ю строчку, очень надеялся на то, что у кого-нибудь что-нибудь упадет. Упало! У меня первая же сданная упала! Тем не менее, это все равно позволило подняться на одну строчку вверх и влезть в "футболки".

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

    Не хочу портить радость, но получают же топ 100? :)

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

      Я про неофициальных, официальные сто получают. Хм, пошел перечитал. А про неофициальных написано, что получают лучшие 50 раунда 3, т.е. следующего раунда. Как так? Господин ведущий, это опечатка?

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

    gen попытался испортить радость, но у него не вышло.

    Пробема слегка в другом. В анонсе не очень хорошо написано... но футболки раздаются не в интернет-трансляции этого раунда, а в интернет-трансляции раунда 3.

    Помимо этого, фирменной футболкой будут награждены топ-50 участников интернет-трансляции Раунда 3.

    Условно говоря, все прошедшие в раунд 3 в официальном соревновании выигрывают её сейчас, а все не прошедшие плюс все неофициальные желающие имеют шанс побороться за неё в онлайн-трансляции третьего раунда.

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

      Zlobober попытался испортить радость, и у него вышло.

      Целый вечер все по диагонали читаю, то условия, то правила. Я правда не очень понимаю, зачем в этом анонсе (где глаза ищут "футболки") писать про футболки, которые будут потом. Ладно, зайду попозже.

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

    Помимо этого, фирменной футболкой будут награждены топ-50 участников интернет-трансляции Раунда 3.

    Не понимаю, что, имелось в виду раунд 2?

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

deleted

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

Для тех кто не прошел, когда появится информация про wild-card round? Будет ли он действительно идти всю неделю, повлияют ли время отправки решений на итоговую таблицу?

»
9 лет назад, # |
  Проголосовать: нравится +37 Проголосовать: не нравится

Looking forward to upsolving!!

Zlobober, fix this, pls!

»
9 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Зато теперь шапочка на авке под цвет подходит.

»
9 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Did you simply forget to make submissions public? If not, what is the reason behind it?

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

I was a bit surprised, this is a team contest but rated? http://codeforces.com/contest/532/ratings

»
9 лет назад, # |
  Проголосовать: нравится +61 Проголосовать: не нравится

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

Спасибо за оповещение в начале контеста о случайном порядке задач.

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

Tourist graph be like: Stop me if you can.

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

Could you please link to English version of editorial (or to both versions at once)?

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

Спасибо, было интересно!

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

Не получается отослать задачу в дорешивание, пишет что соревнование завершено, кто-то еще сталкивался с такой проблемой?

Solved — костылями добрался до интернет трансляции ( в списке соревнований у меня пусто), там сдавать можно.