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, --tofu--, -is-this-fft-, jamesbamber, franv, 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!
Best of look for the new year !
Bad for Chinese, I need to have dinner.
Happy New Year!
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.
Best of luck everyone
Me 2
Best Of Luck!
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
Turkmenistan
Urshjakmy????
Hoysy saher??
Balkanabat
Urşmaň çagalar!!!
div 2 too hard for me
Thanks for making the contest!
Good luck! May the force be with us!
Thanks Luke Skywalker
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
no
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
i hope i could back some rating this contest in which I lost 923 div 3, but div 3 was a fantastic contest
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
go to fight
Suffering from success
good luck!
Good luck!!!
chinese new year : (
GOOD LUCK!
Happy Chinese New Year! Good Luck!
Good start time for Asians
Good luck!!!
Skipping classes for this contest (my second contest)
This is my first comments. Happy new year!!! Please take care of me.
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.
Good start time,I need to work a lot!(After 1 week the semifinal of Olympiad will start)
3:05 PM ist Great timing...
Will Reach CM after this round
Good time. Today is Sunday + I'm free at this time
Good luck for everyone
Guess the rating of Problem
This will be a fantastic contest
good start time, i don't have to sleep
Good time, hope i solve A fast
Fantastic
Because my mind is more active at 17:35 (UTC+8)
I'm Chinese
Good luck!
I will have a negative delta but I will participate anyway
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
My first contest. Good luck everyone! Happy Chinese New Year!
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
thanks
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
not your legs
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://codeforces.me/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
How to solve problem B? what is wrong with my solution: https://codeforces.me/contest/1928/submission/245837687
may be i=j is not work
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
lmao
first time ever that I coudln't find an error in my solution for an hour in B :/
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
approach for B? I tried sliding window, got WA on pretest 3.
did you consider removing the duplicates? because two equal elements can never become same by addition of a permutation of some length. so we need only one, extras are just like my barin.. useless
yeah i removed duplicates
Then no idea, my sliding window passed
I solved B using binary search. Solution.
Good start time, i dont need to stay up late
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
sort arr
i used window slide and check if arr[right] — arr[left] < n
thanks
If put all the numbers in a numerical axis, what can you do?
Ihaven't idea
Maximum number of unique integers that can all be converted to a certain integer and this certain integer shouldn't exceed min(all(unique_integers)+n. The term unique is significant as it's evident from the test case 7,1,4,1 like u can only convert one of two '1's to a certain integer which is 5 here. Cuz for another '1' u need to again add 4 which is not possible in case of permutation.
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.
Nither good nor bad timing in india but would be better if delayed
B problem implementation triki but logic easy.
https://codeforces.me/contest/1928/submission/245807176
you can follow this for easier implementation
how i can do implementation easy way . please share your approch with me ?
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://codeforces.me/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
yeah, I have observed this though could not implement it efficiently, can u explain the time complexity pls
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$$$.
can you recommend similar problems for practice?
idk bro, do meth
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]
B should be difficult but not as much difficult, because then there is almost no difference between a lot of users. If you wanted to make B this much difficult then make A also a little more difficult.
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
anyone can give me a countertest of this submission for problem B??
now that the contest is over you can check the testcases
it's wrong on testcase 45 not showing
I wonder if this is an intended solution for E, or is this hackable.
https://codeforces.me/contest/1928/submission/245851958 (hacked)
https://codeforces.me/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
they told me no , but i have almost 150 points reduced lol
If the contest starts at an unusual time, at least mention it in bold. I overlooked the start time and missed the contest :(
Can anyone explain why A returns JUDGEMENT FAILED verdict in the beginning of the contest?
that is server issue, not our fault I believe
Because there were no pretests. Fortunately, it was fixed much sooner than I expected.
Why round with all math problems?
It happens. Anyway we inserted B (which was proposed for Pinely Round 3 (Div. 1 + Div. 2), then unused) precisely because it is not a math problem.
By doing so you did a great thing. That's funny, because right after I read the problems I said "Problems are too mathematical, although problem B is an exception and it's really nice". I feel really sorry for contestants who come to solve programming challenges, but get the contest full of math.
very classic problems. dislike
Bad start time, I need to have dinner.
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})$$$.
Even though I(my main acc) have +delta for this contest, I think it is mathforces. It's not all bad, I have some new math experience. But I think it is better, more satisfied to do algo contest.
first participated,but bad experience
Can anyone tell, whats wrong in my code for B?. Its failing on test 4 https://codeforces.me/contest/1928/submission/245858210
Take a look at Ticket 17338 from CF Stress for a counter example.
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://codeforces.me/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?
Finally able to do a Div2B with no penalties
Bad time.missed the round due to different timing.
CF needs to bring some UI changes on contests page.
Problem C video Solution here: https://youtu.be/AM6pz2H6JzQ?si=K5JXdOWcbTSiVyRV
Can someone help me understand why my solution isn't working for A problem: https://codeforces.me/contest/1928/submission/245856620
actually, your code gives wrong answer for a test case like this:
8 4you can use another two variables (for example x,y) for the input ,then:Thanks man, I can't believe I overlooked such a simple thing.
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)
My brother in christ, you are Chinese.
Can anyone plz explain y is there TLE for my solution of problem D. https://codeforces.me/contest/1928/submission/245999184 Link of my soln also the code is given below. This is my code for a single testcase:
void solve(){ ll n,b,x,mx_e=LLONG_MIN; cin>>n>>b>>x; vectorrace(n); rep(i,0,n) { cin>>race[i]; mx_e=max(mx_e,race[i]); }
vector<ll>army_str(mx_e+1,0); rep(i,0,mx_e) army_str[i+1]-=(i*x); ll to_p; rep(c,0,n) { rep(k,1,mx_e+1) { ll x=race[c]/k, y=race[c]%k; if(race[c]<k) { to_p = ((race[c]*(race[c]-1))/2)*b; army_str[k]+= to_p; } else if(y==0) { to_p = ((k*(k-1))/2)*x*x*b; army_str[k]+= to_p; } else { ll v=k-y; to_p = ((y*(y-1))/2)*(x+1)*(x+1)*b + ((v*(v-1))/2)*x*x*b + y*v*x*(x+1)*b; army_str[k]+= to_p; } } } ll mx=LLONG_MIN; rep(i,0,mx_e+1) mx = max(mx,army_str[i]); cout<<mx<<"\n";}