Hello Codeforces!
MathModel Setting Tour Continues!
I'm glad to share my tour of problem-setting with you! Recently, I have been setting problems for multiple platforms such as CodeForces Gym, CodeChef, KEP, and more is coming $$$!$$$
We are happy to invite you to RoboContest Round #103 (3.14), which will take place on Friday, March 14, 2025, at 17:30 UTC.
📅 Duration: $$$3$$$ hours.
📝 Number of Problems: $$$9$$$
📈 Rated for All on RoboContest
😎 Statements Avialable in English , Uzbek and Russian
The Round Maintaining Team:
- 🏆 devasadbek & rshohruh – Coordinators
- ✍ MathModel , Timosh and Nasa – Problem Writers
- 🔧 Denisov ,Timosh,azizbek_, Nasa, cry, Satoru, chromate00, RobinFromTheHood , tristansun , Think_Only_Once – Testers & Feedback
- 💙 Nasa for being The honorary savior of the round , Suggestions for Preparation and Statement Translations.
- 💙 Timosh for letting me know about Mr.Robot.

Mr. Robot wish you $$$(\Delta \gt \pi)$$$ and Hope you find the problems enjoyable.
UPD 1: All Cheaters with Confirmation of using of AI Tools Got Banned from the contest , All the banned participants have been reviewed.
UPD2 : Congratulations to Winners ! :
- physics0523
- Sunnatov
- Husanboy
- vako_p
- diobrando97
- heaven2808h
- Edeeva
- Isamatdin
- conqueror_of_timosh
- Sardor Salimov
UPD3 : Editorial








sto sto sto MathModel orz orz orz
As a tester, I forgot
As a tester, problems are great
as a participant, i hope i'll reach M (at robo)
As a tester, please participate and enjoy:)
As a participant, I hope this contest will be legendary!
As a tester, I can confirm it will be
As a forgetful tester, I can't remember much! GLHF!
As a tester, I tested
It's now advertised on Codeforces.com. It's going to be a lot harder. Because GMs will see it.
As a coordinator, thanks to MathModel
As a coordinator, I'm busy waking up testers
I signed in robocontest and should write any Uzbek region and shool I guess. I hope there's an option of just leave it as empty.
Auto comment: topic has been updated by MathModel (previous revision, new revision, compare).
Auto comment: topic has been updated by MathModel (previous revision, new revision, compare).
Auto comment: topic has been updated by MathModel (previous revision, new revision, compare).
Auto comment: topic has been updated by MathModel (previous revision, new revision, compare).
New problems added to ensure an interesting competition for all contestants , Please Participate :)
$$$9$$$ Problems in total and $$$3$$$ hours.
what is the real beginning time at robocontest, because it is set to 22:30 — 1:30. Will you fix it?
Fixed .
Contest starts in 1 hour
Why I was suddenly became unregistered during the contest? As a consequence, all my submissions on the scoreboard have vanished and I needed to resubmit them (with a much bigger penalty) to get back on the scoreboard.
Explain please.
Why my result disappered again from the leaderboard? And rating change wasn't applied? And why I wasn't mentioned in top-10 in the blog? And why I was suddenly became unregistered during the contest? As a consequence, all my submissions on the scoreboard have vanished and I needed to resubmit them (with a much bigger penalty) to get back on the scoreboard.
Explain what is going on please.
Is there an editorial in this contest?
Which problem do you need an editorial of?
I haven't solved G and I, but I guess I can solve problem I by centroid Decomposition. I don't have any useful ideas for G.
How can you solve it with centroids? I only know $$$O(n\sqrt n) $$$ solution using rerooting and sqrt-decomposition for maintaining distances from the root.
My idea is quite similar to the editorial (though I spent a lot of time debugging my dirty code). First we know that for a query $$$q(point, l, r) = q(point, r) - q(point, l - 1)$$$. During the centroid decomposition, we need to construct the centroid tree. For each centroid $$$cen$$$, and in the subtree rooted by $$$cen$$$, I want to quickly know the sum of all nodes within a distance <= x from $$$cen$$$, denoted as $$$presum(cen, x)$$$. For a query $$$q(cen, r)$$$, we need to climb from $$$cen$$$ to the root in the centroid tree to accumulate all contributions. When climbing to a node $$$i$$$, the contribution is $$$presum(i, r - dis(cen, i))$$$. However, this will lead to double-counting, so we need to subtract the contribution from the path between $$$cen$$$ and $$$i$$$. Therefore, during the centroid decomposition, we also need to record the $$$presumson_j(cen, x)$$$ for each subtree $$$j$$$ of $$$cen$$$. BTW, I feel the implementing of square root decomposition method is also quite complicated.
will be posted soon
As a participant, problems were good. But in problem G why O(n*d(n)) does not works?
Why am I specialist?
You can it with Legendre's formula
$$$O(n \cdot d(n))$$$ doesn't work because consider max test which is $$$(n=960960)$$$ with $$$d(960960)=224$$$ , this yields a total computations of $$$215255040 \approx 2\cdot 10^8$$$ which isn't good within $$$1$$$ second.
notice that the set of prime factors common between numerator and denumerator are the same and in the numerator for each power of common it’s at least has the same power as den and We’re aiming to minimize the product thus we need to make a divisible by b (for each prime separately) so whenever we had an even power for some prime the best thing is split it into equal parts.
Calculate sieve for all numbers upto $$$2 \cdot 10^5$$$ this can be achieved in $$$O(n \log(\log(n)))$$$ which is fast , Find the prime factorization of $$$n!$$$ this can be found with the prime factorization form of $$$n!$$$
For each prime factor $$$p_i$$$ the power $$$\alpha_i$$$ can be calculated with the following formula
it can be show that this sum converges in $a$ , $$$O(\log(n))$$$ it’ll take no more than $$$20$$$ runs , thus the final prime factorization will take $$$O(20p)$$$.
Now we want to have $$$a \bmod b = 0$$$ (assuming fraction $$$\frac{a}{b}$$$) , so a productive greedy is to have for each $$$p_i$$$ with power $$$\alpha_i$$$ the following : for $$$a$$$ the power is $$$\displaystyle \left \lceil \frac{\alpha_i}{2} \right \rceil$$$ and for $$$b$$$ the power is $$$\displaystyle \left \lfloor \frac{\alpha_i}{2} \right \rfloor$$$.
Therefore we only need to look at $$$\alpha_i \bmod 2 = 1$$$ i.e. odd powers , and calculate The following
For each test case , we calculate for each prime upto $$$n$$$ it’s power , the count of prime upto $$$n$$$ are approximately $$$O \left ( \frac{n}{\log(n)} \right )$$$ and we check the power in $$$O(\log(n))$$$ and even better in practice , this yields prime factorization of $$$n!$$$ takes at most $$$O(n)$$$ time , we can with each prime factorized if the final power is odd then multiply it by the answer and take the modulus by $$$10^9 + 7$$$ , thus the total complexity for multiple test cases is $$$O(8 \cdot 10^5)$$$ for precalculation of sieve (primes) , and $$$O(\sum n)$$$ for answering test cases.
Robocontest admin will give ratings soon.
Ok, thanks.
No, I mean in "UPD2 : Congratulations to Winners ! :", I am colour of specialist. But in codeforces I'm expert)).
That's because there was rating rollback ongoing while posting , It's fixed now :)
Thanks.