### isaf27's blog

By isaf27, history, 3 weeks ago, translation,

Hi all!

This weekend, at Nov/14/2021 09:05 (Moscow time) we will hold Codeforces Round #755 (Div. 1, based on Technocup 2022 Elimination Round 2) and Codeforces Round #755 (Div. 2, based on Technocup 2022 Elimination Round 2). They are based on problems of Technocup 2022 Elimination Round 2 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.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

Have fun!

The scoring distribution:

• Technocup: 500 — 500 — 1000 — 1500 — 2000 — 2500 — 3250
• Div1: 500 — 1000 — 1500 — 2000 — 2750 — 3750
• Div2: 500 — 500 — 1000 — 1500 — 2000 — 2500

The round is over. Congratulations to the winners:

Technocup

Div1

Div2

Editorial

• +178

 » 3 weeks ago, # |   +42 Note the unusual timings
•  » » 3 weeks ago, # ^ |   -6 no we will not
 » 3 weeks ago, # |   0 My first contest with green color , I hope I will do well, good luck every one .
•  » » 3 weeks ago, # ^ |   +84 My 60th contest with orange color , I hope I will do well, good luck every one .
•  » » » 3 weeks ago, # ^ |   -33 Ratism...
•  » » » » 3 weeks ago, # ^ |   -8 Do you seriously believe that it is that, or are you just going along with the meme?
•  » » 3 weeks ago, # ^ |   0 And you didnt Participate :_:
 » 3 weeks ago, # | ← Rev. 2 →   -35 hope I can get rid of grey soon...
 » 3 weeks ago, # |   -36 I just hope I Got a Good Name.
 » 3 weeks ago, # |   -44 11.35 am I would love to give the round if I woke up by thenಥ_ಥ who keeps round so early in morning that too on Sunday ಥ_ಥ ಥ_ಥ
•  » » 3 weeks ago, # ^ |   0 "who keeps round so early in morning that too on Sunday"A lot of people around the world usually have to wake up wayyyy earlier than 11:35am for a contest. It is what it is.
•  » » » 3 weeks ago, # ^ |   +18 I do understand that its just my pov not meant to offend anyone.(^◡^ )
 » 3 weeks ago, # |   -89 We have to postpone contest a bit. No way I can wake up that early
 » 3 weeks ago, # |   -20 Which approach is better for practicing problems in problemset: topic-wise or difficulty-wise?
•  » » 3 weeks ago, # ^ |   +4 Difficuty wise , because when you are filtering questions according to a topic then you would already have an idea before even looking at the problem that this question can be solved using this perticular logic and this is not good, why i am saying that because when you are giving a contest you are unaware of the approach which is being used thats why it is better to sort according to difficlty then solve.
•  » » » 3 weeks ago, # ^ |   0 Thanks
 » 3 weeks ago, # |   +32 Sleep vs contest. Ape choose sleep.
•  » » 3 weeks ago, # ^ |   0 Ape participated sleeping.
 » 3 weeks ago, # |   +9 It overlaps with Grand Prix of EDG :'(
 » 3 weeks ago, # |   +10 The contest is right after Google kick start, look forward to it. (Finally a good time for NA competitors
•  » » 3 weeks ago, # ^ |   0 Wish I had read your comment sooner. I didn't realize the time was in 24 hr format :_(
 » 3 weeks ago, # |   0 google kick start (or) codeforces div2
•  » » 3 weeks ago, # ^ |   +6 both
•  » » » 3 weeks ago, # ^ |   +3 legends
 » 3 weeks ago, # |   -62 no contestants, the time is unusual and bad
 » 3 weeks ago, # |   0 Dare to join this contest just after Google Kickstart Round-H;)
 » 3 weeks ago, # | ← Rev. 2 →   +15 Google kick stat round H plus codeforces round 755 makes me 5 hours of marathon coding competition.UPD: It's the third time I become candidate master.
 » 3 weeks ago, # |   +7 Overlaps with AHC006. If you fully participate CFR755, only 2h40m will remained for AHC006.
 » 3 weeks ago, # |   +30 Scoring distribution still not announced.
•  » » 3 weeks ago, # ^ |   +3 Too lazy!!!!
•  » » 3 weeks ago, # ^ |   0 Maybe we need more concrete description to replace "closer".
 » 3 weeks ago, # |   +8 very few registrations this time.
 » 3 weeks ago, # |   -10 Speedforces
 » 3 weeks ago, # |   0 How can someone hack a problem even after I locked it ?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   0 That's what locking is for
•  » » 3 weeks ago, # ^ |   +4 After locking, you cannot submit again and can hack other participant's solutions. If not locked, you can submit again but cannot hack other participant's solutions.
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 Thanks to this comment I hacked 7 people.
 » 3 weeks ago, # |   +2 Sorry for asking this, but I accidentally submitted a WA after an AC. So the AC solution done before will be counted for results right? Or is last submission for that problem considered regardless?
•  » » 3 weeks ago, # ^ |   +9 Your AC solution counts, check standings :)
 » 3 weeks ago, # |   +4 What is the hack for C?
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 1110I used this
•  » » 3 weeks ago, # ^ |   0 Multiple solutions passed which weren't intended. So basically it wasn't just one particular hack or idea, but it was just weak pretests.
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   -70 input: 1 1 1 0 This will hack the code that only judges the case of no solution is $b_i-a_i>1$.But sadly I found this after I locked my solution :(
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +2 I noticed two. Not considering index '0'. Taking absolute difference of a[i] and b[i].
•  » » » 3 weeks ago, # ^ |   0 I did the absolute mistake, LOL
 » 3 weeks ago, # |   +11 Div1B/2D is a really nice problem, bricked for a really long time trying to figure out how to solve the problem in just 1 pass of binary search, but the observation needed to solve it is cool af.
•  » » 3 weeks ago, # ^ |   +1 How do you solve it in one pass?
•  » » » 3 weeks ago, # ^ |   +19 Difference between $query(1, k) - query(1, k-1)$ is equal to the $k-j+1$.
•  » » » » 3 weeks ago, # ^ |   +4 Thanks :) Couldn't figure out during contest but the idea is actually very beautiful nonetheless.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +24 Binary search on ranges of the form $[1, x]$ to find $k$ (smallest index with same number of inversions as range [1, n]).Now lets realize that since all elements in $[i, j - 1]$ are smaller than those in $[j, k]$, the number of inversions is exactly $\frac{y \cdot (y - 1)}{2} + \frac{z \cdot (z - 1)}{2}$ where $y = (j - i)$ and $z = k - j + 1$.Now if we query the range $[1, k - 1]$, the number of inversions is $\frac{y \cdot (y - 1)}{2} + \frac{(z - 1) \cdot (z - 2)}{2}$, or exactly $z - 1$ less than the previous value. So we now have $z$ and can get $j$ from it.We also have the total, so we can just binary search to find $y$ that satisfies $\frac{y \cdot (y - 1)}{2} = total - \frac{z \cdot (z - 1)}{2}$. So we can also get $i$.
•  » » » » 3 weeks ago, # ^ |   +2 Also the part of binary searching y can be eliminated using the main observation by querying [1, j-1] and [1, j-2] and subtracting the second from the first to know length of [i, j-1].
•  » » » » » 3 weeks ago, # ^ |   +4 Oops, seems like I overkilled that part lol.
•  » » » » 3 weeks ago, # ^ |   +13 If you binary search two times then won't the total number of queries be $2 \log_2(N) \approx 60$ ?
•  » » » » » 3 weeks ago, # ^ |   +1 The second binary search in his comment is to solve an equation not to query.
•  » » » » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 True, didn't realize that.Thanks!
•  » » » » » 3 weeks ago, # ^ |   +2 The second binary search is finding the largest $y$ such that $y \cdot (y - 1) \leq total - \frac{z \cdot (z - 1)}{2}$. Just a local calculation, no queries or anything. You can just do $\sqrt{total - \frac{z \cdot (z - 1)}$ and check close by values if you aren't paranoid that will somehow make you FST lol.
•  » » » » » » 3 weeks ago, # ^ |   0 That makes sense, thanks!
 » 3 weeks ago, # |   +11 Fragile pretests on C lol. Hacked 8 submissions
•  » » 3 weeks ago, # ^ |   +11 ape hack . ape happy
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   0 I hacked 3 using following test:134 4 43 3 3Anc I jumped from rk~150 to rk~50 lolIs that weakppforces?
 » 3 weeks ago, # |   +5 The pretests in C were reasonably weak. I hacked my way from ~1000 rank to ~350 (And so did a lot of other people).
 » 3 weeks ago, # |   +7 hackfor C es!
 » 3 weeks ago, # |   0 Is div-2 D some sort of ternary search?
•  » » 3 weeks ago, # ^ |   0 I used binary search.
 » 3 weeks ago, # |   +16 ko_osaga did it again!Where is E from?
•  » » 3 weeks ago, # ^ | ← Rev. 3 →   +74 Hi, it's NEERC 2015 Northern Subregional K. It is not very equivalent, but the main observation for that problem can be applied directly. Shoutout to ainta for recommending me this problem. main observation for that problemYou have to see if the cylindric-shaped curve encloses all points. The area enclosed by such curve can be represented as an intersection of an area within distance d from the ray shoot from point $i$ to $j$ and $j$ to $i$. You have to determine if such area encloses all points, and that is a significantly easier problem (compute the intersection of cyclic interval)
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 Also, at least one problem in CF and a recent WF problem related to "distance to line", the only difference is to handle case when distance to segment is to one of two ends, it is easy by sweeping and two pointers.
 » 3 weeks ago, # |   0 Hi,Even though I probably didn't have the right algorithm on the E, the statement was a bit ambiguous on the issue of size 1 segments and other details (e.g. can we increase the ends without increasing the only values adjacent in the subsegment). I rather liked this exercise even if my performance on this competition does not exemplify me :)
 » 3 weeks ago, # |   +62 Problem C and D are easy to come up with . But really hard to implement and debug ...
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   +38 Agreed, on problem C it took me: 5 mins to get rough idea 10-15 mins to work out all technical details 40-45 mins to implement and debug till it passed samples 10 mins to write brute and stress test when I got WA2. The basic idea of parity sums and prefix not becoming negative is fairly standard. I'm pretty sure there was Div2 problem a while ago that required exactly those two observations.Edit: Apparently Div1C is extremely easy to code if you use k-th order statistics. See this submission — 135379742.
•  » » » 3 weeks ago, # ^ |   +11 Thanks , I know few about pd_ds. I think I need to learn more about it .
•  » » 3 weeks ago, # ^ |   0 Could you please share any hints about problem div1 C, thank you very much.
•  » » » 3 weeks ago, # ^ |   0 Hint: you can perform the operations from left to right , and find out when the array is possible to clear . Use some data structure to maintain it !
 » 3 weeks ago, # | ← Rev. 2 →   +272 I'm interested in what happened to antontrygubO_o
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +278 sad, he is already red nowhere's new avatar for Anton Spoiler
•  » » » 3 weeks ago, # ^ |   +35 I remember that his avatar was yellow long long ago?
•  » » » 3 weeks ago, # ^ |   +158 I think this is really ...
•  » » » 3 weeks ago, # ^ | ← Rev. 3 →   +138 I just wonder what happened do Anton,too.
•  » » 3 weeks ago, # ^ |   +248 Nothing special, waking up at 7AM and lack of practice lately :(
 » 3 weeks ago, # |   0 problem C hack when it's almost time :D My rank has dropped like crazy
 » 3 weeks ago, # |   0 Donno where my code was failing in DIV 2 problem B ,C was easier though
 » 3 weeks ago, # |   +8 Today I did my first hack on Codeforces. Felt a little too good to be evil, lol.
•  » » 3 weeks ago, # ^ |   0 Can you please explain the logic behind solution of problem B??
•  » » » 3 weeks ago, # ^ |   0 (n*m+2)/3
•  » » » » 3 weeks ago, # ^ |   0 take 3 squares at a time. color the middle. if extra box(either 1 or 2) color 1
•  » » » 3 weeks ago, # ^ |   +3 First thing to figure out is that when you make rectangles of dimension 3*1 you need minimum possible colourings. So, we divide the base rectangle into as any 3*1 rectangles possible and we will be left with (n%3)*(m%3) sized rectangle, now, the possible rectangles will be 2*2, 2*1 and 1*1 . First 2 cases will have half tiles coloured and the last case is prohibited so what we do here is we spare 4 tiles in one line and divide the rest all in rectangles of size 3. The remaining 4 will have 2 tiles coloured. If I was difficult to understand. Here is my solution- 135359905
•  » » » » 3 weeks ago, # ^ |   +1 Thank you brother got it!
 » 3 weeks ago, # | ← Rev. 2 →   +6 Cries to death
 » 3 weeks ago, # | ← Rev. 2 →   +1 Ready to get FSTd Solution to C cannot be so simple
•  » » 3 weeks ago, # ^ |   0 SAme here
•  » » 3 weeks ago, # ^ |   0 It's rated 900. Definitely can be simple. Here's mine for reference : link
 » 3 weeks ago, # |   +116 I didn't manage to remove cheaters in previous rounds yet. I will do it soon, but as a result, it is likely outcome that someone will change their division of participation in round 755. Regardless of the new division (after removing the cheaters), your participation will be rated in the exact division that you actually participated in round 755. That is, even if after removing the cheaters you change the division, then round 755 will remain rated for you.
 » 3 weeks ago, # | ← Rev. 2 →   -24 if(technocup){ pretest = weak as hell; }next technocup arrives hacker be like "Yeah boiii";-)
 » 3 weeks ago, # |   +19 I am not upset that pretests of C were weak ,I am upset that I didn't attempt to hack
•  » » 3 weeks ago, # ^ |   0 I have the same feeling, I found the hack very soon but I was so scared to try because it was my first time trying to hack, by the time by I gathered the courage 3 hackable solutions were hacked in my room so I had only 1 solution to hack.
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +1 Yeah I also would have felt little nervous as I never hacked before ( It always feels nervy in an unknown territory )
 » 3 weeks ago, # |   +15 I wonder if Div2.C(Div1.A)'spretest is SO WEAK Because I add abs() and go through pretest as well
 » 3 weeks ago, # |   +4 am disappointed because weak test cases in problem C
 » 3 weeks ago, # |   0 Hello All, just needed your attention here. I submitted C once and it showed me an accepted verdict again after a few minutes I again submitted with a slight different approach and it showed a passed verdict.Just when the contest got over I saw a skipped Verdict and queued verdict. May I know why it is happening so.
•  » » 3 weeks ago, # ^ |   0 Only the last accepted is checked against systests
•  » » » 3 weeks ago, # ^ |   0 Thank You so muc
 » 3 weeks ago, # |   0 Is fact what solve with complexity O(n**2) getting AC in Div1C OK? 135376136
•  » » 3 weeks ago, # ^ |   +27 Hacked. It seems that the test cases are too weak.
 » 3 weeks ago, # |   +3 weakpretest :(
 » 3 weeks ago, # |   +28 I never wanted be hacked more than now
 » 3 weeks ago, # |   0
 » 3 weeks ago, # | ← Rev. 3 →   -83 some downvoted wordsThis kind of contests should extinct from Codeforces.There's no reason for these boring&too difficult&Weak pretests problems&contests to appear on cf.The participation rate has dropped rapidly and too difficult A will make the ranklist unfair.
•  » » 3 weeks ago, # ^ |   +27 A is difficult only if you failed your algebra class in school
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   +7 My point is not on A.I decided to solve it after D.now found it the worst decision ever.More,only 5000/9000 participants submitted A.It's not a good thing for cf.
 » 3 weeks ago, # | ← Rev. 3 →   +9 A. Math, Was quite tough to meB. It could just as well be AC. It can be solved with one-liner, why is it C and why there are so many hacks and fst?D. Nice problem, enjoyed solving it
•  » » 3 weeks ago, # ^ |   0 A. I still enjoy solving problems related to algebra, interesting for me.B. Problem was meh, div 3 type.C. Really bad C. This problem is meant for div 3A. How did this even...D. This problem looks interesting
 » 3 weeks ago, # |   0 For problem B, I realized we need to take as much as 1*3 as possible so my solution was based on that. I see some solutions like cout << (n*m+2)/3 << '\n'; how the solution got reduced to that !?
•  » » 3 weeks ago, # ^ |   0 Hi ! In fact the answer is ceil(n*m/3), and with few attempts, you can realise that this is equal to floor(n*m + 2/3).
•  » » 3 weeks ago, # ^ |   +1 In total we have $n * m$ little squares. You mentioned right, that we need to take as much $1 * 3$ rectangle pieces as we can. Now $(n * m + 2) / 3$ is a way to find how much $1 * 3$ pieces we will have plus check if there is something left, so basically it is [ $(n * m) / 3$ + remainder ], where remainder is one if $n * m$ is not divisible by 3. That means that we are left with $1*2$ or $1*1$ rectangle and in both cases we will need to paint exactly $1$ more sell with blue
 » 3 weeks ago, # | ← Rev. 2 →   0 Thank this contest let me become a candidate master.I think problems are good.But the pretest of C was terrible and there were so many hacks.
 » 3 weeks ago, # |   0 Me Newbie here, how to interpret Scoring Distributions?
 » 3 weeks ago, # |   +3 I think D1D is just this problem with much harder implementation.
 » 3 weeks ago, # |   0 So weak pretests on problem C !!!
 » 3 weeks ago, # |   0 Huge difference between no of accepted solution div2 C and D. There should have another problem in middle difficulty.
 » 3 weeks ago, # |   0 Here are the video Solutions to the first 4 problems of Div-2 in Case you are interested.
 » 3 weeks ago, # |   0 Finally turned green..WohooooOOo
•  » » 3 weeks ago, # ^ |   +19 Finally turned green after being specialist and expert. Wooohoooo
 » 3 weeks ago, # | ← Rev. 2 →   +8 Why such a huge gap in the difficulties of (ABC) and D in div2..A newbie could also solve upto C and D was very tough for a specialist(maybe for an expert too)
•  » » 3 weeks ago, # ^ |   0 maybe for some cm too
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   +3 D was pretty much as alwaysThe gap is because C was easier than it should have been. In general C is intended for cyans
 » 3 weeks ago, # |   +18 how come no editorials?
 » 3 weeks ago, # |   +15 This has to be the most unbalanced div 2 round till date
 » 3 weeks ago, # |   +8 Weak pretests for problem C :(
 » 3 weeks ago, # |   +11 waiting for editorial.
 » 3 weeks ago, # |   0 My solutionCan anyone please tell me why this is wrong ?It passed the pretest but now it is showing WA I cannot even understand the test case it failed 1 1 2 1 like why it is failing why its o/p is NO it should be YES isn't? Am i missing anything or my understanding of the problem is flawed?
•  » » 3 weeks ago, # ^ |   +3 you lack of consideration of b[i] < a[i]
•  » » » 3 weeks ago, # ^ |   0 Damn it! this little observation gave me a negative ratingThanks for replying and helping mePS: Just an hour ago I saw you had 2 upvotes on the above reply and now I see 0 I don't know why people just downvote comments that may help others. :(
 » 3 weeks ago, # |   -10 Could anyone tell me what's wrong with my C code? I can not find out and I am wondering whether it is necessary to sort. 135383484
•  » » 3 weeks ago, # ^ |   0 try this TC and you'll realize why is it not working 1 2 1 2 2 1
•  » » » 3 weeks ago, # ^ |   0 Thank you very much~ I know what's wrong with it now
 » 3 weeks ago, # |   +9 Since editorial is late and for some reason no one is discussing solutions, could someone tell me what is the idea on how to optimize D2E(D1C) from O(n^2)?
 » 3 weeks ago, # |   0 I’ve always thought that rounds based on technocup are difficult and need a good knowledge of advanced algorithms, but i think this contest is a bit different , problems A,B,C are the same as a div3
•  » » 3 weeks ago, # ^ |   0 Any hints on how to solve B of div 2 :)
•  » » » 3 weeks ago, # ^ |   0 Think of rectangles of rectangles of area 3
•  » » » 3 weeks ago, # ^ |   0 if you have block consists of 3 cells so you can only do this : Red Blue Red -> RBR so think about using MOD 3 to know how many cells you will have at the end.
 » 3 weeks ago, # |   0 as a Python user, this contest was pretty disappointing. The tutorial Div1D and E solutions have essentially no hope of running in the given time limits in Python because of the absurdly large constraint allotments.
 » 3 weeks ago, # |   0 Pretty good contest, I like this type of style, only on suggestion, the gap between some problems might be a little too big.
 » 3 weeks ago, # |   -8 EASY contest
 » 2 weeks ago, # |   0 Congratulations to the winners