Hello, Codeforces!
I invite everyone to participate in Codeforces Round 884 (Div. 1 + Div. 2), which will start on Jul/11/2023 17:35 (Moscow time). The round is a combined round and will be rated for everyone.
You will be given 8 problems and 3 hours to solve them. One of the problems is divided into two subtasks. The scoring distribution will be:
$$$500$$$ — $$$1000$$$ — $$$1250$$$ — $$$1500$$$ — $$$2000$$$ — $$$(2000+1000)$$$ — $$$3500$$$ — $$$4000$$$
All problems are written and prepared by me. I would like to thank:
- irkstepanov for carefully coordinating the round.
- MikeMirzayanov for the wonderful Polygon and Codeforces platforms.
- 4fecta, ak2006, amethyst0, AndreySergunin, BalintR, ChrisT, Dan4Life, dorijanlendvaj, Dormi, errorgorn, Golovanov399, IndignantHydra, jonatas57, kzyKT, lexiyvv, liouzhou_101, Maksim1744, maximrufed, mc._cari, MvKaio, NoDesire, polosatic, RedstoneGamer22, skittles1412, tibinyte, valeriu for testing the round and providing valuable feedback.
I look forward to your participation and hope you enjoy the problems. Good luck!
UPD 1: Editorial
UPD 2: Congratulations to the winners!
and congratulations to cnnfls_csy and orz for solving problem H!
Now the testers can comment
Now the participants can reply...:)
Thanks to the author, very good experience！
As a tester, I comment
As a participant, I replied
I Guess that you have not been participated in the contest for last year.(except the one in June)
It's amazing that a single writer prepared all the problems for a Div. 1 + Div. 2 contest! Hope the problems are interesting :)
I think the contest is going to give us tough time!!
revision :
one LGM write all the problems
Looking forward! Score distribution means I might finally get a D solve again ;)
Scoring distribution has betrayed us a lot of times ;)
Yeah but this time I truly believe I can do it. ;)
atb!
thanks, good luck to you as well
Worked
Is the cat in Golovanov399's profile coughing?
And all these time, I was thinking that it was trying to salute someone
As a tester, I can confirm the hardest problem is harder than the easiest one.
Good luck!
As a tester ( giving that he participates ), I can confirm tourist will solve at least one problem.
Good luck!
As a non-tester, I shall reply to the claims of the above testers.
hope to become green in this contest.
Why is problem number 6 score (2000+1000)? Is it because of subtasks? Asking because I have never seen subtasks on CF :)
There will be F1 (score 2000) and harder version of the same problem as F2 (score 1000).
It will probably be the easy version with 2000 points and the hard version with 1000 points. For example, they were split equally in the following competition, but not equal points this time: https://codeforces.me/blog/entry/116091
As a tester, video editorials for most problems will be on my channel after the contest
Hoping to reach blue
poorpul
hee hee hee hawww
I was just wondering, is there a reason why this round is combined Div.1 + Div.2, while the rounds are usually separate Div.1 and Div.2? I understand that rounds with prizes are combined to let everyone have a chance for a prize but this round is not one of those.
Congrats!
Here we go, Go to Grey again :)...
Here we go, Go to unrated again :)...
Destroy the feelings :D .
can anyone tell me how can I become a tester?
u can check this blog.
are you from the same London as Justin Bieber?
I thinks that frequency Of DIV : 4 contest is reduced so much??? As earlier DIV : 4 almost happen every month But of now there is no DIV : 4 contests happening.... It's very long time that No DIV : 4 contest has been happened....If it is like this what will happen to the participants like us which are "newbie" on codeforces... Isn't It?? What's Your opinions On this... Just personal Feeling's.. If anyone get's offended by this Sorry for that(:
I mean you could actually try solving some harder problems?
Is +66 delta too much to ask for!!!
and shameless me asking for 113+ delta xD
I think you need about top 700 overall to get this delta
As a partcipant, I excited
poorpul
Enjoy the three hours and get rating
Question:
Sir, I am a newbie. So am I eligible for this contest ?
yes, anyone is eligible for this contest regardless of ratings.
Thanks @amit_pandit_15 for replying. So if I was able to solve only single problem in this hard will this decrease my rating badly. What do you think?
In starting contests(for like first 3-4 contests) the ratings increases only, even if don't have good performance, since you have given only 2 contests, solving even one question will increase your ratings.
I think getting at least 2 problems right should be enough for you to get a +ve delta
Hope to get close to CM :)
i hope to become a specialist again. Are u a third-year student?
I gave my 6th semester exam before this summer vacation , i am currently in 7th semester now.
poorpul
Tonight, I am ready for the first battle to achieve the prestigious Purple Rank.
poorpul
I will try to solve A-D ASAP to have time to solve E, sound interesting!
I'm sad. I have a summer camp so I can't participate. I will definitely up-solve the problems in the contest tho. To everybody who is taking the contest, GL & HF!!!
I wish I can see a Lockout Between tourist and Benq :) ... What is ur opinion guys ?
yes this rivalry is best
I hope we don't go back to the green name
Does this mean that our ranking will be more than 1,000 lower than the usual Div.2, and it will be more difficult to add points, because the experts of Div.1 will also participate.
it doesnt work like this. Actually, because of the rating system its usually easier to get points. Read about how codeforces rating works heres the link: https://codeforces.me/blog/entry/102
Thank you for your reply.
poorpul
hehehehaw moment
i wanted to see tourist at 1 again.
he granted your wish.
lol, cnnfls_csy clutched in last 2 minutes. :D
wait i cannot register anymore, why? Edit: i tried to register 10 mins before contest
now register in extra registration time
Slowly proceeding towards my fav colour :)
Cyan
I wouldn't say that's slowly, that's a big step.
Ah yes, I am really missing Cyan, so I decided to take a big step :)
just kiddin, if you didnt submit all of them at once you would have lost just a little rating. you are closer to CM no worries
is cf-predictor working? it's not working for me
It hasn't been working recently, didn't work for me last contest either.
Use carrot https://github.com/meooow25/carrot
this is more accurate also! thx
i am going to get demoted for sure.
DsolvingForces
Balanced as everything should be ):
speedforces
no hacks forces
mans loh
Wow,5500 submissions on problem D,codeforces has become leetcode. Cheaters everywhere.
Rating is not increasing ,neither the contributions, what should I do now ?
Both doesn't matter.
Problem A
May I know why this condition is not valid
test case :
a=1,b=2
If $$$a = 1$$$ and $$$b = 2$$$ you get wrong answer. Then the first player can take $$$2$$$ and remaining stones are $$$0$$$ total so second player loses.
a = 1 and b = 2 in this case you print 2, but then the first player can win in one move.
What if B is 2, then first person will reduce 2 from 2 (your answer) and second person cannot move.
what if b=2
ConstructiveForces
How to solve C?
It's not possible to sum odd and even index numbers. Try it.
So you have to get max sum from either odd or even index numbers.
The odd (in this case) can be summed up (or deleted) and the even have to be deleted. And vice versa.
Also check for the case when all numbers are negative.
so what was the edge case for C?
are you checking maximum subarray sum for odd and even indexes??
yes
It should be a maximum subsequence. For the array 1 -1 -1 -1 1 you can repeat move on 3rd and 2nd then you will get 2
Ohh got it, thanks.
1 -1 -1 -1 1 test case broke my solution. Did not realize that you can safely discard negative elements.
Codeforces Round #884 (Div. 1 + Div. 2)
ConstructiveForces
Algorithm (X) Construction (O) Contest.
Speedforces from A to D
how to solve C?
Simulate the operations for a few cases. You will observe that the final array collapses to a subset of one of the following index sets: {1,3,5,7,9...} or {0,2,4,6...}. Moreover, no adjacent elements can be part of the final sum together.
what about the case -1 1000 -1 -1, shouldn't the answer be 1000?
yes. In this case, the subset of {1,3,5,...} chosen by us is simply {1}.
how would we go about choosing the subsets?
Just choose all the non-negative elements :)
thanks, well back to cyan
How to solve D?
Answer exists because $$$lcm(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26)$$$ $$$>n$$$, not because $$$26!>n$$$.
thats right...
skill issue
teach me E
yes actually 'teach' is the right expression.
Why does every problem in this contest feel constructive? 🤡
Problem E is cool!
Though ABCD were absolute speedforces which I really failed, after solving E it didn't matter
Swap(C,D), D was very straightforward unlike C.
so huge gap between D and E
Great contest! 2 problems with hello world solution is insane :D
GuessForces
Please explain E.
I guessed the solution of E but don't know how to prove it.
For (i, j) such that 1<=i<=n-1, 1<=j<=m-1, we must have (i, j)==(i+1, j+1) (we denote a[i][j]=0) or (i+1, j)==(i, j+1) (we denote a[i][j]=1), then for any valid grid, there must be some f[i] and g[j] such that a[i][j]=f[i] xor g[j]. Then we can solve the problem by dsu.
I have been thinking for an hour but still cannot come up with a conclusion, can you give me a rough idea?
think not about the letters, but about the grid of choice which diagonal contains the same elements in 2x2 squares — 1/0. All the lines of the grid are the first or the reversed first (suppose you know the first row and the first element of the second — you will see that the second is uniquely restored). Then check if it is possible — a system of disjoint sets and a top-down/left-to-right scanline
apparently, the second part can be made much easier :)
(Editorial is already out)
Can I ask how you found this pattern? I couldn't construct objective examples for me to observe during the competition. Did you figure it out just by looking at the samples?
in samples there is "square"
1 ... 1
.......
1 ... 1 — YES
1 ... 1
.......
0 ... 1 — No
from that and looking at n = 3 m = 3 cases
shout out to ur mom and ur 1e9 copies for problem E
As a leetcode refuge, I really enjoy these problems, even if I solve a few each time. I can feel my brain working ;p. Each problem seems so easy after I finally solve it, but before that I might spend an hour on it.
Amazing contest! Had fun solving A to D, each problem had some beautiful insight hidden — which apparently, I was too dumb to notice, hence overkilled A with DP :X
Cheers to -100 delta, and 3 hours of absolute fun! Kudos to the author, and the entire team. Looking forward to future contests by duality!
No way you used dp on problem A hahaha. Btw, it is always helpful to check the leaderboard. If a lot of people are getting AC on a given problem and you are stuck on it, chances are the solution is much easier than it seems.
Someone tell me how to solve "B. Permutations & Primes" problem?
Anything that includes 1 and 2, but doesn't include 3 has prime MEX. So we place 1 and 2 in the middle and 3 all the way to the side, to maximize number of such segments.
Now, anything that doesn't include 1 can't have prime MEX, so now we only need to consider segments that contain 3 and 1. The only way this can fail to have prime MEX is if it includes 2 but not 4. So, we place 4 right next to 3 to minimize such segments. Now. We only need to consider segments that contain 1 2 3 and 4. These have prime MEX unless they contain 5, so we place 5 all the way to the other side of 3 and 4.
After this you can fill in the rest of the numbers arbitrarily.
I did not partecipate the contest but I Will try to upsolve. I think problem C can be done through DP. Is this the right way to go?
Yes, DP is possible, but greedy is also possible
Ok I Will try both approaches. The first thing which came to my mind when looking at it Is DP. Do you think the DP solution is hard to code?
My implementation was quite simple
congrats on GM :D
Thanks, I should probably celebrate before I fall back to (international) master lol
Within 8 months too damn
I think greedy is easier.
Notice that you can always get subsets of the even elements or odd elements, so just get all positive elements at odd positions, all positive elements at even positions, the maximum of the array, and print the maximum of those.
E destroyed my brain
What a gem of a round! E and G are just stunning problems, and the rest is very good also.
c>>>>>>d anyone?
still more people solved C dont know why
coloringforces
anyway, it was a nice contest, really liked the problems :D
what is the idea behind the d problem?
The min distnict charcter in ansere is always first non-diviser of the given n ,,why this approach will work because let suppose x is not divide and then any multiple of x never divids n like 2x,3x,4x,5x... so on.and for ex. (3x+1) divides the n then the matrix of size 3 cross something and somthing cross 3 never be bad ..hope you understand the approach
Why coloringforces? 0-1 coloring applies only to E I think
D is technically graph coloring
D was also a coloring problem on a special type of graph
D?
Wow! Superfast editorial with hints..
I think C > D......
want more frequency in contests
blazzing fast editorial
Maybe testdata of F1 and F2 is too weak? My O(n^2) solution for F1 successfully passed F2. https://codeforces.me/contest/1844/submission/213394774
and to my surprise, it even faster than most of O(nlogn) solutions.
Hacked. A case containing lots of gaps that are less than $$$|c|$$$ but where twice the gap is more than $$$|c|$$$ causes your code to repeatedly erase from the front of the list, achieving $$$\mathcal{O}(n^2)$$$ behaviour.
Unfortunately, I did not anticipate this approach before the round, so the tests did not contain this type of case.
Also I saw this submission, may be it can be hacked too.
Thank you for pointing out this submission. I hacked it too, using a test where only one small value satisfies the
check_valcondition.Good problems and strong pretest! I ranked 377 when the contest ends, and rank 377 after the system test. The only thing needs to mention is that difficulty gap between D and E is too large.
Do you think you will get master?
I don't know. Can anybody use the rating predictor to predict my rating changes for this contest? I am not able to use Chrome since it gives me 403/forbidden error.
predictor gives me +70 for you
congratulates for master bruh :)
hope for me reaching cyan , i have been fighting for too long TOT
I hope to become an expert：）
Me too :)
Now you have fulfilled your wish
thanks ：）
I really enjoyed solving problems of this round, problem C is my favourite problem now, it is very interesting. But i have a problem, I have "hack it" button after the ending of the round
See https://codeforces.me/blog/entry/68204 for details.
orz Orz
Thank you.
People with rating predictors, could someone tell me my expected delta?
+116
I am trying to figure out what is wrong with my solution https://codeforces.me/contest/1844/submission/213344967
It appears that the checker output does not show failed test case. Is it intentional? If so why is that?
I think from one of the odd or even sets we have to take only positive charges in your solution according to my thinking you are considering the sum as maximum(ith charge or sum + ith charge ) but if ith charge is -ve we dont have to consider it
Thank you, but my question was about why we can't see failed test cases.
output should be 11. your code gives 7.
Thank you for provided test case, but what I actually want to know is why failed test cases are not shown in checker output.
I'm not sure about that. Sorry for the wrong reply.
no offence but why A to D has to be easy speed forces in a div-1 + div-2 round ?
CLIST shows a 1000 rating difference b/w D and E damn
In any contest the starting block consists of quite easy problems, so it's kinda speedforces. Would you like C and D to have been harder?
Yes
C was fine, i guess D should have been in the expert range.
For me at least, C=1400 and D=1800 would have been better, give or take 100 rating points.
So I suppose C was OK today but D was obviously much easier than it should have been.
Div.1+ div.2 = div.3
B>C for me
Did anyone else have an issue understanding problem D on the mirror sites? The string examples didn't have grids around them. I had to open the original CF problem page.
In problem E $$$\mathcal{O}((n + m)k^2/\omega)$$$ passes. 213399890. You can uphack if you want.
1159 Rank can I reach Expert (1478 >>> 1600)? I am eagerly waiting for the Rating Changes.
Also, why isn't the CF Predictor Extension working lately? Does anyone have an idea about that?
Me too, want to be purple.
You got it mate Congratulations !!!
predictor say's you will get 119. Maybe after removing cheaters you can:)
Thanks, 122 is what I need. Can you share the predictor link please ?
https://chrome.google.com/webstore/detail/carrot/gakohpplicjdhhfllilcjpfildodfnnn
Thanks mate <3 I was using CF Predictor, and it hasn't been working lately.
I got +120 happy but 2 points less happy :)
OMG i am 1599…
finally, someone who understands <3 hope we get to expert after removal of plag
Hope you can become an expert soon
Alternate account or a newbie on cf?
The Plag check's done :) Maybe we can get the +1 and +2 we need for Expert !!
Ohh yes!! It looks like it's almost there, let's wait for a good result.
Brooo congo but now I am at 1599
Feel sad about it…but wish you get better performance in the next rounds
кукареку-forces
Very cool problems, thanks!
How do you lose 267 points in a single contest and still say "very cool problems"?
The beauty of the problems does not depend on my performance.
I don't understand the opposite situation when people go to comments after performing poorly and say "It's the worst contest ever". It's not the author's fault that you suck.
thank you for this contest!
No offense, but did no tester feel that this contest was very unbalanced or that there's no diversity in it? And if they did, why didn't change?
I'm sure high rated people enjoyed the problems, but everyone else got stuck and didn't enjoy as much.
I think it's the best contest i have joined in my life Back to specialist
Till now best contest for me. For the first time able to solve A,B,C under 30 mins and also the first time to solve D. Although D was easier comparatively.
Speedforces ABCD
As cyan, i hope to be blue.
How can one become a tester for a contest??
Ask authors to participate in testing.
How can i find the authors before testing?
There are few coordinators on Codeforces, their names are known. You can occasionally ask them, and they can help you contact authors of upcoming rounds.
How to calculate whether i will get a rating increase or decrease
You can use 'carrot' extension on chrome.
just add it to your browser and it will show you the expected delta and how was your performance rate in the contest when you open the standing.
This contest's problem A is the best a+b problem I've ever seen
Rating changes?
Rating changes?
What's the maximum number iterations can we run in 1 second? My 213380076 for problem D is O(n * (no of factors of n)) The maximum number of iterations run is around 2.5 * 10 ^ 8. But it takes less than 300 ms. How?
For n = 997920, it runs 2.4 * 10 ^ 8 iterations. It takes only 218 ms.
I think I did something very similar but my solution is much slower. Is my precomp slow? I think it's $$$N log(N)$$$.
Your precomp is taking more time ig because sample testcase also took 1 sec, in my local machine your code took around 10 seconds, may be RAM block size is the key ig which codeforces use to increase spatial locality
Please explain, how you got the number 2.5 * 10 ^ 8?
You can run a brute force
after you get your number factored, all remaining operations are rather fast, so I think it is possible
When will the rating changes be updated?
.
Anyone, please explain
In problem C why are we taking the maximum of c[i] with 0?
What if we have 1 positive element and the rest as negative?
if there is one positive and rest all are negative then you can simply remove all the elements in front of it and back of it , without adding anything
Then we can leave only that positive element
Like
-1 -5 6 -8 -> -5 6 -8 -> 6 -8 -> 6you can find the sum of all the positive number on odd indices and same should be done for even
we are then finding max of them and printing
in your case when all numbers are negetive suppose -1 -1 -2 5 -9
we know the ans should be 5
we know that the sum at odd indices is more now we will choose the number on odd indices that are negetive and remove them -> -3 5 -9 now we will remove -3 and -9
I have an another solution for D. See Here
I am new to code forces, why did this contest not give any rating? I am still having 0.
Probably they check if anybody has cheated to remove him from the final standing. And then they will publish ratings updates.
so we will get a rating for this contest soon, right?
Yes, I hope so.
This contest's problem A is the smartest way to learn how to print a+b
Is it rated?
I can't wait to see cnnfls_csy reach 3500!
does anyone know how can we predict our rating changes? Becoz CF-Predictor doesn't seem to be working. EDIT: nvm I read the comment above.
is this contest is unrated??
Is the round rated...... been waiting for the update since morning
Can someone help me figure out where this code gone wrong for problem C 213370130
You can apply the operation twice at the middle element: $$$[1, -1, -1, -1, 1] \rightarrow [1, -2, 1] \rightarrow [2]$$$
Hope everyone get good scores!
Is it rated?forces
ratings updated when??
I cannot afford to have this contest unrated. Please update ratings.
May I ask what is wrong in writing the question E like this? Can you explain it or give a wrong example? Thank you very much[submission:213474901]
213474901
Ratings updated, sorry for the delay.
It's okay, buddy, take your time, we don't mind.
thank you for the round! problems are all fun
Can someone please provide a proof of why for $$$c>0$$$, sorted array works in problem F of this contest? It is pretty unintuitive to me.
I just received a email stating that one of my submission(D) is significantly similar to some others I received the email for the first time. The code was my own please guide me on how can I prove the code was not copied
Regarding the D problem of this field, this is undoubtedly an excellent topic, just start from 1 to find the factor that the number is not n, and then use n + 1 to go through the structure of abcdef, A, B are brain teaser questions
Is there currently any working site to know deltas after contest ?
https://cf-predictor.wasylf.xyz/ is not working .
yes use Carrot — https://chrome.google.com/webstore/detail/carrot/gakohpplicjdhhfllilcjpfildodfnnn
Response to cheating in D, Straight of the bat, say like I haven't used any public ide say ideone.com (like the system says_ and other whatever is present since I think it is slow and I am adamant my code runs immediately, and secondly, for this question I have used one code from gfg to find the factors (if n=4, then factors can be 1,2 and 4 (since matrices like 1*4, 2*2, 4*1 can be considered)), and for saving time, took that code from there (link) -> https://www.geeksforgeeks.org/find-all-factors-of-a-natural-number/ (the second post code I have used) (and stored them in set so the factors 2*2 doesn't get inputted twice) and after that I applied own logic and found out the answer. But there was some system check and I have my solution colliding with someother ones. Furthermore, I have always followed ethical guidelines and respected the Codeforces rules. I would like to ask codeforces team to please reply back since it takes lot of practice and time to reach this rating (you can see my graph also, been here for a long time). You can check my previous contest performances and submissions as well and consider my track record. Please reply to me back codeforces team immediately.
The link you provided is too obvious which may not help you in getting out of this, better give links to your submissions and matching submissions as well and ask for help or consideration.
I was falsely accused of plagiarism. Read this blog Please someone help me out
I recently received a notification regarding problem C, stating that my code bears similarities to the code written by some other participants. I want to clarify that I wrote my code independently, without any external influence. I happened to encounter a similar problem in the past and had already developed an approach to solve it. I believe this is a testament to my dedication and practice in mastering such problem-solving techniques.
I kindly request the Codeforces team to review my situation and provide a response. I genuinely value the effort and time I invest in improving my coding skills, and I hope the team recognizes my commitment to fair competition
better provide the details of submissions which matched yours and then ask for help :)
I recently received a notification regarding problem B,C, stating that my code bears similarities to the code written by "VirusARzk" . I want to clarify that I wrote my code independently, without any external influence and i didn't know who is this.
Bro our code is also different. The part of a snippet is same.
lol, I just realize it now, how is this counted as cheating
It was cleared. Now I'm going to change my template.
Dear Codeforces Team, I recently received a plagiarism accusation for problem D during the last contest. I want to clarify that I solved this problem independently and request a rating adjustment accordingly. I assure you that I have always upheld fairness in all my Codeforces submissions. I have reached this rating by giving CF contests continuously and honestly. While my solution may resemble others due to common logic, I affirm that I did not copy anyone's code because of my past experience solving a similar problem elsewhere. I kindly ask you to reevaluate my submission and reconsider the rating adjustment. I value the fair competition Codeforces provides and want to rectify any misunderstandings. Thank you for your attention to this matter. I look forward to your positive response. 213385596 — My submission 213380296 — Person with whom I received plague
better provide links to your submission and the submissions which matched yours and then ask for help. It would be clear for them to solve or for any to help you that way.
Why are my last three contest rating changes of -54 -12 +120 gone? I understand a plag check is going on for Round 884, but I don't understand. My rating is the same, but my graph is distorted, and my last three contests are not showing up on the contests page of my profile.
Is this normal or smtg's happening ?
Same thing is happening to me. When I put show all it shows the contest and says its unrated.
Same thing happened to me, rating for last 3 contests gone as if they're unrated. Also now it says Contest rating: 1301 (max. newbie, 1151), which is strange. I did not recieve any plagiarism letters as some people here. So I dunno what's happening.
Dear Codeforces Team, I wanted to bring to your attention that I recently received a plagiarism notice for problem D of my last contest. However, I want to emphasize that I did not cheat or intentionally copy any code. The similarities in my solution to others might be attributed to the utilization of common logical reasoning and problem-solving approaches. I kindly request you to reevaluate my submission, taking into consideration the possibility that my solution was derived independently. Upholding integrity and fairness is of utmost importance to me, and I have always strived to maintain these principles while participating on the platform.I greatly appreciate the efforts made by the Codeforces team to ensure a plagiarism-free environment. I sincerely believe that the resemblances in code were coincidental rather than a result of deliberate plagiarism.
I noticed this round got unrated, and wanted to know why so I looked at scores. A bunch of gray people solving problem D. Also other div2 people solving D in under 10 min.
unrated???????????????why??????????
.
Why have the rating changes been revoked?
Roll back？
This is my specialist round so thank you, I really appreciate that.