I thought the problem was cool

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?

too math, downvoted...

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

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

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 :(

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

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.

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

I'm also a team member:(

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?

Yay!

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

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

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

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.

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

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

Hope you can reach IGM! ^_^

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.

The model approach is the following one:

orz rui_er

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

because there's no sponsor :(

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]

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.

These are some good problems 💪💪🔥🔥

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.

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://codeforces.com/blog/entry/126124). I studied it today.

proved by ac

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.

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

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.

I went through your blog and comment history and I can't comprehend a single sentence of what you write.

From Pakistan (unofficial online)

Sir-Ahmed-Imran

Ghulam_Junaid

Kaleem_Raza_Syed

Muhammad-Saram

CNOI Round 🤓👎

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

o(4)

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

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

Both Chinese and English statements are provided.

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.

when testing gets more upvotes than the actual contest

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 :(

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

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

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

ur cyan tho

Xylenox has improved quite a bit since then damn

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

The submission

After updates i will be able to participate:)

As a tester, the problems are cool!

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

Thank you very much, the confirmation that I am on the right track motivated me to keep going. I just got AC on it

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! :)

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.

it had some very nice problems, definitely

thank you for point out that. obvious self deception

It seems that there are many alternative solutions to E2. Looking through the submissions, here are some that I don't understand (and they look quite different from the editorial):

258928492 258921598 258925888 258917151

jiangly maroonrk maspy potato167 Would any of you mind explaining how your solution works? :)

Assume that I eat one portion of instant noodles once a month since 20 years ago. Assume I have eaten $$$1 \times 12 \times 20 = 240$$$ portions of instant noodles throughout my whole life. If $$$1$$$ portion reduces my life by $$$30$$$ years, does that mean that I should have died $$$7200$$$ years early?

Notes: I definitely eat a lot more than one portion every month.

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.

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

Yeah, that's right. But the good thing is that I don't have to solve any equation. Just let matrices do it!

I dont think a simple change in the format will make it significantly more exciting to watch. The biggest issue is that there is no visual aspect that a amateur viewer could follow. Traditional sports and chess, for example, have easy to understand rules and ways in which users can follow. Watching someone code something you do not understand at all is not fun.

A big part of following competitive programming is just watching the scoreboard and maybe some reactions on ACs, maybe eventually with a high production you could capture moments like the coder going for a constant optimization or something. But in general the viewer needs to at least actively read the statement to understand what is going on, but that is too much effort.

I solved 100% problems using C11

B2 is restarted

congrats

Is there any issue/delay in updating rating of this round?

I'm gonna try to make it gm instead of noobie :)

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

Just doing cp because it's fun, not planning for future.

Actually, there already exists a task which asks for pretty much the same thing: here

In the solution of the task, you can see that it's possible to do in $$$(n+q)log(n)$$$, which is probably better than $$$n*log(n)^2$$$. If you want a hint on how to do it this way, try to think about Euler Tour and LCA only, and don't use HLD. (If you want to solve an easier version of the task first: BOI 2017 — Railway)

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!

B2 is an easier problem of an IATI problem: https://infos.infosbg.com/files/Contests/IATI/2022/day1/Senior/statements/A3_divide_en.pdf

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

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

please provide an update on when the rating will be updated?

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

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

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

Interesting!

$$$a+b | b\cdot (a,b) \rightarrow g(x+y) | g^2y\space \space(let g = (a,b) ,x = a/g , y = b/g) \rightarrow (x+y)|gy \rightarrow (x+y)|g \space \space((x+y,y)=(x,y)=1)$$$

When you found that $$$x+y | g (xg=a, yg=b, g=(a,b))$$$, you will realize that $$$(x+y)g \le n+m$$$ and $$$x+y \le g$$$ which means that $$$x+y \le \sqrt{n+m}$$$, so you can brute force every possible (x,y) and solve the number of g.

Nope, never. Regardless of the difficulty of the question, plagiarism is a serious issue.

Attractor breaking records. Nice,

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://codeforces.com/blog/entry/90477, where the greedy algorithm is just stated as-is, and then see lior5654's very helpful blog at https://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