Hello, Codeforces!

I invite everyone to participate in Codeforces Round 884 (Div. 1 + Div. 2), which will start on 11.07.2023 17:35 (Московское время). The round is a combined round and will be rated for everyone.

You will be given **8 problems** and **3 hours** to solve them. One of the problems is divided into two subtasks. The scoring distribution will be:

$$$500$$$ — $$$1000$$$ — $$$1250$$$ — $$$1500$$$ — $$$2000$$$ — $$$(2000+1000)$$$ — $$$3500$$$ — $$$4000$$$

All problems are written and prepared by me. I would like to thank:

- irkstepanov for carefully coordinating the round.
- MikeMirzayanov for the wonderful Polygon and Codeforces platforms.
- 4fecta, ak2006, amethyst0, AndreySergunin, BalintR, ChrisT, Div1D4Life, dorijanlendvaj, Dormi, errorgorn, Golovanov399, IndignantHydra, jonatas57, kzyKT, lexiyvv, liouzhou_101, Maksim1744, maximrufed, mc._cari, MvKaio, NoDesire, polosatic, RedstoneGamer22, skittles1412, tibinyte, valeriu for testing the round and providing valuable feedback.

I look forward to your participation and hope you enjoy the problems. Good luck!

**UPD 1**: Editorial

**UPD 2**: Congratulations to the winners!

and congratulations to cnnfls_csy and orz for solving problem H!

Now the testers can comment

Now the participants can reply...:)

As a partcipant, Hoping +ve delta for myself :)

thanks

Thanks to the author, very good experience！

As a tester, I comment

As a participant, I replied

I Guess that you have not been participated in the contest for last year.(except the one in June)

It's amazing that a single writer prepared all the problems for a Div. 1 + Div. 2 contest! Hope the problems are interesting :)

I think the contest is going to give us tough time!!

revision :

one LGM write all the problems

Looking forward! Score distribution means I might finally get a D solve again ;)

Scoring distribution has betrayed us a lot of times ;)

Yeah but this time I truly believe I can do it. ;)

atb!

thanks, good luck to you as well

Worked

Is the cat in Golovanov399's profile coughing?

NoOh, my bad.

And all these time, I was thinking that it was trying to salute someone

ig its laughing :)

I also participate and try to increase my rating

As a tester, I can confirm the hardest problem is harder than the easiest one.

Good luck!

As a tester ( giving that he participates ), I can confirm tourist will solve at least one problem.

Good luck!

As a non-tester, I shall reply to the claims of the above testers.

hope to become green in this contest.

Why is problem number 6 score (2000+1000)? Is it because of subtasks? Asking because I have never seen subtasks on CF :)

There will be F1 (score 2000) and harder version of the same problem as F2 (score 1000).

It will probably be the easy version with 2000 points and the hard version with 1000 points. For example, they were split equally in the following competition, but not equal points this time: https://codeforces.com/blog/entry/116091

One good contest for me and I will be surely on my peak.

As a tester, video editorials for most problems will be on my channel after the contest

Thank you!

Hoping to reach blue

poorpul

hee hee hee hawww

i will try to become pupil on this contest

I was just wondering, is there a reason why this round is combined Div.1 + Div.2, while the rounds are usually separate Div.1 and Div.2? I understand that rounds with prizes are combined to let everyone have a chance for a prize but this round is not one of those.

Congrats!

Here we go, Go to Grey again :)...

Here we go, Go to unrated again :)...

Destroy the feelings :D .

can anyone tell me how can I become a tester?

u can check this blog.

are you from the same London as Justin Bieber?

I thinks that frequency Of DIV : 4 contest is reduced so much??? As earlier DIV : 4 almost happen every month But of now there is no DIV : 4 contests happening.... It's very long time that No DIV : 4 contest has been happened....If it is like this what will happen to the participants like us which are "newbie" on codeforces... Isn't It?? What's Your opinions On this... Just personal Feeling's.. If anyone get's offended by this Sorry for that(:

I mean you could actually try solving some harder problems?

Is +66 delta too much to ask for!!!

and shameless me asking for 113+ delta xD

I think you need about top 700 overall to get this delta

As a partcipant, I excited

poorpul

Enjoy the three hours and get rating

## Question:

Sir, I am a newbie. So am I eligible for this contest ?

yes, anyone is eligible for this contest regardless of ratings.

Thanks @amit_pandit_15 for replying. So if I was able to solve only single problem in this hard will this decrease my rating badly. What do you think?

In starting contests(for like first 3-4 contests) the ratings increases only, even if don't have good performance, since you have given only 2 contests, solving even one question will increase your ratings.

I think getting at least 2 problems right should be enough for you to get a +ve delta

Hope to get close to CM :)

i hope to become a specialist again. Are u a third-year student?

I gave my 6th semester exam before this summer vacation , i am currently in 7th semester now.

poorpul

Tonight, I am ready for the first battle to achieve the prestigious Purple Rank.

poorpul

I will try to solve A-D ASAP to have time to solve E, sound interesting!

I'm sad. I have a summer camp so I can't participate. I will definitely up-solve the problems in the contest tho. To everybody who is taking the contest,

GL & HF!!!I wish I can see a Lockout Between tourist and Benq :) ... What is ur opinion guys ?

yes this rivalry is best

is tourist going to surpass Benq in this contest? make your bets: like for yes dislike for no

I hope we don't go back to the green name

Does this mean that our ranking will be more than 1,000 lower than the usual Div.2, and it will be more difficult to add points, because the experts of Div.1 will also participate.

it doesnt work like this. Actually, because of the rating system its usually easier to get points. Read about how codeforces rating works heres the link: https://codeforces.com/blog/entry/102

Thank you for your reply.

poorpul

hehehehaw moment

i wanted to see tourist at 1 again.

he granted your wish.

lol, cnnfls_csy clutched in last 2 minutes. :D

wait i cannot register anymore, why? Edit: i tried to register 10 mins before contest

now register in extra registration time

I'm unable to submit It is giving me error you should be registered to be able to submit

Is so hard for me

Damn I had AC on the first problem, but I tried other solutions, so I resubmitted 2 times and lost 100 points :'(

Slowly proceeding towards my fav colour :)

and it isCyan

I wouldn't say that's slowly, that's a big step.

Ah yes, I am really missing Cyan, so I decided to take a big step :)

just kiddin, if you didnt submit all of them at once you would have lost just a little rating. you are closer to CM no worries

is cf-predictor working? it's not working for me

It hasn't been working recently, didn't work for me last contest either.

Use carrot https://github.com/meooow25/carrot

this is more accurate also! thx

i am going to get demoted for sure.

DsolvingForces

Balanced as everything should be ):

speedforces

no hacks forces

mans loh

Wow,5500 submissions on problem D,codeforces has become leetcode. Cheaters everywhere.

5k on D is okay, but 10k on B not okay!!!!!!!

Can I know ,why your April 16 div2 is unrated?

Rating is not increasing ,neither the contributions, what should I do now ?

Both doesn't matter.

Problem AMay I know why this condition is not valid

1 2

b can be two while a = 1

Consider the case where a is 1 and b is 2.

test case :

a=1,b=2

If $$$a = 1$$$ and $$$b = 2$$$ you get wrong answer. Then the first player can take $$$2$$$ and remaining stones are $$$0$$$ total so second player loses.

a = 1 and b = 2 in this case you print 2, but then the first player can win in one move.

Given a=1, b=2; you chose 2 stones. first player removes b (2) stones, leaving 0 stones, second player loses.

What if B is 2, then first person will reduce 2 from 2 (your answer) and second person cannot move.

got it, thank you

what if b=2

ConstructiveForces

they should be flipped

Bro , your jump from expert to candidate master is the highest jump ever recorded in human history,may I know the hardwork behind this success

How to solve C?

It's not possible to sum odd and even index numbers. Try it.

So you have to get max sum from either odd or even index numbers.

The odd (in this case) can be summed up (or deleted) and the even have to be deleted. And vice versa.

Also check for the case when all numbers are negative.

so what was the edge case for C?

are you checking maximum subarray sum for odd and even indexes??

yes

It should be a maximum subsequence. For the array 1 -1 -1 -1 1 you can repeat move on 3rd and 2nd then you will get 2

Ohh got it, thanks.

1 -1 -1 -1 1 test case broke my solution. Did not realize that you can safely discard negative elements.

Codeforces Round #884 (Div. 1 + Div. 2)

ConstructiveForcesAlgorithm (X) Construction (O) Contest.

Speedforces from A to D

how to solve C?

Simulate the operations for a few cases. You will observe that the final array collapses to a subset of one of the following index sets: {1,3,5,7,9...} or {0,2,4,6...}. Moreover, no adjacent elements can be part of the final sum together.

what about the case -1 1000 -1 -1, shouldn't the answer be 1000?

yes. In this case, the subset of {1,3,5,...} chosen by us is simply {1}.

how would we go about choosing the subsets?

subsequence i guess?

Just choose all the non-negative elements :)

thanks, well back to cyan

How to solve D?

Answer exists because $$$lcm(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26)$$$ $$$>n$$$, not because $$$26!>n$$$.

thats right...

skill issue

teach me E

yes actually 'teach' is the right expression.

Why does every problem in this contest feel constructive? 🤡

Problem E is cool!

Though ABCD were absolute speedforces which I really failed, after solving E it didn't matter

How to solve C, I understand that I should always remove the current minimum element, but I had no idea how to efficiently implement that?

you can only sum even index with even and odd index with odd so you need to calculate the maximum of both.

Swap(C,D), D was very straightforward unlike C.

wonderful problems!

so huge gap between D and E

Great contest! 2 problems with hello world solution is insane :D

GuessForces

Please explain E.

I guessed the solution of E but don't know how to prove it.

For (i, j) such that 1<=i<=n-1, 1<=j<=m-1, we must have (i, j)==(i+1, j+1) (we denote a[i][j]=0) or (i+1, j)==(i, j+1) (we denote a[i][j]=1), then for any valid grid, there must be some f[i] and g[j] such that a[i][j]=f[i] xor g[j]. Then we can solve the problem by dsu.

I have been thinking for an hour but still cannot come up with a conclusion, can you give me a rough idea?

think not about the letters, but about the grid of choice which diagonal contains the same elements in 2x2 squares — 1/0. All the lines of the grid are the first or the reversed first (suppose you know the first row and the first element of the second — you will see that the second is uniquely restored). Then check if it is possible — a system of disjoint sets and a top-down/left-to-right scanline

apparently, the second part can be made much easier :)

(Editorial is already out)

Can I ask how you found this pattern? I couldn't construct objective examples for me to observe during the competition. Did you figure it out just by looking at the samples?

in samples there is "square"

1 ... 1

.......

1 ... 1 — YES

1 ... 1

.......

0 ... 1 — No

from that and looking at n = 3 m = 3 cases

shout out to ur mom and ur 1e9 copies for problem E

As a leetcode refuge, I really enjoy these problems, even if I solve a few each time. I can feel my brain working ;p. Each problem seems so easy after I finally solve it, but before that I might spend an hour on it.

Amazing contest! Had fun solving A to D, each problem had some beautiful insight hidden — which apparently, I was too dumb to notice, hence overkilled A with DP :X

Cheers to -100 delta, and 3 hours of absolute fun! Kudos to the author, and the entire team. Looking forward to future contests by duality!

No way you used dp on problem A hahaha. Btw, it is always helpful to check the leaderboard. If a lot of people are getting AC on a given problem and you are stuck on it, chances are the solution is much easier than it seems.

Someone tell me how to solve "B. Permutations & Primes" problem?

Anything that includes 1 and 2, but doesn't include 3 has prime MEX. So we place 1 and 2 in the middle and 3 all the way to the side, to maximize number of such segments.

Now, anything that doesn't include 1 can't have prime MEX, so now we only need to consider segments that contain 3 and 1. The only way this can fail to have prime MEX is if it includes 2 but not 4. So, we place 4 right next to 3 to minimize such segments. Now. We only need to consider segments that contain 1 2 3 and 4. These have prime MEX unless they contain 5, so we place 5 all the way to the other side of 3 and 4.

After this you can fill in the rest of the numbers arbitrarily.

thanks

In c is this approach right ?

If there are all negatives , print max of them . Remove all the consecutive negatives from front and back . Move from left to right , if you see a subarray of negative numbers and the size is odd . Add the two positives at two end and delete all negatives and those two. If the subarray negative numbers size is even , add the max of two positive at two ends and remove negatives and those two positives .

At the very end after traversing , check if sum of odd indices is greater than sum of even indices . Print max of them ?

I did not partecipate the contest but I Will try to upsolve. I think problem C can be done through DP. Is this the right way to go?

Yes, DP is possible, but greedy is also possible

Ok I Will try both approaches. The first thing which came to my mind when looking at it Is DP. Do you think the DP solution is hard to code?

My implementation was quite simple

Ok cool. I will take inspiration from your one if needed

congrats on GM :D

Thanks, I should probably celebrate before I fall back to (international) master lol

Within 8 months too damn

I think greedy is easier.

SpoilerNotice that you can always get subsets of the even elements or odd elements, so just get all positive elements at odd positions, all positive elements at even positions, the maximum of the array, and print the maximum of those.

Thx

E destroyed my brain

What a gem of a round! E and G are just stunning problems, and the rest is very good also.

c>>>>>>d anyone?

still more people solved C dont know why

hmmm maybe? dunno, try multiple cases and you ll notice that you can get any subset of even or odd positions

coloringforces

anyway, it was a nice contest, really liked the problems :D

what is the idea behind the d problem?

The min distnict charcter in ansere is always first non-diviser of the given n ,,why this approach will work because let suppose x is not divide and then any multiple of x never divids n like 2x,3x,4x,5x... so on.and for ex. (3x+1) divides the n then the matrix of size 3 cross something and somthing cross 3 never be bad ..hope you understand the approach

Thanks i was storing the total factors of n but got it now

Why coloringforces? 0-1 coloring applies only to E I think

D is technically graph coloring

D was also a coloring problem on a special type of graph

D?

Wow! Superfast editorial with hints..

I think C > D......

want more frequency in contests

blazzing fast editorial

Maybe testdata of F1 and F2 is too weak? My O(n^2) solution for F1 successfully passed F2. https://codeforces.com/contest/1844/submission/213394774

and to my surprise, it even faster than most of O(nlogn) solutions.

Hacked. A case containing lots of gaps that are less than $$$|c|$$$ but where twice the gap is more than $$$|c|$$$ causes your code to repeatedly erase from the front of the list, achieving $$$\mathcal{O}(n^2)$$$ behaviour.

Unfortunately, I did not anticipate this approach before the round, so the tests did not contain this type of case.

Also I saw this submission, may be it can be hacked too.

Thank you for pointing out this submission. I hacked it too, using a test where only one small value satisfies the

`check_val`

condition.Good problems and strong pretest! I ranked 377 when the contest ends, and rank 377 after the system test. The only thing needs to mention is that difficulty gap between D and E is too large.

Do you think you will get master?

I don't know. Can anybody use the rating predictor to predict my rating changes for this contest? I am not able to use Chrome since it gives me 403/forbidden error.

predictor gives me +70 for you

congratulates for master bruh :)

hope for me reaching cyan , i have been fighting for too long TOT

how to use the CF predictor? I used to just use the site but I get a 502 error. How do you use the extensions?

Use carrot extension

didn't you quit CP or something?

I hope to become an expert：）

Me too :)

Now you have fulfilled your wish

thanks ：）

I really enjoyed solving problems of this round, problem C is my favourite problem now, it is very interesting. But i have a problem, I have "hack it" button after the ending of the round

See https://codeforces.com/blog/entry/68204 for details.

orz Orz

Thank you.

People with rating predictors, could someone tell me my expected delta?

+116

Honestly such a well organized contest, I thank everybody involved.

I am trying to figure out what is wrong with my solution https://codeforces.com/contest/1844/submission/213344967

It appears that the checker output does not show failed test case. Is it intentional? If so why is that?

I think from one of the odd or even sets we have to take only positive charges in your solution according to my thinking you are considering the sum as maximum(ith charge or sum + ith charge ) but if ith charge is -ve we dont have to consider it

Thank you, but my question was about why we can't see failed test cases.

output should be

11. your code gives7.Thank you for provided test case, but what I actually want to know is why failed test cases are not shown in checker output.

I'm not sure about that. Sorry for the wrong reply.

This contest is really tricky , I really need to work hard . I wasn't able to think in 3rd problem that from groups of odd's or even sets we can leave negative charges , I was solving like taking the first four charges and finding whether to remove 2nd charge or 3rd one and continuing the process again from remaining ones

no offence but why A to D has to be easy speed forces in a div-1 + div-2 round ?

CLIST shows a 1000 rating difference b/w D and E damn

In any contest the starting block consists of quite easy problems, so it's kinda speedforces. Would you like C and D to have been harder?

Yes

C was fine, i guess D should have been in the expert range.

For me at least, C=1400 and D=1800 would have been better, give or take 100 rating points.

So I suppose C was OK today but D was obviously much easier than it should have been.

Div.1+ div.2 = div.3

B>C for me

Did anyone else have an issue understanding problem D on the mirror sites? The string examples didn't have grids around them. I had to open the original CF problem page.

In problem E $$$\mathcal{O}((n + m)k^2/\omega)$$$ passes. 213399890. You can uphack if you want.

1159 Rank can I reach Expert (1478 >>> 1600)? I am eagerly waiting for the Rating Changes.

Also, why isn't the CF Predictor Extension working lately? Does anyone have an idea about that?

Me too, want to be purple.

You got it mate Congratulations !!!

predictor say's you will get 119. Maybe after removing cheaters you can:)

Thanks, 122 is what I need. Can you share the predictor link please ?

https://chrome.google.com/webstore/detail/carrot/gakohpplicjdhhfllilcjpfildodfnnn

Thanks mate <3 I was using CF Predictor, and it hasn't been working lately.

I got +120 happy but 2 points less happy :)

OMG i am 1599…

finally, someone who understands <3 hope we get to expert after removal of plag

Hope you can become an expert soon

Alternate account or a newbie on cf?

The Plag check's done :) Maybe we can get the +1 and +2 we need for Expert !!

Ohh yes!! It looks like it's almost there, let's wait for a good result.

1599 and 1598 :(

Brooo congo but now I am at 1599

Feel sad about it…but wish you get better performance in the next rounds

Very cool problems, thanks!

How do you lose 267 points in a single contest and still say "very cool problems"?

The beauty of the problems does not depend on my performance.

I don't understand the opposite situation when people go to comments after performing poorly and say "It's the worst contest ever". It's not the author's fault that you suck.

thank you for this contest!

No offense, but did no tester feel that this contest was very unbalanced or that there's no diversity in it? And if they did, why didn't change?

I'm sure high rated people enjoyed the problems, but everyone else got stuck and didn't enjoy as much.

I think it's the best contest i have joined in my life Back to specialist

Till now best contest for me. For the first time able to solve A,B,C under 30 mins and also the first time to solve D. Although D was easier comparatively.

Speedforces ABCD

As cyan, i hope to be blue.

How can one become a tester for a contest??

Ask authors to participate in testing.

How can i find the authors before testing?

There are few coordinators on Codeforces, their names are known. You can occasionally ask them, and they can help you contact authors of upcoming rounds.

How to calculate whether i will get a rating increase or decrease

You can use 'carrot' extension on chrome.

just add it to your browser and it will show you the expected delta and how was your performance rate in the contest when you open the standing.

thank you

This contest's problem A is the best a+b problem I've ever seen

Rating changes?

Rating changes?

What's the maximum number iterations can we run in 1 second? My 213380076 for problem D is O(n * (no of factors of n)) The maximum number of iterations run is around 2.5 * 10 ^ 8. But it takes less than 300 ms. How?

FactFor n = 997920, it runs 2.4 * 10 ^ 8 iterations. It takes only 218 ms.

I think I did something very similar but my solution is much slower. Is my precomp slow? I think it's $$$N log(N)$$$.

Your precomp is taking more time ig because sample testcase also took 1 sec, in my local machine your code took around 10 seconds, may be RAM block size is the key ig which codeforces use to increase spatial locality

Please explain, how you got the number 2.5 * 10 ^ 8?

You can run a brute force

after you get your number factored, all remaining operations are rather fast, so I think it is possible

When will the rating changes be updated?

.

Anyone, please explain

In problem C why are we taking the maximum of c[i] with 0?

What if we have 1 positive element and the rest as negative?

if there is one positive and rest all are negative then you can simply remove all the elements in front of it and back of it , without adding anything

Then we can leave only that positive element

Like

`-1 -5 6 -8 -> -5 6 -8 -> 6 -8 -> 6`

you can find the sum of all the positive number on odd indices and same should be done for even

we are then finding max of them and printing

in your case when all numbers are negetive suppose -1 -1 -2 5 -9

we know the ans should be 5

we know that the sum at odd indices is more now we will choose the number on odd indices that are negetive and remove them -> -3 5 -9 now we will remove -3 and -9

Now understood.

Thanks to all of you.

i don't know how yesterday i done 2 questions

I have an another solution for D. See Here

I am new to code forces, why did this contest not give any rating? I am still having 0.

Probably they check if anybody has cheated to remove him from the final standing. And then they will publish ratings updates.

so we will get a rating for this contest soon, right?

Yes, I hope so.

This contest's problem A is the smartest way to learn how to print a+b

Is it rated?

I can't wait to see cnnfls_csy reach 3500!

does anyone know how can we predict our rating changes? Becoz CF-Predictor doesn't seem to be working. EDIT: nvm I read the comment above.

https://cfviz.netlify.app/virtual-rating-change.html

Try this..

is this contest is unrated??

As a Romanian, I am delighted to see lots of Romanian rounds lately!

Is the round rated...... been waiting for the update since morning

Can someone help me figure out where this code gone wrong for problem C 213370130

You can apply the operation twice at the middle element: $$$[1, -1, -1, -1, 1] \rightarrow [1, -2, 1] \rightarrow [2]$$$

Hope everyone get good scores!

Is it rated?forces

ratings updated when??

I cannot afford to have this contest unrated. Please update ratings.

May I ask what is wrong in writing the question E like this? Can you explain it or give a wrong example? Thank you very much[submission:213474901]

213474901

Ratings updated, sorry for the delay.

its okay buddy, dont put too much pressure on yourself!!!

It's okay, buddy, take your time, we don't mind.

thank you for the round! problems are all fun

Come on guys you can do it 1000 likes target...

Can someone please provide a proof of why for $$$c>0$$$, sorted array works in problem F of this contest? It is pretty unintuitive to me.