Привет, Codeforces!
Благодаря поддержке Neapolis University Pafos, продолжается серия образовательных раундов. Университет предлагает получение степени бакалавра в области компьютерных наук и искусственного интеллекта со стипендиями JetBrains. Получите передовые навыки в области искусственного интеллекта и машинного обучения, которые подготовят вас к востребованным техническим карьерам. Доступно ограниченное количество стипендий. Не упустите свой шанс учиться в Европе бесплатно!
В 22.07.2025 17:35 (Московское время) состоится Educational Codeforces Round 181 (Rated for Div. 2).
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов, Максим Neon Мещеряков, Максим FelixArg Новоточинов и Полина ifive Пикляева. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Спасибо тестерам раунда shnirelman и Brovko за ценные советы и предложения!
Удачи в раунде! Успешных решений!
UPD: Разбор опубликован
I hope to get specialist in this contest, I have a high hope for it. And, BTW, is online class for the university avialiable?
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
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
another edu, hoping to get back to pupil
Is this competition has open hack?
Yes, as mentioned in the contest announcement.
I hope to educate in this round
As an unrated participant, good luck to all rated participants.
what about score distribution ?
I think all problem has same value, I could be wrong.
i hope this contenst doesnt ->()(->)-> ->()(->)-> ->()(->)-> ->()(->)-> ->()(->)-> me
I don't speak unga bunga, care to elaborate?
it certainly ff**ed me
Hi everyone, could someone explain the differences between educational and regular contests?
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.
aahhh. bad experience for me, cause swap n, m I took about 30-40 min on debuging.
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)
No way these many people were able to solve problem D, I suspect AI.
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).
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.
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
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.
Let'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 += prdwas D dp on tree? i tried to dfs for each u to v and dp[u] stores a pair which is the probability that i can reach m from node u
how 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.
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
dp wasn't too hard But I don't think that many beginners (including myself) know how to measure.
I died on the modulo implementation. Knew how to solve the problem in floats but the modulo implementation was too hard to debug :/
12k people for C is crazy, so much AI used
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. ((((((
(((((
Here's my solution to problem C. Let the Hate come.
orz
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!
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
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?
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.
i don't know c is very easy like after 40 to 50 minutes 8-9k solved that problem
i mean, classic known topic
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.
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
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
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
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://codeforces.me/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
codemart786
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
Nice contest, AIForces.
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://codeforces.me/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.
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.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
Hello everyone
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.
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
为什么我这一场比赛的rating到现在还没有结算嘞？为什么主页的比赛记录显示unrated？
Editorial when? Want to figure out how F right now.
It's out now
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,
Anyway, u cheated on recent div2 1111. (evidence — just look at his code)
As I attempted this contest round ,I suggest everyone to try this as a virtual Contest