Автор anta.baka, история, 4 года назад, По-русски

Добрый день!

В воскресенье, 20-го декабря в 18:05 по московскому времени состоится Отборочный Раунд 3 олимпиады для школьников Технокубок 2021. Раунд будет длиться два часа, участникам будут предложены 7 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация (с 18:15 до 20:05).

Зарегистрироваться на Отборочный Раунд 3 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.

Параллельно с Отборочным Раундом будут проведены открытые рейтинговые раунды для обоих дивизионов, в них могут принять участие все желающие.

Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:

Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!

В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

Авторы отборочного раунда — neckbotov и anta.baka. Cпасибо budalnik и KAN за координацию. Кроме того, хочу выразить благодарность тестерам, без помощи которых этот раунд не состоялся бы: isaf27, 300iq, Kaban-5, low_, Shinchan01, wiwitrifai, Ashishgup, spar5h, Nemo, Gauravvv, Vax, XLor, Um_nik, ADJA, jiufeng, RobeZH, Daryusz, antontrygubO_o, Normie28, kalki411, gratus907, manik.jain!

Для тех, кто впервые на Codeforces: в таблице ниже вы можете найти примеры решений на всех поддерживаемых языках:

Группа языков Языки программирования / компиляторы Примеры
C GNU C, GNU C11 10903473, 17029870
C++ GNU C++, GNU C++11, GNU C++14, GNU C++17, MS C++, etc. 23794425, 5456501
C# Mono C#, MS C# 3195513, 3794163
D D 5482410, 2060057
Go Go 7114082, 21366098
Haskell Haskell 455333, 1668418
Java Java 8 25491359, 23678167
JavaScript V8 35963909, 35681818
Kotlin Kotlin 25779271, 25204556
OCaml OCaml 6157159, 1281252
Pascal Delphi, FPC, Pascal.NET 1275798, 1259434
Perl Perl 2519448, 1277556
PHP PHP 413942, 35875300
Python Python 2, Python 3, PyPy2, PyPy3 35883730 (Py2), 36179112 (Py3)
Ruby Ruby 1837970, 1289551
Rust Rust 25180002, 35652442
Scala Scala 35847980, 2456025

Удачи!

В Отборочном Раунде Технокубка будет 7 задач, предварительные стоимости:
500 — 1000 — 1750 — 2000 — 2250 — 2750 — 3250.

В Div. 2 будет 6 задач, предварительные стоимости:
500 — 1000 — 1750 — 2000 — 2250 — 2750.

В Div. 1 будет 6 задач, предварительные стоимости:
750 — 1000 — 1250 — 1750 — 2250 — 3000.

Опубликован разбор.

Раунд завершен, поздравляем победителей!

Технокубок 2021 - Отборочный Раунд 3

  1. almogwald
  2. serg3000
  3. Pechalka
  4. denisrtyhb
  5. amanbol

Codeforces Round 692 (Div. 1, основан на Отборочном раунде 3 Технокубка 2021)

  1. EricHuang2003
  2. jiangly
  3. hos.lyric
  4. ecnerwala
  5. ugly2333

Codeforces Round 692 (Div. 2, основан на Отборочном раунде 3 Технокубка 2021)

  1. KanbeKotori
  2. xmt
  3. RNG-Ming
  4. YANK01
  5. meidong
  • Проголосовать: нравится
  • +295
  • Проголосовать: не нравится

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

))

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

Don't forget to notice the unusual start time!!!

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

I think some registration cleanups need to be done after the rating update from the previous contest

https://codeforces.net/contestRegistrants/1465?order=BY_RATING_DESC

https://codeforces.net/contestRegistrants/1464?order=BY_RATING_ASC

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

I am unable to type in the city name in the Technocup registration page(the input box isn't working ).Can anyone help?

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

As a person who is familiar with the anta.baka and neckbotov, I think that Russian-speaking high-school students are in good hands. I can assure you that everything will be all right with the contest, because anta.baka's passport is in my pocket.

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

How can I improve?

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

I hope that I reach Pupil after this contest.

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

As a tester, I say that Problems are Interesting :)

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

In letter from Mail.ru was said that contest will start 20.00 MSK, but here there is other time.

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

.

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

    There are literally thousands of blogs related to your question (Google?) and why are you asking this here in the contest announcement blog? :/

    P.S: registered 7 months and still new KEKW

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

надеюсь, отбор тк не короткий тур открытки, и я решу больше одной задачи(

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

Scoring distribution??

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

    Elimination Round will feature 7 problems, preliminary costs are 500 — 1000 — 1750 — 2000 — 2250 — 2750 — 3250.

    Div. 2 will feature 6 problems, preliminary costs are 500 — 1000 — 1750 — 2000 — 2250 — 2750.

    Div. 1 will feature 6 problems, preliminary costs are 750 — 1000 — 1250 — 1750 — 2250 — 3000.

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

I am gonna reach pupil.

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

Is it just me, or does the scoring distribution of Division 2 seems a bit scary?

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

is it rated?

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

*Me after doing A and B: Let's check comment section

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

Pretest 4 ruined the party for me... Looking forward to the solution to this one! :D

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

I have a doubt, for a problem if i did wrong submissions and didn't solve that question in the contest, will these wrong submissions have any effect on my ranking?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
Комментарий удален по причине нарушения правил Codeforces
»
4 года назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

What's test 5 in div2C (after contest)

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

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

Can C be done using number of cycles count?

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

    Yes, initialise ans = m, for every cycle increment ans, for every rook at (i, i) decrement ans

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

    Yep, I passed the pretest. Don't know about system test though.

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

    Yeah, any rook on the diagonal contributes 0 to the answer.

    Any rook not on the diagonal contributes 1 to the answer.

    Additionally, any cycle contributes 1 to the answer.

    This is optimal because moving a rook already on the diagonal off the diagonal is a waste of moves. Any rook not on the diagonal needs at least 1 move to get on the diagonal. And any cycle of $$$n$$$ pieces needs $$$n+1$$$ to resolve (you need to move a piece to a free column/row to remove the cycle, put $$$n-1$$$ pieces on the diagonal, then move back the original piece to the diagonal, for a total of $$$n+1$$$ moves)

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

      Can you please share your code?. Mine is bit lengthy and unreadable.

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

        Not sure if you can see it now but it should be visible once system tests finish (and I hope mine passes :P link)

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

could anyone help me with pretest 4 of div2C ?

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

Aah! This $$$D2C$$$ today:

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

how to solve c??

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

    ignore all points on diagonals. for every other point, connect every 2 sharing x or y.

    for each connected component, check if at least 1 point can be moved to diagonal in 1 move.

    if so, ans += no of points in the component. otherwise, ans += no of points in component + 1

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

    Some hack tests:

    5 4

    1 2

    2 1

    4 5

    5 4

    Then the answer is 6.

    For each rooks $$$(x, y)$$$, add an edge between $$$x$$$ and $$$y$$$.

    For each connect component, if it is a tree, the answer of this component is the number of rooks. And if it is a cycle, the answer of this component is 1 + the number of rooks.

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

      this approach also giving wrong answer

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

      can u explain the intuation behind it? pllzzzzzzzzz

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

        When I tested this round, I firstly guess the answer is $$$m$$$ or $$$m+1$$$ (remove rooks at $$$(x,x)$$$).

        The difference between this two case is that the set of x coordinates and the set of y coordinates. You can see that if these two sets are same, then the answer is $$$m+1$$$, otherwise $$$m$$$. Like 2 rooks $$$(1,2)$$$ and $$$(2,1)$$$, the answer is 3 because $$${1,2}={1,2}$$$. If the first rook $$$(1, 2)$$$ wants to go to $$$(1, 1)$$$, but $$$(1, 1)$$$ is banned by $$$(2, 1)$$$. And if the first rook wants to go to $$$(2, 2)$$$, $$$(2,2)$$$ is also banned by $$$(2, 1)$$$. Is it like a cycle?

        And 2 rooks $$$(1, 3)$$$ and $$$(2, 1)$$$, the answer is 2. The first rook goes to $$$(3, 3)$$$, and $$$(2, 1)$$$ goes to $$$(2, 2)$$$, this may be a chain.

        However, the above conclusion does not work only when the board can be split into many parts, like the above hack test. And then add an edge between x coordinate and y coordinate may be a trick with DSU. There is a similar problem 1013D - Chemical table. Finally, if you do this, you can get the above conclusion.

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

          Can u explain how you are taking an edge between the two cells of the board?

          If you can explain with your above example it would be really helpful.

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

      Solved. Thanks

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

How to do D2C ?

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

I think Div 1 Problem E can turn into : the probability of choosing some number from the sg numbers that =0. Am I right?

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

    If I am right , how to compute? Using basis?

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

    It turns into "compute probability that the resulting Grundy number is $$$x$$$, for each $$$x$$$. You can write a classic recurrent probability formula $$$p(x) = \frac{(x = 0)}{N+1} + \sum_{i=1}^N \frac{1}{N+1} p(x \oplus g_i)$$$ and turn it into Gaussian elimination since the Grundy numbers of vertices are $$$0 \le g_i \lt 512$$$ (approx. $$$\sqrt{M}$$$).

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

      I'm so sad, during the contest I (wrongly) concluded that the grundy values can only be 0 and 1, therefore we have just 2 states in our linear system, and Gaussian elimination isn't needed Q_Q

      Followup question, which might be stupid: is it true that under modulo M, if you have $$$a = P_a*Q_a^{-1}$$$ and $$$b = P_b*Q_b^{-1}$$$, and you take $$$c = a * b $$$ $$$=$$$ $$$P_c*Q_c^{-1}$$$, that the $$$P_c$$$ and $$$Q_c$$$ are automatically coprime and you never need to do any GCD-ing?

      I think it is but I'm not 100% sure, thanks.

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

        You should notice that modulo $$$M$$$, a fraction $$$p/q$$$ is the same as $$$pa/qa$$$ for any integer $$$a$$$ coprime with $$$M$$$. We don't care if the numerator and denominator are coprime with each other, only that the denominator is coprime with $$$M$$$ — which makes sense, they represent the same thing. You'd only care about the exact values when printing fractions or dealing with some operations like "add square of denominator to numerator".

        Of course the Grundy values aren't just 0 or 1, take a semicomplete DAG.

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

      So the time complexity of the Gaussian elimination part is $$$O(M\sqrt M)$$$?

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

        Yes,it can pass in $$$O(M\sqrt M)$$$. Though I found this dp transformation in the contest,but I didn't realize the size of dp status is up to $$$\sqrt M$$$(Maybe I'm not familiar with sg numbers),and I focus in finding the probability of "Xor equal to zero".In fact I have never seen the problem which need Gaussian elimination to update dp. It's a good problem ,thanks!

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

Do you know those annoying implementation problems that have like 100 cases? Well, C is the perfect example of it. :))

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

What's the solution for Div2C/Div1A ? I did it by counting the number of cycles formed in the graph when each rook position (x,y) is connected to (x,x) and (y,y), and then added it to the number of rooks not on the main diagonal.

I'm sure there must be an easy solution.

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

    mine is also the same I don't know why it's getting the wrong answer

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

    For each $$$(i,i)$$$, connect the rook in row $$$i$$$ with the rook in column $$$i$$$ with an edge. Discard self-loops. The resulting graph is a union of cycles and paths, the answer is number of vertices + number of cycles.

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

      can explain the intuition behind it??

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

        Take a path. You can move one rook from one end to the diagonal, shortening the path. For a cycle, you can't do that, so you need at least one extra operation with an unused row/column ($$$M < N$$$ so it's always possible), and using that operation turns this cycle into a path.

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

Worst Div2B ever. I thought I'd get TLE with simple brute force approach but then I looked at the number of submissions.

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

    how does that make Div2B worse if lot of people solved it fast and you didn't

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

      Because a lot of people (including me) solved it by looking at speed at which people were getting AC.

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

        How to solve B?

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

          Keep increasing n until you find the one satisfying the required property.

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

            is this a joke?

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

              Only after you get AC.

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

                I need to look at the constraints more

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

                  There exists at least one valid answer every $$$9!$$$ which equals $$$362880$$$. To be more precise, LCM of $$$1, 2, 3, 4, 5, 6, 7, 8, 9$$$ is $$$2520$$$, so at least one valid answer exists every $$$2520$$$. That's why you can do a linear search.

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

                  I wish I had thought this. I wrote the correct ans and them keep worry for next 2 hrs hope system test won't break my solution.

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

          Every 2520th number has this property, so just brute force for each number from N to the next multiple of 2520. You could have also run a simple while loop, but that gives no proof to why it won't TLE.

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

            For anyone wondering how 2520, it is the lcm of 1 2 3 4 5 6 7 8 9.

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

        standings are available to everyone so you can see and guess whatever you want.Though i proved myself .

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

          "standings are available to everyone so you can see and guess whatever you want" ==> And when whatever = solution, that makes a problem worse.

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

      I'm damn sure 90% of the people solved B without even thinking of its complexity ,more like they just guessed it and you dont't expect it from DIV2B level problem.

      Btw were you 100% sure that your code will get AC and not get TLE verdict?

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

        yes i was 100% sure . I calculate 9! and used similar to pigeonhole principle to prove it .

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

        Well I was sure, but again who knows about such a strict time complexity.

        I checked we would get an answer in max 2520 iteration since 5*7*8*9 would include all the numbers in it. But again instead of using 2520 I used 3000 which sadly made me cost -167 rating :(

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

    Same bruh.... it was only after I saw the brute force implementations that I realized that only a maximum of 2520 numbers needed to be checked. :") I should've moved on to C. :"(

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

    The lcm of numbers from 1to9 is 2520 so it does not take more than 2520 for each test case if one does by simply increasing n and checking its fair or not

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

    I was worried as well, but i've tried generating several cases and noticed that the number of iterations would always be pretty small, hence a brute force would pass.

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

    LCM of first 9 natural numbers is 2520. So brute force will work.

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

Solved A, B , D in last 10 minutes it was thrilling experience.

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

Found Div2D to be not that difficult. Don't know why so fewer solutions.

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

I started 1hr late, solved A and B in <20mins and then lost hope after C and then went to play chess. Does C require some advanced data structure or algorithm?

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

    I don't think it requires some advanced shit. I think it's just something simple that we did not quite figure out.

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

why do you use 1e9+7 in D and 998... in E? congratulations, you have trolled me. I hope your problemsetting career has ended today.

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

My solution to D1C passed the 21 pretests but I found a NullPointerException hack right after contest ended :'(

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

Second day in a row with E<D<C XD

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

    I found C pretty easy. The last 2 signs obviously have to be + and -, but then for any string, we can always proceed from the last operation and "merge" a sign into the next sign if they're different, so that lets us turn any sequence of — to one -, any sequence of + (except the last, which is fine here) to +, and when we're left with +-+-+, that can be reduced to + as well. The rest is some careful implementation.

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

Can anyone prove why brute force works in B? I calculated such numbers upto 10, 000 only to find a pattern!

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

In DIV2 C did we have to count the no. of cycles?

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

Hi! This context was not designed like the previous contexts because until the second question the questions were designed at the ideal level, but from the third question onwards the level of questions was very high and this was really a big weakness !!

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

In DIV2 C did we have to count the no. of cycles?

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

Hi . This contest was not designed like the previous contests because until the second question the questions were designed at the ideal level, but from the third question onwards the level of questions was very high and this was really a big weakness

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

I read there are solutions to problem E that don't utilize the fact that the nimber is at most $$$\sqrt{M}$$$, and works in $$$O(N\log{N})$$$. How do those solutions work?

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

    Suppose that all Grundy numbers are in the range $$$[0, 2^d)$$$. Then, let $$$c_i$$$ be the number of vertices with Grundy number $$$i$$$, by definition, all $$$c_i$$$'s are nonnegative integer and their sum is $$$n$$$. Let $$$p_{k, i}$$$ be the probability that after $$$k$$$ steps of the first type the current Grundy number is $$$i$$$ (including the fact that $$$k$$$ steps may not even happen, so $$$p_{k, i}$$$ go to zero as $$$k$$$ increases). Then, we have a very simple formula: $$$p_{0, 0} = 1$$$, $$$p_{0, i} = 0$$$ for $$$i \neq 0$$$ and $$$p_{k + 1, i} = \sum\limits_{j=0}^{2^d - 1} \dfrac{p_{k, i} c_{i \oplus j}}{n + 1}$$$.

    In other words, $$$p_{k + 1} = (p_k \cdot c) / (n + 1)$$$, where by $$$\cdot$$$ I mean the Hadamard product of vectors. Because $$$p_0 = 1$$$, we get $$$p_k = c^k / (n + 1)^k$$$ (again, $$$c^k$$$ here means the $$$k$$$-th Hadamard power of $$$c$$$). Hence, the probability to end with Grundy number $$$0$$$ is the $$$0$$$-th coefficient of $$$\dfrac{1}{n+1} \sum\limits_{k=0}^{+\infty} \dfrac{c^k}{(n+1)^k}$$$. Indeed, to finish, we need to make $$$k$$$ steps of the first type (summands on the right) and then a step of the second type (multiplier on the left) for some $$$k$$$.

    Now, we can find the Hadamard transform $$$H(c)$$$ of $$$c$$$. Because Hadamard transform is linear
    ($$$H(\alpha f + \beta g) = \alpha H(f) + \beta H(g)$$$, if $$$\alpha$$$ and $$$\beta$$$ are numbers) and multiplicative ($$$H(fg) = H(f) H(g)$$$), we can get the coefficients of $$$H \left (\dfrac{1}{n+1} \sum\limits_{k=0}^{+\infty} \dfrac{c^k}{(n+1)^k} \right)$$$ just by replacing each coefficient $$$x$$$ of $$$H(c)$$$ by $$$\dfrac{1}{n+1} \sum\limits_{k=0}^{+\infty} \dfrac{x^k}{(n+1)^k} = \dfrac{1}{n+1} \cdot \dfrac{1}{1 - x/(n+1)}$$$.

    Finally, just apply inverse Hadamard transform to $$$H \left (\dfrac{1}{n+1} \sum\limits_{k=0}^{+\infty} \dfrac{c^k}{(n+1)^k} \right)$$$ that we just found. The probability of Bob's win is the $$$0$$$-th coefficent of the result.

    There are no issues with division by $$$0$$$ here: because $$$c_i$$$'s are nonnegative integers with sum $$$n$$$, the coefficients of $$$H(c)$$$ are integers from the range $$$[-n, +n]$$$. Hence, $$$1 - x/(n+1)$$$ can't be $$$0$$$ modulo $$$998244353$$$, because otherwise $$$n + 1$$$ and $$$x$$$ are equal modulo $$$998244353$$$, meaning that $$$998244353 \leqslant 2n + 1$$$. In fact, this solution proves that there are no bad tests (tests, where the denominator of the answer is divisible by $$$998244353$$$): there are no bad tests exactly because there are no issues with division by $$$0$$$ in this solution.

    This solution works in $$$O(n + d \cdot 2^d)$$$, if the input is just $$$n$$$ numbers from the range $$$[0, 2^d)$$$.

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

      It's not an improvement on complexity but you can in fact save yourself the inverse transform, since the sum of all coefficients in the forward transform is $$$2^d$$$ times the $$$0$$$-th coefficient in the initial vector (every other coefficient cancels out).

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

      This is easier. Consider the string as sequence of numbers 2^(s[i]-'a'). Last two numbers always will wid fixed signs: s[n-1] is positive and s[n-2] is negative. Other numbers can be with any signs. There are 2^(n-2) ways to distribute signs, but it's possible to find the desired distribution by the binary search principle. Sort the array of n-2 numbers by descending, then iterate over it. Initially all signs are positive. For each number find out, whether you have to change the sign of this number. This is necessary only if and only if the sum of all n numbers after changing remains greater or equal to t. If after iterating this sum is equal to t answer is Yes

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

        Why don't you like my approach???

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

          You are answering for Div2E whereas the above discussion is for Div1E.

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

            This problems have same letters, I didn’t understand. But 9 contribution points cannot be returned

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

              contribution points are also absolutely irrelevant

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

                It's still a shame that the minus dirts my profile. It's not beautiful!

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

                In past I thought that contribution is how much money are donated by him

                (I still bad know English, I'm Russian. Fixed me if.)

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

      I was very close to this solution during the contest but I didn't know about the linearity property of Hadamard Transform, which is why I couldn't proceed further. I have read a few articles on FWHT(including serbanalogy's blog) but never saw this property anywhere, can you suggest some source where I can learn more Hadamard Transform and its properties?

      Thanks a lot.

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

I hate D1D...

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

Can anyone help explain the idea of D2D? Thanks!

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

In today's Div2 ~ C problem: // after contest

  • I first precalculated number of rooks in each row and collumn.
  • Then I took a queue and put the numbers in which row and collumn both has no rooks
  • Then I cheked m roocks if they are in correct place or can be sent to main diagonal by one move using a mark array and precalculated row-collumn counters.
  • Then If I am unable to put rook in less then 2 moves, I poped a number from the queue and puted that rook in the poped position and marked that position accordingly.
  • Thus I got the ans

My code's link : https://codeforces.net/contest/1465/submission/101896978

As far as I think my complexity is O(3*m) => O(n) But I got TLE can anyone explain me why it got TLE

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

    You can use heading little shorter .I thought you were giving solution .

    It's because inner for loop can run 'n' times in worst case thus m*n complexity .

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

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

Am I the only one solve D2C without modeling it as graph and write very long and stupid code 101886029?

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

For Problem D (div.2) Greedy Solution WA test case 9: Dude wtf was with that D problem? I figured I would start off the round by solving D first since it would be 6 problems D should have been solvable. Anyway I read it and I figured if I went greedy it would work since for any test case that I could come up with greedy solution worked. When I say greedy what I did was from left to right when meeting a '?' I know the '1's and '0's before (two counters) and after (this can be done with a sum array from right to left) so I can figure which one is better to put. Can anyone please give me a test case where this doesn't work? I was getting WA in test 9 with greedy solution. Also for the cases where I would get the same cost I went recursively and tried both solutions to see which would give the best answer. Again I did not get TLE but a WA in test case 9. So please somebody give me a test case now that the contest is over. Also let's say greedy doesn't work, what kind of a DP solution would work, like I just need a complexity? Though I don't think a DP solution would work either. This problem must have the need of some really sophisticated data-structure/algorithm combination like Treaps with matrix exponentiation or some. But if you are gonna say 6 problems then make D at least solvable. Look at how many people solved C and how many solved D it's insane. Oh I can see why now... it's because they mostly used orange and red testers. Dude like if you are orange you know every algorithm known to man and every technique you have it already memorized. Competitive programming started ageing like chess smh.

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

For Problem D (div.2) Greedy Solution WA test case 9: Dude wtf was with that D problem? I figured I would start off the round by solving D first since it would be 6 problems D should have been solvable. Anyway I read it and I figured if I went greedy it would work since for any test case that I could come up with greedy solution worked. When I say greedy what I did was from left to right when meeting a '?' I know the '1's and '0's before (two counters) and after (this can be done with a sum array from right to left) so I can figure which one is better to put. Can anyone please give me a test case where this doesn't work? I was getting WA in test 9 with greedy solution. Also for the cases where I would get the same cost I went recursively and tried both solutions to see which would give the best answer. Again I did not get TLE but a WA in test case 9. So please somebody give me a test case now that the contest is over. Also let's say greedy doesn't work, what kind of a DP solution would work, like I just need a complexity? Though I don't think a DP solution would work either. This problem must have the need of some really sophisticated data-structure/algorithm combination like Treaps with matrix exponentiation or some. But if you are gonna say 6 problems then make D at least solvable. Look at how many people solved C and how many solved D it's insane. Oh I can see why now... it's because they mostly used orange and red testers. Dude like if you are orange you know every algorithm known to man and every technique you have it already memorized. Competitive programming started ageing like chess smh.

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

    If x>y, all ? will filled by one of sequences like 11...100...0, from 000..00 to 111..11. In the other case, iterate over all sequences like 00...011...1

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

my code for div2 C is ans=m, decrease if x==y, increase if a cycle is found. my solution solves all test cases suggested in the comment section. and still WA on test case 5. help pls :) Edit: found my mistake, got AC.

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

Can anyone explain div2D .Thanks

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

    Consider all ? positions. If x>y, in the optimally case all the positions with ? filled by sequence like 11...100...0. Iterate over all possible sequences beginning a sequence with all zeroes. Next sequence is 100..0 then 1100..0 and etc. until sequence with all ones.

    In order to maintain the answer for each sequence, precalc for each position from 0 to n, number of 0 and number of 1 to the left and to the right of this position. While iterating the sequences you recalc the numbers of 0 and 1 to the left after each position with ?

    If x<=y, iterate over all sequences from the other side: 0..000, 0..001, 0..011, ..., 1..111 and recalc the numbers of 0 and 1 to the right after each position with ?

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

why some people are getting TLE in B ?

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

Why was there so weak pretests in B?

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

    If you mean that actually brute force isn't acceptable, then I will tell you that it can be proved it's acceptable

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

    pretests are not weak, the time limit is too strict :(

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

1000 TLEs for problem B :))

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

I got TLE in Div2 B. I used the obvious iterative approach i.e. keep incrementing value until a value is encountered which satisfies the condition.

The only possible reason for TLE I reckon is I used maps to store frequency ( occurrence ) of each digit.

Why such strict time-limit? :| This is really frustrating, even if time limit was INTENDED to be strict, why were the pretests weak? Why so much intricate optimizations were expected in div2B? 101865684 P.S. I am losing 160 points today!

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

    Yeah that's the reason. I used set and got TLE too :/

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

    Yes. anyone who has added a log factor has a TLE. I dont see the point of such tight limits.

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

    I also think it is not reasonalbe to fail. Because we only want to store 9 digits in unordered_map, there is even not much collision for hashing. That strict time limit is meaningless.

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

      Agreed. anta.baka I am not being rude but I'd genuinely like to know, from experienced coders and problem setters about their views on the FSTs of problem B.

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

        I personally didn't expect FSTs. T * LCM * log sounds good in theory.

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

          Sorry it is T*LCM*18*LOG SO 1000*2520*18. Anything extra to that will be costly. 18 can not be ignored as it is too close to TL

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

Python submissions are getting TLE.

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

i think problem B is such a bad problem for a contest.

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

Please Check problem B , it is bruteforce i agree but looking at c++ submissions they are getting accepted with fast i/o. Java solutions should be given consideration in such problems.

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

I was supposed to get +73, but after system tests for B failed it's -13. Seriously, guys, strong pretests please. 1000 people failed B system tests.

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

I was supposed to get +73 (and get my all-time high), but after system tests for B failed -23. Such a pity that 1000 other people failed system tests. A disgrace.

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

    Hey, how were you able to determine these +73 and -23 numbers. Can you please tell where I can find them.

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

      download the extension on chrome of Codeforces predictor or use codeforces live bot . BTW Todays contest was horrible for me , I solved C just after 2 minutes of contest ending and thus it is counted as upsolved (which is not wrong), but after this I Got a TLE in B as well , Due to a small log factor , log factor of 10 :(

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

Worst Problem B I ever came across. Problem B is not equally good for all the available programming languages

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

Interesting to see that all but one Python 3 solutions TLEd in system testing for Div 2 B.

The one that passed test 11 (system), used an LRU cache. Test 11 was all the same number. 101880982

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

optimizeForce not codeforce

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

There should be a re-evaluation for B anta.baka neckbotov

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

    Yes, Python solutions with the same logic as C++ solutions should pass.

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

      Come on. There are a lots of problems that if you want to get AC with python, time limit should be 30 second.

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

People with same logic for B, someone getting TLE, someone getting AC. I've seen adhocforces, mathforces, but now optimizeforces ?

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

    True, also almost all solutions in python failed B! B needs re-evaluation!!!

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

      I've seen such solutions in Python itself, where both have same logic, but one is giving TLE and the other is giving AC. The only difference was:- one was using list, one was using string.

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

    But it is not optimization . How can you know your code will get FST after getting pretest passed in 125 ms where limit is 2000 ms . Why will u optimise ur solution in this case?

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

      Yes you are right, I would say that the Testcases were not appropriate.

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

    For example see this two submuissions. AC TLE

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

After having 20+ testers, it is very sad to see there are 1000+ system test fails on problem B (mostly for python3). It is advisable to keep at least one python coder as your tester

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

Why do I get TLE on main test cases for problem B? What the hell man! I don't think this was supposed to happen

Edit: my solution is cpp !!

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

Worst round ever! Make it unrated

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

[deleted]

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

With this problem B, I came from cyan to almost gray in one week and the next contest is in 10 days :(

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

    start a 9-day vigorous practice session, hope you'll bring out the fire in good bye 2020!

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

My rating prediction just went from +100 to -100 only because of storing digits xD

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

I can't understand people who use python for competitive programming. If you use python for competitive programming, so you won't become good in it.

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

    Ever heard of pajengod bruh?

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

    Most people do competitive programming to learn a language and to get better at data structures and algorithms. I use Python because I can, what is the meaning of "If you use python for competitive programming, so you won't become good in it"? What does a language have to do with algorithms and logic?

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

got tle because of storing digits...

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

This Contest went Tough for me but Contests like these are real tester of our skills like patience , how good we are in making comeback after slow start ,implementation . Overall it was a great contest and we will surely gain a lot of things (keeping aside ratings ) for long run

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

Why Ternary search gave AC for problem D div2/B div1.

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

Why Div 2 B rejudge on improved time limits would be fair.

  1. A large number of submissions times out on system test (excl. C++) which are of optimal time complexities.

  2. Had it been a case of TLE on pre-tests, (or even close to time limit), one have the opportunity to re-implement in faster languages. (I saw 93ms and thought it'd be fine)

  3. Languages like Python is not an odd choice for the problem, as it particularly helps iterating over digits without divide and modulo over 10s.

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

    I totally agree with you I was a bit sceptical at first but when I saw that it passed all the pretests so efficiently I didn't think it needed any optimisation at all. Suppose I'd have got something above maybe 1 seconds I would've tried to optimise it or would've thought about my approach again. But those silly pretests kept us clueless. In such cases why to even bother giving the pretests. Just don't tell us anything and let us match the answers just from the example given in the problem T-T

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

Can someone tell why i am getting wrong answer in test case 3 in system testing for div2 B my code :- 101899785

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

    I think it's better if you explain your reasoning/logic as well.

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

      I have counted individually digits for 2,4,8 --> max of three for 6 ---> 6 for 3,9 ---> max of two for 5 or 7 ---> 5 or 7

      then checked if it exits and divides the no. , if it divides then break else increment

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

        Your code is a bit hard to follow. Try not to name variables as 'ttt','se' etc. Why do you check if each digit of 'n'(given number) is divisible by every digit?

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

I hope, you will not do unfair with us by making this rated. Atleast there should be increase of TL and a rejudge.

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

    DIV2 B was just bruteforce ,and if they just want bruteforce to pass then why so strict time limit. Using map gives TLE while withot map AC. I know , Its my mistake that I should have taken the complexity of map implementation into account, but Whats the point of making those submissions System Fail. Anyways, Got to know today, "Use map very Carefully"!

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

Strict time limit and poor pretests , this is unfair ... and you have titled div2B as "Fair Number"

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

Pretty good contest. First two questions boosted confidence. Rest questions were really good. Good job setters :)

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

    Good contest when 1000 people failed system tests for B? Think again.

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

      Maybe we should not blame the author, because that test case also not in pretest. They also don't expect that. But hope they can give a reasonable response

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

        1) I never blamed the authors in my response? 2) I never said this was a bad contest in my response; I simply said it’s undeserving of being called “good” when >1000 participants failed system tests. Only one Python code passed system tests. 3) In Div1E and Div2B submitting the exact same code again sometimes give AC. The time limit was far too tight.

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

        Atleast ,they could have designed a single pretest to check that time limit over submissions during the contest rather than making more than 1k submission fail in just a bruteforce problem!

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

          Or maybe a pretest that takes more execution time like more than 1 second. So that people could get a hint that it might fail.

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

      It isn't that much about good or bad contest. I solved 3 questions and found all of them to be quite interesting. But the problem here is that pretests should be set more carefully. What is even the use of pretests then if isn't able to provide any useful feedback. Like maybe not fail such code in pretests but at least have large execution time (under the constraints). Although this was still a lesson for me :)

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

        Can you tell me what's the point of using a map and how problem b is interesting?

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

          What I found interesting is how the concept of LCM got used here to know that what is the max increment under which we will surely find our answer.

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

my exact same code for div2B gave Tle on system testing but now it is accepted why?

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

In Div1 E, I passed pretest on contest, but I failed the same pretest when systest running. After systest completed, I submitted exactly same code but it accepted!

I am really sad. If I were more lucky, I would pass Div1 E......

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

My submission for Div2-B on contest was TLE on system test , but after system test I submit same code and could get AC. The standard of AC become ambiguous.

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

    i am also facing the same issue, the one i did during contest is still showing pretests passed and the one i submitted (same code) again , got accepted.

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

If you got TLE on B that's your fault for not analyzing the complexity of your solution, especially considering how many people that 'solved' it didn't know what was going on.

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

    then wats the mistake of people using python??? is it fair

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

      Yes? If your know your solution makes around $$$2500 \cdot 1000 \cdot 20 = 5 \cdot 10^7$$$ operations in the worst case you know that python will be too slow.

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

        Even my solution failed when it was making around 5*10^7*3 (3 for log factor) and even if I remove that 3 , i.e. use unordered set it is still giving TLE , I used C++

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

        ohhh i got it they should learn c++ to solve this problem!!! now its fair

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

          Dude if you want to python which is such a damn slow language you should know that your just can't make that much operations

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

      1397B - Power Sequence In this problem, many C++ solutions were considered WA whereas many python solutions were considered AC which used the same logic just because of the fact that the overflow limits of Python are larger than those of C++. So, I don't think your morale should be down by this

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

    I also failed the tests for problem B. Which was because of a factor of log n. Right after I modified it to eliminate the log n factor it gave AC. Mine was in C++. Although I'm still kind of fine with what happened with C++ submissions. But it really sucks for those who gave the contest with Python.

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

Anyone did B with the use of string ?

»
4 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
I'm stupid
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

anta.baka If not for the C++ submissions. At least do something for the python submissions.

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

Nice contest

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

I wonder, why is there a huge gap between the number of participants who solved C and D? in two recent contests.

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

Мне пришло сообщение о копировании кода самого себя, тоисть я отправил один и тот же код и на Технокубок и на див2 раунд по нему, вот и все, я не хочу бан... "Ваше решение 101883259 по задаче 1411C значительным образом совпадает с решениями других участников и находится в группе одинаковых решений Betelgeyze/101883259, Betelgeyze/101883936." Это я писал, не понимаю в чем проблема

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

Hey, could anyone please tell me their approach for problem C? I thought about it for an hour or so but couldn't come up with a solution.

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

    Some hints:

    1) initially ans = m 2) if we have a cycle => ans++ 3) if x[i] == y[i] => ans--

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

my div2B solution is still stuck at pretest passed.. later i submitted exact same code and it got accepted. rating for same is also not given[user:MikeMirzayanov] anta.baka

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

This contest makes me know that you should never give up halfway during a contest! Last night it was 0:30 a.m. here and I really wanted to quit the contest and sleep, but I didn't. And I managed to come up with the solution to C in the last 10 minutes, successfully implemented it in about 5 minutes and got AC! And finally I became international master ;)

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

    I have come up solutions in last few minutes for many time,but usually I can't write the correct code in such a stressful situation.

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

Will there be any other contest before Good Bye 2020 or Not

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

Hello everyone, when will there be information about who made it to the Technocup final in the third qualifying round?

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

please change the colors normal MikeMirzayanov It is not fitting well for dark mode users for example :

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

please change the colors normal MikeMirzayanov It is not fitting well for dark mode users for example:  ![ ](del1)