Technocup 2022 — Elimination Round 3 and Codeforces Round #759 (Div. 2)

Hi all!

This weekend, at Sunday, December 12, 2021 at 15:15UTC 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

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

The editorial is published.

• 2 days ago, # ^ |

  still waiting

• 2 days ago, # ^ |

  ← Rev. 2 →  

  +1

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

  • 2 days ago, # ^ |

    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 days ago, # ^ |

  ← Rev. 3 →  

  +13

  An usually unusual timing lol :x... nx5mins too

• 3 days ago, # ^ |

  Okay ,but what's the point?

• 3 days ago, # ^ |

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

  • 3 days ago, # ^ |

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

    • 3 days ago, # ^ |

      The Technocup round is rated for all participants.

      • 3 days ago, # ^ |

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

        • 3 days ago, # ^ |

          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 days ago, # ^ |

            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 days ago, # ^ |

          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 days ago, # ^ |

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

            • 2 days ago, # ^ |

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

• 3 days ago, # ^ |

  Thanks, fixed.

• 2 days ago, # ^ |

  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 days ago, # ^ |

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

• 2 days ago, # ^ |

  This is competitive cheating

• 2 days ago, # ^ |

  Whenever you see the words Codeforces Round #... it just means it is rated.

  • 2 days ago, # ^ |

    Ok thankss___

• 2 days ago, # ^ |

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

• 2 days ago, # ^ |

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

  • 2 days ago, # ^ |

    The comment is hidden because of too negative feedback, click here to view it

• 2 days ago, # ^ |

  hope i am able to solve 3 question

  • 2 days ago, # ^ |

    You will do it.

• 2 days ago, # ^ |

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

• 2 days ago, # ^ |

  i could finished my dinner

  • 2 days ago, # ^ |

    Is that another Codeforces problem?

• 2 days ago, # ^ |

  Don't worry so much about rating. Focus on learning

  • 2 days ago, # ^ |

    I got -160 in the last 2 contests combined. I only want my lost rating back xD

    • 2 days ago, # ^ |

      I got -130 in the last one. Glhf for us I think xD

    • 2 days ago, # ^ |

      look at my last 5 deltas then !

    • 2 days ago, # ^ |

      Still love the screencasts so do give the contest :P

• 2 days ago, # ^ |

  ← Rev. 2 →  

  +3

  No, I Hope you will do good. Good luck.

• 2 days ago, # ^ |

  Unrelated question- When are we going to see you become legendary grandmaster ? Best of luck for that .

• 2 days ago, # ^ |

  oh no, I was waiting for youtube video from u)

• 2 days ago, # ^ |

  haha but we want your stream after the contest :)

• 2 days ago, # ^ |

  maybe I am gonna drop down to specialist too

• 2 days ago, # ^ |

  +10 in total

• 2 days ago, # ^ |

  It is a sign to not attempt this contest for sure now.

  • 2 days ago, # ^ |

    We want screencast

  • 2 days ago, # ^ |

    I wish I had also the same instinct as you.

• 2 days ago, # ^ |

  another delay of 5 mins. maybe two negatives make a positive [ delta :) ]

  • 2 days ago, # ^ |

    This is my only hope now. Finally deciding to attempt it then.

• 2 days ago, # ^ |

  I hope u reach Master in this one

• 2 days ago, # ^ |

  Update: A huge negative delta is on the way. It was a sign xD.

• 2 days ago, # ^ |

  Didn't mean to hurt you, but

• 34 hours ago, # ^ |

  mistakes were made(you didn't heed the signal, neither did I)

• 2 days ago, # ^ |

  Okay this is not fun waiting (:

• 2 days ago, # ^ |

  ok, again 5 more minutes to fix this I hope

• 2 days ago, # ^ |

  Will this contest even start?

• 2 days ago, # ^ |

  Using Inspect in you browser!!!

  • 2 days ago, # ^ |

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

    • 2 days ago, # ^ |

      ← Rev. 3 →  

      +1

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

      • 2 days ago, # ^ |

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

        • 2 days ago, # ^ |

          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.

• 2 days ago, # ^ |

  Hope is a good thing..

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

• 2 days ago, # ^ |

  what is happening??

  • 2 days ago, # ^ |

    mind games

• 2 days ago, # ^ |

  god please....start the contest

• 2 days ago, # ^ |

  "Ah shit, here we go again" (c)

• 2 days ago, # ^ |

  • 2 days ago, # ^ |

    Low register people i guss, due to last round (13152)

• 2 days ago, # ^ |

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

• 2 days ago, # ^ |

  else downvote?? :)

• 2 days ago, # ^ |

  ← Rev. 2 →  

  +1

  Another One DJ Khalid

• 2 days ago, # ^ |

  Ok Sir

• 2 days ago, # ^ |

  ← 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)

• 45 hours ago, # ^ |

  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.

• 2 days ago, # ^ |

  Arrayforces.

• 2 days ago, # ^ |

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

  • 2 days ago, # ^ |

    Is the round going to be canceled?

    • 2 days ago, # ^ |

      ← Rev. 2 →  

      +4

      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.)

      • 2 days ago, # ^ |

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

  • 2 days ago, # ^ |

    Are you a cheater because one of your submission got skipped?

• 2 days ago, # ^ |

  Solution of D (90%): TRPLSRT

• 2 days ago, # ^ |

  WLOG, if a1,a2,…,an is the sorted sequence of positive coordinates, the goal is to try to minimize the number of times you go back to the origin from the later coordinates in the sequence; since the coordinates are increasing, it would be less expensive to go back to the origin from somewhere at the beginning than to do it from somewhere at the end. As an example, let the sequence be 1,2,3, and k=2. If you choose to collect the first two items followed by collecting the last item, it will cost you 2+2+3=7. But, if you choose to collect the first item followed by the second two, it will cost you 1+1+3=5. You can see how it was more optimal to go back from 1 to the origin than to go back from 2 to the origin.

• 2 days ago, # ^ |

  ← Rev. 2 →  

  +2

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

  • 28 hours ago, # ^ |

    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.com/contest/1591/submission/139012140

    • 27 hours ago, # ^ |

      it also worked when i shifted from GNU C++17 to GNU C++20. and thank u very much for taking the time to analyze my code.

• 28 hours ago, # ^ |

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

  • 28 hours ago, # ^ |

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

    • 27 hours ago, # ^ |

      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.

      • 15 hours ago, # ^ |

        Got it now! Thank you :)

• • 2 days ago, # ^ |

    What is the criteria to select points..form the array??

• 2 days ago, # ^ |

  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.

• 2 days ago, # ^ |

  please don't.

• 2 days ago, # ^ |

  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.

• 2 days ago, # ^ |

  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.

  • 2 days ago, # ^ |

    How do you define "inversion"?

    • 2 days ago, # ^ |

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

      • 2 days ago, # ^ |

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

        • 2 days ago, # ^ |

          Ordered set

        • 2 days ago, # ^ |

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

        • 2 days ago, # ^ |

          Applying merge sort you can easily count inversions.submission

• 2 days ago, # ^ |

  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.

• 2 days ago, # ^ |

  ← Rev. 2 →  

  +7

  Case 1: There are no duplicate values. In that case, we can decompose the permutation into cycles where i→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.

  • 2 days ago, # ^ |

    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.

    • 2 days ago, # ^ |

      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

  • 2 days ago, # ^ |

    man what a solution :D

  • 33 hours ago, # ^ |

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

• 2 days ago, # ^ |

  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≠i). Then, if x≠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≤i≤n.

• 2 days ago, # ^ |

  overflow in line 175

  Spoiler

• 2 days ago, # ^ |

  Try this

• 2 days ago, # ^ |

  Tried this during contest, but got ML. Not sure if there's a way to optimize.

• 2 days ago, # ^ |

  Just use implicit segment tree and it works for ai <= 1e9

• 2 days ago, # ^ |

  Yeah you can use a sparse segment tree.

• 2 days ago, # ^ |

  You can use coordinate compression to build seg tree my submission

  • 2 days ago, # ^ |

    Are you sure that it's a normal lazy segment tree?

    • 2 days ago, # ^ |

      Yes, it's a normal lazy segtree written pretty badly. Just the nodes are different.

• 2 days ago, # ^ |

  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.

• 2 days ago, # ^ |

  The comment is hidden because of too negative feedback, click here to view it

  • 2 days ago, # ^ |

    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?

    • 2 days ago, # ^ |

      sorry I'd misunderstood you. Anyway there must be a lot "skipped" verdict so we can easily figure out what they did.

    • 2 days ago, # ^ |

      Today was all about competitive searching then, ig.
      SearchForces

• 2 days ago, # ^ |

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

• 2 days ago, # ^ |

  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.

  • 2 days ago, # ^ |

    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

• 2 days ago, # ^ |

  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.

• 2 days ago, # ^ |

  Your code's complexity is O(n⋅ans). Expected complexity is O(n).

  • 6 hours ago, # ^ |

    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

• 2 days ago, # ^ |

  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

• 2 days ago, # ^ |

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

• 2 days ago, # ^ |

  because we can pick only last element.

  • 2 days ago, # ^ |

    Oh No !!! Thanks

• 2 days ago, # ^ |

  i also thought the same bro

• 2 days ago, # ^ |

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

• 2 days ago, # ^ |

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

• 2 days ago, # ^ |

  The intended complexity of solution is O(n+q). This was an attempt to cut off O((n+q)⋅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.

  • 2 days ago, # ^ |

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

  • 2 days ago, # ^ |

    ← Rev. 2 →  

    +34

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

• 2 days ago, # ^ |

  ← Rev. 2 →  

  -11

  The comment is hidden because of too negative feedback, click here to view it

  • 2 days ago, # ^ |

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

    • 2 days ago, # ^ |

      The comment is hidden because of too negative feedback, click here to view it

      • 2 days ago, # ^ |

        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 nlogn solution and it ultimately just comes down to constant factor.

• 2 days ago, # ^ |

  ← 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.

  • 2 days ago, # ^ |

    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 :)

• 2 days ago, # ^ |

  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.

• 2 days ago, # ^ |

  The comment is hidden because of too negative feedback, click here to view it

• 37 hours ago, # ^ |

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

• 2 days ago, # ^ |

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

  • 2 days ago, # ^ |

    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?

    • 45 hours ago, # ^ |

      https://po.kattis.com/problems/biblioteket I had solved from here before, but this site is for old Swedish olympiads so you probably solved somewhere else if you're not swedish.

• 41 hour(s) ago, # ^ |

  Looks like problem was integer overflow somewhere. Submitting same code by replacing int with long long int everywhere passed.

  https://codeforces.com/contest/1591/submission/138948492

• 2 days ago, # ^ |

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

• 2 days ago, # ^ |

  ← Rev. 2 →  

  +10

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

  • 2 days ago, # ^ |

    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)

    • 2 days ago, # ^ |

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

      Explanation here.

      • 2 days ago, # ^ |

        Cool!

    • 2 days ago, # ^ |

      ← 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 ai≠i you swap ai and aa−1i and change the parity.

      • 33 hours ago, # ^ |

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

• 34 hours ago, # ^ |

  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.

• 2 days ago, # ^ |

  you should include 22-26 too

• 2 days ago, # ^ |

  ← Rev. 2 →  

  +13

  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.

  • 2 days ago, # ^ |

    Thanks for feedback.

• 2 days ago, # ^ |

  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

• 2 days ago, # ^ |

  says an unrated guy!

• 2 days ago, # ^ |

  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.

• 2 days ago, # ^ |

  There had been many instances where problems were directly copied from some other contests. But all of them were rated, as it's not discouraged or penalized by MikeMiryayarnov. So, the contest will be rated.

• 10 hours ago, # ^ |

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

• 2 days ago, # ^ |

  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 :)

  • 2 days ago, # ^ |

  • 2 days ago, # ^ |

    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.

    • 31 hour(s) ago, # ^ |

      I absolutely agree. It is impossible to foresee everything.

• 2 days ago, # ^ |

  I doubt that he gives a shit

• 45 hours ago, # ^ |

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

• 38 hours ago, # ^ |

  And then I used fread and got an AC