We will hold AtCoder Regular Contest 178.

- Contest URL: https://atcoder.jp/contests/arc178
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20240519T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: potato167
- Tester: maspy, Nyaan
- Rated range: — 2799

The point values will be 400-600-600-700-1000-1000.

We are looking forward to your participation!

why put B in contest, nice ACD problems though

I completely agree with this statement. In my understanding math problem is ok for programming contest if it has at least something to do with programming. Problem B can be equally solved on a paper.

UPD: Wrong statement removed. I thought post author is contest author as well.Its not about it being too mathematical. That is perfectly fine. It is not about it being purely solvable on paper. That is also fine. All good problems are purely solvable on paper (by solvable on paper i mean write algorithm and verify correctness, only bad problems need you to experiment with the computer or non provable complexities)

It is about it being very obvious but yet a lot of effort to actually find the formulas, that too for so many cases.

By being solvable on a paper I mean the following: if you remove online judge and ask participants to submit their solutions as formulas with a little bit of text on a piece of paper, there would be no major difference. All you need to check is if the formulas are correct and all the required cases are considered. I honestly don't understand what problems of this type do in programming contests.

I never understood such comments

"I honestly don't understand what problems of this type do in programming contests",You are writing contest where you solve algorithmic/math puzzle problems, programming is side dish.

I follow a different philosophy. But yes, I have noticed that lately competitive programming became less about programming and more about math, which is unfortunate for people like me.

+1

The only.difference is that there is a judge which tells us our approach is correct true. What is the issue with that? MO proofwriting cant scale with number of contestants hence we adapt this

Good and interesting problems, thanks for the good round!

After more than one hour dealing with mathematics, I finally get B accepted. Somehow I thought that I was attending a mathematics exam :D

Thank you for the round, interesting problems as always!

What's wrong with this code please help me ATCODER ARC 178 B !!!!You are dividing without modulo, for example 1/2 is not 0 modulo 998244353, but you will get 0 as the result will be rounded down. Instead of dividing by int 2, using atcoder modint you must multiple by two.inv() with mint two = 2.

Still getting WA. Please Help

Good E but can't figure out the bug until contest end :(:(:(

upd: well i forgot a step for the solution (divide-conquer convolution)

Can anyone explain problem c please

For the problem B, can anyone figure out how the inclusion-exclusion principle is used to get that expression?

Problem C is very cool.

UPD: Got it.

Can anyone explain this part of the editorial of problem C?

I don't understand the last line. I tried to derive the 3rd equation from the 2nd but i only could derive up to this:

Yours are also correct. But we want to get the equation that is related to the difference between $$$B_k$$$ and $$$B_{k+1}$$$.

$$$l\le r,B_{r}-B_{l}=(B_{l+1}-B_{l})+(B_{l+2}-B_{l+1})+\cdots+(B_{r}-B_{r-1})$$$. We can think of it as intervals. $$$[l, r]$$$ includes $$$[l,l+1],[l+1,l+2],\cdots,[r-1,r]$$$. Now we have all intervals $$$[l, r], 1\le l<r\le n$$$ and we want to count the number of intervals that include $$$[i,i+1]$$$, which means $$$l\le i, r\ge i+1\Rightarrow i(n-i)$$$.

The official editorial of problem E noted:

Here, if $$$f(x)$$$ is a polynomial such that $$$[x^{i}]f(x)$$$ is the answer for $$$i$$$, the contribution of $$$j$$$ to $$$f(x)$$$ is $$$A_{j}x^{b+1}(1+x)^{j-b-1}$$$. However, if there exists a $$$j$$$ such that $$$j = b$$$, the contribution of $$$j$$$ to $$$f(x)$$$ is $$$A_{j}x^{j}$$$.

Therefore, if $$$c$$$ is the smallest integer satisfying $$$L \leq 2A_{i}$$$, and $$$B_{i}$$$ is the smallest integer satisfying $$$L - A_{b} \leq A_{i}$$$, the total contribution of all $$$j$$$ to $$$f(x)$$$ can be obtained by evaluating the following polynomial:

Since $$$B_{i}$$$ is monotonically decreasing with respect to $$$i$$$, and $$$i - B_{i}$$$ is monotonically increasing with respect to $$$i$$$, this expression can be evaluated in $$$O(N (\log{N})^{2})$$$ using divide-and-conquer and convolution.

Can anybody gives a clearer analysis of where the $$$f(x)$$$ comes from and how the formula is deduced? Additionally, what's the function of $$$c$$$? It seems that $$$c$$$ didn't appear in the following texts. Thanks a lot.