Note: The text editorials will be provided by the authors of the round. This video tutorial acts as an additional resource for those who prefer video over text, not as a substitute for the text editorial.
2022A — Bus to Pénjamo
Video
2022B — Kar Salesman
Video
2022C — Gerrymandering
Video
2022D1 — Asesino (Easy Version)
Video
2022E1 — Billetes MX (Easy Version)
Video
2022E2 — Billetes MX (Hard Version)
Video
Second comment XDDD
Thank to this contest which give me a chance to CM qwq
Congra XD
Nice contest,but didn't have chance to take part in it.
Oh! nice. Contest was at 1AM IST. Most Cheaters from India could not have participated.
U also didn't participate :)
Hard D2, but really amazing.
B
B was a very bad problem.
To all those who are downvoting this blog, please understand that this is not the official editorial and this guy had nothing to do with the preparation of the problems to be used for the round.
For solving D2, you gotta make three key observations:
Dang, I was so close to getting it :(. Thanks for the solution though!
How about n=3?
for
n = 3, the minimum number of queries is actually4. This is the only case where you have to ask> nqueries. For everyn > 3, you can solve it with atmostnqueries.i got it!thanks.
For B, I'm taking the max x elements from the array and choosing them (subtracting them by the minimum of this subarray), sorting the array again and then repeating until all elements are zero. It's failing at some 294th testcase, why?
Consider n = 3, x = 2 and the Elements {2, 2, 2}
According to your approach you would remove (seconds, third), (seconds, third), (first), (first) giving you an answer of 4.
Whereas you can pair up (first, second), (first, third) and (second, third) giving you ans answer of 3.
So what actually is the issue in the logic?
Issue is, you do not want to make a number 0 when you can decrement other numbers. This is done to ensure that you keep as many different models as possible to choose from. The brute force logic will be to keep sorting the array, taking largest x (or all if count is less than x) non-zero elements of the array and decrement them by 1. This needs to be repeated until all elements become 0. Obviously this will give TLE as array elements can go upto 10^9.
Issue is that the pairing logic its in the update rule you are taking maximum X elements and then removing minimum of these each step.
You logic works like this for {2,2,2}
Take {2,2} and make it {0, 0}
Now we have {2, 0,0} then -> {1, 0, 0} then -> {0, 0, 0}
But if we look at one decrement at a time take {2,2} in the first pairing decrease it by 1, {1,1} now the maximum 2 elements are {2,1} instead of {1,1} which will end up giving the right answer.
Your logic implicitly assume that the maximum elements don't change during the min(max k elements) operations, but if you work this out as shown above then you can see that they do change. So you would have to change your algorithm to account for that.
thank you. this was the best explanation for me.
I thought for a few hours and believe that I've got a perfect proof for problem B. But the comment section is too small and I can't write it down.
I also want know about your proof!.
Hell. I discovered that my proof is almost identical to the video tutorial. But, anyway, the proof framework for this problem is very advanced. You should try to play with it a bit.
Bro thinks he's Pierre de Fermat lol.
Shayan Why do we need to remove edge in E2 ?
People are saying that problem B is quite a famous and standard prob. Can someone suggest some sources where I can make myself familiar with more of these famous and standard problems? Thanks!
Where is text editorial :(
So，how can I see the text version of the solution？
did author forget about the text tutorial?
D2 is really interesting I think though I didn't participate
some ad-hoc constructive solution with 3-4 corner cases maybe?
actually not so many corner cases, just odd even and 3 :)