I thought the problem was cool

The difficulty and quality of the problems are high. It is recommended to challenge yourself here.

not enough persistent segment tree...

My take:

• The only data structure problem here is 1967F - Next and Prev.
• All the problems up to 1967C - Fenwick Tree have almost no implementation.
• Yes, there is a lot of maths. But I prefer an unbalanced contest rather than a contest with bad problems.
• In this contest, $$$26$$$ problems were proposed, and I didn't just accept a random subset of $$$8$$$ problems.
• Most testers confirmed that problems looked good. Are there so many people who don't like this round?

As an author of the contest, problems are great and challenging.

IOI rule brings more strategic choices. Remember that your task is to maximize your score.

Good luck & have fun!

My pre-contest predictions:

• Math
• Data structure
• Implementation

Seems that all my predictions are correct!!

"Thanks" for such a round to let Chinese Rounds become stereotyped!!!

D1 is not mine, it was accidentally invented by the tester newb_programmer while he was solving D2.

too math, downvoted...

Why downvote me, it's the truth...

I'm also a team member:(

I like Div1E, thanks, though I couldn't make it on time...(QAQ) Here is my solution.

We can rephrase the problem as a random walk:

• The states are $$$-1, 0, \ldots, m-1, m$$$.
• Start at $$$b_0$$$.
• States $$$-1$$$ and $$$m$$$ are absorbing.
• From states $$$0, \ldots, m$$$, decrement with probability $$$1/m$$$, increment otherwise.
• Let $$$z_i$$$ be the probability that it does not end up at $$$i$$$ after $$$n$$$ steps. The answer is $$$m^n (1 - z_{-1})$$$.

If we had infinite number of steps instead of $$$n$$$, the problem would be classical. Let $$$f_i$$$ be the probability that, starting from $$$i$$$, it is eventually absorbed at $$$-1$$$ after infinite number of steps. We have $$$f_{b_0} = z_{-1} + \sum_{0\le i\le m-1} z_i f_i$$$. It is known that $$$f_i = \dfrac{(m-1)^{m-i}-1}{(m-1)^{m+1}-1}$$$ for $$$m \ne 2$$$ and $$$f_i = \dfrac{m-i}{m+1}$$$ for $$$m = 2$$$. (Caveat: What if $$$998244353$$$ divides the denominator? It turns out no such case exists within the constraints, luckily.)

To compute $$$z_i$$$ for $$$0 \le i \le m-1$$$, we can reduce it to certain path counting and use reflection method as in the editorial. It takes $$$O(n/m)$$$ time for each $$$i$$$, thus $$$O(n)$$$ overall. (Caveat: The sum of $$$m$$$ is not bounded! We should do this only for $$$b_0-n \le i \le b_0+n$$$.)

FST on D is just me being blind, seeing $$$5$$$ generators (with two of them which weigh 7 KB) and missing $$$n = m$$$. This is the second time I miss this detail, I hope the third time does not happen :(

As a tester I don't know what to comment.

About the last point: feedback is from the testers, which cover a wide range of ratings. In this case there was no big complaint from any tester. Maybe the testers overestimate the beauty of the problems?

Hope I can reach IGM lol

wow CN Round! Hope I can return home on time :D

"I wonder how you folks (BledDest, adedalic, Neon, Roms, awoo) come up with so many tasks. It's like you've been holding Educational Rounds since the invention of sliced bread=)

Yay!

If you like MO this much, you could try asking these on AOPS. That way, non-mathematicians can focus on coding! Leave us some problems!!!

Worst contest I have ever seen!..

I don't think that this round deserves hate. div2A-D2 were all good. I say that as someone stuck on D2 for almost 2 hours. My final submission was rejected because of strict limits. However, the trick $$$p^2 < n$$$ can compensate for it. I find it fascinating, and I am glad to have seen it. The model code is much simpler than mine.

The downside is that all problems (the ones I attempted) had the same (math) tag. But, it is a common trend nowadays. We cannot do anything about it, so cope.

Hope you can reach IGM! ^_^

Loved the round, thank you! The best moment of the contest for me was when I started coding Persistent Segment Tree in Div.1 D (it wouldn't have worked probably) and realized that there's a cute solution with much less code! Though E1 looks like a pretty standart problem to be honest...

As a tester, I comment after purp4ever for a living.

orz rui_er

As a tester, hope you enjoy the problems!

The model approach is the following one:

Absolutely agree! And also when newcomers see such lines, they get a feeling that it is not that important to prove their solutions, and it is ok to guess which doesn't lead them good places.

IOI rule. You can get the result after submit

because there's no sponsor :(

How to solve B2? The max I could reduce the problem to is that any pair $$$(a, b)$$$ must satisfy $$$((a / g) + (b / g))$$$ divides $$$g$$$ where $$$g = gcd(a, b)$$$, but I still have no clue how to actually count this faster than $$$O(n \sqrt{n} \log{n})$$$.

Also B2 >>> C in my opinion, it took me ~15-20 mins to come up with the overall approach for C while I was unable to get anywhere on B2 after 1.5hrs of thinking T_T.

std::set has a lot of overhead as it uses a tree structure, so you end up using a lot of time allocating and deallocating memory, rebalancing the tree, etc.

As far as I know, separate rounds are just the default for historical reasons. I think there is no big difference between separate and combined rounds (i.e., just those 5 minutes).

[maybe having separate rounds instead of combined rounds also affects the rating system? I have no data about that]

I enjoyed div1C a lot, thank you! I came up with a solution different than the one mentioned in the editorial (using matrices).

And here is my submission : 258943002

D <<< C

I think as much I hate CodeChef, I gotta give it one thing: its editorials are really nice to read, because the author != editorialist, the editorialist is someone who specializes in writing editorials. Maybe the author doesn't have enough time, or doesn't know enough LaTeX to write a good editorial, or doesn't know English that well. That's no problem! Just hire/volunteer three or four editorialists who are reasonably experienced (maybe IM+?), and who know how to write a good editorial, know how to write LaTeX, know english, know how to write proofs that are not just "trust me bro". I'm pretty sure a lot of people would be willing to do this sort of thing, and it would really improve the quality of practice on CF.

These are some good problems 💪💪🔥🔥

proved by ac

Certain div1 people have replied to me with "so i dont need to solve 2 more trivial problems"

Doesnt make sense to me because it takes 5 mins but ok

Will the rating changes before 942??

Sounds great!

NOI au's problems/se

Here's how you can normally resolve situations like this during the contest.

• Write a very naive and simple solution to the problem (maybe exponential complexity). One that tries to use no "special" logic, just the barest possible brute force. In this problem, it would be recursively trying to apply the operation on every position.
• Write a program to generate thousands of small test cases.
• Using those two, find a test case where your program gives the wrong answer.

By the way, I would be careful about calling counterexamples to your solution "edge cases". I mean, sometimes it's true and your solution is just wrong on some very specific cases like $$$n = 1$$$ or whatever. But it might be that your solution is just wrong.

For example in this problem, all your program does is finds the pair of adjacent elements with the largest difference and applies the operation to that. But for example, this means you do

while it would be better to do

I don't think it's fair to call this an edge case. Rather, it's an example demonstrating something that your program doesn't take into account: it might sometimes be better to make a not-so-good operation because it opens up very good operations for later.

From Pakistan (unofficial online)

Sir-Ahmed-Imran

Ghulam_Junaid

Kaleem_Raza_Syed

Muhammad-Saram

He is involved in reviewing the problems.

as a Minecraft lover , I hope there is Minecraft in the tutorial

o(4)

Your solution 258433137 for the problem 1966B significantly coincides with solutions cyyzzxx/258425816, SpringBreeze/258427226, JobairHasib/258432282, Tahirliyev/258433137, Levisa/258433632. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://mirror.codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.

I want to address the message that i got that talks about the coincidence between my solution and others (see above) for problem 1966B. This similarity was purely coincidental and not intentional on my part. I want to clarify that I did not engage in any form of plagiarism, nor did I publish my code online. So I would kindly ask the codeforces team to verify the submissions again and accept my solution.

It would be cool to continue the tradition with photo of authors and coordinator:)

Hi, I've fixed it. The rating will be recalculated once the cheaters have been processed.

CNOI Round 🤓👎

Many solutions to problem A, including mine, are hacked, because of set.

How is it possible? The time complexity is $$$O(t∗n∗(n−1)/2∗4∗log(4))=O(5∗10^7)$$$ which should not work longer, than 2 seconds.

I have solved ABCDE, and would become a master, if my solution to A wasn't hacked :(

Fantastic Edu round as always. Thanks a lot BledDest awoo adedalic Neon Roms and all testers!

I think you have commented on the wrong blog.

as a tester, hope you enjoy this round. This is certainly a very interesting round and I personally enjoyed it a lot, hope you guys have fun!!!!

A brutal solution for 1C: Let $$$T$$$ be the linear operator that does the "Fenwick tree" transform, one can verify that $$$(T-I)^{k}=0$$$ for $$$k = \log n$$$. So to solve the equation $$$T^m v = a$$$, just compute the coefficient of $$$x^{-m} \bmod (x-1) = \sum_{i<k} c_i x^i$$$, thus we have $$$v = \sum_{i<k} c_i T^i a$$$. Since $$$T$$$ can be applied to a vector in linear time, this has time complexity $$$O(n\log n)$$$.

I have solve the problem E by Monotonic Stack in O(n).

The submission

i spent more time thinking about B2 than any of CDE.... I even had to use OEIS as a crutch for B2 (https://oeis.org/A063647 is the number of possible $$$y$$$ for each $$$x$$$) cause im too stupid at NT

After updates i will be able to participate:)

thx

I like violet :D

I wrote down brief solutions on my blog (https://errorgorn.github.io/2024/04/30/COI.html) if anyone wants to know solutions before the official editorial is released

Do tell me if there are more elegant solutions

mathforces

Thanks for business. We had a great time there with you guys as well. How are you enjoying the Vietnamese noods? :P

Authentic Indomie were great. The taste was noticeably stronger than the Vietnamese version. I'm soooo glad I brought my own local noods to trade with more of the Indo ones.

If you come to Vietnam/HCMC again (perhaps for another regional), hit me up and I'll treat you to some delicious local food. Perhaps we can even trade more noods of the other varieties.

Lol, I thought about the model solution to E1, but also thought "Huh? quite weird $$$O(min(nm, \frac{n^2}{m})$$$ tradeoff solution with a ton of detailed math? I'm not coding that for 1750 points! There must be some much slicker way to do this!" and that turned out to be exactly the intended solution xD... But I managed to get D instead and I wouldn't be able to do both anyway

pls no guessforces

remove all elements that are not divisor of k as they cannot form a valid pair
The number of divisors has $$$O(n^{1/3})$$$ upper bound so you can just bruteforce after removal

What’s the reason to prefer separate rounds over a combined round?

E can solve by Monotonic Stack in O(n),so the timelimit is enough. Code

Seeing "You" in legendary grandmaster colour felt so heartwarming even though I might never get there.

B2 is restarted

I'm gonna go and say some obvious thing, that's always mentioned in such blogs: you've solved only about 45 problems out of 150 with rating >= 1600. And only about 3 of them are >= 1800. The conclusion is: solve more harder problems, preferably without editorial

Why more and more gcds?They are not interesting!!!!!!!!!

Both Chinese and English statements are provided.

I posted my code of problem D in the last 10 seconds, but the evaluator didn't receive it.

After the contest finished, I reposted my code, and then it was accepted.

Now I wanna die right now.

我觉得你并不应该在 CodeForces 上使用中文。

Can you tell me your password? I will try to help you log in.

it had some very nice problems, definitely

when testing gets more upvotes than the actual contest

After upsolving Fiendish Five, an easy way to prove $$$4$$$ is enough, is to try some combinations of $$$4$$$ vectors, and try to find the inverse of the $$$4 \times 4$$$ matrix, where you remove the last element (it does not matter, as all entries in a vector sum to $$$0$$$). Once you find an inverse which is fully integer, that's a proof.

yes in edu round 155.

Romanian teams (I don't know all their CFs) -- they all compete online

atodo + 3 others

IvanAndrei, anpaio, andrei_C1, andreimarciuc7

lucri, nstefan + 2 others

Last update of this post, I added a few teams and some emojis to highlight the most outstanding teams. In a few days, I'll create the post for the next WF. See you in Kazakhstan! :)

thank you for point out that. obvious self deception

In Edu, many solutions to problem A, including mine, are hacked, because of set.

How is it possible? The time complexity is $$$O(t*n*(n-1)/2*4*log(4)) = O(5*10^7)$$$ which should not work longer, than 2 seconds.

I have solved ABCDE, and would become a master, if my solution to A wasn't hacked :(

Hopefully my solutions will not get hacked in this round.

I really liked problems D and E!

Yes, the $$$i$$$-th value is actually $$$\binom{k+i}{i}$$$. If you turn your head, you should try see a pascal triangle

We can also solve Div1C in $$$O(n \log^{2} n )$$$ by maintaining the generating function $$$g_{i}(x)$$$ for every position $$$1 \leq i \leq n$$$, where $$$[x^{n}]g_{i}(x)$$$ denotes the value of $$$f^{n}(a)[i]$$$ where $$$a$$$ is the array we are trying to find and $$$f$$$ is the "fenwick function" from the statement. We maintain it by processing $$$i$$$'s in the ascending order of their lowest bit and summing up the generating functions. The result can be extracted as $$$a[i] = [x^{k}]g_{i}(x)$$$.

I found myself waking up six times throughout the night, hoping to see my new 'Max Rating,' yet it remains unchanged even now!

Will the ranking be published after mirror finishes?

Hope everyone will not get stuck in A, B and C.

If you want to calculate $$$a + b$$$, you can create $$$dp[1] = a$$$, $$$dp[2] = b$$$, and calculate $$$dp[3] = dp[1] + dp[2]$$$. This is what this blog about.

My solution discussion stream

Let's think of a strategy for Bob. If I take s elements (s>k) then he will choose s-k elements with the minimum b. That's obviously true because sum of a is fixed and to minimize the profit Bob will choose the smallest bs. Now, I'm Alice and I know that. Then I wiill check each b. If I fix some b[i], then for all b[j] such that j>i I will choose minimum k as from them. I know that since they are k and Bob will choose minimum bs, he will not choose from them. So now remains the elements in the prefix of i. Any element I will choose in this prefix, Bob will choose it too. So I want all positive profits in this prefix. I'm not sure if this is kind of a proof, but this was my though process.

I don't believe in proofs very much, but I also believe that proofs of a lot of problems (especially greedy algorithms) are severely lacking right now. They're basically like, trust me bro. Actually, I've seen a pretty helpful website called CP Notes that allows users to write their own notes (editorial) for a problem in which they think the editorial is not possible to understand. As an example, take problem D of https://mirror.codeforces.com/blog/entry/90477, where the greedy algorithm is just stated as-is, and then see lior5654's very helpful blog at https://mirror.codeforces.com/blog/entry/90476 and https://cp-notes.com/notes/fivesixfivefour/CodeForces/1521/D, which has a full proof for the greedy they use. Ok well to be fair, some people proved it in the comments, and this is a 2500, so this proof probably should be doable if you're doing 2500s, but still like, you need to have a proof (even just a sketch) for your own sake because it's really easy to trick yourself into thinking "oh this greedy obviously works" when it really doesn't and then you get an NP hard problem at problem C cough cough

just want to know what does the score distribution (1000 + 1500) mean?

two problems or something else?

Auto comment: topic has been updated by rui_er (previous revision, new revision, compare).

your complexity is $$$O(answer * log(n))$$$ :) max answer is $$$11680996$$$

It is actually a problem from IMO(A3) link

Let $$$path_{[0,M)}(b,i)$$$ denote the number of Dyck path from $$$(0,b)$$$ to $$$(i,0)$$$, which lies within the range $$$0 \leq y < M$$$. Then, we need to compute $$$\sum_i f[i] \cdot path_{[0,M)}(b,i)$$$ for some coefficients $$$f[i]$$$.

By the reflection principle, $$$path_{[0,M)}(b,i)$$$ can be represented as $$$\sum_{b'} (\pm 1) \cdot path(b',i)$$$, where $$$path(b',i)$$$ has no restriction to the range of $$$y$$$.

Therefore, we need to compute $$$\sum_b (0 \text{ or } \pm 1) \cdot \sum_i f_i \cdot path(b,i)$$$. So, the problem is reduced to computing $$$\sum_i f_i \cdot path(b,i)$$$ for each $$$b$$$. In other words, computing the composition $$$\sum f_i(x+x^{-1})^i = f(x+x^{-1})$$$.

In this case, we can show that $$$f_i$$$ forms a geometric sequence (from $$$b_0$$$ to $$$N-1$$$), and $$$f(x)$$$ takes the form of $$$(\text{a sparse polynomial of degree N+1}) / 1-rx^2$$$.

Therefore, $$$x^{N-1}f(x+x^{-1})$$$ is a polynomial of degree $$$2N+2$$$ divided by a polynomial of degree $$$4$$$, and this can be computed in $$$O(N)$$$ time.

By the way, the composition $$$f(x+x^{-1})$$$ can be computed in $$$O(N\log N)$$$ time (https://mirror.codeforces.com/blog/entry/126124). I studied it today.