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

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

Привет, Codeforces!

Я рад пригласить вас на Codeforces Round 547 (Div. 3), который начнётся во 19.03.2019 17:35 (Московское время). К официальному участию приглашаются все, чей текущий рейтинг строго меньше 1600. Все остальные — могут принять участие вне конкурса.

Так получилось, что расписание этого месяца не пестрит раундами (координаторы, мы надеемся на вас!), и поэтому я решил частично исправить ситуацию. Все задачи этого раунда придуманы и подготовлены мной в последний день сборов Hello Muscat Programming Bootcamp 2019 и в перелетах из Маската в Санкт-Петербург. Я даже специально засёк время на подготовку: к текущему моменту (задачи готовы к тестированию) я потратил около 6 часов на их подготовку, включая придумывание некоторых из задач. Мне очень нравится работать над задачами, это что-то на стыке творчества и программирования. Очень надеюсь, что вам понравится результат моей работы.



Я в Омане во время придумывания задач для раунда.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Вам будет предложено 6-8 задач на 2 часа на их решение.

Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Я надеюсь чуть позже вместо этого абзаца появится длинный список благодарностей тестерам. Я пока только планирую отдать раунд в тестирование. Спасибо тестерам ivan100sic, KrK, Benq, I_love_Tanya_Romanova, nhho! UPD: И спасибо новым тестерам Pavs, awoo, Narts, anon20016, Stresshoover, Ivan19981305, кто прорешал задачи в режиме контеста.

Удачи на раунде,
MikeMirzayanov

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

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

Round #543?

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

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

MikeMirzayanov is always ready to take codeforces to a great level. Thank you so much for providing us a great platform to learn.

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

from where mike mirzayanov practice problems ?

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

Thank you for this sudden surprise during these boring holidays

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

Just asking, but how many time did you sleep for the last two days?

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

I'm happy :)

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

I'm a simple man, i see Mike i upvote

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

Where are div1 rounds?))

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

Will Div.2+3 be a new kind of contest

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

Happy to know that the test cases will be stronger enough.

Best of luck

Happy Coding

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

Where's the "Thanks to MikeMirzayanov for codeforces and polygon"???

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

A round without dear Vovuh, but we still got the great Mike :D
Looking forward to it. ;)

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

It seems to have been quite a while since the last contest has ended. So I'm looking forward to the next contest. :)

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

Верните Vovuhа.

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

Great to see Mike frequent involvement in the codeforces community, really inspiring :-)

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

last div3 was awesome!! looking forward to this now...

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

"It so happened that the schedule of this month is not replete with rounds..." true... thats sad :(

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

wow(copy-paste is not contained in the blog of div3 round). I think it is going to be an interesting contest.

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

CF-MEME-2
:3

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

Возможно я чего то не понимаю, но странно что див3 раунд тестируют участники с рейтингом 2600+.. разве не логичней тестерам быть 1500 рейтинга? (Просто я понимаю это так: тестирования надо делать для того что бы глупые решения не проходили в +- сложных задачах, а также что бы совсем плохие решения не проходили претесты, ну и проверить правильный ли порядок задач) А когда решают ребята такого уровня (2600+) они сразу пишут хорошее решение которое не проверяет эти аспекты..

UPD: Когда я это писал, то тестерами раунда были ТОЛЬКО 2600+

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

    Именно поэтому у меня есть договорённость о тестировании раунда студентами Саратовского ГУ (не финалисты ICPC, другие ребята). Но вот отмечу, что от тестирования сильными участниками было много пользы — реально помогли найти интересные тесты, сделали серию улучшений условий.

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

    Это, кстати, интересный вопрос: кто будет более успешен в придумывании плохих решений — участник с рейтингом 2600 или участник с рейтингом 1500 :)

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

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

      Надо отличать такие ситуации от ситуаций, когда участникам с рейтингом 2600 или чуть ниже лень делать тесты, и они просто коммитят рандомные, и задача готова за полчаса, а потом мы наблюдаем 200+ взломов от Халявина.

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

        Я полностью согласен — ровно поэтому я и написал, что это интересный вопрос. Мне не очевидно, что в такой ситуации перевешивает, и какой вариант лучше, если надо выбрать только одно из двух.

        Я бы пошел дальше — и сказал, что в идеальном мире хочется видеть среди тестеров участников со всем спектром цветов.

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

          А зачем нужен серый/зелёный тестер? Он все равно на раунде решает около 1 задачи и все.

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

            Банальный пример: помочь с оценкой того, насколько сложны задачи для синего/зеленого участника.

            Еще пример: как уже указали выше, если ты просто смотришь на задачу и знаешь "ну вроде стандартная задача, решается вот так", то это не принуждает тебя к такой креативности, как попытка решить задачу, которая для тебя достаточно сложна.

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

              Задачи А никогда не бывают сложными. В 90% случаев достаточно просто реализовать написанное в условии.

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

                не сказал бы, что 90%; достаточно часто надо немного подумать, прежде чем реализовывать
                да и каждый раз можно видеть большой лист нулей в конце таблицы

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

                  Когда в последний раз надо было думать в А (кроме Educational 61)?

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

Thanks your your work!!! I am looking form it for a long time!!!

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

a div3 round that needs a legendary to be tested? — it must be a super div3 round.

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

I'm so happy that the original creator is still in touch with us students. Even takes time to think up new and creative problems for us in Div 3 :D

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

You forgot to thank MikeMirzayanov for the awesome Codeforces and Polygon platforms, hope everything goes well!

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

I think two hours isn't enough to solve 8 problems!!!

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

Well, it is harder than normal div3.

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

One of the best contests I have given. All the problems were very interesting. Problem F was very good, I thought of the logic but could not code it within time.

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

I think this Div.3 is a Good Contest with high quality

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

I rewrote my solution for D at the last moment and submitted when 3/4 minutes was remaining.But it was kept in queue for the last 3/4 minutes . And after the contest ended I now see that I got WA for a small mistake that I could have fixed if the verdict was given on time . Is this fair !!!

If there is In Queue problem the duration of round should be extended

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

C was nice. Other ones- Don't give up while implementing. (I did) :p

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

    I go TLE. i tried to avoid it but got TLE in different test cases.

    This is my Code

    any hint ?

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

      assuming there are n numbers then you can get n equations with n variables from the constraints given. Use the fact that the sum of numbers is S= n*(n+1)/2 and other n-1 equations can be obtained from the q array. You can get the last number using these equations and then all other numbers can be calculated using this and q array.

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

      If you get any element other can be found. So we try to find out the first one. Observe that p2=p1+q1 , p3=p2+q2 = p1+q1+q2 , p4 = p3+q3 = p1+q1+q2+q3 and so on. So add all p1,p2...pn which is an equation in p1 and you already know the sum of the expression. Thus you get p1 and other elements. Output -1 if p1 is not an integer or obtained permutation doesn't contain all numbers from 1 to n.

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

      The time complexity of your code is O(n*n)

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

Почему показывалось, что моё решение к задачи Е тестировалось на 115 тесте?

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

C was very nice problem, can anybody explain me the approach. Can't wait till editorials are out!

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

    You are given essentially a difference array, so if you compute the prefix sum array you should get the original elements offset by some number. You keep track of minimum and maximum of this prefix array, and the first element should be 1-minimum. While constructing the original array you also make sure each element from 1 to N is seen once only.

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

    Hello! Let's write our array as: p2-p1, p3-p2, p4-p3, ... , p(n) — p(n — 1).

    Now let's find the prefix sum of this array. Then we will have following: p2-p1, p3-p1, p4-p1, ... , p(n) — p1.

    I think it is obvious that if we have two same elements in the prefix sum array then answer is -1.

    Otherwise let's take element n-p1 (it is the maximum). Let it be equal X. Then n-p1 = X -> p1 = n-X. Now, using this p1, we can construct our array. If such answer is valid, we can print it. Otherwise answer is -1.

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

    You can assume the first element be x. then the second element is q1 + x third element is q1 + q2 + x. the fourth element is q1 + q2 + q3 + x and so on. the sum of all elements is (n*(n+1))/2

    so you can find the value of x.

    after finding x you can easily find entire permutation

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

    I solved using prefix sums and some basic maths.

    Approach:

    $$$(q_1) = (a_2-a_1)$$$

    $$$(q_1+q_2) = (a_3-a_1)$$$

    $$$(q_1+q_2+q_3) = (a_4-a_1)$$$

    And so on. Summing all the above equations we get:

    $$$\Sigma ($$$prefix terms of $$$q)=(a_2+a_3+...+a_n)-a_1(n-1)$$$

    $$$\Sigma ($$$prefix terms of $$$q)=((n*(n+1)/2)-a_1)-a_1(n-1)$$$

    Find $$$a_1$$$ from the above equation. Once you find $$$a_1$$$, you can easily find the rest terms using the given values of $$$q$$$. Finally, check if all terms are present in the range $$$1$$$ to $$$n$$$ and also check if all terms are distinct or not. If not, print $$$-1$$$ and exit. Else print the numbers.

    I'll leave the implementation part for you to try. Hope this helps. Happy Coding.

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

    Think of it as plotting n points on a 2d grid where the index of the array is the x coordinate and value at that index is the y coordinate, start from (1,0) (assume the value of the first element to be 0) and use the given array q for calculating the position of next points. a[1] = 0 a[2] = a[1] + q[1] a[3] = a[2] + q[2] and so on. Now find the minimum value in this array, let the minimum value we get from the constructed array be min_val. Now add min_val+1 to all the elements of the array (shifting the whole plotted figure up so that the lowest point is 1).Now check whether the array is a valid permutation or not and print the result. Here's the implementation of above mentioned approach. 51508498 Hope this helps.

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

    My approach i wrote the O(n ^ 2) approach to find a sequence. let's assume that the first element is a1 = n, so we get sequence a1, a2, .., an if we decrease the first element by 1 all other elements also decrease by 1 so i assume that the first element is n and i make sure that are elements are distinct and if i increase or decrease my sequence the min and max element inside the sequence is 1 and n. 51541819

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

The speed at which people here solve problems is just unbelievable! Kudos!

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

Kudos to MikeMirzayanov. Organized a great Div. 3 round in minimal time!

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

Well I thought there were ONLY 24!!!! characters in English then I got sweet WA for D at last second, switch to 26 after the contest and I got AC What the heck I am thinking about ????

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

Что-то, кажется, и сам MikeMirzayanov не справился.

Если что, https://codeforces.me/contest/978 вот каким должен быть Div 3.

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

Problem G is a fake problem! I'm so weak

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

Could you help me problem C, I got TLE. I generate all permutation and check for each of them. My code: https://ideone.com/PME2fJ

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

    This complexity is too high I think you should learn from others' code.

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

    The number of all permutation is $$$O(n!)$$$, and for each permuation, you need $$$O(n)$$$ to check it.

    So your solution is $$$O(n\cdot n!)$$$, quite large :(

    You can try an array $$$n, n-1, n-2,\dots,1$$$, and n is $$$10^5$$$, your solution will get TLE :(

    When n is quite small, your solution can get the answer.

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

How to solve problem F?

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

    Just use map<int,vector<R,L>> store the sum of every l and r,after that you can sort the vector and get the answer.

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

    $$$n \le 1500$$$, so you can use a map to store each block with the same sum.

    For each sum, there are many segments, and some of them may intersect. so you need to calculate the maximum number of disjoint segments, and this problem an be solved using greedy algorithm.

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

      How would you calculate time complexity for this solution? O(n^2) for all possible sum but what about upper bound on processing each vector corresponding to a certain possible sum?

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

        There are $$$n^2$$$ possible sum, so $$$O(n^2 log n^2)$$$ insert all the sum into the map.

        In the greedy algorithm, we also need at most $$$O(n^2 log n^2)$$$ to sort all the elements(each element will be sorted at most once), and $$$O(n^2)$$$ to get the answer.

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

        Same as total times insertion is done because each pair is processed only once.

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

I enjoyed this round Strong pretests and balanced problemset

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

Awsome DIV3 contest!!!

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

can someone please help with f2

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

F и G просто прекрасные задачи, спасибо!

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

For question 2, How

1
1

is invalid input. According to question it seems good.

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

i have a question what will happen if you hack your own code?

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

How to solve H?

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

kudos to MikeMirzayanov !!! . Conducted really good round with awesome questions.

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

Why its showing WA even though the TC is giving the correct result on my PC. solution

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

    I'm pretty sure that your solution also gives the wrong result on your computer. Check again.

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

plz find a test case at which my solution is getting wrong answer. https://codeforces.me/contest/1141/submission/51545372

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

Problem E , Can anyone tell me why this code is giving wrong answer at test case : 92

https://codeforces.me/contest/1141/submission/51547489

what i did is , suppose we had played x-1 round and currently at round x , we will check whether we can kill monter in that round x or not , if yes we shift high to curr round — 1 else low to curr round + 1 .

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

    Write a brute-force program and make some small scale random input to check whether your algorithm is correct.

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

    If you can't kill the monster in round x, it doesn't mean that you can't kill it in earlier rounds.

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

    why i am dwnvted. have i asked anything wrong

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

.

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

Overall round was pretty good, I thought that this was one of the easier Div 3. Although wish I had 10 more min to submit E ;) I hope to see more of these types of problems in the future.

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

anyone could say me the solution of problem G ?

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

anyone could say me the solution of problem G ?

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

    So, I haven’t submitted this solution yet, but I think I have the idea.

    Generate the degree sequence for the tree. The k nodes with the highest degrees will be bad nodes. Then the (k+1)th highest degree (call it c) will be the number of colors needed so that (n-k) nodes are good and k are bad. That is, with c colors, we can color edges so that (n-k) nodes have edges of all distinct colors. This will work because (n-k) nodes will have degrees <= c.

    We can then choose a root, and greedily color the tree from the top down.

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

      why color the edge greedily will be the answer ? (with dfs)

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

        let's say the highest degree is C.

        if we're at a node which has a degree greater than C we can colour them all the same colour, it doesn't really matter. If it's less than or equal to C, we start colouring it from 1 and keep incrementing it for each child(with the exception that it can't be the edge connecting it to the parent's colour)

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

Here,the scenario is look like for starting questions Div2<Div3

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

Has anyone solved problem E using Binary search, I am getting wrong answer on test case 17.

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

    Your binary search borders are so high they cause long long overflow in min hp calculations.

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

      Yes i got it why it is failing. can u suggest what changes should i make?

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

        I set the upper bound to $$$\lceil \frac{hp}{-sum} \rceil$$$ in my solution and it worked fine.

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

          Yes, you are applying binary search for the round right? I was applying for the minute at which the monster will be killed. The solution with binary search on rounds got accepted. Thanks.

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

    yes.. i solved it.. see my solution and if doubt dm or tag me in announcement

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

      Yes, I saw ur solution, it was involving binary search on rounds right? I was applying binary search for the exact minute at which the monster will be killed, and apparently as Pikmike mentioned, while calculation of min, long long would overflow. Thanks for help!

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

        no calculation of minute along with overflow will give wrong answer .

        if it is not possible to kill monter in x th minute then its not possible to kill monster in < x minutes , is wrong approach . u have to take rounds .

        at first i thougt bs on minutes , but laster i realized its wrong .

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

Why my contribution went from 0 to -4 by itself (just wondering)

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

whats going on? why C is rejudged??

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

whats going on?? why C is rejudged?

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

Problem c Many people construct a sequence starting at 1, and then judge whether {1 2 3 ... n} is satisfied. In the judgment, some people use the Vis array mark to determine whether there are duplicate numbers. This is not a good solution. Considering the worst case, (2e5 19999 19999.....), this will appear. The case where the array is out of bounds.

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

    Meh, that's the boring hack. Check this solution 51538168! $$$cp$$$ gets equal to $$$-2^{31}$$$, then $$$x$$$ becomes $$$2^{31} + 1 = -2^{31} + 2$$$ and thus no $$$-1$$$ checks are hit because the conditions are too weak.

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

      X and map should be long long? I think his code is not rigorous.

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

        Basically, $$$x$$$ and $$$cp$$$ is enough to be long long. I don't think you can break map being int tbh.

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

C:

Runtime error on test 42;

solved: 5->4;

standing:249->756;

I:happy->unhappy;

Anyway, excellent and innovative problemset .

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

Can anybody please tell me why this solution for problem F2 is failing at test case 28?

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

Someone, Please explain D.

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

    Just think simple!
    We know that ? will make compatible pair with anything!
    So first we make pairs that doesn't have any ? and after that pairs that has exactly one ? and at the end pairs that are both ?.
    It is clear that the algorithm is the optimal.

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

wrong answer in D: "You can't use one boot in two pairs", can anyone tell me what it means? and why it give me a wrong answer, this is my practiceYour text to link here...

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

    Look, the boots are for the left or for the right foot.
    You want to match these boots (make pairs of left and right boots).
    And "You can't use one boot in two pairs" means that you can't match a boot with two other boots.
    For example you have two boots of left foot numbered 1 and 2, and two boots of right foot numbered 3 and 4. you can't match boot number 1 with boots 3 and 4, you can choose at most one of them.

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

      oh, Thanks for your answer! I have thought that! But why my practice is wrong, I have checked for much time, can you speed a little time checking my practice? Wrong answer on test 22, the test data is so long, I can't see the remaining part.

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

I thought successful hacking would add my points, but it seems to be not the case. The rule says it's worth 100 points. Has it been changed?

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

    that is for div2 and div1 contests (expect educationals).
    hacks in contest's that have hacking phase after the contest don't have any point.

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

Thank you for this good contest.

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

Why did so many people fail problem C? Somehow, my solution passed but I was still wondering.

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

1

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

C was indeed a creative problem! :)

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

When can we expect editorial of this contest?