Автор KAN, 3 года назад, По-русски

Добрый день!

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

Зарегистрироваться на Отборочный Раунд 3 →
Соревнование открыто для всех в виде отдельного раунда.
Раунд Технокубка является рейтинговым для всех участников, Параллельный раунд рейтинговый для участников из второго дивизиона.

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

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

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

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

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

Удачи!

UPD: поздравляем победителей!

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

  1. LeoPro
  2. princebelkovetz
  3. DDima
  4. pelmenner
  5. abdula-mon-fon-alibaba-A

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

  1. Maria_Akizuki
  2. maxlevel_spyofgame
  3. zhaojianmin
  4. FlameDragon
  5. Shawn

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

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

Группа языков Языки программирования / компиляторы Примеры
C GNU C11 10903473, 17029870
C++ GNU C++14, GNU C++17, GNU C++20, MS VC++, 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, Java 11 25491359, 23678167
JavaScript V8 35963909, 35681818
Kotlin Kotlin 1.4, Kotlin 1.5 25779271, 25204556
OCaml OCaml 6157159, 1281252
Pascal Delphi, FPC, PascalABC.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
  • Проголосовать: нравится
  • -673
  • Проголосовать: не нравится

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

was waiting for this since long :)

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

can't wait :)

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

Note the almost unusual timing.

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

if any of you are interested in cheating, send a message to nitin_05 or ashokesen02. they both became experts in codeforces by buying solutions and adding many comments in the codes.

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

Wait, why is elim round 2 rated for div1+div2 but elim round 3 only rated for div2 and those div1 contestants that are Russian-speaking students?

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

    Because we don't have a good set of problems for div. 1 round this time.

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

      Then the official round is unrated for those few 2100+ registrants, right?

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

        The Technocup round is rated for all participants.

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

          But you don't have a good set of problems for div1 participants. The official round has div1 participants.

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

            Maybe it's just unbalanced for Div. 1 participants, but balanced for an elimination round rated for all Russian schoolers.

            Just me trying to justify this move. I was also disappointed with the absence of a Div. 1 version.

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

              What makes those Russian students so special? It's easy to find an explanation but not so easy to find one that actually makes sense when you think about it and doesn't become a completely "ICPC Asia"-like arbitrary cutoff.

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

            Maybe they don't have hard enough problems to serve all Div 1 contestants (like IGMs and LGMs) but good enough for lower rated Div 1 contestants, which they expect in the official round.

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

title only in russian

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

if problem statements were this short like this blog!

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

Sad for div1. But I think that there WAS a div1 in the list.

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

    It is indeed sad, but I prefer having no Div. 1 rather than shitty Div. 1 where you only find out it's shitty after you've started participating.

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

When I see a Technocup will be hold, there will be a high-quailty contest.

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

Hope I can become Candidate Master in after this round

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

so nitin_05 and ashokesen02 both registered in this round.

  1. will they cheat again in this round?
  2. if so, will they not be caught and be rated again?!
  3. who will cheat better and drain more ratings from other innocent users?!?
»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Codeforces round based on Technocup is rated or not?

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

What about the scoring distribution?

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

As a tester, I heard that problems are beautiful!

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

    You heard? Don't the testers see the questions beforehand as they give a VC of the same contest? Just want to know.

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

It's about 10 minutes to start, What about score distribution?

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

It's about 10 minutes to start, What about score distribution?

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

note 5 minutes delay

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

I think the additional 5 min delay is to apply and fix the last round rating changes.

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

Contest extended by 5 minutes. Is everything ok?

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

hope I do better....

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

+5 minutes. Might be a signal that I should not attempt this round if I don't want to drop down to Expert!!!

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

delay?

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

I think the additional 5 min delay is to apply/fix the rating changes of the last round.

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

Yo bois Have fun solving.. :)

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

Why delayed by 5 mins!

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

Will this be the first contest without the score distribution known in advance? :O

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

Hope to increase my rating by 50 pts

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

Another 5 minutes delay!

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

Are there queue issues?

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

another 5 minutes...

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

Oooh ! Another 5 minutes delay !

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

heab

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

Not A good sign of a Good Contest !!!

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

delayforces

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

What's going on ?? delayed by 5 mins again.

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

Double delayed!

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

Late OP >_<

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

why is it constantly delaying?

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

Am i really on codeforces or i am on codechef!!!

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

I can't see the round in contest list ... what happened ?

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

+5 again, hope this round will be smooth.

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

Delayforces!

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

Upvote if you think there will be another 5 mins delay?

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

delayed ;_;

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

another 5 min delay , it's irritating!

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

:(

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

how many selection rounds for techocup gonna be?

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

CF Be like

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

Bye I am going to take my dinner.

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

Waiting for another 5 min delay

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

I have a joke on codeforces but I'll say it after 5 mins.

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

will codeforces catch them as cheaters or not ? I think the answer is NO.

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

    I also want to report this. Is there a person manipulating different accounts in the contest? This should also be considered cheating. And since these accounts are newbies, it will make others rating drops much since you will be considered "defeated" by a bunch of newbies if these cheaters are not removed.

    UPD: They finally appear on official ranking 22-26, 28-39 (except two CM and one expert)

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

    WTF???

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

    Actually, they were also cheated in Educational Codeforces Round #118, ranking 20~24. I expected them being caught cheating and became skipped then. Seems like they were not caught by Codeforces by using random space or different name of variables.

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

speedforces again...

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

Solution of F : ARC 115 E

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

what do you think of problem F?

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

My E has encountered memory problems when in my opinion there is no real improvement to do. Are others in this case?

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

How to solve C?

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

A strange thing happened to me, this solution to problem C gave RunTime Error on Pretest 1 but, on local ide it gave correct output and when I submitted it to C++ version 14 instead of 17, pretests passed!

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

    somebody please help. why this is giving RTE?.link

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

    It has undefined behaviour in line "ll x=a.size()-1, y=b.size()-1;". When a.size()=0 or b.size()=0.

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

      Shouldn't x or y be simply -1 in that case and the control shifts to the next line? Or, am I missing something?

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

        Well a.size() returns unsigned int 0. When you subtract 1 from it, it overflows which then is assigned to x. Hence a undefined behaviour (overflow). Most of times it evaluates to -1 but i guess undefined behaviour is called undefined for a reason.

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

What is the approach to solve problem C??

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

    For me C was horrible implementation problem, I fiddled like an hour on it.

    Actually it is not so complecated. First observe that left and right side are independent of each other, each can be solved separate.

    Then consider blocks of k elements, starting with the outermost (the longest distance) elements. For each block we need to walk the distance to the max one, and most likely back.

    Do this for both sides. Then, after end, we can remove the one distance we not need to go back, that is max(abs(a[min]),a[max]). i.e. we go to the farthest element last, so can subtract that distance in the end.

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

Too little time limit in task E. Please raise the time limit in task E up to 8-10 seconds.

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

This F question is as like as two peas ARC115E. It's really speechless!!!

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

How to solve D ?

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

    I don't know how to prove it, but the ideia is that if inversions%2 = 0 or any number appears twice the answer is YES, otherwise is NO.

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

    The cases where n = 1 and n = 2 are trivial.

    Let's suppose n >= 3 and all elements are distinct. We can notice that by using a 3-cycle, the parity of the number of inversions in our vector remains the same. So, if all the elements are distinct, then we only have to check whether we have an even or odd number of inversions in our array.

    If there are at least 2 equal elements, then we can use them to put all other elements in their place, so the answer is YES everytime in this case.

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

    I did with counting inversion, such a triple swap of three distinct elements changes the inversion count by 0 or 2.

    Also the array can be pre sorted. And if the array includes any element twice, then it is allways sortable because we can use the double element to simply swap elements.

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

    Case 1: There are no duplicate values. In that case, we can decompose the permutation into cycles where $$$i \to a[i]$$$. After playing around with some cases on paper, you'll find that we can perform the following operations:

    1. Merge two cycles of size $$$A$$$ and $$$B$$$ into a single cycle of size $$$A + B - 1$$$, or split one cycle into two.
    2. Merge three cycles of size $$$A, B, C$$$ into a single cycle of size $$$A + B + C$$$, or split one cycle into three.
    3. Increase of decrease the size of a cycle by $$$2$$$.

    An array can be sorted if it can be split into cycles of size $$$1$$$.

    So now we decompose the array into cycles, merge the cycles, and the answer is YES if the size of the resulting cycle is odd.

    Case 2: There is a duplicate value. In that case, it's always possible. Say the value $$$x$$$ appears twice in the array. For the case where all our cycles merge into a cycle of even size, we can reduce the cycle to size $$$2$$$, then shift the cycle to one between two values $$$(x, y)$$$, then fix that swap with the help of the second $$$x$$$.

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

      The implementation can be even simpler. In Case 1 we can show that the permutation can be sorted if and only if the number of even cycles is even. We just run dfs and find the number of even cycles.

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

        I think that's around the same implementation difficulty as mine, because when I say "merge cycles," I just mean "add up their sizes."

        Submission for Reference

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

          I'm having a little problem in wrapping the idea. It would be great if you can answer the following questions:

          Why is sum initialized with 1 in your submission and what does it denote?

          Why are you adding cycle - 1 in sum and what does it finally result in?

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

            Why I add cycle - 1: I'm merging all of the cycles by incrementally adding cycles and using the rule for merging two cycles stated above. So the total size becomes $$$A$$$, then $$$A + B - 1$$$, then $$$A + B + C - 2$$$, then $$$A + B + C + D - 3$$$ and so on.

            Why I initialize sum = 1: Adding the first cycle is an edge case because I have to add cycle instead of cycle - 1, so to account for this I initialize to 1 instead of 0. This will also work if I detect no cycles since that would mean the array is already sorted, so sum % 2 == 1 and I print "YES".

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

          What a nice explanation guys! Thanks to both of you.

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

      man what a solution :D

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

      In other words, the given operation is performed using 2 swaps, a swap merges two cycles or splits a cycle.

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

    I solved D without using the ideas of inversions. First, for the case with duplicates, we can see that we can use any two of the same number and "move" a third number into sorted order.

    So, for the case without duplicates, the array will be a permutation. The sorted array will have $$$a[i] = i$$$ for all $$$i$$$. Instead of using inversions, I tried, for every $$$i$$$, to swap $$$i$$$ into position $$$i$$$. If after all swaps the array is sorted, the answer is YES and otherwise NO.

    To swap $$$i$$$ into position $$$i$$$, assume number $$$i$$$ is at position $$$x$$$ ($$$x \neq i$$$). Then, if $$$x \neq n$$$ we can select the positions $$$i$$$, $$$x$$$, and $$$n$$$ to move $$$i$$$ to position $$$i$$$. If $$$x = n$$$, we can use position $$$n - 1$$$ instead. This works because we only care if number $$$i$$$ is at position $$$i$$$, so we can arbitrarily use the last position to be our third number. All we have to do is keep track of the positions of each number when performing our operations and lastly check if the $$$a[i] = i$$$ for all $$$1 \leq i \leq n$$$.

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

Finally managed to solve two questions for the first time.

Spoiler

Edit: FST :( on B

I stupidly printed 1 instead of 0 if the last element was max (when not sorted), surprised the pretest didn't cover it, oh well, I will try to solve 2 or more next time :).

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

The more famous Codeforces will be, the more cheaters will be there.

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

Can we solve F using a lazy seg tree? I got a solution if $$$a_{i} \le 10^{5}$$$.

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

How did you guys solve problem B?

I figured out that the array stops changing when we have a[n] = max(a1, ..., an), but could not continue from there.

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

    If a[n] is not the biggest element, then it is changed to the next one left of a[n] with a[k]>a[n] And so on. Just count them until you found the max element.

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

Can someone who found the similar problem to F during the contest please tell how did they go about searching it?

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

    That's a well known problem, and I had solved it before. Any questions?

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

      By seeing the number of solves, some very fast solves and the simplicity of the statement I also figured that there's a very good chance that a similar problem may have existed. I was just curious if someone who hadn't solved that atcoder problem was able to find it and if yes how?

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

    I doubt it's searchable tbh. Probably just solved it there and can remember it.

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

    I thought I remembered it from an Atcoder contest so I searched the 50 most recent ABC's and then went through ARC's until I found it.

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

      Wow, I think this is the only reasonable way unless someone was able to find it through google search. I guess you deserved the solve after that much effort xd

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

I "solved" B by going over the problems but it was too slow on pretest 5. Was there any way to make it faster? Was it just a "recursive" problem until the biggerThanX arrays length is 0?

https://codeforces.me/contest/1591/problem/B

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

    The expected solution has a complexity of O(N).
    Just iterate over the array from the last position, and whenever you encounter an element greater than the current max, increment a counter and update the current max.
    If the array is already sorted in asc. order, the counter's final value will be 0.

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

    Your code's complexity is $$$\mathcal{O}(n \cdot ans)$$$. Expected complexity is $$$\mathcal{O}(n)$$$.

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

      Thanks Kirill,

      How do I know what is the expected time/memory complexity of the task? I didnt see anythig in the description that would indicate this requirement.

      Andras

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

        Complexity requirement is based on time limit and modern processors' speed. You can follow the rule: $$$C\cdot10^6$$$ op/s.

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

Problem E is really good, it can be solve in O(n log n).

The ideia is really similar to this old one from Codeforces, besides the MO and stuff:

https://codeforces.me/contest/375/problem/D

PS: finally coded it right, here it is: https://codeforces.me/contest/1591/submission/139023972

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

Problem B : In the 2nd test Case [1,3,2,4,5], why not we pick "2" and then [1, 2, 3, 4, 5] ?

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

    Read the statement. You always pick the last element. You pick 5 here and the array doesn't change at all and the answer is 0

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

    Read the problem more carefully. We always pick the last element (a[n]) in every operation.

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

I can't believe that none of the testers has solved ARC 115E

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

Why do you set problemF without changing any words? Maybe your purpose is to find the participants who have solved thisARC115E-LEQ and NEQ?

I mean this round should be unrated. It's a big mistake.

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

I'm confused about the decision to make $$$n \leq 10^6$$$ in problem E. DFS with recursion depth $$$10^6$$$ is quite dicey, and if you look in the accepted submissions list almost every submission runs in at least half, if not almost all of the time limit.

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

    Ah yes, and now there are FSTs coming in on the leaderboard. What a surprise!

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

    The intended complexity of solution is $$$\mathcal{O}(n + q)$$$. This was an attempt to cut off $$$\mathcal{O}((n + q) \cdot \log(n))$$$ solutions with big constant.

    Unfortunately, I wasn't allowed to decreases TL any further. As I see it, recursion and input takes most of the time in linear solution, so decreasing TL to 3s wouldn't change anything for them independently from implementation. But it could have cut off some solutions with __gnu_pbds::tree or segment tree.

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

Why is the time limit for problem E so tight? What solution are you trying to kill?

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

    That was an unsuccessful attempt to kill nolinear solutions with bad constant.

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

      I think trying to distinguish $$$O(n)$$$ vs. $$$O(n \log n)$$$ is a terrible idea here (and usually is in general). Both I/O and DFS have a comparable runtime to $$$n \log n$$$ algorithms in practice.

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

        Of course, it's impossible to cut off all nonlinear solutions. It was meant to kill only heavy ones. IMHO, here they were actually distinguishable with TL=3s. As DFS and I/O takes about the same time independently from implementation, and solutions with SegTree or std::set are using statistically more time.

        Anyway linear solutions were't harmed by tight limits, but maybe it was actually dumb to try to kill heavy nonlinear ones.

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

          The desire to prioritize linear solutions makes sense to me, but in practice it's a horrible competitor experience when virtually everyone who passes has an $$$n \log n$$$ solution and it ultimately just comes down to constant factor.

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

can someone explain solution of problem c?

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

    Lets solve the problem separately for elements with xi < 0 and elements with xi > 0.

    Notice that if number of elements, that are for example more than zero(lets denote them as R), is divisible by k, we can get optimal answer by going firstly to closest 1...k elements, than to k+1...2k, and so on.

    So, we can firstly take R%k elements, return back, and R-R%k elements that will left can be taken using greedy approach that I have described. Solve it independently for two types of elements(smaller and greater than zero) and subtract maximal abs(xi). I hope i have explained clear enough, sorry for my english :). If you have any questions I can send my code.

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

      I understood the coding part 138928969 , but still lack clarity in the whole idea.
      I want to make sure that some idea from this problem sticks to my knowledge tree, so that it becomes transferrable to other problems. I want it to have an impact on how I will think of other problems in the future, but so far I didn't manage to extract anything generalizable.

      My best attemt is a two-part summary:
      1. Try to ignore one part of the solution (probably they are symmetric).
      2. Try to split the space into $$$k$$$ parts.

      But I doubt that this summary is a useful insight that will stick with me and will help me solve other problems. There has to be a clearer picture or some other useful abstraction :)

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

When you choose few testers to test the contest : problem D : https://open.kattis.com/problems/bread problem F : https://atcoder.jp/contests/arc115/tasks/arc115_e

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

    This contest was even worse than the previous contest. If the solutions to problem D and problem F are already out then it's just the sport of Googling, not a mind sport. Why do problem setters even try to copy the same problem? It's not just a coincidence that the problem setter in atcoder (problem F) and in Kattis will form exactly the same question.

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

In the problem E, setters want to kill set's $$$\log$$$ isn't it?
My solution without set passed in 1871ms

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

Number of successful submissions in F are far more larger than those in E.

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

Is this contest rated??

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

What's the solution for F?

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

Did expected solution for F require inclusion exclusion?

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

The explanation of example test case 1 in Problem B has something wrong. In the explanation, it's said: The first eversion: a = [1, 4, 2, 5, 3]. But in fact, a = [2, 4, 1, 5, 3]. The explanation troubled me a lot and made great influence.

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

The explanation of example test case 1 in Problem B has something wrong. In the explanation, it's said: The first eversion: a = [1, 4, 2, 5, 3]. But in fact, a = [2, 4, 1, 5, 3]. The explanation troubled me a lot and made great influence.

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

138924326 138922538 why does this always happen to me. I lieterally only needed 10 extra seconds to submit.

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

People who saw problem F before on AtCoder, Problem

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

I don't understand what's wrong with my solution for D using segment tree.

https://codeforces.me/contest/1591/submission/138912355

Can someone point out mistake.

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

I didn't like the round. Coding segment tree for D, coding treap for E, coding compressed segment tree for F... It was too much of binary balanced trees. However, one friend of mine told me that I could have used __gnu_pbds::ordered_set for D and E. Also, I am glad to hear that the intended solution for E is linear.

UPD: Well, it seems that F also have linear solution. Then... OK, I just have chosen bad ways to solve the problems.

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

    You can also solve F in O(n) with a stack instead of segtree (the dp value doesn't change much at each prefix).

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

    D, E also have linear solutions without any binary trees too)

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

      Really, you can count inversions in O(n)? I have believed that the two ways for it are merge sort and segment tree, both are O(nlogn)

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

        There's a way to solve D without using inversions, which I did in contest.

        Explanation here.

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

        I can count parity of number of inversions in permutation in O(n).

        Iterate through permutation from right to left. Maintain inverse permuation along the way. Each time you look at $$$a_i \neq i$$$ you swap $$$a_i$$$ and $$$a_{a^{-1}_i}$$$ and change the parity.

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

          Could you explain more specifically, please? Is there any code/submission I can take a look at? thx.

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

    coding treap for E

    The high constraints should hint that treap will probably TLE but if you really want to use treap, there are ready implementations like mine.

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

F is literally copy paste from this https://atcoder.jp/contests/arc115/tasks/arc115_e

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

Cheating reported. Official ranking of 28-39 (expect two purple users) are all have same code.

UPD: So as 22-26 (except 24)

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

Because many people solved the last problem, I was convinced that it's easy and I spent all the time working on it, Didn't even think about doing D lol. All this because people just copied solution from some Atcoder submisson. It happens, whatever.

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

Why so many downvotes for this post?

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

another <0 rated blog lol

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

Am I the only one who got D correct but missed the fact that there could be repeated numbers ? :'(

Spent entire contest trying to figure what's wrong.

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

Problem F : Non-equal Neighbours is repeated from past atcoder contest:(

the source :

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

Next time give links to the sources where you have copied the problems from, why put in so much work? At least it won’t be unfair for those who don’t use google during contests.

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

Here are the copied problem's link found till now :
Problem C : https://po.kattis.com/problems/biblioteket
Problem D : https://open.kattis.com/problems/bread
Problem F : https://atcoder.jp/contests/arc115/tasks/arc115_e

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

A great contest with completely original problems and reasonable time limits.
It provides great experience and shows how dumb I am.
12 out of 10, would absolutely lose my ratings again.

Sorry for the italics, but this is not the best contest I've ever had :(
I thought F was easy when I saw a lot of people solved F and wasted some time on it.
Plz check again with your tasks to see if there's any existing problem that has a similar solution.
At least change the statements a bit more if you intended to add these problems...

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

    I mean I solved F without knowing it appeared before, but couldn't solve D so I think it was also easier + appeared before => many solves

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

One more contest being downvoted a lot.

Have fun!

Almost everybody: It's not funny

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

F

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

This contest deserved downvotes. Last one didn't.

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

Seeing 8 people from Japan in the top 10, I should have known to look for F on AtCoder...

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

if this is rated it'll be my last contest on CF, bye bye!

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

Make it unrated, it’s unfair for those who didn’t search the problems on the web.

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

Codeforces Round #759 (Div. 2, based on Googling 2022 Elimination Round 3) much better

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

    If you have to give such a name then replace Atcoder with Kattis as 2 problems were copied from there. You can replace Atcoder with Googling as well :)

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

      I think the problems were not copied (most probably, the authors didn't even know the existence of those problems). Unfortunately, the probability of coming up with an already used problem is quite high. I invented at least $$$6$$$ problems that turned out to be already on the Internet.

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

KAN getting all the negative contribution of down votes although he is neither among authors nor testers.

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

Hi, so to me seems like a notorious coincidence.

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

Добрый день. Мне кажется, что в задаче F решение за O(n^2) проходит системные тесты. Я отослал его во время дорешивания и получил вердикт "полное решение". Могу показать код решения или прикрепить ссылку на посылку.

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

Is this contest unrated?

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

The author wants to filter out O(nlogn) solution in E, but I got AC with O(nlognlogn) (query fenwick tree in binary search checking function)... I don't think a O(nlogn) solution is bad even if there exists linear solution.

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

Why the problem E are difficult to solve in O(nlogn)? I have done it for half a noon!

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

I just noticed that problem D is similar to AOJ 0448. https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0448

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

This contest:

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

i don't know where to clarify, so i post here yeah...

why i got rank 83 in these publish rating changes.

but my actual rank 74 (handle:Son) in common standing ??

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

Why is rating relapsed? Recalculation? EDIT 3: it keeps on relapsing and fixing itself... strange.

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

Please increase the TL for E in practice at least by a few seconds. Non-standard IO optimisation shouldn't be the difference between AC and TLE.

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

This morning (GMT +7), I get a message from the system that my submission: https://codeforces.me/contest/1591/submission/138915027 for E is the same as some https://codeforces.me/contest/1591/submission/138907536, but actually I don't even know who this guy is, and after using a pbds, this problem is very easy to implement, and it seems like we have 0% of chance to share code with others and I don't see any reason to skip my contest this time.

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

    did this round became unrated ?? since my pointes got reduced if this gets unrated I don't like the logic if people like me who solved this contest without the help of google or anything got +ve delta are getting 0 I know it's bad for many people but still some people will still suffer from making it unrated

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

Здравствуйте! Я получил письмо от [email protected] о том, что решения wynell/138917073, SUPERustam/138918045 находятся в группе одинаковых решений и о том, что при имении общего источника, опубликованного до соревнования, необходимо написать комментарий к посту со всеми деталями. Чем, в общем, я сейчас и занимаюсь. Я использовал материалы из этого файла (https://github.com/Petrivah/youtube-caption-scraper/blob/master/src/olympiad.md). Возможно, этим же файлом пользовался и SUPERustam и система посчитала это достаточным совпадением. Хотел бы вернуть баллы за эту задачу, я был очень рад, когда ее решил.

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

The problem 1585F is same as ARC115E...