Hello, Codeforces!

NJACK — the Computer Science Club of IIT Patna is excited to invite you to Codeforces Round #956 (Div. 2) and ByteRace 2024 under Celesta — the annual Techno-Management Fest of IIT Patna.

The contest will take place on Jul/07/2024 17:35 (Moscow time). This round will be rated for participants with rating lower than 2100.

Many thanks to all the people who made this round possible:

- The problems were authored and prepared by AwakeAnay, ShivanshJ, TimeWarp101, DC17, BlazingDragon, Swap-nil, Pew_Pew. and me.
- Special thanks to ScarletS for coordinating the round (and not killing me)!
- A big shoutout and thankyou to Alexdat2000 for providing the Russian translations.
- Thanks 2.0 to ScarletS for having improved the experience of other CF users over the years.
- Special mention to mayankfrost and quantau for their guidance and moral support.
- A_G, Andreasyan, maomao90, CSQ31, fishy15, eggag32, MateoCV, Evirir, bananasaur, satyam343, jat.arc2004, chromate00, hashman, Nishant_K, Ali_cs7, Patel45, Newtech66, CIXTEEN, braman, 7oSkaaa, Edward4762, LucaLucaM, waidenf, yoyo0869, priyanshu.p and ishaandas1 for testing and providing detailed feedback that improved the quality and balance of the round significantly.
- Our lord and saviour MikeMirzayanov for great systems Codeforces and Polygon.

You will have 2 hours 15 minutes to solve 7 problems.

**UPD**: Scoring Distribution: 500 — 1000 — 1250 — 1750 — 2000 — 2500 — 3000

**UPD**: Editorial

**UPD**: Congratulations to the winners!

Top 5 (Div 2):

1. _worst_

2. Shirayuki_Noa

3. cynNYCal

4. cocae

5. _furina

Top 5 (Div 1):

1. neal

2. jiangly

3. BurnedChicken

4. turmax

5. Sugar_fan

## About Celesta

Celesta is the annual Techno-Management Fest of IIT Patna. Celesta conducts a variety of events in various technical domains. Some of these are open and free for all, with exciting prizes and goodies for the winners!

You can head over to our website and check it out for yourself!

We have had the 2023 edition of ByteRace hosted on Codeforces too. Feel free to have a look: Codeforces Round 845 (Div. 2) and ByteRace 2023

Good luck!

yet.

bro is prefiring :(

Auto comment: topic has been updated by MrSavageVS (previous revision, new revision, compare).As a tester, I tested after getting to

violet:)As a tester, I was told to farm contribution here

He he big brain move

NJACK orz

As a tester, the problems are nice and you should read them all!

Give me problem A, B, C, D and I will make you my friend

When you realize that you're rickrolled by the announcement

As a tester, I can confirm that writers have brainrot

lmao

As a problemsetter, all the problems are really cool and interesting. Wish all the participants a large positive delta and a fun experience.

finally

roundSyndryVictoryAs a tester, wait I didn't tested it well I belong to IIT Patna and NJACK so I am just happy.

I am now at 1399 after this contest no one can ever imagine how much I love codeforces.

You will most likely get specialist after they remove cheaters :O

Yeah my friends are saying that too let's see

On behalf of all the missing newbies and negative testers, I can say that this round is going to be awesome!

As a participant, I can confirm that the testers are crazy!

Rick Astley is mentioned in the blog!

Will try to reach as near to CM as possible

Did I just get rickrolled?

FINALLYYYY!!!!

:(

As a tester, testing this round was tasty, although I did it in hasty.

As a tester, f*ck the cheaters!!

As a

participant, I am getting a vibe that this contest is going to begreat:)As a participant, I can confirm that MrSavageVS is indeed Savage.

Feeling excited :)

very excited for this contest.

I dare you to write down red highlighted character! -_^

Auto comment: topic has been updated by MrSavageVS (previous revision, new revision, compare).Why no author pics, Lets continue the tradition.

Ayo thats stealthy. Rick rolled us.

As a tester, the problems are nice and you should read them all!

All the events on the website are dated 2023 -_-

the contest was supposed to happen in 2023 itself , it had a very long queue

Oh, wow... Got it

NJACK orz

IndianFORCES

Rick Astley orz

Did you just rickroll us?

Nvm, got it.

Ratings for problem prediction:

A:800 B:2500 C:2600 D:2700 E:3000 F:3200 G:3500

The poster in blog is very attractive and catchy!

IITPforces

Scoring distribution: 100 5000 6000 7000 8000 9000 10000 skul

AI generated banner lmao

nice rickroll.

As a participant, what should I do?

reach pupil!

never gonna give you up...

never gonna let you down...

Never gonna run around and desert you

Good luck everyone

Thanks to all

I hope they will take cheating seriously.

Expecting great problems from IIT Patna

wtf epic games hosted a cf round and now celeste??!!11!1!

7/7/24 .. 7 problems .. thala for a reason

It took me a couple of minutes to find out how I got rickrolled.

Okay thanks :')... Ig you're the 4th person to rickroll me...

Seven questions in total? I need the score distribution to decide whether to participate in this competition

This is like the best rickroll I ever got tbh.

Excited for this!!!

excited for this contest!

As a tester, I'd say problems are crisp and interesting. All the best!!

Let me blue. I beg u

Where is the credit to Rick Astley?

Scoring distribution when?

Dear Mr Savage MrSavageVS, are you planning to update score distribution later than the contest end?

Please update the scoring distribution.

Good luck everyone !

Rick Astley lol

i hope i reach pupil

Auto comment: topic has been updated by MrSavageVS (previous revision, new revision, compare).will try to reach newbie

red letters spell rick astley gl to every1

how to participate in celesta

Hope B be segment tree+dp

my target : solve one question

Excited for this round! Let's solve some interesting problems together!

rickrolled!

Let's Gooo.. Participating in a rated contest after 9 months :)

I predict this round is going to be mathforces.

After over 7 months of inactivity, I am coming back to demote. cya in the tutorials ;D

Let's Goooo..

I am in the same boat but 1 month :D

4th problem ragdolled me for quite a while, just got a gist how to solve but no chance to finalize and code it up ;D

Cannot submit code even registered. logout/in cannot work.

working now

thank you a lot for your great effort but the problems are not beautiful. I am sorry but now I just want to not become nwebie again[standings:1983]

Lets Goo!! Let's GOOO

Did my best

I hope my solution for all Problems pass the system test

Mathforces round

I coded by hoping my approaches were correct.

someone famous proved that there are unprovable facts

True, But there were observations that made the maths part skip

After I saw the authors, I was ready for round like that. But, since I don't really care about my rating I decided to participate anyway.

I have to admit: this round has nothing to do with programming for problems A-E. Maybe only problem C is at least not about math. So, as was discussed in the recent post about "the fall of Codeforces", I am pleased and honored to give this contest my sincere dislike.

yeah. its just some useless observations. No programming required. Should rename the site to stupidpuzzleforces.

I think you are not smart enough to judge.They all are Iitian.

he is CM and was grandmaster a few years ago. most iitians are not even expert.lol. Being an iitian doesnt mean u r smart. Also no one outside india care about IITs.

Why do you feel being expert is the indication of being smart and why should all IITians should do CP. I am pretty much amazed by your comment. We IITians are engineers, we do solve the technical and real-life problems which society asks us and contributes a lot in development of technology.

I can again smell the jealousy inside you by your statement of "_No one cares about IITs outside India_" . I guess you should get some exposure to the world, kid. The value IITs have in world is remarkable, and the entrance exam JEE Advanced is meant to be one of the toughest exams in the world and people really toil hard to solve that paper.

I can understand your frustration by the comment by system_check_account, but please do think before you text.

lol, mf I am an iitian, Thats how I know most of us are not exactly smart. Spending 2 years of your life mugging up stuff and having no life doesnt make you smart. Also people like you who make their entire personality as "I am iitian" is an embarrassment to all of us. The only people who are jealous of us are a few nerds who couldnt clear jee.No one else gives a shit.

sir i need ur advice i m passing to second year bachelor computer science

and for now all i know in dev

some html css and a little js

should i focus more on dev or keep grinding cp

or should i quit codeforces and start practing on leetcode

Do both

Ohh please shut-up, i abhor comments like these. CP encompasses alot of things which includes Maths and If a contest happens to comprise of only one of those things i don't think that should be a problem, you didn't come here to write best selling novels.

its not even math. its just pattern recognition and guessing. thats it. lol. such terrible questions.

why does D exist?

NGL reminded me of that Veritasium video of 100 prisoners Riddle

How to do B ?

how is that related to problem D?

How to do B?

Sum in every rows and columns must be equal modulo 3

summation for all row and col in grid A and Grid B mod 3 if equal then yes

else No

But why ?

Because each conversion does not change the sum in the row and column modulo 3

This only proves one direction; it doesn't prove that every matrix $$$b$$$ can be reached from $$$a$$$ if the sum in each row and column are equal $$$\mod 3$$$ though!

I just believed it worked)

Can you please explain the approach ?

Yeah that's the only hard part to proving the solution. Figuring out that the parities of sums and columns mod 3 can't change is pretty obvious.

I have no idea how to prove that every matrix that meets the above conditions can be reached, but I think it's a similar question to determining whether or not a rubik's cube with a certain arrangement of colors can be solved.

https://puzzling.stackexchange.com/questions/53846/how-to-determine-whether-a-rubiks-cube-is-solvable

It's very easy to prove that every matrix b can reached from a if the sum in each row and column are equal mod 3.

Always take a subrectangle that uses the very bottom right of the array as a bottom right corner. Use it to modify the first element of the first row as you wish. You don't care what happens on the first element of the last row and the last element of the first row. Then do the same of the second element, again you don't care about the last row and the last column. At the end you set up everyone correctly except the last row and the last column. However since the sum of row 1 is the same in a and in b and is an invariant, the last element of row 1 is necessarily set up correctly. Same for all the elements of the last column and the last row.

Thank you, very nice proof. I think we have different definitions of "very easy" though.

I meant very easy to understand once you read it, sorry

Nice proof, thanks!

Usually it's other people helping me, feels good to be on that side for once haha

Then shouldn't it be the diffrence between each position of the two grid creates what matrix,thats row and column?

if u take a subrectangle and perform operations multiple number of times in any order than either u will get same subrectangle or the one diagonal will increase by one and other by 2 or one will increase by 2 and other by one and this can be proved very easily.... hopefully this much is sufficient to get the answer

Then diffrence of two grid should be checked ,isn't it ?

no than we just compare elements of both and try to make them equal . only some values can be made fully equal rest values should be such that they should become equal ... lol i am very poor at explaining things but i'll try my best sorry

Something related to invariants.

What things don't change when you apply operation once?

Problems B and D were totally not cool, I just had to guess both of them and I'm not sure which one I dislike more.

Problem C was kind of obvious but felt like: "Do I really have to implement this?"

Problem A: ???, but I guess even an output of 1 2 ... n-1 n works

i just wrote the same thing on a previous comment lol

Literally me. Nice thing I trusted in my guessing skills

like i am just curious, you are rated very high, do you guys still face some problems while solving B and D? (I just want to know, this is not to mock in any sense cuz i cant i am rated 1200 lol)

yes! it took me 20 minutes in B

damn

I bricked and took 1hr+ for B lol

It took me 2 hours for B and 15 minutes for D.

I pretty much had the idea since the moment I read the problem, but you have to kinda proof your solution before, and that's what takes time. I got the idea probably because I have been solving a lot of problems, so, you will just get better by practicing

yeah, gotta practice maths problems i guess :)

I found the source of B.

I could prove all of them. I think they were fine problems. Except C, I agree it was somewhat obvious but annoying to implement.

B: Just do the greedy thing where you update a[i][j] to be equal to b[i][j], and update corners (i,j+1),(i+1,j),(i+1,j+1). Then notice this doesn't alter row or column sums mod 3. At the end you'll have fixed all the positions for 1 <= i < n, 1<=j <m. And if you haven't fixed the rest, you have to have that the columsn/row has different column sum

D: First notice its not possible if they are not the same as multisets. Then notice if they are the same as multisets, but have repeated elements, it is always possible, because you can rearrange one freely and just swap the same elements in the other. If they have the same elements, with no repeats, you can do coordcompression and turn them into permutations. Then its possible iff they have the same number of cycles mod 2, because swapping two elements in an array either increases or decreases number of cycles in each array by 1, and thus maintains their difference mod 2. So if they have the same number of cycles you can sort both of them, and if they don't you'll never get them to have the same number of cycles, so they'll always be different.

I also thought E was a very nice problem.

D does not have to be that complicated... all we need to do is check the parity of inversion index of both the arrays and that the arrays are equal after sorting

Man, looking at the comments make me realise how dumb I am. But one question,how do I learn all of these things. I mean parity, inversions and all these fancy terms?? Is there a good learning site or should I just practice questions and upsolve??

I think you should just solve problems. I had solved this problem a while ago https://codeforces.com/contest/1768/problem/D that uses this technique. I think without that maybe I would not have been able to solve it.

Very thank you for replying... I'll stick to solving.

Half of these are just fancy terms and not some high-level stuff. Parity just means whether something is odd or even. Similarly, you can search for what the inversion count of an array means. It is not that complicated.

Yeah,I looked at the editorial for D and slowly it all started to make sense,I stopped at the "Inversion count in efficient time" but now I'll go straight to learn it

for D I also had a different approach, where I just iterated over the arrays and greedily matched B[i] to A[i]. I kept an array pos that stores the positions of the values in array B, so I could look up the index of the value A[i] in B in constant time and swapped B[i] with whatever element is at pos[A[i]], then swapped arbitrary elements in A in the range [i+1, n) to make the swap operation in B possible. From this you get the invariant that A[j] == B[j] for all j < i. This always works up to n-2, because there is always at least one auxiliary element that can be swapped. After going through 0 to n-2, I check if the last two elements are in correct positions, because if they aren't, there is no way to make them equal, as swapping any element but the last two will break the order of another index.

I've been thinking about this for a while and I still can't figure out why it actually works, mostly why swapping arbitrary values in A seems to have no impact on the result of the last two elements: 269285999

I'm trying to derive a way to determine parity of permutation just from cycles, but some things you said need more address. The fact you said "swapping two elements in an array either increases or decreases the number of cycles in each array by 1". That's true for a permutation (crisscross apple sauce, cycle here, cycle there, yea, it changes by 1), but making cordcompression doesn't make an array a permutation, we just have all a[i] < n. So if after swap my parity didn't change, what does it tell me about an array?

The main problem for me is: permutation swap causes a change in parity of inversions and also changes the parity of the number of cycles. Therefore those invariants are intertwined (seems like n + cnt_cycles(p) mod 2 = inversions(p) mod 2). But I didn't try to derive exactly how they are related, because I don't understand how to get the number of inversions just by looking at a cycle decomposition.

So I have proven fact for permutations, but this logic crumbles for an arbitrary array since swaps now can change or not change the parity of an array. But if it does not change the parity, does the number of cycles stay the same? And also goes the other direction: if the number of cycles stayed the same, did the parity change? I already did consider some cases (like if we picked two elements to swap and positions are both on a cycle, only one on a cycle, none on a cycle, etc.), but I don't understand how to get the parity of inversions in those cases. Any help appreciated

tldr. I deduced that for permutation p the following holds: n + cnt_cycles(p) mod 2 = inversions(p) mod 2. But does that hold true for an arbitrary array where a[i] < n?

I explained how to deal with the non-permutation cases. In those cases, you either have different multisets, in which case you can't solve it, or repeated elements, in which case you always can.

In D, it was given that both arrays contain only distinct integers, which makes it a little easier.

Totally!! Such a poorly written contest, zero quality questions.

nice guessForces :)

GuessForces

Stuck at E again.

how to be that strong

A to D is leetcode medium, E is pain.

https://codeforces.com/blog/entry/97849

D is a ripoff of this

Nice, someone already proved my D guess lmao

Very nice problem E! I really liked how the permutations of the balls can be rephrased as weak compositions which makes the probabilities almost trivial.

Can you please elaborate on how you got to weak compositions?

My issue with the task that I cannot grasp how to calculate how many special balls does alice take on average. I understand that every time Alice passes the turn to Bob and vice versa the amount of regular balls is decreased by 1.

So if there are 3 regular balls we have 4 moments when one of the players can take special balls

And when I compare case 1 and 3 for example, I see that Alice has a bigger chance to take a special ball, because there are less balls in total.

So let's label the special balls as

`*`

and the regular ones by`|`

. Now every permutation of the balls looks something like this:where A means that Alice takes it and B means that Bob takes it. Now we can view this as representing multiple "bins", separated by

`|`

, and containing the`*`

(this is a classic proof in combinatorics, see (https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)) on wikipedia) (this is also the weak compositions of`k`

with`n-k+1`

terms). Thus we have`n-k`

regular balls, separating`n-k+1`

bins. Now it is quite easy to see that any such configuration of`*`

and`|`

is equally likely, so any special ball is equally likely to end up in any of the`n-k+1`

bins. Note that the odd-indexed bins correspond to the ones containing balls taken by Alice, and the even ones by Bob. And we can easily compute the probability that a random bin is odd-indexed (`1/2`

if`n-k+1`

is even,`ceil(1/2*(n-k+1))`

otherwise), which is the same as the probability that some special ball is taken by Alice.Please let me know if anything is unclear.

wow B is really cool

Yeah guessForces. I couldn't guess B but guessed D lmao.

Is there some edge case in C? My code was failing on pretest 7

Nvm, it was a typo resulting in out of bounds error

oh boy, I sure hope my python hashmap solution for D doesn't FST

OMG I new F but no time

Answer for $$$E$$$ is (sum of special values)*$$$\left(\frac{\lceil \frac{n-k+1}{2} \rceil}{n-k+1} \right)$$$ + (sum of non-special values)*$$$\left(\frac{\lceil \frac{n-k}{2} \rceil}{n-k} \right)$$$

Could you explain how you get the (sum of special values) * $$$\left(\frac{\lceil \frac{n-k+1}{2}\rceil}{n-k+1}\right)$$$ part?

The sequence of non-special balls picked alternate between Alice and Bob (for a total of n-k moves). We can insert the special balls in any gaps (n-k+1 in total). Half (the ceiling expression to be precise) of them precede Alice's choice of a non-special ball, which is precisely the special balls chosen by Alice. All the gaps are equally likely for a special ball to be placed.

Thanks!

I had this idea during the contest, but I could not figure out the probability distribution of the positions the special balls are placed in. How would you justify that all of the gaps are equally likely for a special ball to be placed?

I don't know if its useful, but, imagine every turn is a box, like this: Alice's turn | Bob's turn | Alice's turn | ...

Any distribution of the special balls on the boxes corresponds to a posible game, every game is diferent, and should have the same probability out of a random game (ignoring the normal balls). So given a game, what's the probability of the i-th special ball falling onto first box? Well, it could have fall into any of the n — k + 1 boxes, and there is no any other restriction, so every box has the same probability which is 1 / n — k + 1. The you count Alice's number of turns, and Bob's number of turns and you got it.

Let me know if there's something still missing.

I see. But I don't think this

is a trivial statement. For example, for the first box, the probability of ball $$$j$$$ (or any ball) falling into it is

For the second box, this number would be a lot more complicated. I really don't see how you would mathematically show that all of these are 1 / (n-k+1). Maybe I'm just overthinking it.

I don't really understand your formula. I think you are omitting, or maybe it's what you're asking, the fact that the probability of the distribution of a special ball is NOT affected by the distribution of other special balls or the distribution of the non-special balls. As it is nos affected, you can ignore the other special balls, and calculate the probability of choosing a random gap between n — k + 1 gaps.

It's hard to explain why the special balls don't affect each other rather than asking why would them affect each other? Mathematically, generating the formula having all in mind, simulating the process, we may not see how we end up with the probability being just equal, but it is because we are ignoring that other balls don't matter

You can find this in another way as well.

first of all you have to understand that

expected number of points = expected number of special values * average of special values + expected number of normal values * average of normal values

Now how to find the expected number of special values and the expected number of normal values?

I basically used a $$$2 \cdot N^2$$$ DP to generate the formula.

The Dp problem was if it is

my turnand there are $$$x$$$ special values and $$$y$$$ normal values, what is the expected number of special values and normal values I will get?You can easily solve this in $$$2 \cdot N^2$$$ .

Note that you don't need to use large N :)

spoilerI don't know why people are calling this contest GuessForces, A, C and D were easily provable. However, I guessed B, does anyone have a proof of the solution?

If D is easily provable during the contest then it's time for me to lay off the competitive programming

For D I "simulate" the process of swapping. I could use the operation of length $$$2$$$ on array $$$b$$$, and I will try to make $$$b$$$ equal to initial $$$a$$$ after those operations. If the number of operation I used is even, then the answer is NO, and YES otherwise. This is because when we used the operation on array $$$b$$$, we can used it in $$$2$$$ adjacent elements of array $$$a$$$. Then the array $$$a$$$ will be unchanged after even number of operations.

For example if $$$a$$$ is [1, 2, 3, 4, 5] and $$$b$$$ is [1, 4, 2, 5, 3] then $$$b$$$ will be like this after the operations: [1, 4, 2, 5, 3] -> [1, 2, 4, 5, 3] -> [1, 2, 4, 3, 5] -> [1, 2, 3, 4, 5]. Meanwhile, $$$a$$$ will be: [1, 2, 3, 4, 5] -> [2, 1, 3, 4, 5] -> [1, 2, 3, 4, 5] -> [2, 1, 3, 4, 5] (we keep swapping the first and the second element of $$$a$$$). As we can see, the number of operation is odd, so the answer is NO.

This is a solid solution, however I applied the following:

`1 2 3`

and b =`3 1 2`

on paper by handNever stop guessing

To clarify, I don't think that this method of solving problems is good, but it is what it is when it comes to codeforces nowadays

I have the same approach in mind , but I am having trouble implementing it, can you please shed some light on the implementation.

For now what I think is, I will store all occurrences of every number in a vector of vector , or set<int, vector> , then I will just calculate the number of positions required to shift a number at index 'i' in array B to its concerned position in array A, however , when I am shifting an element to its left side, then all the elements to its left will be shifted to the right by 1 index. I am having trouble in optimizing this to O(nlogn) or O(n). Any help will be appreciated.

EDIT: Counting the number of inversions for both the given permutation worked!!

Okay so assume we move elements of $$$b$$$ to match $$$a$$$ from left to right. Supposed we want to move a $$$b_j$$$ to the position $$$i$$$ on the left. Then the operations count will be added by $$$j-i-1$$$. After that, we need to shift all the elements in range [i, j — 1] to the right. It just like adding $$$1$$$ to the value of the position in range [i, j — 1], which can be done by segment tree or fenwick tree (DM me if you have hard time understanding it).

Got it, Thanks !

If we try to sort both 'a' and 'b' using adjacent swaps and check parity of no. of operations to sort 'a' and 'b', if their parities are the same, the answer is "YES" otherwise "NO". Will this also work?

UPDATEIt did work!The main point I used in proving $$$D$$$ is that every swap between elements at positions $$$i$$$ and $$$j$$$ ($$$i<j$$$), can be achieved using $$$2\cdot (j-i)-1$$$ adjacent-element swaps, i.e., by moving the $$$i^{th}$$$ element all the way right to $$$j$$$, then moving the $$$j^{th}$$$ element (which is now at $$$j-1$$$) all the way left to $$$i$$$.

With some well known facts it is. Proving that two permutations must have same parity is trivial when you know that making swap always changes the parity. To prove that it is sufficient you can use the fact that every permutation can be decomposed into some swaps of adjacent elements, and the parity of the permutation is equal to the parity of the number of those swaps. So, if the parity is the same, you can decompose both permutations and eliminate those swaps one-by-one.

But of course, you need to know something

The main point I used in proving $$$B$$$ is that that any sub-rectangle can be achieved by using sub-rectangles of size $$$2\times 2$$$., i.e., applying the $$$2\times 2$$$ sub-rectangles from right to left for every row from top to bottom will achieve the same effect of using the large sub-rectangle at once.

how do you prove D ?

It is easy to see that the sums modulo 3 of each row and column are preserved. We can use the following simple algorithm to convert matrix $$$A$$$ into $$$B$$$ if they have the same row and column sums:

It is clear that the first $$$(j-1)$$$ elements of each row become correct. But since the sum of each row is preserved, and we assumed that $$$A$$$ and $$$B$$$ had the same row sums, therefore, the last value will be correct as well. By similar reasoning, the last row will also be correct after the first $$$(i-1)$$$ rows have been fixed.

Assume sum of every row/column of A equals to B modulo 3. This is a necessary condition since operation doesn't doesn't change sum of rows/cols modulo 3 (1 + 2 = 0 mod 3, nicely explained lol). Then start greedy algorithm using 2x2 rectangle. If a[i][j] != b[i][j] then apply 2x2 putting a[i][j] element in the left corner of operation until we are equal. We will get a (n — 1) * (m — 1) correct submatrix in the upper left corner (by correct I mean a[i][j] == b[i][j] for all 1 <= i <= n — 1 and 1 <= j <= m — 1) . But the remaining elements (last column and last row) would be also correct since we sum of rows/columns of A and B are equal. Therefore it is enough to just check equality of rows and columns modulo 3 since greedy will always make them equal

How to solve A ?

just print 1 to n

How developers comment their code:

problem B don't seem to be the guessing type but it seems that any hard matrices problem in this rating should be guessing and that's actually what I have learnt today, next time if I see a hard matrices problem in B then it's definitely guessing thanks for the author I really learnt something new today!

it's not guessing. You can use 2x2 matrices as building block for any matrix. Also twice a matrix in form [[1, 2],[2, 1]] gives you the other type of matrix

what about [[1, 1],[1, 1]] and [[2, 2],[2, 2]] ?

you can't make those matrices by themselves, you need to change other entries. You can make a 3x3 matrix of ones, but not a 2x2 one

There are only two types: guessing and remembering

How to solve C?

just brute force all the 6 possibilities, using a prefix sum array

without psa will also work

well, true that

How come, the solution to 2nd pretest solution NOT be — Alice:[3,4], Bob:[5,6],Charlie:[1,2]? My code was failing with 2nd pretest, for this mismatch. I believe, above blocked answers can be rearranged too! 2nd Pretest:

6 1 2 3 4 5 6 5 6 1 2 3 4 3 4 5 6 1 2

CringeForces

A: Obviously a[i]=i satisfies the condition.

B: Let c[i][j]=a[i][j]-b[i][j] and we need to make c[i][j]==0. Let row[i] be the sum of i-th row, col[j] be the sum of j-th column. Notice that every operations don't change row[i] and col[j], so they must be 0 initially. In fact, if row[i]==0 and col[j]==0 initially, we can make c[i][j]==0 by operations on 2x2 subrectangles.

C: There are 6 possible relative orders of l_a, l_b and l_c, we can find the answer by brute force for all possible orders.

D: Each operation will change the parity of inversion number of a[i] and b[i], so they must be the same initially. If they are same initially, we can sort a[i] first, and b[i] will be an array with even inversion number, and we can sort b[i] by swapping adjacent elements, while swapping a[1] and a[2] repeatedly.

E: Let S1 be the sum of special balls, S2 be the sum of normal balls. If we let p1 = the probability Alice can get i-th ball when i<=k, p2 = the probability Alice can get i-th ball when i>k, then ans=S1*p1+S2*p2. For n-k normal balls, Alice and Bob will take a normal ball alternately, so p2=(ceil((n-k)/2)/(n-k)). For the i-th special ball, Alice can take it if there are even normal balls be taken before it. The number of normal balls taken before a certain special ball can be any integer in [0, n-k] with equal probability, and p1 is the portion of even numbers in this range, which is (ceil((n-k+1)/2)/(n-k+1)).

F: Let's find the answer by binary search: For certain number A we need to calculate number of pairs (i, j) where i<j and a[i, j]<A. Let f(i) be the minimum j where i<j and a[i]^a[j]<A (if not exist f(i)=n+1), then the number of valid pairs will be sum(1<=i<n)(n+1-min(i<j<=n)(f(j))). We can calculate f(i) with binary trie: Let r be the highest bit where (a[i]^a[j]) is 0 and A is 1, then valid values of a[j] will be corresponding to a node of the trie.

what do you mean by this because it's not clear -> Notice that every operations don't change row[i] and col[j]

The change of values in one operation will be like this:

0 0 0 ... 0 0 0

...

0 1 0 ... 0 2 0

...

0 2 0 ... 0 1 0

...

0 0 0 ... 0 0 0

Where the sum of each column and row is 0 or 3, which is 0 modulo 3.

For D how do you calculate inversion number

Any data structure with point update and range sum query (Fenwick Tree for example).

You can do it with merge sort too https://www.geeksforgeeks.org/inversion-count-in-array-using-merge-sort/

Actually computing the parity of inversions is easier. Since even-length cycles can be decomposed into odd number of swaps (for instance $$$(a\;b\;c\;d)$$$ is the same as $$$(a\;b) (b\; c) (c\;d)$$$), and (for the same reason) odd-length cycles can be decomposed into even number of swaps, you only need to calculate number of even cycles.

When I first read your explanation of E, I thought you were wrong at something. Then I returned to the problem and saw a very important thing:

While I'm thinking about those k indices could be random.

I did the same. Struggled to simplify the 2D recurence

Would it be true to say that for problem D if there weren't the additional constraint that all elements were distinct, then we could always transform a in b if there is an element that appears twice? (since we can do dummy-bubble-sort-like-operations on two identical elements once one is sorted and the other isn't (and actually do bubble sort on the other one)).

Yes, assuming that a and b contain the same elements

my solution for D was as follows:

let's say that we want to fix a and convert b to it

we can every time do two swaps on b without affecting a, by choosing the same two indices in a in both of those two swaps(for example, we can simply choose 1 and 2 in a every time we do a swap)

now start from the beginning or the end of the array b and convert it to a by doing swaps

if the number of required swaps is even, then answer is yes. otherwise, answer is no

Can't I use lazy segment tree, to find the minimum of a range and update xor in range

G: use HLD, then it turns into solving queries with parameters l, r, c of sum a[i + x] xor (x + c) for l <= i <= r.

If you're able to solve queries with c = 0 and r — l + 1 = 2^p for some p, then you can break the query down into queries of power of 2 by doing:

We can solve a query of r — l + 1 = 2^p when 2^p is smaller or equal to the smallest bit in c or c is 0 by solving it for that range with c = 0 then fixing the bits higher than 2^p. So do that to carry over the bits as much as possible (do query of smallest set bit length while it would be a subarray). After that, we can do binary lifting.

Could you explain the intuition behind this? I can't prove it.

Assume the order of balls are randomly shuffled before game starts, and each turn players take the first remaining ball. Then for a certain special ball, let's ignore all other special balls, we need to shuffle it with n-k normal balls randomly, it can be arranged from 1-st position to (n-k+1)-th position with equal probability, which means, the number of normal balls before it, is uniform distribution on [0, n-k].

HLD isn't needed for G, solve for each bit separately. Consider the $$$k$$$-th bit, for a path $$$v_0$$$->$$$v_1$$$->$$$\ldots$$$->$$$v_n$$$. the numbers in $$$[0,2^k-1]$$$ will have the $$$k$$$-th bit off, $$$[2^k,2^{k+1}-1]$$$ will have the $$$k$$$-th bit on so on and so forth alternating in blocks of length $$$2^k$$$.

So this leads to the idea of splitting the path into blocks of size $$$2^{k}$$$. Then $$$a(v_i) \oplus i$$$ will have the $$$k$$$-th bit on if $$$i$$$ belongs to a even block and $$$v_i$$$ has the $$$i$$$-th bit on ($$$i$$$ mod $$$2^{k+1}$$$ $$$< 2^k$$$ and $$$v_i$$$ mod $$$2^{k+1}$$$ $$$\geq 2^k$$$) or vice versa. To count how many xor in the path has the $$$k$$$-th bit on, you can precompute $$$f(k,u)$$$ = how many $$$i \oplus v_i$$$ have $$$k$$$-th bit on if $$$v_0,v_1,v_2\ldots,1$$$ is the path from $$$u$$$ to root.

I am omitting some details, but $$$f(k,u)$$$ is enough to compute everything with some additional path queries. Eg for a path $$$a$$$ to $$$b$$$ where $$$b$$$ is an ancestor of $$$a$$$, let $$$p(i,v)$$$ be the $$$i$$$-th ancestor of $$$v$$$. To compute the number of xors on the path with the $$$k$$$-th bit on, first take $$$f(k,a) - f(k,p(c2^{k+1},a))$$$ where $$$c$$$ is the biggest integer such that $$$p(c2^{k+1},a)$$$ is still below $$$b$$$, we are left with the path $$$p(c2^{k+1},a)$$$ to $$$b$$$ that is still unaccounted for but it can be counted in by at most 2 path queries of the form: How many $$$a_{v_i}$$$ in a path $$$v_0,v_1,\ldots,v_n$$$ has the $$$k$$$-th bit on?

edit: The sol is $$$n \log n$$$ but very unpleasant to implement, during testing I passed with a simpler and nicer $$$O(n\sqrt{max_{a_i}})$$$ but authors decided to block that :(.

I hate Cloudflare, my submission in the last 10 seconds for C doesn't considered because of it

couldn't solve B, still have 0 clue whatsoever.

completely loss hope in CP.

like is there any chance to improve? even slightly

solve 600+ problems in cf still fail, it must be IQ issue.

check my solution:

I smell ChatGPT

nah bro, i just tried to make every element of the difference array equal to 0 by applying the optimal operation on a 2X2 subrectangle.

This problem ate so much time, i have code C written but was unable to submit it as contest went over.

https://archive.org/details/isbn_9780806944562/

hhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhhh

i am with you

How are there more than 3k submission for D

Cheaters.

Exactly

I found this (FYI after the contest), which had a link to this. The cheating is insane.

That's craziness. On leetcode, the cheating has gotten so bad recently that 2k+ people solve Q4s that are worth 7 — 8 points. Just a few months ago, <500 people would solve such problems.

I also think it's because of cheaters. When authors give round where problem D require no implementation, it's a green light for cheaters.

I got D... But I couldn't figure out B haha... I think I just couldn't understand how to get B... My implementation of D is quite obscure because I just count the parity with merge sort... But I didn't know what else to do... I'm sure other people implemented better solutions than mine. (And I tried afterward to use the same thinking with parity with B... But it's so complicated with the diagonals so I didn't have time...

todays B>>>

problem B, is not Trivial at all.

Problem C was much easier then B, don't know why they thought about putting B in the contest.

We notice that after an operation, the sum of a row doesn't change modulo 3 because one element is incremented by 1 and one element is decremented by 1. However, I do agree that this shouldn't be in the contest, because it seems more like a Math Olympiad problem rather than an actual coding problem.

Exactly!

Problem B — stupid greedy algorithm

how?

Just apply the operation to each 2x2 matrix so that the upper left corner coincides with the cell being processed, process all the cells except the last column and the last row, if after checking the operations the matrices are equal, then the answer is yes, otherwise no

how is this considered greedy and not guessing ? I mean the 2x2 thing

This problem ate so much time, i wrote C but was not able to submit on time.

:(

i had to ask for screenshot of Problem A in errichto server due to cloudfare stuck in a loop. M1 and M3 weren't showing latex and M2 didn't work.

Man, if only I hadn't wasted 1hr on that goofy ahh problem B I could've gotten more points for C and D :')

i ended up solving E where any k balls are special instead of the first k balls ;_; (SERIOUSLY THEY COULD HAVE JUST ADDED THE WORD FIRST RIGHT ON TOP)1.

The statement doesn't mention that the first k balls should be special. What do you mean?

Edit: Just saw it. Problem setters should apologize us for giving those crucial detail just in a very small corner of input LOL.

under Input section it's given in a very small corner ._.

OMG I just saw it. What the hell man. It is catastrophic as I thought about random position of k balls @@.

ikr

they have mentioned that in the "input" section alongside constraints

oh my god dude same i just saw it after seeing your comment :/

Can you elaborate your solution ?

Some people (me included) think that the problem description section should define things like that. Others think the statement includes the other sections as input, output, sample and extra comments.

Next time try to read everything.

I agree but you better read everything next time

Solved A,B and B in 7 minutes.

I solved A, A, A and A in 3 minutes.

i solved nothing, nothing, and nothing!

Problem setters need a lesson on the difference between "guesses" and "observations."

What's the difference?

Guesses are made randomly without thinking, and observations are made with thinking and logic?

why it wasn`t stated int the statement of E that the first k elements are special and it was only stated in the input section?

I coded for any k elements and debugged it and calculated the samples manually and read the statement multiple times but at the end of the contest I read the inputs and figured out the first k elements are special.

it should have been stated in the statemen!

Wow, I remember thinking the problem would be much easier if the first k were special. I didn't see that part and gave up because I couldn't solve it.

I might not be getting something, but if the special elements are chosen at random, the problem almost doesn't change. You just have to calculate the expected value of a sum of $$$k$$$ random elements instead of the sum of the first $$$k$$$.

the problem changed A LOT for me (i did eventually solved it both ways and my solutions for both are VERY different)

Whats your solution?

you can check my submission for the implementation (it's really bad but who cares)

but basically my idea is you have k special balls and n-k normal balls

across all n! cases, you will pick up all special balls the same amt of times and all normal balls the same amount of times (but doesnt have to be the same as the special balls)

so the solution must be some R = (special sum * special factor) + (normal sum * normal factor)

let's call a cluster some amount of special balls followed by a normal ball

any case could be reduced to

[cluster 1] [cluster 2] [cluster 3] ... [cluster n-k] [special cluster (consisting of only specials)]

you will pick up the balls in any odd clusters

-> ceil(n-k)/2 normal balls will be picked up per case

-> each normal ball will be picked up (n!*ceil(n-k)/2)/(n-k) times

for special balls, solve for each u -> number of special balls in odd clusters

the number of ways will be (oddPos+u-1)C(u-1) * (evenPos+(k-u)-1)C(k-u-1) {stars and bars} * k! {k shuffle} * normalBalls! {normal ball shuffle}

each case will give u special balls, distributed between k balls so the final formula is $$$\binom{oddPos+u-1}{u-1} * \binom{evenPos+(k-u)-1}{k-u-1} * k! * normalBalls! * \frac{u}{k}$$$

solve for each u from 0 to k and you should be able to calculate the special factor (tho edge case if there arent any normal balls then the output is just [sum, 0])

the expected value for bob is just S — [alice's expected value]

\\\\\\\\\\

my solution for the

wrongversion does involve a lot of combinatorics spamexpected values for each where alice recieves sA effective special balls (special balls that arent the last) and bob receives sB ESB

let A,B be the balls alice and bob picked up respectively (this is easy enough to calculate)

let S be the sum of balls

let v = $$$\binom{A-1}{sA} * \binom{B-1}{sB}$$$

(v is the number of combinations of special balls)

alice: $$$\frac{v*((n-1)!*S*A)}{n! * \binom{n}{k}}$$$

bob: $$$\frac{v*((n-1)!*S*B)}{n! * \binom{n}{k}}$$$

(no proof since it's absurdly long)

You are right my solution for these two versions wasn't different that much but the fact that I read the statement multiple times and checking the samples manually is very frustrating. and there is no reason that it wasn't stated in the statement when most of people just ignore the input section because it is just about the input of the problem not the statement of it.

C is obvious right from the start, just painful to implement. While B is definitely not obvious at all.

If the reason that B is placed before C is because it has shorter code to write then it's kind of a lame reason tbh...Obviously problem C is an easier problem, and is more solvable.

Won in this speedforces :)

Time to back to CM!

For Problem D:

That's it done..................

Problem B is a weak form of 2015 USAMO Problem 4. FYI for those people asking for proofs.

Completely lost solving B. Feeling low. Still donno why my sol works

Proof of D (with some group theory):

First, we need $$$a$$$ and $$$b$$$ to have the same elements (with multiplicity).

Once we have that, each action we perform is just a transposition (i.e. a permutation of the form $$$(i,j)$$$) of the elements of $$$a$$$ and $$$b$$$. We know that

Fact.Transpositions generate the full symmetric group $$$S_n$$$.So we can get $$$a$$$ to $$$b$$$ with transpositions if we didn't modify $$$b$$$ at all.

Lemma.We can get any transposition as the composition of transpositions that swap adjacent elements.Proof.Let $$$(i,j)$$$, $$$i<j$$$ be a transposition. ThenNow there are two cases.

Case 1.If $$$a$$$ and $$$b$$$ have two identical elements, we can get from $$$a$$$ to $$$b$$$.Proof.First, perform a transposition so that the two same elements are next to each other in $$$b$$$ (it doesn't matter what the corresponding action in $$$a$$$ is). Then perform some permutation to turn $$$a$$$ into $$$b$$$. Since we can decompose it as permutations that swap adjacent elements, let the corresponding action on $$$b$$$ be swapping the two identical elements. $$$\blacksquare$$$(otherwise the group $$$S_n$$$ acts faithfully on $$$a$$$ and $$$b$$$ by permuting the elements since the elements are distinct, so we may just view $$$a$$$ and $$$b$$$ as permutations)

Case 2.Otherwise, $$$a$$$ can be turned to $$$b$$$ if and only if the parity of the pemutation of $$$a$$$ is the parity of the permutation of $$$b$$$.Proof.If $$$a$$$ and $$$b$$$ have the same parity, perform the permutation on $$$a$$$ to turn $$$a$$$ to $$$b$$$ (this has even parity). The corresponding action on $$$b$$$ can just be swapping $$$2$$$ adjacent elements, which after doing an even number of times leaves $$$b$$$ unchanged.If $$$a$$$ and $$$b$$$ have different parity, then each action is a transposition, changing both of their parities to not match again. So they will never be the same. $$$\blacksquare$$$

Such a cringe TL for problem F (as far as I can see a very big proportion of the Ac submissions use more than half of it). I wonder what ratio between TL and worst source from testing they decided to use...

does amazon pay well ?

Terrible contest.

peak guessforces

Well well, todays contest clarified why some newbies might reach expert and eventually fall on their faces to newbie again

pls fix the cheating issue, do whatever is required, linking with mobile number, banning codeforces ids of people who do this, pls do something, but stop these cheaters on this platform atleast, just spoils the whole contest,MikeMirzayanov

IIT PATNA students ruin this contest agree -> upvote disagree ->downvote

TOday was my worst round of CF so far...........got stuck on B and couldn't take chances on C..... Need more practice ig......

1983B - Corner Twist is almost coincide with 1119C - Ramesses and Corner Inversion and required same technique to solve MrSavageVS!

what technique is needed? isnt it just brute force and check

Just apply the operation on 2 x 2 submatrix! (It would better if you have a look at the solution of 1119C - Ramesses and Corner Inversion)

Damn I figured out how to solve E but I didn't have a mod_frac template QvQ

Cringeforces + Guessforces, did not enjoy this round at all (or maybe im just mad at the -150 delta t_t)

There were a lot of cheaters :(

https://www.youtube.com/watch?v=vo8LeUJjh6c

Leaked a bunch of solutions... I don't think you're delta will be as bad as you are thinking, but yeah this round was tough...

EDITGoogle drive link is in youtube description posting here just in case it get's removed:

https://drive.google.com/drive/u/0/folders/1J8B0EgsoBuDZQD0HSCXpmBTnM-pOuwO9

is there any extension to know your delta before the official results come out??

You can use the CF-Predictor

i have tried it and it does not work

Then use Carrot