Diall_'s blog

By Diall_, history, 2 days ago, translation, In English

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 \[^-^]/

  • Vote: I like it
  • +187
  • Vote: I do not like it

»
32 hours ago, # |
Rev. 3   Vote: I like it +11 Vote: I do not like it

Good luck everyone!

»
32 hours ago, # |
  Vote: I like it +20 Vote: I do not like it

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.

»
32 hours ago, # |
  Vote: I like it +6 Vote: I do not like it

Hoping to get back to expert after a huge drop in rating -____-

  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, what a coincidence to see you here again, I hope you can play superbly this time:)

  • »
    »
    17 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Wow, you lose so many scores in last contest

»
31 hour(s) ago, # |
  Vote: I like it +9 Vote: I do not like it

As a tester, I hope you'll enjoy these problems

Spoiler
»
31 hour(s) ago, # |
Rev. 4   Vote: I like it +17 Vote: I do not like it

As a tester, I wish you good luck and Praise the Sun for your best participation!

\[^-^]/

»
31 hour(s) ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

\[^-^]/

»
30 hours ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

Another cool round! \[^-^]/

»
30 hours ago, # |
  Vote: I like it +8 Vote: I do not like it

Do you guys think this round is going to be harder than typical Div 3 rounds because it is based on an Olympiad?

  • »
    »
    30 hours ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    No.. this round was easier than other div3 for me.. what your opinion?

  • »
    »
    25 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
30 hours ago, # |
Rev. 4   Vote: I like it +10 Vote: I do not like it

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

»
30 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

it would be cool if at least once every 2 weeks there would be a div 3 or div 4

»
30 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck everyone!

its based on olympiad so its going to be interesting

»
30 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

I hope I can become Expert after this contest.

»
30 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

It's a chance to be back to CYAN...

  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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...

»
29 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Goodluck everyone :3

»
28 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck Guys...

»
28 hours ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

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.

»
27 hours ago, # |
  Vote: I like it -24 Vote: I do not like it

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.

  • »
    »
    27 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I downvoted, let's see what will happen! ಠ_ಠ

    And, u aren't a tester T.T

  • »
    »
    26 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what happens if i vote?

»
27 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

\^.^/

»
26 hours ago, # |
  Vote: I like it +23 Vote: I do not like it

Great contest. Relax and solve as much problems as you can!

»
26 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope i'll be green again. After this GeometryForces contest, ii couldn't get any points.

»
26 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Best Of Luck Everyone For A Positive Delta

»
25 hours ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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...

»
24 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

Looking forward to touch 1000 after this contest. In fact, any amount of positive delta would motivate me.

»
24 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

GL HF! As a tester, I hope you will feel the maximum dope from the tasks and be able to achieve your best results!

»
17 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
15 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

May all the problems be kind to my brain

»
14 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

like div3.This means that I can see and solve more interesting problems instead of only doing three problems like div2

»
13 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's learn something new from this contest!!

Good luck everyone!

»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

It's time to up expert:)

»
6 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm Excited!!!

»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope I finally become a newbie ,lol.

»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm fine if I solve a and b at least

»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

hoping for a great contest all the best everyone

»
3 hours ago, # |
  Vote: I like it -27 Vote: I do not like it

What an absolute trash contest, more like a speed-guessing contest.

»
3 hours ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    3 hours ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    for the first time I solved till E then saw 4k people already solved lmao!!!

  • »
    »
    3 hours ago, # ^ |
    Rev. 3   Vote: I like it +4 Vote: I do not like it

    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.

  • »
    »
    111 minutes ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I just used bitset 312451438

»
3 hours ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I increased 1e5 to 1e6, thinking I increased 1e6 to 1e7 and got one penalty. Think about me, though. T_T

    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why to code miller-rabin when we can find primes in √n*log(log(n)) by sieve only.

    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wasn't even think about the sieve till last 30 minutes of the contest, I got blind spotted.

      • »
        »
        »
        »
        3 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        that's really painful, sometimes happens with me also,stuck at one approach and debugging.

»
3 hours ago, # |
  Vote: I like it +8 Vote: I do not like it

This round is amazing! I really enjoyed D and E.

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

was F fenwicktree + dp ??

»
3 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

Wow! Most balanced Div3 in recent time. Kudos to the everyone involved.

\[^-^]/
»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved E one min after the contest :(

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

really good problems fun F

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    you don't need segment tree bruhh , just prefix sums are needed.

    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 hours ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

    • »
      »
      »
      3 hours ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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')?

  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    prefix sum on current and previous row

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

G wrong ans on test 7 :( could not debug, not sure if solution is correct though.

»
3 hours ago, # |
  Vote: I like it +12 Vote: I do not like it

please review whoever submitted F in the last 30 minutes

I'm pretty sure 70% of them are fake

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

D was my favorite problem.

  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    easy binary search! my fav too

    • »
      »
      »
      68 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes it was clear to apply BS . i just got stuck on calculating the spots filles for each mid value

»
3 hours ago, # |
  Vote: I like it +5 Vote: I do not like it

My screencast for this contest, for anyone interested: click

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F ?

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 hours ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Basic number theory

  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    3 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    101 minute(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was planning to try pushing the formula, but I simulated the example and discovered the pattern

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

For C i had no proof , but it luckily got AC. https://codeforces.me/contest/2091/submission/312369723

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, can someone tell me why my submission is accepted ? I think the time complexity is $$$O(n\sqrt n)$$$

code
»
3 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

I've just realized that Igor can go to row i - 1 only from row i

I thought that he can go to row i - 2 from row i if d is 2, but seems like this can't happen

nice problem btw

  • »
    »
    106 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh no, i was solving different problem for 1 hour

    • »
      »
      »
      93 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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$$$)

  • »
    »
    98 minutes ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    sorry

»
3 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 hours ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 n, m, k;

cin>>n>>m>>k;

int total = m * n;

int value = (total &mdash; k) / n;

if( value == 0)
cout<<m<<endl;

else{
    cout<< m / (value + 1) << endl;
}

}

int main(){

ios::sync_with_stdio(0);

cin.tie(0);

int t; cin>>t;

while(t--){

    solve();

}
return 0;

} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

»
3 hours ago, # |
  Vote: I like it +7 Vote: I do not like it

For C, does anyone have a proof of why it is impossible to form such a permutation for even values of $$$n$$$?

  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    115 minutes ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Here's a mathematical explanation wrote it quickly in notion

»
2 hours ago, # |
  Vote: I like it +6 Vote: I do not like it

Terrible statement for F. Understanding it took a lot of time. Request for the authors to take out checking of comprehension from CP.

»
2 hours ago, # |
  Vote: I like it +18 Vote: I do not like it

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

  • »
    »
    108 minutes ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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 )

»
2 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Best Div3 of recent times [^-^]/

»
2 hours ago, # |
  Vote: I like it +1 Vote: I do not like it

Please improve the plag check and permanently ban accounts and IP. There is no way this many people solved the latter problems.

»
93 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain thought process of solving Problem E . I tried to solved during contest but i can not solve.

  • »
    »
    74 minutes ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    Note that F = b / a; also F must be prime
    	=> b = F * a
    I just run loop for all a and f values and did prefix sum
    
    Steps
»
75 minutes ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone help to make this work 312418567

»
23 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

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?