By KAN, 3 years ago, translation, In English

Hi all!

This weekend, at Dec/12/2021 18:15 (Moscow time) we will hold Codeforces Round 759 (Div. 2, based on Technocup 2022 Elimination Round 3). They are based on problems of Technocup 2022 Elimination Round 3 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup website and take part in the Elimination Round.

The Div.2 edition is open and rated. Register and enjoy the contests!

Have fun!

UPD: congratulations to the winners!

Technocup 2022 - Elimination Round 3

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

Codeforces Round 759 (Div. 2, based on Technocup 2022 Elimination Round 3)

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

The editorial is published.

  • Vote: I like it
  • -673
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

was waiting for this since long :)

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    still waiting

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes 18:15

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    will this be this final 5 mins or there's more to come. lol

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I am getting owned, woke up at the asscrack of dawn to participate in this contest in my timezone and it's delayed.

      Must be for good reason though.

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can't wait :)

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Note the almost unusual timing.

»
3 years ago, # |
  Vote: I like it -147 Vote: I do not like it

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 years ago, # |
  Vote: I like it +82 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +95 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

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

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        The Technocup round is rated for all participants.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +65 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +21 Vote: I do not like it

            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 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              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 years ago, # ^ |
              Vote: I like it +13 Vote: I do not like it

            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 years ago, # ^ |
                Vote: I like it -6 Vote: I do not like it

              Then the unofficial round should be rated for those lower-rated div1 contestants.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it +107 Vote: I do not like it

              • »
                »
                »
                »
                »
                »
                »
                »
                3 years ago, # ^ |
                  Vote: I like it +128 Vote: I do not like it

                In general, why doesn't Codeforces make Div. 1.5 rated for $$$< 2800$$$ (like ARC)?

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

title only in russian

»
3 years ago, # |
  Vote: I like it +25 Vote: I do not like it

if problem statements were this short like this blog!

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    Last time, there was a weak pretest. And this time, there's even not a div. 1.

»
3 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Hope I can become Candidate Master in after this round

»
3 years ago, # |
  Vote: I like it +40 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Codeforces round based on Technocup is rated or not?

»
3 years ago, # |
  Vote: I like it +33 Vote: I do not like it

What about the scoring distribution?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Yeah I thought they'll publish it at least 30 min before the round, but still nothing.

»
3 years ago, # |
Rev. 2   Vote: I like it -31 Vote: I do not like it

As a tester, I heard that problems are beautiful!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -26 Vote: I do not like it

      That’s joke. All in all, problems are beautiful!

»
3 years ago, # |
  Vote: I like it +36 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

note 5 minutes delay

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Looks like they don't want to reveal the score distribution for the technocup participants

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    i could finished my dinner

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Contest extended by 5 minutes. Is everything ok?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hope I do better....

»
3 years ago, # |
  Vote: I like it +37 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

delay?

»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Yo bois Have fun solving.. :)

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Why delayed by 5 mins!

»
3 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    ok, again 5 more minutes to fix this I hope

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Will this contest even start?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to increase my rating by 50 pts

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Using Inspect in you browser!!!

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      By that I can virtually become grandmaster in just 5min!!

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 3   Vote: I like it +1 Vote: I do not like it

        Well you want exact 50 else you can get +50 easily by solving 2 problems very fast IMO.

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          I did 2 problems but predictor is showing -26 :(

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            well i said if you solve two problems very fact like in 20 minutes or something you can get a +ve delta of 50. But it was a bad round for me as well.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Hope is a good thing..

    but may be you can give contest without thinking much about rating and surprise yourself..

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Another 5 minutes delay!

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Are there queue issues?

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

another 5 minutes...

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Oooh ! Another 5 minutes delay !

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Not A good sign of a Good Contest !!!

»
3 years ago, # |
  Vote: I like it +12 Vote: I do not like it

delayforces

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Double delayed!

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Late OP >_<

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

why is it constantly delaying?

»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    The problems aren't accidentally visible during these delays so probably not Codechef :P

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

+5 again, hope this round will be smooth.

»
3 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Delayforces!

»
3 years ago, # |
Rev. 2   Vote: I like it -29 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

delayed ;_;

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

:(

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how many selection rounds for techocup gonna be?

»
3 years ago, # |
  Vote: I like it +72 Vote: I do not like it

CF Be like

Spoiler
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Bye I am going to take my dinner.

»
3 years ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

Waiting for another 5 min delay

»
3 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it +56 Vote: I do not like it

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

Spoiler
Spoiler
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    WTF???

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 years ago, # |
  Vote: I like it -10 Vote: I do not like it

speedforces again...

»
3 years ago, # |
  Vote: I like it +110 Vote: I do not like it

Solution of F : ARC 115 E

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Oh my god !

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Yeah, got first solve on F because of this. lol

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -25 Vote: I do not like it

      Is the round going to be canceled?

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +4 Vote: I do not like it

        There are several duplicated problems in the past, but they never made a round unrated because of duplication. So I think it's still rated. (Though, I think it should be unrated in my opinion. I didn't like free rating like this very much.)

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it -18 Vote: I do not like it

          As this is the last problem of the contest. Can they just delete the problem from the problemset and recalculate the scores?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Solution of D (90%): TRPLSRT

»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

what do you think of problem F?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      A bit wierd. Now technically integer overflow is undefined behavious as it happens in line "for (int i = sz(pos) — 1; i >= 0; i -= k)" when size of pos is zero (size is a unsigned int), however most of the time it works fine.

      Anycase it is a bad idea to rely on undefined behavious. I just typecasted it to signed and it worked fine. https://codeforces.me/contest/1591/submission/139012140

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the approach to solve problem C??

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +11 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it +54 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve D ?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you define "inversion"?

      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        An inversion is a pair of indices (i, j) such that i < j and a[i] > a[j]

        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Maybe apply coordinate compression and use fenwick tree or segment tree to count number of inversions?

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Ordered set

          • »
            »
            »
            »
            »
            »
            3 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            There's no need for coordinate compression since all values are <= 10^5. But yes, Fenwick Tree is one of the ways

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 2   Vote: I like it +7 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            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 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      man what a solution :D

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    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 years ago, # |
Rev. 3   Vote: I like it +61 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -29 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Today was all about competitive searching then, ig.
        SearchForces

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +44 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    Whenever you see short statements on codeforces, head over to atcoder....

»
3 years ago, # |
  Vote: I like it +48 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +30 Vote: I do not like it

      Yeah, unfortunately it's practically impossible to distinguish $$$\mathcal O(n)$$$ from $$$\mathcal O(n \log n)$$$ in the world of CP. I think the best course of action in this case would be to either give up and let $$$\mathcal O(n \log n)$$$ pass, or try to modify the problem in some way such that the $$$\mathcal O(n \log n)$$$ solution doesn't work. Trying to force $$$\mathcal O(n)$$$ with a strict time limit is almost guaranteed to cause negative feedback.

    • »
      »
      »
      3 years ago, # ^ |
      Rev. 2   Vote: I like it +34 Vote: I do not like it

      My $$$O(n+q)*sqrt(n)$$$ solution passed under 3s

»
3 years ago, # |
  Vote: I like it +70 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it -11 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +38 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it -19 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it +34 Vote: I do not like it

          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 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain solution of problem c?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 years ago, # |
  Vote: I like it +10 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it +14 Vote: I do not like it
»
3 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    I tried to kill nonlinear solutions with bad constant. I personally would have decreased TL even to 3s.

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well that was idiotic my set solution 138883336, also my non-set (NOT SO DIFFERENT) Solution 138939436

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Is this contest rated??

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

What's the solution for F?

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Did expected solution for F require inclusion exclusion?

»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

People who saw problem F before on AtCoder, Problem

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    At least three (F,D,C) out of six problems are literally stolen from older contests lmao

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah C was also like I have seen it somewhere. But coded once again on my own instead of finding. Can you please post the link from where problem C was copied?

»
3 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    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 years ago, # ^ |
    Rev. 2   Vote: I like it +10 Vote: I do not like it

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

    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +23 Vote: I do not like it

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

        Explanation here.

      • »
        »
        »
        »
        3 years ago, # ^ |
        Rev. 2   Vote: I like it +17 Vote: I do not like it

        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 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

»
3 years ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it

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

UPD: So as 22-26 (except 24)

»
3 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Why so many downvotes for this post?

  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    Problem F is just an Atcoder problem (exactly the same, not a word changed) It is unfair for others who haven't seen it before.

»
3 years ago, # |
  Vote: I like it +15 Vote: I do not like it

another <0 rated blog lol

»
3 years ago, # |
Rev. 2   Vote: I like it -12 Vote: I do not like it

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 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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

the source :

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
  Vote: I like it +52 Vote: I do not like it

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 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 years ago, # |
Rev. 2   Vote: I like it +23 Vote: I do not like it

One more contest being downvoted a lot.

Have fun!

Almost everybody: It's not funny

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

F

»
3 years ago, # |
  Vote: I like it +27 Vote: I do not like it

This contest deserved downvotes. Last one didn't.

»
3 years ago, # |
  Vote: I like it +93 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    says an unrated guy!

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Since this will be your last rated contest, then comment with your original id. What will you do with your contribution? It will become 0 someday since you had quit.

»
3 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    but what about people who still got +ve delta and solved it by themselves ???

»
3 years ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      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 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        I absolutely agree. It is impossible to foresee everything.

»
3 years ago, # |
  Vote: I like it +134 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    I doubt that he gives a shit

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, so to me seems like a notorious coincidence.

»
3 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Is this contest unrated?

  • »
    »
    3 years ago, # ^ |
      Vote: I like it -13 Vote: I do not like it

    If there's no claim "this contest will be unrated" , that will be rated.

»
3 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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 years ago, # |
  Vote: I like it +21 Vote: I do not like it

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

  • »
    »
    3 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    And then I used fread and got an AC

»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it +31 Vote: I do not like it

This contest:

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because common standings only contain "trusted participants".

»
3 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 years ago, # |
  Vote: I like it +18 Vote: I do not like it

The problem 1585F is same as ARC115E...