Hello Codeforces!
The series of Educational Rounds continues thanks to the support of the Neapolis University Pafos. They offer a BSc in Computer Science and AI with JetBrains Scholarships. Gain cutting-edge skills in AI and machine learning, preparing you for high-demand tech careers. Limited scholarships available — don't miss your chance to study in Europe for free!
On Jul/22/2025 17:35 (Moscow time) Educational Codeforces Round 181 (Rated for Div. 2) will start.
This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.
You will be given 6 or 7 problems and 2 hours to solve them.
The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Maksim FelixArg Novotochinov, Polina ifive Piklyaeva and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.
Big thanks to the testers shnirelman and Brovko for their valuable advice and suggestions!
Good luck to all the participants!
UPD: Editorial is out
I hope to get specialist in this contest, I have a high hope for it. And, BTW, is online class for the university avialiable?
I hope too...
I was going to be Specialist but, now I first want to be pupil!
I was going to be Legendary Master but, now I first want to be pupil
The CSAI curriculum link leads to a deleted file.
As a tester, i recommend!
bro u haven't even tested
did you really test?
i have very bad track record with edu,hoping to get positive delta in this contest!
what is delta ?
Δ (Delta) represents the rating change from a contest. A positive delta means you gained rating, while a negative one means you lost rating.
thanks wizardrabbit
Good luck.
I hope it goes well
I hope after this round I feel some confident
pls postpone this contest by 2 hours I have doctor appointment
Funny
Is the appointment related to your profile pic in any way?
Oh dont worry its unrelated
less go. another edu round :fire
why does all the edu rounds are authored by awoo and BledDest ??
and Neon too
another edu, hoping to get back to pupil
lol
i did it nvm
Is this competition has open hack?
Yes, as mentioned in the contest announcement.
i love edu round
Good luck to myself and all of you!
I hope I become pupil in this round!
I hope to educate in this round
As an unrated participant, good luck to all rated participants.
Div 2 haha
Again! gonna get down! :(
I love edu round in CF as like as messi in football :v
what about score distribution ?
I think all problem has same value, I could be wrong.
In edu all problem scores are the same.
i hope this contenst doesnt ->()(->)-> ->()(->)-> ->()(->)-> ->()(->)-> ->()(->)-> me
I don't speak unga bunga, care to elaborate?
it certainly ff**ed me
Are you talking about body parts colliding not so sophisticatedly???
Hi everyone, could someone explain the differences between educational and regular contests?
+1
The educational round is more educational, so the questions will be more skewed towards classic algorithms and classic routines, and the quality of the questions will be higher. Finally, there is no hack session in the educational round, and the ranking will be based on the penalty time instead of the score of the questions.
ahhhh. bad experience for me. Cause swap n,m, I took about 30-40 min on debug. Wish less mistakes on next round.
Same I read n as m and Moreover I used 1e9 + 7 Mod value. so many mistakes
GPTForces. Brutal, people who can't even solve A on their own are getting (A-C) now.
This will also screw up the problem ratings. Problems that would have been legitimate 1500-1700 will now be considered 1100-1200 due to these AI scammers.
Seems like all the cheaters that got banned from Leetcode have migrated here because they have worse cheat detection
atleast CF has divisions, because of it, we can expect minimal no. of cheaters in DIV 1 rounds.
it used to be competing in div1 was worse for your rating because of tougher competition. Now it's better for your rating because div2 is flooded with cheats.
Interesting anecdote: in leetcode contests usually around 50% of competitors get pruned due to cheating, so if you place 1000th or so you'll usually end up around 500th. Codeforces doesn't even prune 1%. There's Zero cheat detection.
Your variable names are interesting
I'm autistic. Deal with it.
AiForces
i think this round should be renamed to "Math & Combinatorics Round"
I hate contests with only single topic of tasks :((((( MathForces :(((((
(i am angry because i bad at maths lol)
E made my head hurt; What's the solution?
First observation : you can always take an array a with 1 in it and all other element are unique (you add 1's to shift the min),
Then you have just to count f(y) the number of n distinct elements (the smallest being 1) with sum y for all y<=x+1, and the final number is sum (x+1-y)f(y),
f(y) can be computed with a classical dp similar to knap sack in O(xn) and n=O(sqrt(x))
How can I compute f(y) for all y <= x+1 in O(xn)?
The idea is to tranform that in a sum of coin problem
$$$1=a_1 \lt a_2 \lt a_3 \lt ... a_n$$$
$$$\sum a_i=y$$$
let $$$d_i=a_{i+1}-a_i-1$$$, $$$y=n(n+1)/2+\sum (n-i) d_i$$$ so you wan to compute the number of way y-n(n+1)/2 can be expressed as sum of integer $$$\leq n-1$$$, iterate over this numbers and update dp in linear time
I did reduce it to this sub-problem but couldn’t solve it. It seems like the kind of sub-problem that one would encounter frequently but I haven’t seen it before somehow.
Thanks you
Got it. So we are incrementing suffixes and $$$d_i$$$ is the number of times we increment $$$i^{th}$$$ suffix. When we increment a suffix, we add (size of the suffix) to the sum. And we start from $$$a = $$${$$$1, 2, 3, ..., n$$$}
MathForces :)
for E i figured out n<500, any more hints?
N should be a bit larger ($$$\frac12 n(n+1)\le x+1$$$)
ya a little bit i forgot about 2. anymore hint?
Calculate the number of difference arrays of a where a is strictly increasing and $$$a_1=1$$$.
No way these many people solved problem D, I suspect AI.
Master finally! Thanks for great problems (especially E)!
C got me bad
I misread D as Your task is to calculate the probability that each cell is covered by at least one segment. instead of Your task is to calculate the probability that each cell is covered by exactly one segment.and wasted more than 1 hour:(( still happy because after a long time I will get positive delta in Edu
I solved the problem completely and it was my first time solving a dp problem! The only thing I didn't understand properly was the last explanation and how to submit the answer. This really bothered me.
The last explanation is just telling you to do all your computations modulo 998244353. You just have to use %998244353 after each sum or multiplication you do and know how to calculate the modular multiplitcative inverse (you can find it here).
I had the same issue, i think that it is written poorly is to say the least if not even wrong at all.
主播主播，这比赛很nb但还是太吃操作了，有没有那种即不吃操作又能上分的比赛 Streamer, this game is awesome, but it's still too skill-intensive. Are there any games that are neither skill-intensive nor hard to rank up in?
yes,bro,yes.there are too many such competitions……
in problem 2,,,,
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
include <bits/stdc++.h>
using namespace std;
int main() { int ;cin>>; while(_--){ int a,b,k; cin>>a>>b>>k; for(int i=2; i<=k; i++){ if(a<k && b<k){cout<< 1 <<endl;break;} else if(a/i <= k && b/i <= k && a%i==0 && b%i==0){cout<< 1 <<endl; break;} else{ cout<< 2 <<endl; break; } } }
}
~~~~~~~~~~~~~~~~~~~~~~~~ Why did this went wrong?
This should use "<=": if(a<k && b<k){
Consider a = 11, b = 3, k = 11
Also, you should not loop up to k, b/c k can be up to 10^18. Instead, find the gcd of a and b, and check a/gcd <= k and b/gcd <= k.
Consider a = 12, b = 18, k = 3: gcd = 6 a/gcd = 2 b/gcd = 3
By using 2 and 3, you travel "diagonally" to (0, 0).
Can you explain why GCD ? please.
Taking the GCD will make sure that both coordinates are divisible by the same base step. So when we choose (dx, dy) = (a/g, b/g), we form a step that aligns perfectly with both axes — meaning the robot can reach the origin using just this one operation type. Now, regarding the cost: The first time you use (dx, dy) costs 1 All subsequent uses of the same operation are free So the total cost is simply 1, as we only introduce one unique operation. When these (dx,dy) steps are somewhat greater than k , you can just use (dx,dy) = (1,1) , until the value at 1 axis becomes 0 and then use (0,non_zero) or (non_zero,0) as (dx,dy) for 1 more coin , which will cost a total of two coins.
because gcd(a,b) divides a and b perfectly so that we can use pair(a/gcd(a,b),b/gcd(a,b)) multiple times and which cost only 1.
You want to find the smallest numbers such that you can move “diagonally” to (0,0).
For a = 12, b = 18. You could get to (0, 0) using either dx = 4, dy = 6 OR dx = 2, dy = 3. This is because a/dx = b/dy, so an and b shrink proportionally as you perform operations. Now notice that the optimal pair is dx = 2, dy = 3 b/c it allows k to be smaller, k=5 wouldn’t work with dx = 4, dy = 6.
Now you want to find the smallest dx, dy such that one number (which is a/dx or b/dy) can be multiplied to them to reach a and b. Because you want to minimize dx, dy, that means you want to maximize that number, which is why use the gcd
you can't do loop in this question think other logic
I was stuck with second question. Trying to conjur some way to get the minimum number of operations. After trying and failing for long. I had an ephiphany that other than a particular edge cases everything can be achieved with 2 operations. I had a feeling, I couldn't prove but as I already give 3 incorrect submissions. I tried and it passed. Not sure if this is good or bad.
The pressure of having WA that too multiple times is enough to frustrate you. If you still found the mental strength to give it another shot and submit even with 3 WA, it was all worth it. After all in the end you are competing against your own mind too.
Just keep trying (1 , 1) and when one of them becomes 0 you can use (1 , 0) or (0 , 1) And with just these two you can reach (0 , 0)
How to E?
E is definitely NTT
How? I didn't use any algorithms except dp.
Yes, I know it can be done with dp, because constraints are a bit small, $$$O(n \cdot x)$$$ dp works because of the check $$$(n - 1) + \frac{n \cdot (n - 1)}{2} \gt x$$$, we immediately return 0, so your worst case complexity is $$$O(x \cdot sqrt(x))$$$ right? I just did it in $$$O(x \cdot log(x))$$$
What is NTT? Could you please elaborate on your approach?
He was making a joke, probably based on problem A, where the problem statement says: a contest is difficult if it contains "FFT" or "NTT" as a contiguous substring.
The joke here is that FTT and NTT (which stand for Fast Fourier Transform and Number Theoretic Transform, respectively) are advanced algorithms that may be used to solve difficult programming challenges. However, you won't encounter these in Division 2 level problems, and problem E isn't solvable with FFT/NTT.
from D to E is always hard to me
I defined dp[i] as the probability that cells 1 to i are fully and uniquely covered. So for each segment ending at i, we add dp[l-1] * (p/q) * Π(1 — p_j/q_j) over all other segments ending at i. correct?
You also probably should take into account that you want ALL other segments to be off (basically at the start we have Π(1 — p_j/q_j))
ABCD was posted on youtube 20 mins after the contest started, how am I supposed to compete?
Exactly
I'm unable to figure out the issue in my code for D. Since contest is over, I didn't make any submission since it was failing test cases so I'll add it as context at the end.
Approach: Made a graph connecting r to l-1 with edge cost p/q (using modinv). Recursion is:
rec[i] += rec[j-1]*prob, where prob is choosing interval (j,i) with its probability and all other intervals ending at i are not chosen. So product of all 1-c, where c is edge cost, multiplied with cost of (j,i) divide the complement.Not sure if the inverse handling is wrong, or the probability math, the recursion etc. It would be great some one could help debug this.
Should have named variables better in retrospect...
Figured out my mistake. Have taken only product of branches and not all. Fixed in https://mirror.codeforces.com/contest/2125/submission/330457836
Can someone link me the technique needed to do C? I dont know how to handle duplicate numbers that are divided by multiple primes less than 10
https://cp-algorithms.com/combinatorics/inclusion-exclusion.html
Thanks, there's even a segment where they demonstrated the same problem as C
https://cp-algorithms.com/combinatorics/inclusion-exclusion.html#the-number-of-integers-in-a-given-interval-which-are-multiple-of-at-least-one-of-the-given-numbers
Principle of Inclusion-Exclusion
read about inclusion exclusion.
You can use inclusion-exclusion. Let
S_ibe the set of all numbers divisible byi. We basically need to compute union of (S_2, S_3, S_5, S_7) and remove them from all the numbers between l and rSince there are only 4 prime numbers with one digit, I just did all possible combinations of them which was very painful.
You can use bitmasks for an easier implementation I suppose
I also did all calculations. Can you elaborate on the bitmask approach.
countfunction calculates the number of distinct numbers from 1 to x(inclusive) which have a divisor 2 or 3 or 5 or 7.The position of set bits in binary representation of
masktells the number currently under consideration from{2, 3, 5, 7}. Ifmaskhas only one set bit then you are basically considering only one number in the array and its contribution should be added. Otherwise if it has more bits then you are considering their lcm which should be removed from contributionLet's say we are dealing with the first
pprimes. Then we iterate over all numbers from0..(2^p-1). Let's say0<=i<2^p. Then we go through all the bits iniwhich are set to 1. Initializeprd = 1. For every bitbofisuch thatb = 1, calculate the total product asprd *= primes[b].Also keep a count of how many bits as set in
i. Now we doprd *= (-1) ^(cnt +1)And finally
ans += prdhow to C?
simply consider 16 cases...
:skull:
Rephrased to make it less scary for people.
We've to subtract the multiples of subsets of {2, 3, 5, 7} from all available numbers
A relatively straightforward solution:
First, we observe that we only need to implement the function
count(x), which calculates how many good numbers are less than or equal tox. The final answer is simplycount(r) - count(l - 1).Another key observation: A number
Nis good if none of the primes 2, 3, 5, or 7 divide it. Since the least common multiple (LCM) of these primes is 210, the problem exhibits a cyclic pattern. This means the distribution of good numbers in the interval[1, 210]is identical to that in[211, 420], and so on.Let
Mbe the number of good numbers in[1, 210]. We can then break downcount(x)into two parts:1. The first part is
(x // 210) * M, representing the number of good numbers in complete 210-number cycles.2. The second part counts the good numbers in the partial cycle
(x - x % 210, x]. Since this interval has at most 210 numbers, we can compute this efficiently using brute force.The final result is simply the sum of these two parts.
thank you for answer
Why over 4,000 D solves? I thought it was a pretty challenging problem to figure out, and you're telling me there are hundreds of newbies and pupils who get the DP trick and correctly implement the modulo in <1hour?
I defined dp[i] as the probability that cells 1 to i are fully and uniquely covered. So for each segment ending at i, we add dp[l-1] * (p/q) * Π(1 — p_j/q_j) over all other segments ending at i. correct?
Looks roughly right. I used a different DP (cells from i to end are fully covered) but if correctly implemented this should work. Don't quote me on that, though
Codeforces has no cheat detection. I thought C was pretty challenging with a tricky inclusion/exclusion and it has 12,000+ solves with tons of newbies and pupils. I had gotten expert and held for 10+ contests, but will now be back to pupil after this contest due to cheaters
I don't get why everybody used inclu/exclu for C. Just... find the closest multiples of 2*3*5*7=210 to l & r? You only need to check for divisibility by four numbers, after all.
I solved using Inclusion Exclusion as well. Can you share the 210 multiples approach. All I can understand is that gcd(x, 210) > 1 then 'x' has to be removed. How can we calculate that?
Find the smallest l2 >= l and r2 <= r such that both l2 and r2 are multiples of 210. If l2 > r2 then you can just brute force since the gap is small, otherwise bruteforce l to l2 and r2 to r and add (r2-l2)/210*48 to the answer (there are 48 numbers from 210 to 420, 420 to 630, etc. that satisfy the properties)
Honestly this seems harder than Inclusion-Exculsion.
The window trick is definitely clever, but i don't necessarily think it's any easier to implement or discover.
In other words, that doesn't convince me that C is any easier lol
I mean, it's pretty trivial to implement imo? Solved in 10min by doing
and copy-pasting 3 brute force loops.
Inclusion/exclusion is pretty trivial to implement as well, but I think discovering the solution is the hard part.
AI gives the solution and any donkey can implement it
C is a very very standard problem taught in India preparing for competitive exams for clgs. I am sure in other places also it is taught in PnC very likely. (I think that's why also it was solved using inclusion exclusion method by most)
dp wasn't too hard But I don't think that many beginners (including myself) know how to measure.
I had a vague idea it was gonna be dp but had no idea how to implement it & I didnt get the gist of modulo at all, can you help me with what that meant?
I died on the modulo implementation. Knew how to solve the problem in floats but the modulo implementation was too hard to debug :/
made a stupid mistake in A, acted so dumb in C tryna find a sieve method until i had a good look at the range and realized there was a super easy way :c and i was dumbfounded at D and E cus what are thoseeeee
i can relate with every single one of those lmao
12k people for C is crazy, so much AI used
A few pages from my notes on the Inclusion-Exclusion Principle.Sufficient to solve Problem C link
Can F be solved with lambda?
Yes it can be!
Would you mind elaborating on this?
Sure thing!
First of all, let's find current number of occurences of "docker" in string $$$s$$$, let's call that $$$occ$$$. We can create from $$$0$$$ to $$$\lfloor \frac{n}{6} \rfloor$$$ occurences. Next let's find lowerbound and upperbound of the number of occurences, that we need to create. Because after each replacement the number of occurences changes at most by 1, we only need to reach either lowerbound or upperbound. Reaching lowerbound is trivial, let's focus on reaching the upperbound.
let $$$c_i$$$ be the cost of making the substring that ends at position $$$i$$$ equal to "docker". Then I want to pick $$$upperbound$$$ indices, such that the distance between adjacent is at least 6 and the sum of picked $$$c_i$$$ is minimal. Let $$$f(k)$$$ be the minimal sum of $$$c_i$$$ if I pick $$$k$$$ indices. Turns ouf $$$f(k)$$$ is convex, so lambda optimization is applicable. If I want to pick some number of indides, the dp for that is trivial.
I am interested in the proof of convexity of $$$f(k)$$$.
Quick question about this idea. Suppose we have a test case where we need to have X occurences of the string "docker". What happens in the case where we're doing the binary search on the value of lambda and find that:
That is, there is no integer value for lambda where the dp will use the exact amount of occurences of the string "docker". In cases such as these, how can I find the optimal value for lambda to calculate the answer?
Just asking because I always thought you had to implement this idea with the value of lambda being a real number (instead of integer), but I noticed you implemented this idea with integers and I'm not sure why it works.
If the function $$$f(k)$$$ is strictly convex (i.e. $$$f(k) - f(k - 1) \lt f(k + 1) - f(k)$$$), then such a thing won't happen. However in most cases the function isn't strictly convex, i.e. only $$$f(k) - f(k - 1) \le f(k + 1) - f(k)$$$ holds.
Then there's still an optimal whole lambda for each $$$k$$$, but for some values $$$k$$$ it coincides. Why is it an integer? Consider lines $$$f(k) + \lambda k$$$ and $$$f(k + 1) + \lambda (k + 1)$$$. They intersect at the point $$$\lambda$$$, where
$$$f(k) + \lambda k = f(k + 1) + \lambda (k + 1)$$$
which can be written as
$$$\lambda = f(k) - f(k + 1)$$$, which is an integer (if function $$$f(k)$$$ returns integers)
That way each pair of adjacent lines intersect at an integer $$$\lambda$$$
I never would have been able to think of this, so elegant. Thanks you so much for the help!
**
I completed 4 tasks in 22 minutes, and I have a -13. Before 37 minutes I can't send tasks. ((((((
(((((
sooo many math problems!!!!
Here's my solution to problem C. Let the Hate come.
orz
So my initial approach was to do figure out sieve to keep track of primes because I found a pattern where every prime number increments the answer by 1. Like for 2,11 the answer was 1, for 2,13 was 2 and 2,17 was 3. So I would have answer for any range in the format [2,N].
Then I started looking for distribution based prime counting functions to get a O(1) but couldn't get the correct answer.
Then I figured, okay. I can just rid of all numbers that are divided by 2,3,5 and 7. Every thing else would have a factor greater than 9 and it would naturally include prime factors. But I also need to keep the common divisions so I don't discard the counts twice. Like for 6. It would be discarded twice because of 2 and 3. So I would like to keep 6 back.
So I came up with -2, -3, -5, -7, +6, +10, +14, +15, +21, +35.
ButI don't understand why everyone is doing 210 at the end (to remove multiples of 10 and 21?) But if so why stop at 210? You can keep going at it indefinitely?
ALL Of this Gymnastics done to avoid double-counting of cases (both in addition and subtraction)
Ofc there are better ways to do it. (Just check out any solution by a specialist+ ig)
The solution was hilarious in itself then I read your name. Epic!!
I enjoyed the round however I find it a bit of a speedforces one. The statements we concise and clear which is commendable. Also loved the number theory theme behind most problems.
Overall, a good educational round. Great job!
C was like a tipical 1100 rated..
how is D easy problem lmao, am i that bad with DP
please id love to know which topics to focus on for solving such question as D
maths, probability (and dp).
I disagree with D being C problem
Man why was this contest time only 2 Hr instead of 2:15. I literally solved D just when the contest time completed :(. Today when i needed that extra time didn't get it :( . Please keep the contest time as 2:15 as before.
After submitting 3 in 1h, finding myself in 7k+ position!!! The AI force is ruining the contests. Isn't there any way to detect these?
Honestly the same for me. I completed all 3 in 1 hour and when I saw the number of solves I felt so dumb but with the number of cheaters that we are seeing now a days I knew no point thinking too much about it.
just dont measure your success with a stupid rating i literally solved 3 questions in 22 mins and ended up ~5k ish
5k people solved D is still insane to me
lol why are people downvoting !!!
He's right, the amount of cheaters have increased insanely. I miss those days without AI.
Now the ratings are not legit at all.
Keep downvoting scammers and cheaters. I don't care about negative contribution xD
Can someone explain why most implementations for D not considering the probability $$$ 1 - \frac{p}{q} $$$? (or at least it seems so?)
What I did was for each suffix, calculate the probability of not taking segments and for a segment $$$ [l, r] $$$ we need to consider those probabilities in $$$ [l, r] $$$ divided by the notTake probability of current range. Let this value be $$$ bad $$$. Then $$$ dp_l = bad * \frac{p}{q} * dp_{r+1} $$$ over all segments starting at $$$ l$$$
You need to calculate the following:
$$$\sum_{S}{(\prod_{i \in S}{(\frac{p_i}{q_i})} \cdot \prod_{i \notin S}{(1 - \frac{p_i}{q_i})})}$$$,
where $$$S$$$ is a set of segments that covers the whole strip with no overlaps.
You can think of $$$\prod_{i \notin S}{(1 - \frac{p_i}{q_i})}$$$ as $$$\frac{\prod_{i}{(1 - \frac{p_i}{q_i})}}{\prod_{i \in S}{(1 - \frac{p_i}{q_i})}}$$$.
Now let $$$G$$$ denote $$$\prod_{i}{(1 - \frac{p_i}{q_i})}$$$, you get that the original sum we needed to calculate is basically $$$G \cdot \sum_{S}{(\prod_{i \in S}{\frac{\frac{p_i}{q_i}}{1 - \frac{p_i}{q_i}}})}$$$.
It seems like we have introduced a new $$$1 - \frac{p}{q}$$$, but this one is better since now the whole product is about one single set.
Above code id not working fow test3 given in question could u plz tell why??
is giving output as 97787202 instead of 94391813.
i don't know c is very easy like after 40 to 50 minutes 8-9k solved that problem
i mean, classic known topic
i miss the shit that classy number should have two digit prime number i read like just prime number that why i just finding for some formula , number of prime number less than n n/ln(n) or digit dp , and implementation of that in 20 minutes was stranger for me
Why did everyone solve C in the worst possible :sob: This passes:
ayyyy another 210 solution
what the hell is going on at this solution
210 is lcm(2, 3, 5, 7). That means for any prime p less than 10, p%210 = 0, so the "goodness" of a number is constant mod 210. You can count the number of good numbers under 210 with euler totient:
That means there are 48 good numbers for every 210. You can multiply to get the number of groups of 210 and manually count the remainder with a for loop.
wow
Wow..
I think you meant $$$210 = \text{lcm}(2,3,5,7)$$$. This is a very nice approach, I learnt a new thing today.
oops u right
can u please explain what’s going on here? this seems new to me
nevermind, got it thanks
Have to admit, this is glorious, but I just speedran it with a PIE bruteforce... I feel ashamed now, to have forgotten about the elegant usage of the totient function :(
Maybe it's the worst solution of C, but definitely the cutest one :))
had so much fun this time, thanks for hosting :)
How This is Possible?
Problem B
Testcase : a = 3, b = 7, k = 2
How the Output is here two, No paths allows us to have answer 2 the actual is 3 why Getting 2.
You can always choose (dx, dy) as (1, 0) and (0, 1) to get anywhere
thanks
ans will always be 1 or 2. To obtain 2, you just select (1, 0) and (0, 1)
You can use (1, 1) to get (0, 4) then use (0, 1) to get (0, 0). Hence, answer is 2.
4000 people passed D？ SMH. Come on guys，stop using AI to cheat in a public CP competition. You benefit NOTHING from doing so. Use your god damn brain instead.
I don't understand why the solution I wrote for D does not get correct results, I use DP on m + 1 states setting dp[0] = 1 and all other states are set to 0, and then sort the segments based on l first then r then I do transition like that : let current segment be from l to r with p probability then dp[r] += (dp[l-1] * p) mod m, another thing I do I just transform every p and q to p by p* (q^m-2) mod m, what is wrong with that?
You are not counting the probability of not taking the rest of the segments.
thanks for clarifying
My rating is 403 if i was able to solve 1 question only div 2 educational contest will my rating will increase or decrease penalty 43
Increase
I have just solved C using chatgpt here is submission the problem is good and educational but it's obvious and easy for anyone know the theory (including AIs)
I tried using deepseek for todays contest problem D (obv after contest)
It solved in just one prompt the full correct solution
did anyone solve D with a recursive DFS-type approach(not DP)?
I think it was possible to start with the segments with l=1, then check all the segments starting at the endpoints of these segments, and continue this proccess. We can store the probability for every segment and store which segments have been visited(like a dfs).
I wasn't able to complete the implementation so not completley sure if it works.
I tried this but couldn't figure out how to fix integer overflow. https://mirror.codeforces.com/contest/2125/submission/330391378
You will get TLE, you are basically exploring all paths.
The process should be O(n) (not counting inverse calculations) because you are traversing at most n segments
Yes but only if you use memoization
well i tried to do this you can check my solution https://mirror.codeforces.com/contest/2125/submission/330393122 i used bs(lower bound and upper bound) for the same segement idea and then recursed to the next seg r+1. the main part ig was handling the prob which i handled with the use of considering not take for every segment initally and then simply mult take/nottake.
I tried exactly this, but got TLE on test 5. https://mirror.codeforces.com/contest/2125/submission/330388500
Direct DFS wasn't optimal enough, as worst case here would be O(k*n).
codemart786
Can anyone please send the solution of the third problem. And different approaches to solve the B problem
Can someone please explain the solution of tourist for problem D?
I didn't understand why he used the odds ratio
You need to calculate sth like:
And the last product is a prefix product which can be precalculated
Got it, thanks
But I still can't understand the DP transition to maintain the probability
I think we maintain the value for each $$$i \in m$$$ like this
Suppose we have the set $$$K$$$ that contains all the segments ending in index $$$i$$$
I see the value of $$$P(\text{i exists}) \cap P(\text{all other values don't exist})$$$ is maintained correctly by the expression you gave above but maintaining the existence probability of segments in $$$P[j.start]$$$ is not obvious
Thanks for the explanation, but I still didn't quite get it.
$$$\text{coeff} = p_i \cdot \prod_{j \neq i, j\in S}(1 - p_j)$$$ is the probability that the $$$i$$$-th segment appears and all other segments don't appear.
$$$dp[k]$$$ is the probability of covering the first $$$k$$$ cells.
Then the product $$$dp[k] \cdot \text{coeff}$$$ doesn't make sense to me. On the one hand, $$$\text{coeff}$$$ doesn't allow any segments other than $$$i$$$-th segment to appear. On the other hand, $$$dp[k]$$$ allows some segments other than $$$i$$$-th segment to appear.
Oh I got it.
$$$dp[0] = \prod_{j\in S} (1- p_j)$$$ is the probability that no segment appears.
Suppose the first $$$k$$$ cells can only be covered by the $$$s$$$-th segment, then the probability is $$$dp[k] = {p_{s} \over 1 - p_{s}} \cdot \prod_{j\in S} (1- p_j)$$$
Suppose the next $$$l$$$ cells can be covered by the $$$t$$$-th segment, then the probability is $$${p_{t} \over 1 - p_{t}} \cdot {p_{s} \over 1 - p_{s}} \cdot \prod_{j\in S} (1- p_j) = dp[k] \cdot {p_{t} \over 1 - p_{t}}$$$.
$$$dp[k]$$$ already makes sure that the $$$s$$$-th segment would appear.
Your explanation helped me to understand it too
Thank you too much
BTW it works with paths summation also, multiplying $$$\frac{p_t}{p_t-1}$$$ by $$$dp[k]$$$, means to distribute the fraction to be multiplied by each selected path then take $$$\cup$$$ to them all
I can't believe there are over 4000 solves on D. I thought I was doing pretty good when I solved it around the 70 minute mark. I guess it was not such a difficult problem after all...
Nah man, a lot of newbies and pupils have solved it and looking at some of the solutions it’s clear that they have used AI.
https://mirror.codeforces.com/blog/entry/144923?#comment-1296466
can anyone explain the sol of D?
First of all, notice that each points must be covered by exactly one segment.
Let the success probability be the probability that the segment exists, and the failure be the probability that the segment fails to exist.
Assume that you have a set named $$$S$$$, where $$$S$$$ contains any set of segments indices that can cover all the points.
This is how to calculate the probability of one valid tiling, but we need all the different combinations of valid tilings.
We have
and since
is just products, we can do the following trick.
Notice that the right term is the global product failure, so factor out this, calculate it and save it in a variable for a later multiplication.
The first term can be calculated using DP for different tiling combinations, and then multiply by the factor
What do you guys think is the probable rating of C?
1000-1200, standard PIE problem, once you understand PIE it’s super easy. But this is just my personal guess. As many people are saying, its rating will be deflated due to cheaters.
Im surprised I didn't know about PIE before this contest, it is very well known topic apparently.
Yeah it’s fine, I know about it only because I did competitive math in high school. Take more contests and that stuff will stop happening. Learning is the whole point of edu.
I can't believe so many people solved Problem D. I suspect that many of them used AI to solve it.
Same with C honestly, inclusion-exclusion principle is a pretty standard trick but not one that I would expect the average 1200-rated user to know
It took me 1 hour and 30 minutes to do problem D. It took me like 20 minutes, basically way longer than it should've taken me, to figure out how to manually calculate the simple first test case, and then it didn't take me that long to figure out the DP formula after that and it was correct from about the first time I figured it out, but then it took me at least 40-50 minutes to debug mistakes which were ALL related to mixing up
(1 - p)and1/p(e.g. using (1 — p) instead of 1/x to get range product from a prefix product, using 1/p instead of (1 — p) for probability not, basically really stupid mistakes), before managing to submit and AC in the last 5 minutes lol.bruhh i forgot it cauze hollow knight
Yay, my first ever hacks! They are super simple inputs though, they (or similar) should have been part of the pre-tests imo.
which p ?
A
BRUHHH it just sort and reverse GG
AIForces Edu Round. A~C are brainless. My grandma can solve them with her toes.
My grandma runs faster than the code
To be fair, if not for the existence of our AI overlords, problem C was a nice educational problem since it relied on the inclusion-exclusion principle which is a common mechanism in some more difficult problems (although here, obviously, it was just hardcodable)
True. But with AI and a classic D, this contest has become a speed contest. Almost four thousand people passed D but only hundreds of people passed E and F.
Yeah, D was too easy and E probably a bit too hard
Why is it unrated?My performance was good(4 problems solved),and I hoped a lot on it,but it is unrated!
Why was Div2 cinsidered unrated for me? I selected rated?
Div not end yes still hacking working after that more judjing
Same for me, in my contests section it's showing as unofficial, it was my best performance and i won't even be rated lol
same here
Can anyone explain as to how the first test case has the answer 5/18 for the Problem D
I made the same mistake Basically the entire segment will be on/off with probability not individual cells
There are two cases that all cells are covered exactly once: The 1st and the 2nd segment appear, the 3rd one doesn't appear; or the 3rd one appears and others don't.
Than the answer is $$$\frac{1}{3}\times \frac{1}{2}\times\left(1-\frac{2}{3}\right)+\left(1-\frac{1}{3}\right)\times \left(1-\frac{1}{2}\right)\times \frac{2}{3}=\frac{5}{18}$$$.
Can problem D be solved with sweep line and partial product?
xD
I was writing the solution for someone for some problem and mistakenly typed it here, sorry for this.
speedforces, AIforces, ...
How to solve E ?????
It looks like a Knapsack problem.
I could derive one observation. Sum couldn't be more than 2*x ( x is given in the input ).
But couldn't proceed further than that.
If the original array
acontains the element 1, we can add 1 toa, causing all elements in the complementary sum setQto increase by 1.Examples:
-
a = {1, 2, 3, 4}→Q = {6, 7, 8, 9}-
a = {1, 1, 2, 3, 4}→Q = {7, 8, 9, 10}Now consider incrementing suffixes in
a:- For
i=2: Modifyato{1, 2+1, 3+1, 4+1}→Q = {6+2, 7+2, 8+2, 9 + (n - i + 1 = 3)}- For
i=3: Modifyato{1, 2, 3+1, 4+1}→Q = {6+1, 7+1, 8+2, 9 + (n - i + 1 = 2)}Define an array
dp[y], whereyrepresents the maximum value inQ.When incrementing suffixes starting at position
iina, the dynamic programming update rule becomes:dp[y] += dp[y - (n - i + 1)]Finally, to calculate how many 1s can be inserted into
a(given a target maximumx):ans += dp[y] * (x - y + 1)My English and expressive abilities are limited, so my explanations might be a bit unclear. Sorry.
.
So much math honestly, a bit tough as it was my first time on codeforces. I'm your usual leetcode guy.
Hello Codeforces team,
I received a plagiarism warning for my solution to Problem C (2122C): https://mirror.codeforces.com/contest/2122/submission/329867080.
I would like to clarify that I solved the problem entirely by myself and did not copy anyone else’s code. The approach I used (sorting by x, splitting into two halves, and sorting again by y) is a common one, and this may have caused similarities with other users’ solutions.
I did not share my code or collaborate with anyone during the contest. If needed, I can provide my thought process, logic, or handwritten notes.
Kindly review the case. Thank you for your time.
Regards,
karyampudikomal417
The difference between D and E is too much ,problems are ok but this problemset shouldn't be approved.
Yeah, also D was relatively easy so it was a bit speedforces for the mid-rated users... But I think C and D are pretty cool problems at least
Loved the contest! Also, my first A, B, C in Div. 2.
Yay
Clean solution for problem C:
Dear Codeforces team,
I received a plagiarism warning regarding my submission 329503821 for problem 2126B. I want to clarify that I did not copy or intentionally share my solution. If there was any unintentional leakage (e.g., through an online IDE with public access), I sincerely apologize. I respect Codeforces' rules and will be careful going forward.
Please review my case. Thank you for your time and consideration.
— siripuramvinodkumar333
Using iostream, excessively verbose comments, unusually long variable names, and mixing C++ with Python in a single contest submission- these patterns strongly indicate that the solution was generated using AI tools. It would be more appropriate to acknowledge this openly and consider refraining from participating in competitive programming under such circumstances.
为什么我这一场比赛的rating到现在还没有结算嘞？为什么主页的比赛记录显示unrated？
is it unrated
Editorial when? Want to figure out how F right now.
It's out now
can any correct why this is wrong for problem -B
if (a == b || (gcd(a, b) <= k && gcd(a,b)!=1) || (a <= k && b <= k) || (a == 0 && b != 0) || (b == 0 && a != 0)) cout << 1 << endl; else cout << 2 << endl;
long long a,b,k; cin>>a>>b>>k; long long m=gcd(a,b); if(a/m<=k&&b/m<=k) cout<<1<<endl; else cout<<2<<endl;u have included multiple checks which can be done in a single line. Also, if you have failed in testcase 3 it might be due to int overflow that can be catered by long long type variable, committed this mistake in contest.
This case is wrong:
(gcd(a, b) <= k && gcd(a,b)!=1)gcd(a, b) only indicates how many times you have to use the operation, not the actual lengths of dx and dy. Consider this test case:
1
2 6 2
Your code will give 1, because gcd(2, 6) = 2 <= k
But in reality, it needs to use dx = 1 and dy = 3 for the cost to be 1, but dy = 3 > k so the answer should be 2.
To calculate dx, dy:
dx = a / gcd(a, b)
dy = b / gcd(a, b)
when will ratings came?
Patience
``` #include <bits/stdc++.h> using namespace std; long long gcd(int y, int x) { while (x) { y %= x; swap(y, x); } return y; } int LeftDown(long long a, long long b, long k) { if (a <= k && b <= k) { return 1; } long long x = min(a, b), y = max(a, b); if (x > 0 && y > 0) { long long d = gcd(y, x); a /= d; b /= d; if (a <= k && b <= k) { return 1; } } return 2; } int main() { int t; cin >> t; while (t--) { long long a, b, k; cin >> a >> b >> k; cout << LeftDown(a, b, k) << endl; } return 0; Whats wrong in this code its giving wrong answer on 3rd test } ```Why this contest is classified as unrated I wanted to increase my ELO?!__
But its written rated
got +413! I'm finally rated on codeforces!
Any tips to beginners for reaching master quickly in minimum amount of contest
Hope it helps me to become pupil :)
Hello, my solution was flagged as coinciding with others. I realize I might have unknowingly caused this (maybe by using a public IDE). I assure you that I will never repeat this mistake again and will strictly follow Codeforces rules. Please give me another chance.
Hello, I recently received a plagiarism warning for my submission. I understand that my solution was flagged as similar to others. I realize that I might have unknowingly caused this issue, possibly by using a public IDE or by not being careful about keeping my code private. I take full responsibility and assure you that I will strictly follow Codeforces rules in the future. I will only use my own account, avoid sharing solutions, and never make my code public during contests. Please consider giving me another chance. I will make sure this does not happen again.
Hi,
My submission to the problem 2125D has been skipped due to similarity with some other submissions.
Binary exponentiation for modular inverses under a prime modulus is standard in competitive programming. Fermat’s Little Theorem (
a^(mod−2)) for inverses under a prime modulus is also standard in CP.The expression used
((q-p+MOD)%MOD)* invq%MODis inevitable when implementing(q-p)/qin modular arithmetic.Below is my template which I used for this question: Link
Question 2125C was also from my notes,99% same code,see yourself Link
Please look into this matter awoo,MikeMirzayanov and unskip my submission.
Educational Codeforces Round 181 (Rated for Div. 2) Dear Codeforces Team,
I am writing to respectfully appeal the plagiarism notice regarding my solution 330384162 for problem 2125D. The system has flagged it as being significantly similar to submissions from Niki_fx/330343057 and others. However, upon manual inspection, I believe this is a false positive.
Here is a comparison of the key differences:
using ll = long longandmodexpfor modular inverse.totalB,ends,dp, etc.) and modular arithmetic structure.int64,int128,all(), or debugging conditionals (#ifdef DEBUG) as used in the flagged submission.Attached below is my full solution (also visible in the submission):
If any similarity has arisen, it is purely coincidental or likely due to the constraints of solving a structured DP problem involving modular arithmetic with probabilistic weights — which tends to have common patterns (e.g., use of modular inverse, array of vectors, and accumulation loops).
Please look into this matter awoo,MikeMirzayanov, and I kindly request you to lift the plagiarism flag and restore any rating penalties if applicable.
Thank you for your time and for maintaining the integrity of the platform.
Sincerely,
Codeforces handle: lonely_warrior_lak0708
My Code (lonely_warrior_lak0708, Submission 330384162)
~~~~~
I recently received a message that my solution for Problem 2125B (Submission ID: 330358733) significantly coincides with other users’ submissions.
I want to clarify that I wrote the solution independently during the contest and did not engage in any kind of collaboration or cheating. However, after reviewing the situation, I realized that I may have accidentally made my submission publicly visible on a GitHub repository that I was using to track my contest practice and submissions.
If that is indeed the cause of the similarity, I sincerely apologize — it was entirely unintentional and due to a lack of awareness about the implications of keeping such repositories public. I have since made the repository private and will take all necessary precautions to ensure this does not happen again.
I respect the rules of Codeforces and the integrity of competitive programming and hope you will take this context into consideration.
Please let me know if any further clarification is needed.
Sincerely,
I received a message about code similarity in my submission for problem 2125A.
→ Submission ID: 330336557
→ Username: Darsh_01
I have an explanation for this because on_loop is my other account for my brother and when I gave the contest, it was logged in that account but while solving the problem 1 I did not realize it till i submitted, so I then changed to my original account, submitted that code and then solved further problems from my original account. I am soory for this and will make sure this will not happen any further. Let me know if further clarification is needed. You may check the login email-id for both accounts, they are same as these both are my accounts only
Regards,
Darsh_01
As I attempted this contest round ,I suggest everyone to try this as a virtual Contest