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

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

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

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!

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

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.

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

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

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.

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.

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

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]

These are some good problems 💪💪🔥🔥

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

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.

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

From Pakistan (unofficial online)

Sir-Ahmed-Imran

Ghulam_Junaid

Kaleem_Raza_Syed

Muhammad-Saram

Xylenox has improved quite a bit since then damn

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

Codechef needs to make some changes in its contest-making policies. Why do I think so?

As a tester, the problems are cool!

Every one knows that tourist is the greatest of all time. Whenever, I see posts like this I can't help but feel like the author is just trying to farm contribution by milking clout in the name of tourist.

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.

I also solved 5, but felt like the quality was noticeably lower than previous Starters. All the problems came trivially and I ended up wasting most of my time on implementation errors instead of the actual thinking.

Not sure about 6th and 7th problem but Div 1 A-E were just way too standard for a contest of this type.

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

CNOI Round 🤓👎

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

ur cyan tho

by now tourist is a legend of cf, having hundreds of fans.

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

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

After updates i will be able to participate:)

thank you for point out that. obvious self deception

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

I tried Omachi during the ICPC Asia Pacific Championship last February. It's so good (and so instant)! Thanks for bringing me another pack!

But, I haven't tried any of the noodles from the trade last ICPC World Finals as right after getting back to Indonesia, I felt unwell :(

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.

Thanks for telling us that you actually need to cook Vietnamese Indomie, not just pour hot water over it like cup noodles – now I wonder, should we contact the Vietnamese person who told us otherwise and shock him by this fact? 😅

Good point, I didnt mean that at all. I dont even realize the point of contribution like having a negative contribution is bad? Who gives an F
I just saw he got the first place back in while in subway just typed it in my phone to express the feeling

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

it had some very nice problems, definitely

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

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

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

As far as I'm concerned, E is a bit classical and similar to CF837F.

By the way, thanks anyway to this round that made me GM.

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

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

I solved 100% problems using C11

B2 is restarted

congrats

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

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

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)

so happy for him, nice comeback!

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

Well, here is the main contribution list of the writers.

• A：idea by rui_er, prepared by rui_er
• B：idea by rui_er, prepared by rui_er
• C：idea by yinhy09, developed by TheScrasse, prepared by N_z__, wyrqwq
• D1 & D2：idea by wyrqwq, developed by N_z__, TheScrasse (UPD : newb_programmer), prepared by N_z__
• E：idea by rui_er, prepared by rui_er
• F：idea by wyrqwq, developed by N_z__, prepared by wyrqwq, N_z__
• G1 & G2：idea by wyrqwq, developed by A_G, prepared by wyrqwq, N_z__
• H：idea by N_z__, developed by negative1, prepared by N_z__

Please feel free to tell us which is you favourite problem and why, and even the problems you dislike too. Meanwhile, I would also like to thank our hard-working coordinator and testers. They together made it possible for us to hold this round.

If there is a chance, we hope to meet again with better problems.

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!

tourist is back on top againnn

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

I just love to drive taxi. But I ain't sure what will i do.

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

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

two problems or something else?

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

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

It is actually a problem from IMO(A3) link

orz rui_er!

the best for a reason

I wish high rating to participants. Best of luck everyone.

I see an example in CodeTON Round 8 F there were 2 facts (shown as key "observations"):

• One can always add floors to the square root

• The square root only propagates at most 6 steps

Those 2 facts were left completely unproven in the editorial. Also the editorial is hard to read, and I can't understand it clearly, but it is not as important as the 2 unproven facts.

Very good math problems and fast editorial. Thanks!

I am still an expert and I didnt improve. :|