Hello, Codeforces \[^-^]/
The competitive programming laboratory of the IT campus NEIMARK from Nizhny Novgorod is pleased to invite everyone to participate in Codeforces Round 1013 (Div. 3), which will be held on Mar/25/2025 17:35 (Moscow time).
The round is based on the problems of the final of the first olympiad by IT campus NEIMARK. 312 students from 28 subjects of the Russian Federation took part in the olympiad. And at the final competition, in addition to Nizhny Novgorod students, we met finalists from the Chuvash Republic, Moscow, Tolyatti, Kirov, Saransk and Ulyanovsk.
If you participated in the final of this olympiad, please refuse to officially participate in this round.
The topics of the tasks will be related to the working days and weekends of our laboratory. The laboratory has existed for a little less than a year, but during this time several training camps, many personal and team trainings have been held, and dozens of tasks for school and student competitions have been developed (you can find some of these competitions in the section Gym). We opened competitive programming clubs in schools in Nizhny Novgorod, and began training interested IT teachers. We also acted as a venue for several programming competitions.
And at Mar/25/2025 17:35 (Moscow time) we will finally share with you one of the most important results of our work.
You will be given 7 problems and 2 hours and 15 minutes to solve them.
Note that the penalty for the wrong submission in this round is 10 minutes.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks. After open hacks all accepted solutions will be rejudged on successful hacks.
Remind yourself that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:
- take part in at least five rated rounds (and solve at least one problem in each of them).
- not have a rating of 1900 or higher at any moment in time.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you (unless you register unrated).
We hope you will enjoy problems! The tasks were prepared by our laboratory staff: Alexey ashmelev Shmelev, Islam l-_-l Shayakhmetov and Diana Diall_ Alyaseva.
Thanks to MikeMirzayanov for the CodeForces and Polygon systems. Thanks to Vladosiya for the coordination and help in preparing the round.
Thanks to our testers: MForest, OG_Matveychick1, Tmitmi, Riladavin, quaha, eepsilon, SL0NYARA, konred, NerfThis, gtheoden42, sasha00123, doreshkin, blinowartemcka, --S, bugrova, Itsmylove1
Good luck for everyone and praise the sun \[^-^]/
Good luck everyone!
It looks really cool. I'm considering participating in this contest, although I'll have to sacrifice some sleep due to the different time zones.
It does mean sacrificing some sleep, but I don't want to join.
Hoping to get back to expert after a huge drop in rating -____-
Wow, what a coincidence to see you here again, I hope you can play superbly this time:)
Wow, you lose so many scores in last contest
As a tester, I hope you'll enjoy these problems
And praise the sun!
As a tester, I wish you good luck and Praise the Sun for your best participation!
\[^-^]/
I hope that today I will become a specialist. Hope on this contest.
[^-^]/
\[^-^]/
Another cool round! \[^-^]/
Do you guys think this round is going to be harder than typical Div 3 rounds because it is based on an Olympiad?
No.. this round was easier than other div3 for me.. what your opinion?
Probably not. I assume (based on other such rounds) that, if the problems are too hard, some new, easier ones will be added, or some of the olympiad problems will be simplified
I hope your thoughts happen!
Good luck!
Hope! we have a contest where
I hope I can solve four problems in this round and finish A, B, and C within 30 minutes as I am a newbie.
Good Luck Everyone
Happy Coding
it would be cool if at least once every 2 weeks there would be a div 3 or div 4
++ for div. 3s
good luck everyone!
its based on olympiad so its going to be interesting
I hope I can become Expert after this contest.
High five we have the same rating and the same goal!
Same
It's a chance to be back to CYAN...
The sooner you get it, the sooner you can solve it. Because, it's just a while loop template. Yes, I'm talking about BINARY SEARCH. Problems 'D' and 'E' — I have solved both using BINARY SEARCH! And again, I am going to be CYAN...
Goodluck everyone :3
Good Luck Guys...
And praise the Sun !
Occasionally, it’s humorously linked to brute-force approaches (like iterating over all possible solutions) because brute-force can be seen as a last resort, much like praying for a solution. I hope you see something like this in the contest.
As a tester, I have a proof that upvoting this comment will lead to positive delta. But the proof is too long to fit the margin.
I downvoted, let's see what will happen! ಠ_ಠ
And, u aren't a tester T.T
Hello
what happens if i vote?
\^.^/
Great contest. Relax and solve as much problems as you can!
I hope i'll be green again. After this GeometryForces contest, ii couldn't get any points.
Best Of Luck Everyone For A Positive Delta
Having this kind of Laboratory and Olympiad event in your region is undoubtedly a blessing. From there, we get such tricky problems that AI models fail to generate solutions. So, bad luck for cheaters (who are going to downvote this!) and exciting for real CP lovers. And of course, I belong to the latter...
Looking forward to touch 1000 after this contest. In fact, any amount of positive delta would motivate me.
GL HF! As a tester, I hope you will feel the maximum dope from the tasks and be able to achieve your best results!
Hopefully I will get my specialist back, kinda nervous tho as I feel it would be harder than normal div 3s since it's based on an olympiad
May all the problems be kind to my brain
like div3.This means that I can see and solve more interesting problems instead of only doing three problems like div2
Let's learn something new from this contest!!
Good luck everyone!
It's time to up expert:)
I'm Excited!!!
I hope I finally become a newbie ,lol.
I'm fine if I solve a and b at least
hoping for a great contest all the best everyone
What an absolute trash contest, more like a speed-guessing contest.
So can anyone tell me how to solve prob G?
UPD: Report a stupid Indian cheater's youtube, share the code from A to F during the contest
for the first time I solved till E then saw 4k people already solved lmao!!!
Imagine you're Gleb, and you have to cross a river to reach a point exactly s meters away. Each time you paddle, your current power (or energy) determines how far you go. BUTTT every time you decide to turn around to adjust your course, your power drops by 1 (unless you're already at the minimum power of 1). So, you want to minimize turns because every turn costs you power.
I originally considered trying every possible sequence of moves forward and backward to see which one would land me exactly at point s. this was stupid i am stupid — charles leclerc
Now here's what I actually did:
Good ol dp. The key idea was to base my dp state on a modulus (p) and, for each residue modulo p, store a pair of numbers. These numbers represent the minimum and maximum effective move counts/strokes needed to reach that residue.
Now we can build the state transitions using modular arithmetic. For each residue in the current state, calculate the new residue after a move by taking into account the effect of the stroke. I solved a linear congruence using the extended euclidean algorithm to compute a modular inverse, which was crucial to adjust the equation based on the gcd. Now with rnges I determined the valid range of multipliers (stroke counts) that would keep the move within the acceptable bounds.
To showcas ethe actual movement, I defined two functions: one for forward moves (fwd) and one for backward moves (bwd). The forward function simulates strokes that add distance, while the backward function handles strokes that subtract distance (after a turn). Now if I alternate between these, I can build a detailed map of all the positions I could reach after any number of moves.
The final step was to check if the dp state allowed me to reach exactly point s. I did this by looking at the residue corresponding to s and verifying whether the range of move counts included a valid solution. Since every turn reduces my power, the whole process was aimed at finding a sequence of moves that minimizes the number of turns, thereby preserving as much of my initial power as possible.
Sorry if this is text heavy its hard to explain in text its why I prefer pen n paper
UPDATE : This is based on number theory and there's a better solution using bitset by Edu175 below mentioned as well.
Thank u very much!
I just used bitset 312451438
Cost a lot of time to code Miller-Rabin for problem E. Just to realize it's bad because n <= 10 ** 7.
Damn another minus delta for being such a noob.
I increased 1e5 to 1e6, thinking I increased 1e6 to 1e7 and got one penalty. Think about me, though. T_T
That was painful, but at least my man still have plus delta :(
Btw you do have time to attempt F is already awesome. I don't have time in my hands.
yeah that sucks
why to code miller-rabin when we can find primes in √n*log(log(n)) by sieve only.
Wasn't even think about the sieve till last 30 minutes of the contest, I got blind spotted.
that's really painful, sometimes happens with me also,stuck at one approach and debugging.
This round is amazing! I really enjoyed D and E.
was F fenwicktree + dp ??
prefixsum + dp is suffice.
oh shoot! prefix sum was much more easier to implement and easy to debug, totally missed it :(
I spend almost an hour trying to debug this can you please help me with this submission
Wow! Most balanced Div3 in recent time. Kudos to the everyone involved.
Praise the sun!
Solved E one min after the contest :(
really good problems fun F
Can anybody tell me how can i use segment tree in this problem, in which i only have to get the sum of the answers in a range such that if value at that index is 1, then take it, or leave it. 312465645
you don't need segment tree bruhh , just prefix sums are needed.
Yes, I think prefix sum can do that. But I'm still unsure that how would i selectively get the sum in the range. For example, I'm adding +1 to all the indices in a range [l, r], even if some of them is'nt valid (c = '#'). Now, when retrieving the sum in this range, how would i make sure that sum of such indices are not considered, that's my problem.
set the dp value of # cells to 0 compute prefix sums on this dp and to get sum in range in same row u can move d to the left and d to the right at most in previous row u can can move sqrt(d^2 — 1) to the left or to the right cuz of euclidean dist
Something sweep line thing can help, in which i update the value using f[l]++ and f[r + 1]--, but when accumulating them, i only consider f[i] if that cell is valid (c = 'X')?
prefix sum on current and previous row
G wrong ans on test 7 :( could not debug, not sure if solution is correct though.
please review whoever submitted F in the last 30 minutes
I'm pretty sure 70% of them are fake
My position dropped from 600 to 1100 in last 30 min.. T_T
same bro . I dropped to 1500 .
I want my 700 back T-T.
you're very fast today, will plus delta enough to reach expert?
Don't think so.. :]
why? :(
D was my favorite problem.
easy binary search! my fav too
Yes it was clear to apply BS . i just got stuck on calculating the spots filles for each mid value
My screencast for this contest, for anyone interested: click
How to solve F ?
dp
The contest was truly enjoyable! I think I performed well, even though an obstacle in the form of DP in F was tough enough to make me give up on that. Anyway, thank you for the incredible contest :D
How do you come up the intuition for E? Any ideas and topics to practice ?
Tried to compute Sieve of Erastosthenes and then brute force it
Basic number theory
Sieve approach works, you can set a = dx and b = dy so gcd(x, y) = 1 and d is maximum. So d is gcd of a and b. Then problem wants lcm/gcd, which is xy here. As we need xy prime you can set x = 1 and y primes. Then simply find all valid values of d for each prime.
Sieve of eratosthenes is a typical way to identify all the primes in some range of values. That's all that's really needed for the implementation part of things, and the idea is just knowledge of gcd and lcm defintions.
I was planning to try pushing the formula, but I simulated the example and discovered the pattern
F can be solved by assuming an edge between two points if it is reachable. After that, it is kind of dp on the graph which is pretty systematic.
Definitely TLE
I just cannot process the fact that I mindsolved $$$F$$$ 50 minutes ago of End of contest, and finished implementing it (along with debugging) , 10 minutes after end of contest , just realized my implementation skill is slow
What is your logic for F
it’s just a classic prefix sum dp problem
For C i had no proof , but it luckily got AC. https://codeforces.me/contest/2091/submission/312369723
In problem E, can someone tell me why my submission is accepted ? I think the time complexity is $$$O(n\sqrt n)$$$
Its nlog(n)
nlog(n) factorial?
UPD: he updated, that was kinda confusing
You!
I've just realized that Igor can go to row
i - 1
only from rowi
I thought that he can go to row
i - 2
from rowi
if d is 2, but seems like this can't happennice problem btw
Oh no, i was solving different problem for 1 hour
The same thing happened to me, until I tried to solve the testcases using pen and paper, then I realized that I could go to the row right above me only :(
this made the problem easier, but I think it will be nice if there is a hard version using the idea that Igor can go to any row above him if the row is reachable ($$$\leq d$$$)
sorry
I am talking about problem F !^_^
I kept thinking that problem F was some kind of BFS where we can precompute the allowed dx and dy before starting the bfs.
basically start bfs from every non-visited node in row n-1. at any moment if we reach row 0 then ans++
also have an underordered map parents to ensure that if we are coming from the same row to the current node then we cannot have dy = 0 to ensure a max of 2 holds.
Can someone tell what's wrong in this logic cause I kept getting wrong answer in local testing itself.
What am i missing here for D ? 312462491 [](https://codeforces.me/contest/2091/submission/312473448)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ // this is the code
include <bits/stdc++.h>
using namespace std;
void solve(){
}
int main(){
} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
try long long?
yeah i did and i cried a lot after that
For C, does anyone have a proof of why it is impossible to form such a permutation for even values of $$$n$$$?
Yea I am also confused for the proof. I just tried to find the permutation for some even numbers and saw that for every even number (that I tried) there would be one instance where 2 numbers would be at the right position at the same time. So, I just went with that and it got accepted
in C when you have even n you cannot interchange 1 element at a time. What i mean to say is you need just 1 element to be at its own place for example 1 on a1 or 2 on a2, etc but when we have even n we swap 2 numbers or say we need to leave 2 numbers as is to its place for example -> 1 3 2 5 4 6 -> here 1 is left on one place but now we need to swap all other numbers say swapped 6 and 4 above and it becomes -> 1 3 2 5 6 4, but now you see the real problem any two consecutive numbers together because they will take their own place in some cycle which means -> 1 3 2 5 6 4 will become -> 4 1 3 2 5 6 and it is not allowed, i hope you were satisfied with my answer
Here's a mathematical explanation wrote it quickly in notion
Terrible statement for F. Understanding it took a lot of time. Request for the authors to take out checking of comprehension from CP.
E was relatively very easy , You guys should've removed the constraint of sum of n over all testcases doesnt exceed 1e7. Atleast then precomputation would come into play
hey, yea i agree it was very simple for an E. Removing the constraint would make it a proper E. (BTW even i am a huge fan of Kurt <3 )
Best Div3 of recent times [^-^]/
Please improve the plag check and permanently ban accounts and IP. There is no way this many people solved the latter problems.
can someone explain thought process of solving Problem E . I tried to solved during contest but i can not solve.
Can someone help to make this work 312418567
Hi, I participated in Round 1013 and registered as a contestant. I solved 4 problems during the contest, and my rating is below 1600. However, I was marked as "Unrated, Allowed". Could you please check if there was a mistake?