Hello!

Welcome to the Codeforces Round 844 (Div. 1 + Div. 2, based on VK Cup 2022 - Elimination Round) that will start on Jan/15/2023 15:05 (Moscow time). It will be a combined rated round for both divisions and open to everyone.

This round is a mirror of VK Cup 2022 Elimination — annual programming championship for Russian-speaking competitors organized by VK. VK Cup started in 2012 and has grown to be a five-track competition in competitive programming, Mobile, ML, Go, and JavaScript.

All the problems are authored and prepared by me. Thanks to KAN, errorgorn, lperovskaya, dario2994, Monogon, Arpa for making this round better.

You will be given 8 problems and 3 hours to solve them.

**UPD**: Editorial

Congratulations to the winners:

and to maroonrk for getting the only accepted solution to problem H2.

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

我的天啊我打破了你愚蠢的锁链!

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

haha broke your silly chain

haha restarted the silly chain.

Omg tourist round.

You do realise I can just break it once it reaches a significant length again?

You do realize that I can just restart it once you break it again?

if(no_of_chain_makers > chain_breakers) cout<<"Relax"<<endl;

Now for everyone's sake,Im restarting the chain again. Thank's for the support guys.

Omg turist round.

You do realise that I can just break it once again?

I'll start again.

Omg turist round.

Omg turist round.

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round.

omg tourist round

omg tourist round

omg tourist round

omg tourist round

Omg tourist round.

Omg tourist round

omg tourist round

Omg tourist round.

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg round tourist

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

turist lol

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

We need more!Notice the unusual time

OMG tourist round

omg tourist round

omg tourist round

omg tourist round

omg tourist round

no

If it's possible can you please explain how did you get Specialist Rank?

just be good at programming lol

omg tourist round

Damn, 3 hours for only 8 problems. Scary

omg tourist round

Damn, 3 hours for only 8 problems. Scary

omg tourist round

omg tourist round

I am so interested in your graph, how did you maintain a slope of 45 degrees ?

وانتا مالك؟؟

What language is this, looks Arabic I don't know it. Speak in English. Also, I expressed my interest in speedy_boy graph

NOT yours. Actually, your graph isn't interesting at all mr.newbie! The comment directed to you is below : Newbie detected, opinion rejected XDRespect to newbie

yes sir. all due respect! but he seems talking in a rude manner to me by a foreign language tho I didnt talk to him and replied to ur comment only :-( However, your graph with slope 45 is so cool ✪ω✪ speedy_boy

He didn't maintain it after this contest though, if he did he should be orange by now.

newbie detected.. opinion rejected xD

Shortest announcement ever *_*

Yes, hope the problem statements will be short as well.

:DAlso the most upvoted one :)

Not even close...

(although this might still not be the most upvoted one)

Tourist can't compete against benq in this round, but he can make some crazy geometry problems to force benq to lose rating and get back to rank #1.

What an wonderful Opportunity. Haha to be crowned again.

This contest is only for Russians ig.

Yes VK Cup is for Russians, but this is a mirror of this contest and everyone can participate.

What a great idea

good

3 hours? How difficult the problems will be

Maybe my "master experience card" will be expired in this contest.

talent, and nice avatar

I don't care about the difficulty lvl of the problems if it's Tourist Round. All i know that it is going to be fun.

Note the unusual timing

omg tourist round ...^,^

what you guys think is Benq gonna or not gonna participate this contest?

Benq will not participate, because tourist has intentionally made problems with topics where Benq is weak. This is to make Benq fall to second place in top rating chart, so that tourist can become #1 again.

Oh,man !! Is there any topic on earth in which these legendary guys are weak?

I don't know, maybe some optimization of matrix multiplication algorithm from $$$O(n^{2.43})$$$ to $$$O(n^{2.42})$$$.

To make benq lose rating you have to specifically make it hard for him. If it’s hard for everyone he won’t lose rating.

I think Benq only wanna compete with tourist who is well-known as the

No.1in competitive programming. In my opinion, he will not participate contests without tourist such as this contestTomorrow i will miss Benq vs tourist but no worries because later they will be facing each other soon

Omg 3hr Round ><

I think, Benq will not perticipate in this contest. But I will participate and face to the world number one Programme's problems...☝️

Score distribution.......???

tourist is a great personBut I really hate most of his problemsBut I can't skip his contestI'm crazy.

omg tourist round

Omg clash with ABC.

.

My IQ has decreased by 20 points while trying to read this. Thanks.

This is the shortest announcement for a round that I have ever seen :))

Legend don't need to say much. Their presence is enough alone sir!

omg tourist round . Probme 1 will be 1200+ Rated now

Nope. It was 800 Geometry. Haha

It is rated ？(⊙﹏⊙)

well, obviously, sorry bother……

TFW you expect tourist to claim back first place then see that tourist himself is the author

.

It was good one . Don't know what's wrong ? Maybe too rude or offensive for some people ?? Atleast you should have blurred the authors above. It's disrespectful for them.

Contest Clashing with atcoder Beginner Contest 285.

Tourist round >>> Any Other round on this planet. As Simple as that .

I might just end up top1 because problems are being designed by tourist.

score distribution when?

omg tourist round

ok

omg tourist round

~~Thanks to MikeMirzayanov for amazing platforms Codeforces and Polygon.~~Contest Collision (CF & ABC):TimingsAtCoder->17:30 ISTCF->17:35 ISTCF is based off VK cup. It can't ve postponed

i do bad in tourist rounds, hopefully this will change tomorrow

why problem in this year contests are didn't given any rating till now?

conflict with ABC285... what a pity that i can't participate in both contests...

That's right...

Your profile picture looks great

tourist gang

The One Piece is real!!!

Originally I am not planned to participate this contest because I have a date then. But when I see the author, I just postponed the date and register for this contest. Wish I can turn cyan once again.

You guys are having girlfriends!

Reference

omg tourist

I wish the next round will be written by BenqObviously tourist round will be full of fantastic problems. Good luck, yeah! ^=^

I will always be a fan of tourist!

It is briefly before the beginning of the round now, and score distribution hasnt been announced yet...

Where is

score distribution?I think I may not be able to participate because I feel like going to the toilet right now. What a wrong timing. :(

glhf

OMG tourist round

I regret I couldnt participate in it as I got stuck with some personal work

why the rating of H2 is higher than the rating of H1

it said that H2 is the hard version,doesn't it?

its not H1 vs H2 but rather H1 vs H1+H2

A solution for H2 always works for H1. So if you solve H2 you get the points for both.

F is an amazing problem! couldn't code it in time though, but mindsolved it

Can somebody please tell the solution?

$$$dp[i][j]$$$ = $$$P$$$(Minimum Prefix $$$\geq$$$ $$$ -j $$$ )

In E, finding maximum total area is not that hard but finding the exact subrectangles seems quite difficult. Stuck on it's implementation. Any approach regarding the same?

Maintain a stack for the rightmost intervals for u, d, ud rectangles. It was very painful implementing this, especially when the contest started at 4am for my local time.

Hey, thanks. I just implemented the logic using your stack idea. Yeah, felt like handling a lot of cases!

My solution

Pretty hard contest.

No idea for D. Have idea for E but got WA. Now I'll return to CM.

how's C done ....?

It's pretty annoying. You need to consider all j that n is multiple of j, calculate how many char will be changed if you make the string to j kinds of different chars. You need consider 2 cases: j<j0 , j>=j0, where j0=the number of different chars in the initial string. If j<j0 you need change some chars with low frequency.

After you decided the optimal j, you need to add all chars you'll put to the final string into a "char pool" (implemented as int pool[26]), first try to make every chars remain the same(if(pool[s[i]]>0) pool[s[i]]--; flag[i]=true;) the assign i where flag[i]=false any char in the pool.

Well consider two indices i and j. now calculate all such x that make both a[i] + x and a[j] + x a perfect square. the rest should be easy

In E we can first shrink rectangles with same type (row1, row2, row1+row2) and then consider for each 2-height rectangle, shrink it if it's penetrated by any 1-height rectangle, and shrink every 1-height rectangles who doesn't penetrate it but cross with it.

However I got WA at pretest 15. Also C was very annoying. I spent about an hour for it.

What I did is calculate the answer firstly for two numbers, let's say a and b. We want to transform a into x^2 and b into (x+k)^2 (because b > a), and that means that $$$b-a = (x+k)^2 - x^2$$$, so $$$x = {(b-a-k^2)}/{(2k)}$$$. You can just try every k from 1 to sqrt(10^9) to see whether that k satisfy this condition, then, for each valid k, calculate the number of perfect squares you'd also obtain from the other numbers in the array.

Let's choose some x. If ai & aj becomes perfect square after adding x, then: $$$a_{i}$$$+x = $$$u^{2}$$$ & $$$a_{j}$$$+x = $$$v^{2}$$$ Substracting , we get $$$a_{i}$$$ — $$$a_{j}$$$ = $$$u^{2}$$$ — $$$v^{2}$$$

=> $$$a_{i}$$$ — $$$a_{j}$$$ = (u-v)*(u+v)

Now split ($$$a_{i}$$$ — $$$a_{j}$$$) into 2 factors f1 & f2 such that f1*f2 = $$$a_{i}$$$ — $$$a_{j}$$$.

So, f1 = u-v & f2=u+v.

Find, u from here. Substitute in $$$a_{i}$$$+x = $$$u^{2}$$$ & you will get x.

Find the count over all possible x in this way & take the minimum one.

I thought trying for every factor of a 10^9 number for 50*(50*49/2) times would cause TLE…

my thinking was similar to you though instead of tle i got wa

Now I upsolved D. My submission:189361440

The proof of that the submission is available:

In the algorithm we consider for all divisor k of (aj-ai) where j>i. The maximun number of divisors we check in one case is:

sum(1<=i<j<=n, sqrt(aj-ai)/2)

The "/2" is because if (aj-ai)%4==0 k must be even, if (aj-ai)%4==1 or 3 then k must be odd.

Notice that sum(a[i+1]-a[i])<=A (A=max(a[i])=10^9). We can see for each d, sum(1<=i<=i+d<=n, sqrt(a[i+d]-a[i])/2) is maximized when all a[i+d]-a[i] are same (can be proved by the mean value inequality) and the maximun value is about (n-d)*sqrt(A*d/n)/2=n*(1-t)*sqrt(A*t), where t=d/n. We sum up it for d=1...n-1 and the sum is about O(n^2*sqrt(A)), which fits the time limit.

It doesn't TLE, because you're factoring the differences of $$$a_i$$$ and $$$a_j$$$, all of which can't be around $$$10^9$$$ simultaneously.

it's around 4e7 operations (which should be doable even with 1s time limit), plus the time limit is 4s.

But for case a[i]=1+20408160*(i-1), it runs for 10622587 operations.

My testing codeOHHHHH I forgoted there's this line in the statement:

I missed in the contest.... I've thought sum(n) could be 2500 and missed the intended solution.

I just upsolved D with a similar solution. I iterated over all n^2 pairs of numbers. For each number, i iterated over all values of f1 (so sqrt(max(a)) time) and did some math to see if it worked. Then I took all the possible values of x I got, and I simulated the process for each value of x.

Problem A was kind of ugly. C also required (at least in my case) a quite hefty implementation.

problem C is tough :((( Can anybody show me some hint? :((

Definitely, not an easier one!!

I spend almost 3 hours but still couldn't solve it :((( But i see so many people could solve it :((( Pardon me for my bad english

Just brute every i from 1 to 26(i is how many letters will be left in string -> n % i == 0) and then you should calculate how many ops(call it cnti) you needed to make string balance(i used greedy in this part). So your first answer is min among cnti.

Implementation is nightmarish.

Suppose you want to modify the string to have exactly $$$x$$$ distinct characters. How many times will each character appear? Which $$$x$$$ characters should you pick? Can you calculate the minimum number of changes to reach $$$x$$$ distinct characters?

ofc the first question immediately got hit by annoying geometry question lol(don't worry imo it's also interesting)

how's problem C solved ...... nothing struck my brain for like 1.5 hrs i took multiple examples but i couldn't generalize it .

You can keep only 1 <= i <= 26 characters with n/i frequency for each one

Try them all and minimize the answer

Can't believe I clutched C like that.

Seeing the drawing for problem A before reading the problem statement was intimidating lol

Anyone know what pretest 11 was about in problem E ?

I got WA11 and 2 1 3 2 3 2 3 2 4 helped me find the mistake. When I was using only 1 row out of 2-row rectangle I forgot to clear the other row in the segment tree

How to solve D? :(

See here

The answer can always be 1. Now let's see what will happen if the answer is $$$>1$$$.

So suppose the answer is 2. This means that there are any two indexes(let's assume i and j) such $$$a[i]+x=c*c$$$ and $$$a[j]+x=d*d$$$. Here c and d can be any valid integer. So now $$$d^2-c^2=(d-c)*(d+c) $$$.This is equal to $$$(a[j]-a[i])=(d-c)*(d+c).$$$

Now if we factorize $$$a[j]-a[i]$$$. We can find the value of $$$d. and .c$$$. Using those values we can find the value of $$$x$$$. Now we will store all the eligible values of x and use the best possible option.

SpoilerHow's the factorization is happening. Suppose $$$a[j]-a[i]$$$ has a factor($$$A$$$).Then there will be also be another factor $$$(a[j]-a[i])/A (assume B)$$$. Now $$$A*B=(d-c)*(d+c)$$$. So $$$d=(A+B)/2$$$ and $$$c=B-d$$$.

I didn't get how you solved to get, d=(A+B)/2 and c=B−d

since $$$d+c=B$$$ and $$$d-c=A$$$. If we add both the equations we get $$$2*d=A+B$$$ which is equal to $$$d=(A+B)/2$$$. For the value of $$$c$$$ it comes from equation 1 by shifting $$$d$$$ from left side to right side.

I swear F is easier than E...

any hint on d?

D is simple but the constraints are way to big. Any idea how to solve it ?

Suppose that $$$b_i^2 = a_i + x, b_j^2 = a_j + x$$$, then we have $$$(b_j - b_i)(b_j + b_i) = a_j - a_i$$$. By enumerating $$$b_j - b_i$$$ we know what $$$b_i$$$ and $$$b_j$$$ are, and also the $$$x$$$.

So ... it is not simple, then?

D was very good

Yeah, it was nice. I initially thought it was some sort of meet-in-the-middle trick, but was pleasantly surprised to see it was a much nicer brute-force.

How did u solve D ?

Spoilerlets consider i<j and a[i]<a[j] then if both a[i]+x and a[j]+x turn out to be perfect square then

$$$a[i]+x=n_{i}^{2}$$$

$$$a[j]+x=n_{j}^{2}$$$

then from $$$ a[j]-a[i]= (n_{j} - n_{i})*(n_{j} + n_{i}) $$$ you can find all possible x's in $$$O( \sqrt{n} )$$$

then for any x if total number of pair's it makes perfect square simultaneously is y then this $$$ ^{ans} C _{2} = y$$$ should hold

As x can be of the order 1e18 wouldn't O(√n) will be of the order 1e9? which should TLE?

We only need to find the factors of a[j]-a[i] to deduce all the x's and a[j]-a[i] can at max be 1e9.

Can you please Explain About How to Find X using (a[j]-a[i]) what two factors represents of difference and how this term come (factor1 + factor2)/2

i am not getting it :(

see for $$$n_{i}$$$ and $$$n_{j}$$$ to exist $$$n_{j}-n_{i}$$$ should exist and be a factor $$$a[j]-a[i]$$$ because this equation $$$a[j]-a[i] = (n_{j}-n_{i})*(n_{j}+n_{i})$$$ holds.

therefore if we iterate on all the factors of $$$a[j]-a[i]$$$ , (p,q) such that p*q = $$$a[j]-a[i]$$$ then we can treat smaller of p,q & p<q as $$$n_{j}-n_{i}$$$ and the bigger one as $$$n_{j}+n_{i}$$$ and solve these two equations

$$$n_{j}-n_{i}=p$$$

$$$n_{j}+n_{i}=q$$$

find a feasible $$$n_{i}$$$ , $$$n_{j}$$$ if it exists we can get the respective x from equation

That's what she said

trash problem E, only boring implementation.

I will never think a strong competitor to be a certainly good author any longer.

I thought it has to be obvious after first stage

Implementation is an important aspect of problem solving too; in my opinion, there's nothing wrong with problem E. You need to find a way to systematically reduce the rectangles, and figuring out how to structure your code to do this as efficiently as possible is part of the challenge.

I agree. Compaired with implementation, observation is much too easier in this problem. That makes me feel really bad.

I can't implement it, too. But I think it's not all the author's fault. E is not very good but also not trash.

We should consider to improve ourselves. I have already suffered a lot for my poor implementation ability.

Problem E is a good problem. Please do not send such stupid comment only because you can't solve it. This will make you look like a loser.

I don't solve FGH, but I don't criticize them. You never get to know why I am saying it's trash and others are upvoting me. So you are a fool.

That's because you can solve E in usual, while you have never been solved problem FGH in the past. You just arrogantly make silly comment on problems you can't solve, and try to infect others with your trash emotion. You never get to know why I am saying your comment so brainless, you will just like a mouse hide in the hole and won't listen to others opinions.

OK, next time at div4 A I will provide you with a math problem that has 10,000 corner cases and requires 100KB code and you cannot solve it and I say to you that you should improve your coding skills and not complain about the problem itself

Actually, E was not that difficult to implement.

For me, implementation is like an art: if you do it the right way, it feels godly.

Yes, of Course he will not complain.

I really hate a homeless dog barking at me when I'm walking in the street. It's really annoying. But I can't have too many requirements to a dog, right? They just want a bone.

The same to you, fucked bitch

Angry fool, LOL. I don't mention anyone. If you are angry, that's only because you are shame on yourself<3

I know.

But why are you grey?

More often than not I cannot solve problem E even D in div1+2 but never have I criticized them if it's my fault that causes me to fail to solve it

You are being offensive. You are not offering any explanation for your words. You are attacking when attacked. I really can't stand this behavior by entitled contestants. Many comments by you in the past have a similar attitude, that makes you a bad member of the community. Please be more respectful.

Problem E was rather easy to mind-solve in quadratic time (and still interesting). Rather hard to implement properly in pseudo-linear time. That is one of the main points of the problem. The implementation itself (at least mine) is short, but I wasted more than one hour because of wrong assumptions, wrong ideas, not having the whole picture clear in mind, and blah blah. That does not make the problem trash, it makes me weak. I was very satisfied when I finally solved it.

You are the fool if you assume that codeforces upvotes are a valid support for the content of your messages.

pls shup up until you can solve E

What make you mention that i can't solve E? Please shut up until you can prove it.

so how can you know he can't solve E

He agree it himself bro, please don't ask such stupid question next time.

Arisu_Sakayanagi can't you?

they ACed A-D 1:17 into the contest, then proceeded to WA on pretest 1 on E for two hours.

Now, perhaps I'm too low rated, too unexperienced to judge a master, so take my word with a grain of salt all you like, but that doesn't sound like they can solve "only boring implementation". If they only had a hour or so sure it might have been a time issue, but two hours for ~150 lines of implementation that only involves greedy and sortings? Please.

When I get stuck on implementation for two hours in a contest, I don't say the problem is trash. I say that I'm too bad at programming and that this problem exposes an issue in me. I should be grateful to this problem even though it gave me -delta because it shows me how to improve my ability.

That's very offensive to say Sir. Either problem is Good or it is not meant for you. Tourist has put his hardWork and time into that problem, atleast he deserve a valid constructive criticism sir. Codeforces upvotes are merely a number to me. You are still wrong to me. Also Someone hardwork isn't trash at all.

thanks for this great round

How to solve problem C?

My idea was to enumerate the number of occurrences of each character.

It took me about 2 hours. But I got TLE on pretest2.

(Forgive my poor English.)

Edit:

Why many people downvote this comment?

My idea was to first, implement a function that optimally changes the string to be

balancedwith $$$x$$$ different characters ($$$O(n\log(n)$$$) in my implementation). And then go to all the divisors of $$$n$$$ less than 27, because the number of characters cannot be greater than 26. Then in total is something like $$$O(26 n\log(n))$$$.Thank you for helping me to solve this problem.

How to solve F?

I turn the problem into this:

There's an array S indexed from -n to n, the number on index 0 is 1, rest is 0.

Do n operations, on each operation there's S[i]/sum(S) possibility to choose index i, add 1 to S[i], then P possibility to add S[i+1] 1, 1-P possibility to add S[i-1] 1.

Output the possibility to make S[-n...-1] both 0 after n operations.

But I have no idea how to solve this :(

perhaps we should add s[i] 1 too?

Oh I forgot to mention it. Now it’s fixed. Thanks!

If D doesn't use

`long long`

type to save $$$x$$$, will it be WA on #5? I got WA on #5 and I think it was because I didn't use`long long`

type to save $$$x$$$, but I didn't have enough time to change. :(Yes.

Thank you. I will resubmit my code later. :(

F was a lovely problem, absolutely loved it !

How to solve Problem B

More generally, how to approach these questions based on sorting?

Check if you can take k people. You can take k people iff there are exactly k people for whom a<k and there is no person for whom a=k

In problem D, suppose any two consecutive square numbers are p^2 and (p+1)^2 . Then their difference will be

(p+1)^2 — p^2 = 2p+1.Now given the maximum element is 1e9. so after choosing some x and changes a[i] to a[i]+x. The maximum number of all a[i]+x will be at most 2e9 or even less than 2e9. Isn't it? Or I am wrong somewhere? If this is the final solution we can brute force all the perfect squares of a[i]. But this solution gives me WA at test 5. Where is this solution wrong then? My solution . TIA :)Hint: 1e9*1e9=1e18

no, difference is at most

`5e8`

, but actual squares can be up to`3e17`

,and number of squares is still`1e9`

"so after choosing some x and changes a[i] to a[i]+x. The maximum number of all a[i]+x will be at most 2e9 or even less than 2e9"How you came to this fact?, like x can be upto 10^18.

Got it. Found the mistake. Thanks a lot.

8

6 0 3 3 6 7 2 7

For the third testcase in problem B (reproduced above), why couldn't 2 people (persons 2 and 7) come? They'd both be happy (2 because at least 0 come and 7 because at least 2 come) and the rest because they're each happy if and only if 3 or more come; less than 3 come, so the rest should be happy as well. Why isn't this a valid result?

a person is happy if at least ai persons OTHER THAN i are coming

The problem statement says a[i] excludes the i-th person themselves. So 7 would not be happy, since there aren't two

otherpeople who went (just one).How can you participate in 234 contests consistently for 4 years and still be a newbie?

When will we be able to upsolve?

Wrote solution for 1782D - Many Perfect Squares few minutes after the contest and got WA on test 6. Can anybody tell me what's wrong? (189360636) It passed more than 50000 random tests with $$$n\leq{7}$$$.

You shouldn't stop iterating over $$$k$$$ when you found an appropriate one. If you try out all valid $$$k$$$'s, your solution will pass the tests (check out this submission: link)

Thank you so much!

A pretty hard contest tbh especially C, so hefty implementation

I liked C. Good problem where you think how to implement rationally.

...Cofeforcer codefofced coresorces!...The ratings are updated preliminarily. Tomorrow I will remove cheaters and update the ratings again!

Thank for kicking me back to div2. Maybe I need more practice before being a genuine master.

Welcome to the club!

Now I've upsolved E. My submission:189365023

Basic idea:

First the maximum total area is the initial area. Proof: for any 2 overlapping rectangles, if they are same type (row1, row2 or row1+row2; we'll call them type1, type2 and type3 later), we can shrink one of them to remove the overlapped area and remain the same total area,like this:

[-------[+++++]||||||] -> [-------] [|||||||||||]

('-': left '|':right '+':overlap)

So we can remove all overlaps caused by same type of rectangles. If they are still 2 rectangles who are overlapping, then one of them is type3, the other is type1 or type2 (since type1 cannot overlap with type2, and we've removed all overlaps of same type in previous step). WLOG assume they are type 3 and 1. If type3 is "penetrated" by type1, which means type1.L<=type3.L && type1.R>=type3.R, we need to shrink type3 to row2 (and it becomes type2), like this:

[---[+++]---] --> [---------]

.....[| | |]...............[| | |]

('-': type1 '|':type3 '+':overlap)

Otherwise, we can shrink type1 to remain the area (since type1 can only get out of type3 from at most 1 side). Now we could solve the whole problem.

The naive approach is O(n^2), but by classifing rectangles by different types and sort them by the left borders, we can get an O(n*log(n)) solution. In the first step, for each type of rectangles, we keep prevR=the largest right border of rectangles we've checked, and for every rectangles with left border <= prevR, we move it’s left border to prevR+1 (and if it's left border is greater than the right border, we mark it as removed). In the second step, we maintain 3 pointers p1, p2, p3. For each type3 pointed by p3, we check for every type1 and type2 until there's no more that type of rectangles, or it's left border is greater than type3.R. If there's any type1 penetrates the type3, we mark flag1 as true, similar for flag2. After checked type1 and type2, if(flag1 && flag2) we mark type3 as removed, elif (flag1) we change it's type to 2, elif(flag2) we change it's type to 1. (However, the code implementation is very very very annoying)

Update: Now I've kicked back to div2. Maybe I need more practice to make sure that I can solve all solvable problems in contest.

Worst problem C ever

Cheating case Codeforces Round #844 (Div. 1 + Div. 2, based on VK Cup 2022 — Elimination Round)

problem CZaoldyeck code :- 189324513

HAKUNAA_MATATA code :- 189349431

Thanks for the fast editorial

I suddenly know why 19000+ people registered but there were only 9000+ people submit.

People either got scared of problem A, or they accidentally slept in. (I started the contest 30 minutes late bc I slept in XD)

Unusual timing also didnt helped the cause. I couldnt participate due to contest getting started ealier than usual

This is the hardest race I've ever done

Can someone plz tell where this code goes TLE. Solution code for problem C 189395773

omg tourist round

Hi there!

If you have any doubts in problem B and C you can checkout the tutorials here- www.youtube.com/@grindcoding . Happy coding!