Hello Codeforces!
$$$\newline$$$
Do you know that eating cheese can make you code faster than the running speed of a Tyrannosaurus REX?
It's been a while, today GlowCheese and I are delighted to invite you to participate in Codeforces Round 963 (Div. 2). This round will be rated for all participants with a rating lower than 2100.
Our round will start on Aug/04/2024 17:35 (Moscow time). You will be given 6 problems and 120 minutes to solve them.
This contest is brought to you by Code Mely, a Vietnamese community for Computer Science. Reach out to us here.
Special thanks to:
- Akulyat for his wonderful coordination and translating our statements.
- Our testers: mzen, lmqzzz, i_love_huyhau6a2, _Fake4Fun, AkiLotus, LetterC67, McPqndq, Evirir, Lyde, Hihihah, Yugi.Hacker, uncle-T, Shz__, mp1309, phungthienphuoc, Etohari, moonlight_in_the_sky, hydroshiba, zeena., bibimoni, kodomo_tachi, StenSoSmol, ijljjl, and DOCUTEE.
- DeMen100ns, shine_, Asamai, Miko_UwU and nohandle_5 for joining with us.
- MikeMirzayanov for amazing platforms Codeforces and Polygon.
- KFC for their chicken nuggets.
- You for participating. $$$\newline$$$
Score distribution: $$$500 - 1000 - 1500 - 2000 - 2750 - (2500 - 1000)$$$
Hope to see you in the final standings!
UPD1. Editorial is out!
UPD2. Congratulations to the winners:
Div.2:
Div.1 + Div.2:
As a tester, TrendBattles orz
DA GOD, ORZ
My birthday is on contest day :)
Amazing!
Happy Birthday in Advance.
Me too
Happy Birthday :)
Happy Birthday!
Happy Birthday :D
Any idea when will points distribution updated
Orz
As a participant, I am here before the testers.
Oops, I'm late.
No, I'm late.
As a tester, I was too busy doing last-minute testing that I run out of good pick-up lines for contribution pleadings.
Also, I wanna say a lot but the authorities will shut me dow-
As a tester, i_love_huyhau6a2 orz
Hello, I don't have much time to tell this but as a tester I've known quite some things. Specifically for problem D you can solve usingdajpoiiadaodald;/;
Ahem... cough
Yes my lord, as a tester I am programmed to prioritize security and integrity of Codeforces rounds, and problem spoiling heavily damages the experience and trust of the majority of round participants, which can be considered inappropriate, or even harmful to the Codeforces community as a whole. I can offer suggestions for alternative positive problem solving methods that can be practiced for enhancing one's ability to compete in such Codeforces rounds instead. Please let me know if you would like me to assist you with any further requests.
No, I'm just having a flu.
get well
currently working on decoding dajpoiiadaodald
1 Hint: It's first query in first test
lookes like string problem + dp, it's my weakness
as a tester, i_love_huyhau6a2 orz
as a tester, i_love_huyhau6a2 orz
As a tester, I did nothing but still be mentioned.
as a participant, Asamai orz
em chao dai ca
orz Asamai, nga`i
As a participant,
I wasn't involved in any problem, thank you for noticing :D
As a participant, TrendBattles orz
as a random person on cf, TrendBattles orz
i thought it's
ChatGpt solved 0 probelm
As a testers, I tested all over the problems
Hope for reaching Master after after after this round.
I think you need a top-30 finish to gain this much. Good luck!
As a participant, i_love_huyhau6a2 orz
Hope to reach master before i die !
yo wtf
What extension are you using to differentiate everyone’s comments in your image?
I think everybody's just screen captioning one after another.
Imagine if one day your wish were granted, and codeforces permanently shut down the next day. You'd be immortal, but you probably wouldn't be immune to aging. That sounds like hell on Earth.
As the tester, I tested.
wooow impossible i don't believe that i didn't notice that testers test
as a participant, bibimoni orz
Can you spoil 1 problem? <(")
no.
=))
omg based frieren the slayer pfp
Best wishes to my purple friends, hope they become orange!
As a tester
As a participant, I know you are a tester
Wow,Marisa
patchy my beloved
https://i.imgur.com/Ym6joaX.png (imgur links not working D:)
Seems that nobody like my joke
And what's the joke?
The T-REX are d.e.a.d.
Oh, I got that joke about trex. I thought there's some hidden joke in that picture, you've posted earlier.
as a dino, :skull:
did you know that eating cheese can't make you code faster than the running speed of Jeffrey Epstein?
as a tester, i did literally nothing...
ngl it was the shittiest joke I've ever read
hydroshiba orz
why target him?
we love him
why does the round number doesn't show up in cf contests page? image
Watch your 6 homeboy I'm coming for your as-
As a Faze fan, I can confirm karrigan is the World No.1 IGL
Make you code? Shouldn't be make your code?
As a participant, i'm on hopium :D
i want to be tester
As a tester, I currently have no contributions.
ORZ
What is ORZ can you explain?
orz, lowercase, looks like a guy bowing
ORZ uppercase doesn't mean anything but people like to capitalize orz. If you want a capital version of orz, OTZ works.
oh my gad glow cheese round!!!!
As a participant, chikien2009 orz
What do you mean?
orz
As a GlowCheese fan, I will participate
will there be pics of the authors ?
sorry but... GlowCheese and *I =))
Oops, sure
As a participant, uncle-T orz
As a participant, khoad orz
As a contestant, I wish i can change be master
Still preparing cheese for the contest
Done eating 5 kg of cheese...
A faster submission doesn't need to be an AC ;)
hope to solve C and get +ve delta
I think it will be Permutation_force :(:(
Do you know that eating cheese can make you code faster than the running speed of a Tyrannosaurus REX?
is it some kinda hint or wot??
LongPinky208 pls comeback cf im begging u
Hoping you guys will make this contest fantastic
GlowCheese, thanhchauns2 oooooorzzzzzzzzzzzzzzz
oh, Vietnamese contest!!!
Hope to reach Candidate Master after this contest
All the best
should increase rating at least by a bit
rating distribution when?
As a participant, I hope I'm not choking in this contest
I hope everything goes well. I can play as well as I should in this game.And....stO Akulyat Orz.
As not a tester, how to become tester?
CM go go?
newbie to codeforces. any advices?
don't rely on the codeforces IDE
wish work out E today.
hope for Salah7_a <3
This made me happy <3
XD
great round!
good A B C, never again ^_^
may be problems are easy or difficult compare to other div2 round but i find it much difficult need to practice more
d and e are much harder than most div 1 and 2, let alone a div 2
My dislike to this contest is addressed not to the authors, who did a great job, but to Akulyat, who completely fucked up problem difficulty estimation. Awful work as a contest coordinator.
I'm sorry that the gap between C and D turned out to be that huge
Based on the testers' performance C seemed harder and D easier, so we assumed that the gap was reasonable
No luck. Unfortunately, it happens quite often to div2 rounds. Probably something is wrong with the way problems are being assessed.
I think it is a bit harsh to blame the coordinator for that as the problem difficulty assessment is based on the testers feedback (and the tester pool seems diverse enough). It turned out that D was maybe a little bit on the hard side (but it still got around 600 solves in contest which is reasonable imo). The issue might be that C is "too easy" as it has 7k AC so the round feels speedforces for some contestants. However, I believe this is more of an issue with the div2 format rather than problem selection.
Problem C is not "too easy". it has 7k AC out of which at-least 3k are cheated solutions.
SpeedForces!
I'm seeing a lot of people who were not even able to solve 3 problems in div3 or 2 in div2 in their past few contests have solved 1500-rated problem in this one. Are they suddenly becoming intelligent or what? If they are cheaters, will CF do something for them, or are they also silent like LC? I'm not aware of what CF does to catch them. Do anyone know, if they have a strong plag check or not?
C is easy for a 1500
yes it was slightly easy for a 1500 rating but still no that easy.
someone like me?
Actually, You have the strength of IGM.
actually, i'm an IGM
Multiaccount actually
casework orz
C and D are too far apart.
I was very mad...
Is D binary search?
Yes.
Dang, I kept getting WA and wasn't sure if it was correct. How does the check function work? I took all numbers greater than the one we're checking and did two pointers.
I binary searched on the answer and verified with dp. I kept getting MLE and it would've probably TLEd but basically create a new array $$$b$$$, $$$b[i] = (a[i] \gt = mid ? 1:-1)$$$ and now you have to find the maximum sum of the elements outside the intervals where you placed $$$ n/k - (n mod k == 0) $$$ disjoint intervals on the array $$$b$$$. If that sum is greater than 0, the mid is valid.
I think problem C has extremely weak pretest,
I passed pretest it without binary search O(n * k)
even wrote hack myself but anyway I didn't hacked :)
UDP: it actually passed systest wtf I'm so lucky
You don't even have to binary search, O(n+k) is possible, so yeah
i think the main tests is a lot harder
is binary search the intended solution? I solved it without binary search in O(n). At least I passed the pretests, I hope it doesn't FST.
Uphacked as per your wish :)
Thank you for the great animations in F!
Ordered sets got TLE in D, I suppose BIT is the intended solution? Didn't have time to implement at the end
UPD: nvm, in worst case for values $$$k$$$ close to $$$n$$$ and all unique values of $$$a_i$$$ this approach is both quadratic time and memory, regardless of DS used ;c
think about binary search
Binary search + DP.
Sounds evil, ngl
I did that only. https://codeforces.me/contest/1993/submission/274414638
The only thing that screwed me is I guess, the constraint mentionining final array should be more than 'k'.
I Please elaborate how to handle that edge case ?
the speed of solving B, C is normal or bcos of cheating?
plenty of cheaters these days. Just compete with yourself, learn new concepts and upsolve. Dont bother too much about the rankings or ratings.
seeing alot of people solve very fast/difficult problems (not normal) while u still didn't get it yet, not good feeling
F2 = F1 + CF710D
D is so hard that only 400 (unofficial excluded) solve it!
What a joke! 7500+ solved C — 500+ solved D
I really liked problem D, the fact that the $$$i$$$-th element of the resulting set must be in a position $$$j \equiv i (\mod k)$$$ is a really really cool invariant, and the resulting DP to check if a median is achievable is really nice as well.
ARGHH i think i solved F2 but i was about 10 mins too slow
basically from (0,0) -> (a,b) -> it will visit some nodes [k = 1] -> (x,y) -> (a+x, b+y) -> more nodes [k = 2] -> (2x,2y)
it's a (0,0) if it's a multiple of (2w,2h) or x'%2w = 0 AND y'%2h = 0
let W = 2w, H = 2h
let's say you're working with some coordinate (u,v) -> it's a (0,0) iff (u-kx)%W = 0, (v-ky)%H = 0
kx%W = u
ky%H = v
if gcd(x,W) not 1 then kx%W = -u eqv to k(x/gcd)%(H/gcd) = (-u/gcd) (same for the y case)
solve for k for each one (assuming there is a solution) -> k = u*lcm(H,W) + w -> then just check how many k exists between [1..k]
repeat for each coordinate (there can only be at most 10^6 of them)
In D, I tried doing binary search and converting the arrays into 1s and 0s based on if element >= mid. Now we basically need to choose more 1s and 0s. What do we do beyond this? I though of dp but thats n*k
Which elements of $$$a$$$ can be the first element of the resulting array after performing the operations.
More generally, which elements of $$$a$$$ can be the $$$i$$$-th element of the resulting array?
Using your "0/1" formulation, if you pick the $$$i$$$-th element of the original array as the $$$(i \mod k)$$$-th element of the resulting array, can you calculate the minimum number of "0s" till now using dp?
You are AWESOME!!!!
nvm.
Didn't read the question carefully.
In your states, if you try to minimize the number of remaining $$$0$$$, you don't need to remember how much elements you've taken (you will have to take at least $$$n \bmod k$$$ and there is no point in taking more). You just need to remember if you took at least one element in the case $$$k$$$ divides $$$n$$$. So you have $$$2n$$$ states.
I think it's a cool observation, congrats to the problem author :)
Damnnn thats actually cool
That is probably sufficient to pass, but FYI it can be optimized to a linear DP with $$$n$$$ states. We want to pick, sequentially, an element that is in a index with
1 mod k,2 mod k, ...,n mod k(using 1-indexed and considering the case wheren mod k!=0). The problem arises only when we "wrap around" and start taking1 mod k,2 mod k, ...,n mod k, ...,0,1 mod kand start taking more than the limit. This can be avoided by simply preventing the transition from0to1 mod kand instead settingdp[i]=(a[i]>=x)for every index $$$i\equiv1 \pmod{k}$$$. SubP.S. It's even possible to optimize it to $$$k$$$ states.
can anyone tell why this failed, this is hurting my brain 274401938
Take the case
{1,2,10}If you have to make two moves why not make it on the largest even element and in that way you can take all other element in one move
you need to run backward 1 more time cause there are some case where running backwards have smaller moves
Think in this example: 1 2 6 Your code gives answer=4 but the answer is at most number of evens+1, because you could turn the greatest even number into an odd number and it would be bigger than the rest of evens. If the greatest odd is less than the greatest even you can turn the greatest even into odd in 2 moves, otherwise it will take only 1 move.
How C?
Denote $$$\text{ans} = \max(a_i)$$$, iterate all lights and find the next $$$x \ge a_i$$$ that the light in question will be on, then assign $$$x$$$ to $$$\text{ans}$$$. Check if $$$\max(a_i) + k \lt \text{ans}$$$.
I don't mean any offence towards anyone! Just a joke
What is idea B?
Except for when all elements are even at first, the common parity of every final array is odd.
mathforces :(
A-D din't need any crazy math.(I don't know about the other problems) :)
A: sum(c)(max(0, cnt(c)-a)) for 'A'<=c<='D'.
B: Assume there are both odd and even numbers in a[i] (otherwise answer is trivially 0), because in each operation we can reduce count of odd numbers by at most 1 in each operation, and when there's only 1 odd number we can't change its parity, we need to change all numbers to odd. So we can add the greatest odd number to smallest even number repeatedly, until there's no even number. If we can do this, the answer is (count of even numbers). Otherwise, we can add the greatest even number to an odd number, and add this odd number to all even numbers, then answer is (count of even numbers)+1.
C: Let A = max(a[i]), the number of lights turned on will change with period 2*k after A minutes, and the answer cannot be small than A, so we only need to check range [A, A+2*k-1] using prefix sums.
D: Let's find the answer by binary search. So for certain M we need to change a[i] to 1 when a[i]<M or 0 otherwise. Then we need to choose some remaining indexes {i0=0, i1, i2, ..., i_r, i_(r+1)=n+1} where i_(j+1)-i_j-1 is multiple of k (0<=j<=r), and sum(a[i_j]) is minimized. We can solve this by dp: let dp[i] = the minimum sum if we let i_r=i. Then we have dp[0]=0, dp[i]=a[i]+min(0<=j<i, j%k==(i-1)%k)(dp[j]), the minimum valid sum is min(1<=i<=n, i%k==n%k)(dp[i]).
D is somehow similar to https://codeforces.me/problemset/problem/1486/D
E: Thinkless $$$O((n+1)^2(m+1)^2 (2^n+2^m))$$$ cooked me (I need one more optimization to get AC)
btw, in this kind of problems, why not limit $$$t \le 10$$$ (small constant) or use single test, instead of complicated bound for one input?
Single test leads to having too many tests. Since the resources are limited, it leads to worse coverage.
If we do $$$t \le 10$$$, then we can have $$$10$$$ large tests or $$$10$$$ small tests, meanwhile we want to have just a couple of big tests (otherwise the complexity would be multiplied by $$$t$$$) or lots of small tests (for better coverage)
TBH, $$$\sum (n^2+m^2) \le 500$$$ seems very heuristic and I think it's difficult to determine which complexity is acceptable.
This problem is D2E, so the limit of #tests isn't have to tight I guess.
The limit was set in such a way so as not to let determine the complexity based on it
Is judging cooked? Some early submissions are stuck in queue (including my A)
i think so i have same issue with problem B still in queue
same, all problems i passed pretest are in queue
any idea why it doesn't work for B ? https://codeforces.me/contest/1993/submission/274399672
1
3
1 20 40
your code returns 4
correct answer is 3
1 20 40 -> 41 20 40 -> 41 61 40 -> 41 61 101
Cheaters must be stopped before it runs into Cheatforces
Problem C by 7k+ people. It's a sure shot cheating case. Please do look at it :)
Either that or just really weak pretests on C (lots of O(nk) sols passed)
Can anyone tell why O(N*K) working for problem c https://codeforces.me/contest/1993/submission/274391283
Problem D: Find error in my logic, it is giving WA (176th number) on test case 2
274418415
Hey everyone
can someone please tell me why my solution for Problem B — Parity and Sum is WA on test case 2
My c++ solution:
I think the intution is same as per the editorial
my submission
whenever you would do ans+=2, you can just break and print out the amount of even numbers+1, because if that ever happens, then its optimal for it to happen to the biggest even element, after which you will always be able to just do it in 1 step. i hope i explained it well
Consider this case :
4 ----> 2 6 10 1
according to your code answer will come 5, but answer is 4 1 + 10 = 11, 11 + 10 = 21, 21 + 6 = 27, 27 + 2 = 29
Sorry I didn't get it why ans will be 4 (I think you're missing updating 4, we just updated 1,10,6 and 2)
4 is the array size.
Link of editorial don't work
update : it is working now : )
The test of Problem C is too weak. Many people accept this problem with a solution which has time complexity of O(nk).
There are already more than 100 fails on my uphack on C. I can't even imagine how many on-contest solutions would've failed if this was on systest.
Thank you the authors and
Code Melyfor the awesome contest! I enjoyed it a lot!I think the cases were too weak for problem B and C. Many submissions of O(n*k) for C are accepted and for problem B https://codeforces.me/contest/1993/submission/274429127 this code runs for 10^16 how? MikeMirzayanov thanhchauns2
It's Gcc optimization
it gets compiler optimized...
Omg Dominater069 Orz. Can you please tell me more about this. I don't know what GCC optimisation is
Those loops don't make any actual effect on anything, and the compiler can notice it just by analysing the code. So therefore it just entirely removes the loops so they become non-existent.
Why does it work, i can't understand.
Can't open tutorial. I'm getting this error:
You are not allowed to view the requested pageThe same
thanhchauns2 GlowCheese please make it public.
Fixed!
I solved ABC under an hour as a 1000 rated. C definitely seemed easier than almost all Div 2s I’ve done.
2 pupils in top 5 beating all candidate masters sounds fishy. Moreover they aren't new accounts either. The guy at rank 1 had 10k rank in last contest and 8 in last to last. Don't you think it's too strange of a variation?
that's because he tried the rainboy style solving in the reverse order
still 2 pupils having lgm perf just screams alt accounts
B, D, and E are great problems <3
Problem C was not qualityfull at all whereas B was enough good
Thank you to the authors and coordinator for the nice problems!
D is a great problem, but F2's trick is trivial :(
i think it'll be better if swap(E,F), E is much harder than F for me.
Funny, while testing I keep baffling myself at "why don't people solve E? it's straightforward as heck".
Actual contest seems to show the opposite of my opinion, heh...
I wasn't able to solve D in contest because I didn't think in terms of binary search and then converting the array to binary and then solving it using DP.
Is it a known technique, which I am not aware of or are there more questions like this?
I want to solve them and learn as it isn't intuitive for me yet.
I think the data of problem C is a bit weak. I used the method of O(nk) with a little trick and then passed problem C.
.
Bruh, it is skipped because he submitted it again, and only the last submission is judged in the contest
I hate Median
7k people solve C? That's impossible. I almost become expert, but I didn't solve C and get -80 scores, that really hurts : (