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 SyndryVictory round
As 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 be great :)
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.
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.
Deleted
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://mirror.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://mirror.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 ofkwithn-k+1terms). Thus we haven-kregular balls, separatingn-k+1bins. 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 then-k+1bins. 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/2ifn-k+1is 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 turn and 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 :)
I 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 3and b =3 1 2on 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? UPDATE It 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.
.
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 wrong version does involve a lot of combinatorics spam
expected 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. Then
Now 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...
EDIT
Google 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
Use Carrot
Can anyone tell me which edge case I am missing for question c 269290282
Problem D is very similar to this problem, my approach is: if the number of inversions of a has the same parity as the number of inversions of b, and they both have the same elements (sort(a) == sort(b)), then the answer is yes
Can u prove ur fact ?
Kind of proof: (very unclear, sorry) Only do flips of length 1 for convenience since it doesn't change the answer. Fact: all operations are reversable, so you can't do an operation that changes the answer since you can just reverse it. That means, if with some operations we bring the arrays to an obviously impossible place, we know the answer is NO. Let inva and invb be the necessary nb of inversions to sort a and b respectively, then you can start sorting both. Assume you will finish sorting a first (if not just change the variables in the proof). Then b will need invb-inva more operations to finish sorting. If invb-inva is even, you can keep sorting b while flipping the same two elements in a to keep it sorted, if it's odd then a will no longer be sorted by the time b is sorted and it's impossible
Instead of considering the fact blindfolded that you can swap 2 elements present at the same distance, let us approach it in this way.
r−l=q−p
just see the small observation that it means in a way you can swap adjacent elements. (distance = 1)
It means that essentially you can swap any two elements in both the arrays. (quite intuitive, if not then try doing a dry run on pen and paper. Also can refer to the swapping in Bubble sort.)
So let us think to bring both the arrays at a particular centralised state. Now this centralised state could be anything. For better understanding, let us take it as sorted.
Now let's say you are taking X adjacent swaps to sort the first array and Y adjacent swaps to sort the second array.
X+Y should always be an even number for the final answer to be YES.
For example, X=6 and Y=4
Now let's assume we have completed 4 moves till now.
Array 1: Unsorted(Still 2 moves left) Array 2: Sorted
But 2 moves are left which are nothing but adjacent swaps. And we know if we perform a swap in array1, we need to do it in array2 also.
So this remaining number of moves now should always be even for the final answer to be YES.
When we perform the 5th move in array1, we swap any two adjacent elements in array2.
Let's denote those 2 elements as A and B.
Array 2 State after 4th move : { . . . . . . A B . . . } — Sorted
Array 2 State after 5th move : { . . . . . . B A . . . } — Unsorted
Array 2 State after 6th move : { . . . . . . A B . . . } — Again Sorted ;)
So now, this problem simply boils down to count the number of swaps to bring both the arrays in a centralized state.
In my code, I considered the centralized state to be array A itself and hence changed array B into array A and calculated the number of swaps.
It is quite a well-known fact that the number of swaps that are required to make an array to the sorted state is nothing but the Count of Inversions in the array. Although, not at all required in this approach.
269287338
2nd Question....
I am new to cf(and cc in general as well), this was the first contest here, where I could solve a problem, how many more do I have to give to be rated here.
You will be given a rating in this contest itself, it usually takes a day or two for the rating to be updated.
Nice title of E .
After seeing 3/4 constructives, we all pretty much knew that about the authors.
Kudos to the authors for choosing such an amazing title.
For real, it takes so much courage to say "balls" on the internet! /s
First Solves:
A: KimJinwoo
B: PurpleCrayon
C: potato167
D: Muaath_5
E: dyppp
F: lsxhyyds
G: _worst_
Poor problems.
A — guess simplest answer, redundant long statement
B — guess to reduce bigger than 2x2 rectangles as obsolete
C — didn't read (statement too long)
D — guess to reduce to simplest greedy
In fact in a real ICPC contest, the statements probably are much longer. Don't judge C just for that.
.
Not even in my worst nightmares i could think of solving C as pupil and getting -ve delta.People really ruined this platform.Cheaters better do development,there cheating is valid and allowed(untill and unless you steal).
how do you know youre getting -ve delta, results are not out yet
just predicting from prev results of mine
looks like problem setters were having constipation and they successfully pooped on today's pset.
For C , first fix the ordering of arrays , then its a dp . For each index j find k ( k <= j ) such that sum[j] — sum[k] >= target ( can be done using sliding window or binary search ) . Now use prefix dp to find if dp[i][j] is valid or not . General solution for any number of arrays
Even Div 2 D can be solved using chatGPT
https://chatgpt.com/share/070c1de1-cda6-4f3f-a283-dc5b726d0f1d
https://chatgpt.com/share/64e84c6d-969b-4945-9309-afb01faef97e
I used chatGPT after the contest.Proof: I didn't submit the solution of D during the contest
Wow. That is quite surprising actually, and a little concerning too. (although to be fair it didn't know how to find inversions in $$$O(n \log{n})$$$ using segment trees)
You can also find the number of inversions using handwritten mergesort (but I'm not quite sure that this is easier than solution with segment tree)
I solved it using mergesort. Only need to add 1 code, which is calculate the swap when the element in the left side is bigger than the right side. The rest is the same.
number of inversions can also be found using ordered set
The setters should really check if the problems are solvable by Chat gpt and gemini before using them in contests
Hello Can you give me hint for B
Try to think of invariants, ie, some property that does not change about the matrix after you apply an operation. For example, one invariant is that the (sum of all elements)mod3 of a matrix does not change if you apply an operation.
This is not sufficient, but there is another similar invariant that will solve this.
is it that
each row and column sum modulo 3 doesn't change either, so the modulo 3 of each corresponding row and column of both arrays must be the same?
Yes! That's absolutely correct :)
thanks for your help mate, is this a general strategy for applying operations type of problems? I seem to struggle with those a lot, especially when its a 2D array and you have to pick sub rectangles from it
No problem. This strategy is not very common in problems that I have seen. I dislike 2D array problems too as they are not very intuitive. What I find helpful is trying to solve some testcases manually, hoping to see some pattern or hint.
Why did this not work:
269283769
where is the tutorial?
It would be 10x funnier if the first sentence in E was "Alice and Bob are playing with balls." instead of "Alice and Bob are playing a game."
Problemsetters, I need to see your coordinator
can any one give me a hint in problem c?
I solved it by breaking the problem into 6 cases. A's first B's second, C's last A's first C's second, B's last B's first A's second, C's last B's first C's second, A's last C's first A's second, B's last C's first B's second, A's last Basically you try all of these at the same time and whichever works you can just return immediately. It's quite a boring solution :( and just implementation heavy...
This was my solution (I didn't use an array because didn't get good sleep last night and was just going to pay close attention to my variables... It probably would have taken a lot less code if I could have thought about the array solution).
https://mirror.codeforces.com/contest/1983/submission/269274852
Edit
just a quick note that the comments aren't correct on which things we are modifying because I was too lazy to change the label when I'd copy the block and do a find/replace in my editor to get all 6 cases...
This is why arrays were invented!!!
As a IIITian who couldnt crack IIT, the contest was great :)
Thank you for this really splendid round! I'm especially grateful for the amount of sample tests and engaging problems. :))) The only complaint I have, is that B was maybe a little bit too rough, aside from that, all things were good.
It would be better if you write important information on the problem state but not the input.
Auto comment: topic has been updated by Swap-nil (previous revision, new revision, compare).
You are right but rickroll in the announcement.
Already their are many cheaters who cheat through telegram or youtube and my making these type of rounds where questions are totally of guessing type and even D question can also be solved by chatgpt just increases the amount of cheating.
Can anyone please tell that in this contest second question I coded is running on vs code with correct output but when submitting on platform it is telling wrong answer on 1st testcase but it is running on vs code
because there might be few logical errors which got caught in the pretests
Ok so is it that vs code not detected but it did?
No it's not like that, here we have online Judges which has more test cases which aren't given to you and you've to pass those all to get Accepted. At VS Code you just passed the given Test cases from the questions
I know that but on the the testcases shown to us code is giving same ans on vs code but here not
Why don't you actually copy & paste examples when you test it? The way your code gets inputs is wrong, because each row of the grid is given without spaces between the elements, so `cin >> a[i][j];' will try to read the whole line as a single integer and not digit by digit.
It must've been a tough work of manually typing the whole example even with adding spaces...
In problem C, has anyone solved it using concept of sliding window? My approach was finding all the windows of sum k for alice, bob and charlie. After that, finding the non-overlapping ranges bw them.
But I was not able to implement it fully. Kindly help me out with my query or tell if I am thinking in wrong direction.
Thanks.
You don't need sliding windows. You just need to iterate from 0 to N, assign the cakes to Alice until the $$$sum \geq \frac{tot}{3}$$$. Once the condition is satisfied, there is no point to give more cakes to Alice. So you can move to assigning the cakes to Bob, until Bob's $$$sum \geq \frac{tot}{3}$$$, then go to Charlie.
The order of who you assign is important. Maybe assigning (Alice -> Bob -> Charlie) doesn't work, but (Charlie -> Bob -> Alice) works. Therefore, you just need to check every possible order. If none of them works, then you cannot assign the cakes to satisfy the constraint.
In my submission 269266307 I used a sliding window in combination with dp. I used a dp array for each person, that contained from where to where should a peace of cake be cut (dp[i] = j, where i is the start of the peace and j is where it should end). To then actually generate the dp array i used a sliding window (but I think it can all be bruteforced). After the dp array is generated try all 6 possible orders of people (ABC, ACB, BAC...).
Hope this helps (even though my implementation isn't that clean)
for problem number D: I find that simply swapping the numbers with their correct position in sorted array and counting those for both arrays give the result without using any segment tree or merge logic: submission
good luck next time in div 3!
How you solve 4 problems within 1 min in last contest ShivanshJ? Any tips
he probably used his alt and then submitted accepted here :)
Can any one find his alt.So that it can be reported.
and who's alt are you?
B and 1119C - Ramesses and Corner Inversion are basically same problem. Difference is mod 2 and mod 3.
I recently received a plagiarism flag on my solution for problem D in this contest. I believe this is a misunderstanding, as the solution is straightforward and widely known. The problem and its solution closely resemble problem 1591D, which is why many solutions might appear similar.
Given the simplicity and commonality of the approach, I kindly request a review of my submission to consider the context and remove the plagiarism flag. Thank you for your understanding.
This in regard for the my solution to problem 1983D of this round.
I got a notification regarding my the coincidence of my solution 269270131 with 269259042. This was due the coincidence of the algorithm used in the problem, both were taken from this source link. I had even mentioned the source in my submission. I wrote rest of the code myself. Also the style of writing the code matches with my previous submissions.
I request the Codeforces Team to review my submission.
MikeMirzayanov CHEATERS: There are several youtube channels that are streaming all the code solutions live, telegram channels that share the code before and during the contest. Due to these activities, users like me who do fairly in the contest get improper allegations of plagiarism. If talk about my case, my code and syntax are all of my own, I can also share the source of my code. I do not know why I have been accused of plagiarism. I hereby request the admin to please check into these cases.
MikeMirzayanov, I believe I have been falsely accused of plagiarism in the recent contest. My solution matches a publicly available code from GeeksforGeeks that was published before the contest. Could you please review my case? Here are the details:
-Description: In last div2, My solution https://mirror.codeforces.com/contest/1983/submission/269278403 got skipped telling in has significant match with https://mirror.codeforces.com/contest/1983/submission/269258951 this solution. But the two functions minSwapsToSort() and minSwapToMakeArraySame() was copied from geekforgeeks https://www.geeksforgeeks.org/minimum-swaps-to-make-two-array-identical/ . Our main functions are even different. Hope codeforces will take steps as soon as possible.
My solution https://mirror.codeforces.com/contest/1983/submission/269263444 got skipped telling in has significant match with (1) https://mirror.codeforces.com/contest/1983/submission/269253412 and (2) https://mirror.codeforces.com/contest/1983/submission/269251305 this solution. I see that the logics that we have used are same for the problem, but I think for (1) solution, it matched because of similar prompts/ responses from chatGPT, and (2) might have written it by his own, I have no connection with the people with whom my solution matched, also my solution was submitted after a huge time gap from both the people and also please take into consideration the limitation of python solutions that tends to be very similar if they have a same logic, also I thinks using chatGPT solution should not be considered as plagiarism as ChatGPT is an open-for-all software which can be used by anybody and if we give it same logic to solve a problem, it might generate similar solutions, I hope that my solution will be considered after this clarification
I just received an email stating that my code for B 269246318 has coincided with 2 other people's solutions and has been disqualified. Now, before you guys start to question the authenticity of my previous contests, the skips were due to me accidently using public mode on IDEone. I went through the rules and did not complain.
However, for yesterday's contest, I was using GPT to help me implement my idea, as I was blanking out a bit there. After going through the rules, any tools published before the contest are not prohibited. I understand this is not the right way to go about giving the contests, and I acknowledge this was a lack of judgement on my behalf. However, I would like to appeal regarding this solution as this is not a violation of the rules per se. Using AI tools which are not prohibited and copying other's codes should not be treated as same in my opinion.
Thank You. PS: It is a conversation with an attachment in it, which is apparently not supported yet, thereby I cannot provide the conversation as proof; but anyone can try to run the problem and get the desired result.
Edit: The coincidence occurred with 269249083 and 269251658.
Bro its so easy to recognize that you cheated it took you 13 to 14 mins to solve A and you did B in 11 mins which even expert rated coders had tough time dealing with stop cheating and do CP for your own skill improvement not for ratings as you grow rating will come with it as a perk
Ah! Got a mail regarding the solution matching with other candidates idk what went wrong I totally accept that there was something that went wrong and i am an absolute beginner and i don't know much about rules and regulations but one thing i can make sure is that it was not intentional or you can say i was not aware of consequences of these things. I am sorry i will take care of it in future and about my profile it does not have anything, if it get suspended on my first mistake then i will start again with another profile make sure to keep that clear. Sorry if i did any cheating or be the source of cheating ,unintentionally.
is there some issue with cf my solutions are in queue for 2 hours now??
.
Bro, don't you know, you can't delete account on codeforces
But you can write to MikeMirzayanov who is developing this feature for now he said "Just erase all personal data from your user account and don't use it anymore. We don't store personal data long-term." so I will do the same.
I just received an email stating that my code for B 269266228 has coincided with 269287776. and has been disqualified. I see that the logics that we have used are same for the problem, but I think for solution, may be it matched because of similar prompts/ responses from chatGPT, or might have written it by his own.There is almost an hour gap between our submission.I hope that my solution will be considered after this clarification
you are not supposed to use chatgpt you dumbass
CF system had sent me mail about vioaltion for my solved problems.I solved the problems using chatgpt Prompt(as far i know this is legal). I do not know my code got same with others.Please help me on this
Dear Codeforces Team,
CF system had sent me mail about vioaltion for my solution 269286787 for the problem 1983B.I solved the problems myself and used chatgpt for error handle I do not know how my code got same with others.Please help me on this i have been regular and faithful in codeforces since 3 year . please help me don't give penalty.
Please help me someone.why didt i get this violation mail.I just use chatgpt
I have attempted the test and my solution 269278694 for the problem 1983B is said to be identical to others solution. I just want to this is so because this problems solution can easily be found on GFG and Leetcode with identical or near to solution and also could be generated through chatGPT thus wanted you to kindly remove plagiarism from my solution
lol. dont come here and cry now. Thats what happens when you take expernal help instead of using your own brain.
oh no indian round
He rickrolled us through the red letters :)).
B is waste of time ..