Hello, Codeforces! We're glad to invite you to take part in Codeforces Round 924 (Div. 2), which will start on Feb/11/2024 12:35 (Moscow time). You will be given 6 problems and 2 hours to solve them.
This round will be rated for participants whose rating is below 2100. Participants with higher rating can participate unofficially.
The problems were authored and prepared by vaaven, silvvasil, Alexdat2000, teraqqq and me.
The round is based on Moscow Olympiad for school students.
We would like to thank
- TheScrasse for his high-speed coordination;
- nor, Wizard_of_Orz, GreatEagle, rolandpetrean, volochai, A_G, Wobert, crispy-tofu, -is-this-fft-, jamesbamber, francesco, MatteoArcari, sum, rayban, Be11T_, sashastrakhal, ihavenoenemies and cowgirl for testing;
- MikeMirzayanov for creating Codeforces and Polygon.
Score distribution: $$$500 - 1000 - 1500 - 1750 - 2250 - 2750$$$
UPD: Editorial
UPD2: Congratulations to the winners!
Div. 2
Div. 1
Good luck to everyone. I hope to reach expert in this contest.
congrat you reach it
Thank you.
contemplating taking this contest at 1:35 AM :)
The start time is good for Chinese.
Today is Spring festival eve.Happy new year!
The start time is perfect for middle east:).
happy new year!
Bad for Chinese, I need to have dinner.
GOOD LUCK!!!
GOOD DUCK
bed time for pacific programmers
bed time for pacific programmers
sleeping time for pacific programmers
Hope to maintain my specialist rating.
Hope that Delayforces won't come again
Good!
need to run out of college class to attend the contest
College class on sunday?
in my country Sunday isn't a holiday , Friday is
which country ?
Bangladesh
Good luck! May the force be with us!
As a tester for this round, this round is great, please participate!
Good start time.
I can participate in contest instead of going to school :)
as a tester, i can confirm that the problems are problems
as a tester, i too can confirm that the problems are indeed problems
as a participant, it will be amazing to solve problems which are problems xD.
Hope to become master after this.
Finally :)
Congrats!!
As a taster, the contest was delicious and I ate the problems
Nah I'd Win (I will most definitely lose)
(JJK Special joke, hope you get it) First problem: Divide this element into two...
Lol, problem A actually involves dividing into two parts ... cut midway
lmao
bad start time, I've school ig I'm gonna be "sick"
lets see if i can become specialist
Bad time contest for New York contestant
The round is based on an official russian competition. I don't know why the authors decided to support the existing system by organizing official events, but I encourage other users to avoid this mistake. Many other competitions are more worthy of your problem ideas and participation.
bro look at your profile picture, i can find it googling "cute авы стим аниме", you can't be taken seriously XDD just go chill somewhere, no need to litter here
orz
Hope to get a negative deltaa so that div 3 becomes rated for me.
Come to my level and you can enjoy smurfing in Div 4 too then
Rankup time...
6 contests in a row!
well, yes, to each person according to his taste
Suffering from success
Good luck!!!
GOOD LUCK!
Today is a special day for the Chinese (the second day of the Chinese New Year) and it's also a good start time for the Chinese.I think it may be a wonderful contest.
Let's skip class and reach specialist.
Will Reach CM after this round
Guess the rating of Problem
Good time, hope i solve A fast
Fantastic
Because my mind is more active at 17:35 (UTC+8)
I'm Chinese
Good luck!
Happy Chinese new year!Good luck to everyone.
Any ways the start time is good for India. Sunday afternoon :)
I wish I will have positive delta during Chinese New Year!
I hope be expert in this contest!
may the force be with you
First CF Contest
Hoping to reach expert with this round
lesgo
Judgement failed?
glad to see another Mathforces round.
nice math contest
I am considering whether to die or not,because I only complete question A.
B is just sliding window.
My code fails in system test.
EDIT: it didn't fail :)
Emm...Are you wanting A cute new student who has only studied for one year to realize that?
Well atleast now you know the name of one more topic that you must learn. Pretty useful, unlike some of these questions that just require math
was there system testing this round ? cuz the results were declared so fast
yes, It completed in like 5 mins
do u have any idea why it was so fast though, the last div3 took atleast an hour
There are less tests than usual in problems A and B.
А раунд был основан на Московской Олимпиаде по Математике? =)))
MATHFORCES :((
Did they assume us mathematicians?
is $$$D$$$ binary search?
Yes. Observe that as you increase the number of squads, the amount lost by b only increases by a fixed amount(b), while the amount gained from adding a new squad, decreases as you add more. Therefore, we should find the amount of squads at which adding a new squad gives less than b. Since the amount given by a new squad decreases monotonically, we can use binary search.
yeah bro I mind solved it but didn't have time to implement , wasted a lot of time in $$$C$$$
Though binary search may work, it isn't actually needed to solve it.
You can just realize that the number of pairs for a group with $$$c_i$$$ members only increases till the number of groups becomes $$$c_i$$$, so you can just recalculate it for each $$$1 \leq \text{squad size} \leq c_i$$$. This runs in $$$O(n + \sum {c_i})$$$ which is fast enough for the constraints.
Code — 245818007
ExplodingFreeze why your solution passes time complexity,
N : 10^5
max(c): 10^5
O(N*max(C)) = TLE right? please explain if i missed something
You actually don't have to recalculate every time (I see that he used the pop_back function for the optimisation), so the solution is only O(N+C)
See the last line of the input section — "It is guaranteed that the sum of the values $$$c_1 + c_2 + \cdots + c_n$$$ over all test cases does not exceed $$$2\cdot10^5$$$."
So $$$O(n + \sum{c})$$$ is by definition fast enough.
This is a convex function, which can more easily be solved with ternary search.
kind of, I get AC with a ternary search for the amount of groups we are doing, run time is O(n * log (max C))
Hint for C please
consider 2 cases x is in between 1..k or in between k — 1..2
Yeah, I considered those cases, but still unable to come up with solution. What I came up with after doing some calculations is to find number of even factors of (x-n) and (x+n-2) such that size of one unit of repetition is atleast n. Is this approach correct?
for even a factor i you have k = i / 2 + 1 in first case k >= x and in second case k > x
my code got accepted just by changing condition from factor>=n to factor/2+1>=n. still couldn't understand why...
That's because factor is 2k-2
thanks! I was putting constraints on (2k-2) instead of k lol
Good contest, interesting problems. Thanks to the authors.
how to C
open your eyes
How to solve D?
notice that sum of c[i] <= 200000 => number of different c[i] is at most sqrt(200000) => simply iterate over all possible num of squads in O(max(c[i]) * sqrt(200000))
I tried that approach and got TLE during contest. https://mirror.codeforces.com/contest/1928/submission/245833868
i had the same mistake. in every test you create vector of size 200000, which gives TL.
You are genius. Thank you!
Suppose a group with $$$c_i$$$ members is divided into $$$k$$$ pairs, then it is optimal to split it into groups of size $$$\lfloor \frac{c_i}{k} \rfloor$$$ and $$$\lceil \frac{c_i}{k} \rceil$$$ to maximize the number of pairs. You can trivially calculate the number of groups of each size and the number of pairs for a given $$$c_i $$$ and $$$k$$$.
Then just realize that the number of pairs for a group with $$$c_i$$$ members only increases till the number of groups becomes $$$c_i$$$. So if you iterate on squad size in increasing order, you can just recalculate it for each $$$1 \leq \text{squad size} \leq c_i$$$ and then maintain the last value in a common sum. This runs in $$$O(n + \sum {c_i})$$$ which is fast enough for the constraints.
Code — 245818007
bad F.
Problem D: binary search on answer(no. of squads) because the target function has only one extreme large value
i think it's ternary search
I didn't wrote this algo but I read a code when hacking. I think this algo is right, because it's a quadratic function which has only $$$\le 2$$$ max value. But I prefer the $$$\Theta(\sum c_i)$$$ solution better :).
but how do we decide whether to increase lower bound or upper bound during binary search i was thinking of BS but above confusion made me quit it
with binary search you can check whether it is increasing or decreasing
ternary search is easier though as someone said
I applied binary search but I think I will get FST soon :(
How did you check if the answer from bin sh can be obtained?
U actually did ternary search :|
I am not certain of it. It can definitely have 2 maximums of equal value.
I did solve it with binary search on
f(m)<f(m+1)but I was not certain if it is monotonic until max. I did see 2 equal maximumsf(max)==f(max+1)You are right, 2 adjacent maximums are possible, I didn't mean to be precise on my og comment
first time ever that I couldn't solve A, I still have no idea
extremely frustrating actually
Very dramatic that hmmmmm solved problem F in the last minute(may win a prize in some contests) and became the only AK. Congratulations!
Thanks!
Very dramatic that 74 solved F in the last 10 minutes. Maybe he is (re-)learning to setting problems.
bro that joke got me dying never joke again pls
Really tough B
I found D easier than C.
solved D within 30+ min and wasted 1 hours in C :3
If the round is based on some olympiad, I guess it's understandable that the authors didn't have the time to fine-tune the TLs for codeforces, but still repeatedly getting TLs in F with $$$\mathcal{O}(n\log n)$$$ was pretty frustrating
STFU BUNDLE OF STICKS
Had to google what that was (in this context), haven't laughed that hard in a while, thank you lol
Anyone else spend a long time without realizing that the triangle numbers start from "0" in E? I spent like 1 hour trying to think about how to calculate both exact length and sum before realizing right at the end that only min length was required T_T.
Can you please elaborate how you mapped E to triangles and how to solve it ? It seems very interesting as the problem does not seem to be about geometry superficially.
Triangular numbers are of the form n*(n+1)/2 where n is a natural number.
I want hint for B
If put all the numbers in a numerical axis, what can you do?
I got WA2 on problem E. What is incorrect in this solution?
$$$x \; mod \; y$$$ subtracts $$$y$$$ from $$$x$$$, so it makes sence to work with multiples of $$$y$$$. Look at this sequence: $$$a_1 \cdot y + p, a_2 \cdot y + p, \dots$$$, where $$$p = x \; mod \; y$$$. Then either $$$a_i = 0$$$ or $$$a_i = a_{i-1} + 1$$$, so this is a sequence of arithmetic progressions.
What is the sum of sequence? It is $$$\sum_i{(a_i \cdot y + p)} = y \cdot \sum_i{a_i} + n \cdot p = s$$$. This gives $$$sum = \frac{s - n \cdot p}{y}$$$. Check that this is an integer number.
Now our problem is to find sequence of arithmetic progression with given length $$$n$$$ and sum $$$sum$$$. We can find minimal length instead, and after it append zeros at the end. Let's first $$$a_1 = 0$$$. This is a simple $$$dp$$$. We iterate over length of additional progression. There are $$$\sqrt{n}$$$ of them, so it takes $$$O(n \cdot \sqrt{n})$$$ time.
How about $$$a_1 = \frac{x}{y}$$$? Let's just iterate over all prefixes-progressions and find the best one prefix.
Did you test your code on this?
Some solutions will fail when $$$y=1$$$.
Oh, no. The problem was following:
instead of
Anybody knows greedy doesn't work here?
Greedy for making sequence of arithmetic progressions? If taking maximal progression, then no.
$$$12 = 0 + 1 + 2 + 3 + 4 + 0 + 1 + 0 + 1$$$ — greedy.
$$$12 = 0 + 1 + 2 + 3 + 0 + 1 + 2 + 3$$$ — dp.
B problem implementation triki but logic easy.
https://mirror.codeforces.com/contest/1928/submission/245807176
you can follow this for easier implementation
Why anyone would just cheat to get better rank? For real I don't know how you doin that and u think u are good but the fact that u r cheating
Problem C is not that easy to get 3k accept
Fu*k youtube channels and telegram and anyone that take anything from them
they will most likely get plagged and the round will get skipped for them negatives included
why don't you cheat?
How to solve the problem c? I got TLE with this solution: https://mirror.codeforces.com/contest/1928/submission/245842512 anyone please explain.
Notice that the position where x appear is x and 2k — x adding 2k — 2
so what you need to do is calc the number of k satisfy n % (2k — 2) = x or n % (2k — 2) = 2k — x
I understood the part where we need to find all divisors for n — x, but why do we need to check the n + x — 2. Can you help me please?
Case $$$1$$$: $$$n\mod (2k — 2) = x$$$.
This means there exists some $$$y$$$ such that, $$$(2k - 2) * y + x = n$$$ $$$\rightarrow$$$ $$$(2k - 2)*y = (n - x)$$$. So, if we find divisors of $$$(n - x)$$$, we can find the candidate values for $$$k$$$.
Case $$$2$$$: $$$n\mod (2k - 2) = (2k - x)$$$.
This means there exists some $$$y$$$ such that, $$$(2k - 2) * y + (2k - x) = n$$$. Subtract $$$2$$$ from both sides, $$$(2k - 2) * y + (2k - 2) = n + x - 2 \ $$$ $$$\rightarrow$$$ $$$(2k - 2)(y + 1) = n + x - 2$$$. So, if we find divisors of $$$(n + x - 2)$$$, we can find the candidate values for $$$k$$$.
I have applied Binary search on 1928D - Lonely Mountain Dungeons and got Accepted, but I think my solution can be hacked. Try it.
How did you divide
c[i]inksquads optimally, heres += b*(c2(c[i])-(c[i]%g)*c2(c[i]/g+1)-(g-c[i]%g)*c2(c[i]/g));in functionst.sorry if my explanation is bad
Thanks a lot bro ! Appreciate it.
[deleted]
Bad start time , i need to eat dinner with my family during the spring festival.
Well balanced round although a bit mathy.
GOOD ROUND !!
On my way to Specialist
I wonder if this is an intended solution for E, or is this hackable.
https://mirror.codeforces.com/contest/1928/submission/245851958 (hacked)
https://mirror.codeforces.com/contest/1928/submission/245926933
The problem can be reduced to constructing an array of length n of sum z where
The strategy is to greedily increase, except for the following scenarios
In other words, the only times you do not go greedy is when the constructed array ends in
[..,0,1,2,3,4...,n,(and maybe a few more zeroes)]
or
[..,0,1,2,3,4...,n,0,1,(and maybe a few more zeroes)]
or
[..,0,1,2,3,4...,n,0,1,2,(and maybe a few more zeroes)]
I tried this exact same logic, but it didn't work. I wonder why though...
I found that maybe 0,1,2,3,4,0,1,0,1 is worse than 0,1,2,3,0,1,2,3
The greedy algorithm I have described covers this case, it knows it can end with 0,1,2,3 and so it will not increment.
Very tricky E!
Welcome to Mathforces dot com
Can someone explain in for testcase 3 in D why the answer
1 1 5 5 16
is 525? I calculate 530 when I use 10 squads. I even did a brute force of the squads and get the following
1 0 2 315 3 415 4 465 5 490 6 505 7 515 8 525 9 525 10 530 11 530 12 530 13 530 14 525 15 525 16 525
Disregard that. I think the issue is with the formula I was using.
Can anyone tell me if the penalty applies only for solved problems? If I have submited 3 wrong answers for a problem but I fail to ultimately solve the problem, will my overall points still be reduced by 150? Thank you.
Yes u get a penalty of a wrong answer only after solving the problem
If the contest starts at an unusual time, at least mention it in bold. I overlooked the start time and missed the contest :(
very classic problems. dislike
Bad start time, I need to have dinner.
Очень хороший раунд! Задачи классные, быстрое изменение рейтинга и авторы общительны! Поздравили меня после того, как я решил Cшку! 9.95/10
D could be solved with brute-force, by fixing the number of squads, and iterating over the races with population higher than the fixed value.
It is $$$O(s \sqrt{s})$$$ actually, or something like that
Actually, I think it works in $$$O(N \log N)$$$ where $$$N = 2.10^5$$$ as $$$\sum_{k=1}^{N} \frac{N}{k}$$$ is $$$O(N \log N)$$$, and the sum of values of $$$c_i$$$ is bounded by $$$N$$$ in all test cases. I don't have exact proof but it passed in 31 ms, and I don't think $$$O(N \sqrt{N})$$$ is that fast.
I guess it is just because of the weak tests. It is exact $$$\mathcal{O}(n\sqrt{\sum c_i})$$$.
Can anyone tell why my code for problem B fails so hard on test case 3?
One quick observation: when you update your answer, you should use max instead. This way, you get the best answer (largest possible interval) and not the most recent one.
Well I get the largest possible interval anyways because r-l only gets smaller in the code I wrote. The only possibility is that my approach does not yield the optimal answer, and I'd like to know why that is.
Makes sense. Indeed, your algo doesn't get the optimal answer sometimes. A good strategy to prove this is to find a good counterexample.
What you are doing is you make the interval to consider smaller based on which difference in values of either the right or left end is bigger. Let's try to find a correct answer that exploits this.
Try for example: [1 2 3 501 502]
The optimal subarray is [1 2 3]. Notice that your algo disregards 1 at the first iteration, so that's a valid counterexample.
A hint to solve the problem: assume that we have a set of (distinct) values and we want to make them equal using a permutation. Try to find what condition we need to have in order to make all the values of this subset equal.
Let me know if you need more help! :)
Thanks for helping me find a counter example to my code. I managed to get AC just by switching the implementation from l=0 r=n to l=0 r=0, and it indeed gives a correct answer. Thank you once again :D
I had good contest but the ratings was too bad and I got positive rate only for 14
can someone hack this solution? -> https://mirror.codeforces.com/contest/1928/submission/245838079 this solution uses unordered map and i think it can be hacked?
or maybe it's impossible to hack because d(n) is very small
Square_root_forces
i wish there was at least a reminder that we could put even so the start time is bad anyways so
I don't really believe this solution for problem E is correct, but for some reason it passed all the tests:
Brute force the largest index
ibefore we take element moduloy.For the rest of the array (after index
i) try to distribute sum across the elements greedily (it gets WA11 without the next step).Before doing the greedy thingie, try to remove prefix of length
L(Lis from0to10) and pick the way with the least number of elements required.Am I right that this solution doesn't look correct?
Bad time.missed the round due to different timing.
CF needs to bring some UI changes on contests page.
Эти бро реально сделали контест из задач МОШа.
One of the most interesting contest I've ever written, Thanks)
Thanks to the round, finally an Expert
not yet xD
Rating rolled back lmao
A really good contest, even though the contest inspired by olympiads are generally more mathematical than usual but this one had a great balance. Great work by authors!!
.
Honestly I don't think this contest should be regarded as mathematical, as least the first five problems (which I solved during contest). I'm only a junior 2 student that had only learnt junior high school math and a little of senior high school math, and I have no MO background. I believe lots of people have an age larger than mine, so imo they have math knowledge better than me, st they shouldn't think this is a "math" round.
I've faced many times that people say that "... round is full of math", but I usually cannot understand (once was a round I VPed when I'm in primary school)