Hola, Codeforces!
We're glad to invite you to take part in Codeforces Round 978 (Div. 2), which will start on Oct/13/2024 22:35 (Moscow time). You will be given 5 problems and 2 hours to solve them. Some problems will be divided into subtasks.
This round is based on day two of the Mexican Olympiad in Informatics (OMI) 2024.
Please note the unusual starting time.
The team of writers is conformed by JuanPabloAmezcua, SebR, Marckess, and myself. We have spent a ton of effort setting the round as well as the Olympiad, we hope you enjoy it.
(This is our logo, cookie points if you can guess the names of the two characters in it)
The team would like to thank:
errorgorn for the most based coordination. The round exists thanks to him, the team loves you sir.
All the testers for their support and great feedback: blackyuki, Dominater069, frodakcin, bashkort, _istil, prvocislo, mzen, MeGustaElArroz23, Ari, gxlois, Error_Yuan,_rey, LoboLobo, maomao90, oursaco, willy108, fishy15, AlperenT, JoenPoenMan, Skywk, ozy1220, Daniel19Frenzy, nyaruhodo, Elliptical_Curve, karlamun, biank, Alexbrii, El_Roge, JuanJL, dazlersan1, juanbrau.or, HerreraDaniel, saultapiaprogra, viktorchares, mafflopez, tibinyte2006, nbreakable, RasecBadguy
Alexdat2000 for translating statements.
KAN for believing in the project.
ocarima the godfather of the Mexican Olympiad in Informatics, for believing in us, all his support and pushing us to grow.
MikeMirzayanov for creating codeforces, and sorry but I have to say this, the amazing system Polygon.
Score distribution: 750 + 1000 + 1750 + (1750 + 2000) + (2250 + 1000)
We wish you happy coding and good luck to all participants!
Winners Div 1:
Winners Div 2:
First solve for each problem:
UPD 1: We have added new testers and score distribution.
UPD 2: There is at least one interactive problem, so please read the guide for interactive problems if you are unfamiliar with them.
UPD 3: The editorial is ready. Congratulations to the winners and first solves for each problem!
As a problem setter, I hope you enjoy the problems ;)
As JuanPabloAmezcua's former roommate at MIT, I enjoyed the problems :)
Here's my livesolve of Problems A, B, C, and D1! https://www.youtube.com/live/CvCjhMRWmhc
Thanks Filbert! We appreciate it <3
As a fellow MIT student, I got cooked on problem B.
Very nice problems tho
as a writer, i want to go to sleep
good night
ill love u if we keep this numbers please
Is that the reason why the maximum number of questions in D1 is $$$n+69$$$?
your pfp reminds me of Attack on Titan :(-
There were 6 days gap before 14th october and have 4 days gap till 19th october . I am wondering why 2 contests are going to be arranged in the same day!!!
Wow. After more than 2 years of him dreaming about it (
and me scamming him), the time finally came for jampm to become a Codeforces problem setter. I'm so proud of him and happy I could help with testing.You did scam me hahaha. I met some of your students and they asked me for an editorial of a problem I gave you LOL (you had my consent to scam though :).I wish we can do a round together eventually bro, thank you for always being such a cool and supportive friend :))
jampm round orz
jampm round orz
Contest start at 03:35am in China.Can't participate o(╥﹏╥)o
sleep early and get up on time o(╥﹏╥)o
It is a nice time actually. Although you might not be used to waking up early
Mordecai and Rigby
The contest will start at 01:35AM(at such a nostalgic time) in Bangladesh. Wish to become specialist at least.
Are unusual starting times and late score distributions a recent trend?
Thanks for bringing finaly the problems of the Mexican Olympiad in Informatics to codeforces jampm , JuanPabloAmezcua, SebR , Marckess and all the ones who contributed to the proyect.
Hope you enjoy the round!
Expert this round ? lezgo
2AM in Vietnam and still participates :) I'm taking part in ICPC Vietnamese southern 2024 contest 12 hours before this round, what a busy schedule.
As a tester, I really liked the problems!
Finally a better time :)
What is the score distribution by the way?
"This is our logo, cookie points if you can guess the names of the two characters in it"
I know really well one of them is Karel but who is the other one? I have some clues but not sure. Now can I have real cookies?
Hope the best to 1ANH6 in the Mexican Olympiad!
Did you say “cookies”?
Why contest at odd times becoming common these days?
Because Olympiads usually happen this period
As a tester, I tested after the announcement was post :pensive:
As a tester, I can say the problems are interesting to solve and highly recommend you to participate.
bad starting time for Chinese.
Because it's bed starting time for Chinese.
3:35 for UTC+8. I need to sleep early and get up early to participate in :)
Finally a Mexican round ❤️. Muchas felicidades al COMI y todo el equipo detrás porque siempre ponen problemas muy chidos en las OMI's, y sé que implica mucho esfuerzo. ಥ‿ಥ
Can the round starting time be extended? I think many asians will agree.
But many south/north americans will disagree.
Does Mexicans have their own judge site for practicing problems?
during the contest all of Asia and east of the Europe are slipping then who is awake to compete?
Contest is based on Mexican OI. Who do you think?
they could start the contest 2 or 3 hours earlier so the most of countries that are good in IOI can participate in the contest and wtf so many people cried and down voted my comment did I say something bad?
and contests like this are an unfair way to increase rating of the participants in some countries
yes, mexico should shift its OI to cater to non-mexican participants.
Who cares about IO this was a rated contest for any div2 if they want to participate in day time in Mexico they could release it as a gym
fym "who cares about OI" this is literally a mexican contest, they have no obligation to release it as a div2 contest but they did. if you want to participate in the contest at daytime take a virtual.
Where are the point values?
dunno, probably they havent decided on some of the problems yet(?
Is this contest IOI formatting?
I received an e-mail a few hours back, saying that the round starts on Sunday, October, 13, 2024 19:35 (UTC). Please resolve the discrepancy, if any. Thanks!
Nvm, it was a misinterpretation on my part :-/
Nice but why does the timing of the competitions continue getting weird and weird
Score distribution?
In China,the time is 3:35.Even in Russian time, it is still 22:35.Is it free time for Russians?
Score distribution ??
Reveal the score distribution please..
Zzz
Won't be able to participate due to the timing T_T Anyway good luck to all of ya who'll be participating...
Don't be lazy
I hope i remain a specialist after this round.
You will. just don't participate
Bad timing for Indians.
I think this is the first round in the history of Codeforces when there will be no cheaters because time is unusual. (At Night)
god bless this round, let there be a 2-minute delay
less than 7000 people made a submission lol. i wonder why
Normal ppl sleep
26k people registered tho
How to solve B??
$$$answer = max(a_{max}, \sum^n_{i = 1}{\lceil \frac{a_i}{x} \rceil})$$$
but why though?
The $$$a_{max}$$$ part is obvious, however the second part is pure guesswork. I had already given up on the contest but wanted to submit this solution just on the off 0.01% chance that it is correct.
You can easily put all $$$a_i$$$ in priority queue to solve it. Consider that we always pop first $$$m$$$ types. For each type we minus $$$1$$$ and push in queue. After $$$k$$$ times, the rest types are less than m. We can get that the rest answer is the maximum for the rest. Following the steps, we can solve it with $$$ans = \max\left(a_{max}, \left\lceil \frac{\sum_{i=1}^n{a_i}}{m} \right\rceil\right)$$$
The correct formula is: $$$answer = \max\left(a_{max}, \left\lceil \frac{\sum_{i=1}^n{a_i}}{x} \right\rceil\right)$$$
I wonder, how did I get Accepted with a wrong formula, hmmmm?
Problem C is such a pointless DP exercise.
In D2, anyone knows how to use 3 operations when n=3? I writed tons of case work and can't solve it ;)
I felt like D2 involves some graph theory. May be whenever there is some cycle detected, we have to stop...
No Solid idea though. Just sharing my thoughts...
We proved it is impossible.
Sorry for the delayed editorial, we (the team of writers) have also been hosting the Mexican Olympiad in informatics and monitoring both contest. Give us some minutes we'll finish it up.
Finished yet?
I think no, the number of all possible combinations of 3 players with 1 imposter is 12, while 3 operations will give you at most 8 different outcomes. You cannot make one to one mapping from the outcome to the three players.
if in 2 queries you have no cycle -- there are still 3 possibilities for imposter, but only 1 query with 2 different outcomes left -> impossible
if you have cycle in 2 queries and answers are different, one of them is imposter -> easy to see no rest query can give you who exactly is imposter (cause you know nothing about 3rd player)
Really loved the problems.
A-B-C are getting difficult day by day... It took me 1 hour to solve just ABC :|
how E1 is 2250 score huh
video editorial by Um_nik for 2022E2 - Billetes MX (Hard Version) aka Atcoder: Grid and Integers
thanks for sharing.
was it just me or B felt really hard. spent 1 hour 50 minutes on it and didnt proceed with anyything
Overthinked :(
You're not alone!
Okay, who thought that C is a good enough for a div2 round? It is simply pointless implementation task.
How did you solve it?
consider i as the current index in the upper string and j in lower one , now there can only be 3 cases i exceeding j by 1 , j exceeding i by 1 or i and j being equal.. make 3 states of dp corresponding to one i and the three cases.. it will be an n*3 dp..
It's hard to undertand that more than 30 people made feedback and nobody noticed the huge difficulty of the problemset. Only 3 solved in problem D2 (tourist and rainboy getting WA), 26k registered users but only 7k could solve problem A, some people beeing about top1000 without beeing able to solve problem B. The problems were quite intersting (at least trying them), but completely unbalanced.
I think the point distribution checks out. C is harder than a normal C, so it has 1750 points (more than usual), D1 is easier than normal D, so it has 1750 points (less than usual), D2 is worth 3750 points so it's harder than most D2F. B is oddly hard though.
Agreed. B is very hard if one lacks attention.
I think B is a problem that is very easy to overthink. I wasn't able to solve it, but the solution is the first idea I thought of (and rejected).
A was difficulter that average A, not only by the really low AC, the time that took thus AC is a lot for an A too. B gives only 250 point more than A and it was quite difficult and C was annoying to implement but not that hard to see the DP. D2 could be harder than most D2, but... what the point of having 3 out of 7 problems that won't be solved by more than 30 people? Even red coders can't solved that problem, I feel it's not worth it a problemset like this. Maybe for a global could work better
A is slightly harder than usual but fine. Hard A usually isn't a problem. C has annoying implementation, which is justified because it is worth more points.
On your point that D2/E1/E2 aren't solvable for most people: just treat this round as a 5-problem round. Ignore D2 and E2 and it becomes a pretty normal round: ABCD are all doable and maybe E is slightly harder than usual. It's fine.
Problem B gave me new neurons.
C can be solved for 3 rows too!
Code courtesy of liympanda https://pastebin.com/mjcPwbAa
literally what is idea behind of C?
how to be good at problem like this, it's so hard
C is a simple dp.. as we can't have 2 dimensions due to n being large to track both the first row pointer and second row pointer I just keep the first row pointer and the 2nd state being difference between first row and second row pointers.. The difference can never be more than 1 to be eligible for dividing districts.
can problem C be solved greedly ? DP was always at the back of my mind but I was too lazy to implement it(Maybe cuz am not very good at implementing quickly).
idts, you've choices to make at each moment and that can't be decided greedily
wtf was wrong with B ;;
What is the proof behind answer in B?
Suppose we have $$$C \geq \max a_i$$$ customers.
Imagine a box with $$$C$$$ rows and $$$x$$$ columns. Filling up your box column by column is sufficient.
and how do u know which car to put in which row?
Fill up every column of your box from up to down. Because $$$C \geq \max a_i$$$, doing so ensures that you won't place two cars of same type into the same row.
Thank you.. i tried with paper and pen using your approach.. It helped me upsolve this. First I did this below binary search that runs in nlog(1e16)
Later I was able to easily convert this to O(n)
i will never recover from B's trauma
Felt like I'm giving a div 1 contest today
I'm still wondering why my binary search on the answer solution didn't work on problem B. Can we say that the minimum "mid" >= max(arr) and mid * x >= sum(arr) would suffice?
BS works on B: https://codeforces.me/contest/2022/submission/285725858 P.S: Sorry for the overworked and terrible implementation :(
B made me feel empty.
In question C, 2nd test case, shouldn't the answer be 4?
We can divide it into 4 districts such that each one has 2 Js.
I wrote the solution but I didnt see test cases and now nothing makes sense,
Edit — I have to look for As and not Js. I am way too much sleep deprived, -_-
Why were A and B so hard? If they are going to be this hard, there should be more div 3 contests.
Agreed .
I solved problem B with binary search.
What is the solution of D1 ?
my solution was to group all people in groups of 3(ill explain how i handle if n%3!=0). so for each group of 3 you query 1,2 2,3 3,1 . and then lets say the type of the 1st guy is 0. then the type of 2nd guy and 3rd guy is fixed. and then you can check if the 3rd query contradicts the type of the 1st and 3rd guy. if this happens then you know that the impostor is one of these 3 guys, and you can basically brute force the solution. and if n%3==1 and we dont find an impostor then its the n-th guy for sure, and if n%3==2 you can just check both with the first guy, since we know the 1st guy isn't an impostor and find out which one is the impostor. this works in n+ 2 queries at worst. there is a simpler solution that ive seen though
Consider comparing two players with each other (ask each other about the other one). If the results of the queries are the same, then both are either knights or knaves. If the results are different, then one of them is the impostor. To find out which one is the impostor, compare them with a third player. So now, you can compare player 1 with player 2, then player 3 with player 4, etc. until you find the impostor. Submission
u can make groups of 2 people, u make they answer query about the other, in this groups of 2 if the answer are different then the impostor is one of them (u use n queries or n+1 and reduce the impostor to 2 candidates) then u pick one of those 2 and make a group of 2 with a third one, if the answer are differents then u have the impostor, otherwise the impostor was the other.
Thanks. Got it.
C is the worst dp problem i have ever seen
Maybe It's a div3 D or div4 E , nonetheless you need to get used to implementation to tackle such:)
B = guessing the answer and hoping it's correct.
not really. It's simple maths trick, it took me more than 20 minutes to prove this trick with pen and paper. Not everyone guesses. Guesses won't get you far.
Only mathematical proofs and intuitions will.
can you explain your proof?
There's nice proof by IceKnight1093
proof
how did you prove that trick, like i used that trick in an earlier problem where i was not able to come up with it so this time i knew after sometime what do but still i am not able to prove it
Try thinking this way,
0) N < K : This is very easy to understand. If the salesperson can convince to buy 'K' distinct items, then no matter what, we can Never sell 'K' items to the same customers ( since N < K ) . In this case, it is easy to see, ans is just Max of an array ( Because, everytime we will sell as many as possible items to the customer ).
1) N == K : Here also, similar logic like above. answer will be Max of an Array.
2) N >= K : This is crucial and tricky part. Implement Greedy logic on the sample test case [ 2 , 2, 3 , 3, 5 , 5, 5, ] for K = 4 . It is easy to see that, it is optimal to sell the items, which has the highest frequency. Everytime we pick top 4 elements from this array, and reduce their values by '1' and then again sort the array. After 2 operations, we will get this [ 2 , 2 , 2 , 2 , 3 , 3 , 3 ].
This is where I got the intuition. CONSIDER A SORTED MULTI-SET, WHERE WE ARE ALWAYS REDUCING 1 from TOP K ITEMS. How many operations it will take, to make the set empty ?
Every time we reduce 1 from top K member, the sorted set will sort itself and pick the optimal 'K' values in next time. This way, you are ALWAYS REMOVING 'K' ITEMS from the set ( except for the last time, where you will remove remaining (SumOfArray % K ) items ). So
answer = (SumOfArray / K ) + (SumOfArray % K > 0 ? 1 : 0)There is small edge case required, when the there is very large number in array, and we need to reduce that number every operation. To tackle this edge case, just take
answer = max(answer, maxOfArray)This is how I approached the solution.
I tried to brute force this problem using Multiset just like you said.
but i took the $$$x$$$ biggest elements and substracted them from the smallest one and then reinserted the new values to the multiset and repeat
why didn't this work ?
285732512
It won't work
Counter Test Case :
Reason : You are taking k largest elements and then subtract the minimum one from all those
but the optimal way is to subtract 1 from each and now perform with modified k largest elements from the array.
I hope it is clear. If not, then try to dry run the test I have given, you'll get it.
READ AGAIN , what I have written.
OK ok got it ! I haven't read your comment. Thanks for sharing
Ohk got it thank you
@ drexdelta
CONSIDER A SORTED MULTI-SET, WHERE WE ARE ALWAYS REDUCING 1 from TOP K ITEMS. How many operations it will take, to make the set empty ?
why did you not brute force it? i did in 285718545
what possibly went wrong?
If your bruteforce is passing then test cases are weak. The values are from 1 to 10^9. BF solution shouldn't pass.
no it is not passing. i was wondering why so I asked. Why though? isn't it like <= 10*(n) with n<=5e5 ?
it is failing on some test case and i do not know what is wrong in doing this BF
plz provide the proof, i cant think of it at this time
link to comment
B's easily provable, that's why it's B
Video editorial by adaptatron
Their video is for
x=2but same arguments hold here.I think this is a well known trick. i have solved something similar before, and I think it's not that hard to come up with the quick solution.
Yeah, it is well known, nevertheless I haven't seen a well known proof (other different form the greedy algorithm: always taking first $$$x$$$ greatest elements) xd I almost solve it but I missed the lower bound $$$max_{1 \leq i \leq n} (a_i)$$$ part.
I hope to see a good editorial with a proper proof for this kind of problems.
TLDR : just fill stuff cyclically, and it can be proven to be good
We want to prove that ans = max(ceil(sum / k), max(a[i])) is achieveable. Consider "ans" number of boxes (0 — indexed) each with capacity x
We do the following process :
This will always provide a valid arrangement. Why?
1) First condition : No box will have more than x things, well this is obviously true because ans >= sum / k, and we fill stuff cyclically
2) Second condition : no two things of same type end up in one box Proof by contradiction : assume that two things end up in same box, then it means that wherever we started filling type t, we returned back to it after cycling through everybody else. Therefore, a[t] > ans, but ans >= max(a). Contradiction
just binary search on the answer
Binary search always works here , if u get to this point(how to check for BS), mathematical formula makes much sense(and provable!)
Wrong Answer on pretest 2 for D2 :(
What was the problem with B..(am I wrong or they)??
How to solve B???
its quite standard problem (most time you've seen of breaking into two groups)
https://leetcode.com/problems/domino-and-tromino-tiling/description/ problem C looks much similar to this one, a DP exercise basically transformed to a new question!
Why did Problem B have the condition
x <= 10?i got WA on pretest 2 by doing something with a vector of size x, so maybe its to trick people? if i saw x was up to 10^4 or smth, i wouldnt waste 2 attempts on that, so it could be just to confuse people
My solution(285744957) for E2 using binary search to check when the answer is 0 got TLE. Is that a constant issue or did I write something wrong?
upd: It is a constant issue. I got accepted after removing some useless edges. See 285745386.
This was the first solution I came up with when thinking about the problem. There's also a couple of alternative solutions. There's also a way of solving the problem online in $$$\mathcal{O}\left(n\log(n)\right)$$$.
Mine (285739542) got TLE on Pretest 21 (technically only an E1 solution, but easy to make an E2 solution from it) — would also like to know if it's because of python or if there's a way to do it faster (in particular, I'm suspect of my
testfunction, which is just a BFS looking for a cycle, and doesn't update anything).What's the point of B? I've solve this problem at least twice before.
Thank you for the problemset! D2 is a very cool problem.
Sorry for commenting on this thread, but could anyone pls clarify my doubt in D1?
We know that if ask(i,j)!=ask(j,i) then one of them must be the impostor, However, I'm slightly confused as I queried on pairs that are distinct (i.e 1,n 2,n-1 and so on). Since the grader was adaptive, I declared j as impostor if ask(i,j)!=ask(j,i), since it's possible for any of them to be the impostor, and since the queries are independent of the previous ones.
Why do we need to verify again which one is the impostor once we get the above condition?
Can you explain your solution to D2?
For $$$n=3$$$ you can find out on paper what is the best strategy, and it turns out $$$f(3)=4$$$. For all other $$$n$$$, I made a strategy such that $$$f(n)=n$$$. Basically you can always take person $$$1$$$ and $$$2$$$, do queries $$$1 2$$$ and $$$2 1$$$, this detects the impostor. If you detect it, do two more queries to find out which of the two it is. If not, you reduced to a subproblem of $$$n-2$$$ people, and used $$$2$$$ queries. For $$$n=5$$$ and $$$n=4$$$ you need to write a special case which does the querying in $$$n$$$ moves. For $$$n=5$$$ the main trick is first querying $$$1 2$$$,$$$2 3$$$ and $$$3 1$$$. This lets you notice if impostor is one of $$$1$$$,$$$2$$$ or $$$3$$$.
Proof sketch of the lowerbound on $$$f(n)$$$: Lets look at the queries as directed edges that get added to a graph. If there are $$$n-1$$$ edges placed, then some node has indegree $$$0$$$, and some node has outdegree $$$0$$$ by pigeonhole.
Case $$$1$$$: If there are two different nodes with either indegree $$$0$$$ or outdegree $$$0$$$, then there are still multiple options of where the impostor could be, so if we always gave queries that are consistent, never revealing the impostor, the player cannot know where the impostor should be.
Case $$$2$$$: If the indegree $$$=0$$$ and outdegree $$$=0$$$ coincide, then the graph must look like a bunch of cycles and one isolated node. If we make sure that at the $$$n-1$$$'th query, if this query closes a cycle, and we would end up in Case $$$2$$$, we give an inconsistent answer now, such that the impostor is inside some cycle of $$$\geq 2$$$ nodes, then the player cannot know which of the nodes the impostor is in,
This proves $$$n-1$$$ queries are not enough to know exactly where the impostor is. And we have a strategy for $$$n$$$ queries, that does find the impostor, except for $$$n=3$$$ which is a special case.
Thanks, implemented and got AC.
I can swear I saw something super similar to E1 before (possibly but not necessarily on codeforces) — might have been sum instead of xor but it was the same underlying task of either finding a contradiction or counting the unforced cells by merging row restrictions when they share at least a column, does anyone remember any similar problem? Also it's NOT the atcoder one (Grid Integers)
Maybe Extending Set of Points? I found it very similar to this one.
Found what I was thinking about: Tick, Tock !
The condition here is being able to make all cells equal by adding 1 to either to an entire row or an entire column, which ends up being equivalent to each subgrid having equal sums of their opposite corners (a[i1][j1] + a[i2][j2] = a[i1][j2] + a[i2][j1]). Other than that it's the same idea — some cells are not occupied and we need to count the valid ways to fill them.
Just solved B (literally by luck), This is the most problem that ever made me mad, I hope that the tutorial will show why this solution is valid
D1 is much easier than C (they should be swapped)
I agree, but C is easy to think about but hard to code.
Having a C2 as the hardest problem is rather strange
B looks like a standard Q. Have a gut feeling that I have seen it before as well.
I have seen that many people are solving problem B with the following approach :
Use Max Heap priority queue and take k largest elements from the array and then subtract minimum from all k, then push non zero elements into PQ, and continue until PQ is not empty. (Even I have tried this during the contest)
But this won't work. Let me Explain why.
Counter Test Case :
Reason : You are taking k largest elements and then subtracting the minimum one from all those
but the optimal way is to subtract 1 from each and now perform with modified k largest elements from the array. (But this will give TLE because arr[i] is up to 1e9).
I hope it is clear. If not, then try to dry run the test I have given, you'll get it.
Would subtracting (min — 1) work?
nope.....the optimal way is to subtract 1 from each of min(k, remaining>0) largest then again choose k largest from remaining.
but this approach will not work because Complexity will be high
Thanks so much for the clear explanation.
Why constraint for D1 is n+69, not n+1 or n+2? Is it a kind of misleading to n+O(log(n)) solution?
Funny number
Because participants are not supposed to guess stuff from constraints :)
This is just a joke!
First solve :)
Why is your profile disabled?