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

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

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

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.

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.

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

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

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.

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

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

As a tester, the problems are cool!

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 💪💪🔥🔥

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.

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!

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

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

CNOI Round 🤓👎

ur cyan tho

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

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

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

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'm gonna try to make it gm instead of noobie :)

tourist is back on top againnn

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

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

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

so happy for him, nice comeback!

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.

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

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

I solved 100% problems using C11

B2 is restarted

congrats

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)

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!

it is mid night here and i had to do mAtHs

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

Solving problems randomly while ignoring the tags. Try not to dwell on a topic for too long, as it will affect you. and practice makes perfect, enjoy your journey!

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!

flip burgers

the best for a reason

As a contribution farmer, I disagree

How to solve E1 using NTT?

For the $$$dp_{i,j}$$$ as mentioned, could understand that $$$dp_{i-1} \times (x^{-1}+(m-1)x^1) = dp_i$$$, but the transition has limit at -1 and m.

Does it use "circular convolution" trick (on CDQ processing) just like this AT problem?

Very good math problems and fast editorial. Thanks!

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

how have so many people in Div2 solved D2?

I hope there will be a plagiarism check for this Round, since apparently the solutions to Div 2 A, B, C and D1 were leaked hardly an hour into the contest.

Maybe it is an easier way:

let $$$s=a+b$$$, then $$$(a+b)|b \cdot \gcd(a,b)$$$ equals to $$$s| b \cdot \gcd(b,s-b)$$$, equals to $$$s | b \cdot \gcd(b,s)$$$.

It meens that, for each prime $$$p$$$, let $$$p^{k_1}|b$$$ and let $$$p^{k_2}|s$$$, then $$$k_1 \ge k_2/2$$$.

Calculate all prime factors of all integers, for each $$$s$$$, calculate the number of $$$b$$$.

We can also notice that $$$a$$$ must be a multiple of $$$b$$$ and iterate $$$b$$$ from $$$1,2,..m$$$ and $$$a$$$ from $$$b,2b,...n$$$, then it turns into $$$O(n\log{n})$$$.