I used a 6-dimensional Fenwick tree. And laughed out loud when it got AC.

While you are thinking about D,I am working my head off on B without success.

You need to hold for each $$$X$$$ the number of elements $$$Y$$$ where for all $$$i$$$ in digit representation of $$$X$$$ and $$$Y$$$ $$$Y_i <= X_i$$$, You can do that by using inclusion-exclusion for example let's call the number of correct elements $$$F(x)$$$ so $$$F(99) = F(98) + F(89) - F(88)$$$.

Now the answer is $$$\sum_{i=1}^{n} F(999999 - a_i)$$$ with some case handling for the $$$i < j$$$ part.

SOS DP but with multisets.

Maybe,you can use High-dimensional prefix sum(I got this name from translation,so it may be strange). This is my code:D

You can also use meet-in-the-middle, that is:

1. Define $$$dp[i][j]$$$ where $$$i, j < 1000$$$, for how many number in array $$$A$$$ whose first 3 digits are equal to $$$i$$$ and last 3 digits are smaller than $$$j$$$'s 3 digits respectively. You can fix $$$i$$$ and enumerate for $$$j$$$ to compute $$$dp[i][j]$$$.
2. Then define $$$dp2[i][j]$$$ for how many number in array $$$A$$$ whose first 3 digits are smaller than $$$i$$$'s 3 digits respectively and last 3 digits are smaller than $$$j$$$'s 3 digits respectively. Now you can fix $$$j$$$ and enumerate for $$$i$$$ to compute $$$dp2[i][j]$$$ using $$$dp[i][j]$$$.
3. Lastly, compute the answer.

It seems that we need calculate $$$10^9$$$ times, but it turns out that we only need about $$$3 \times 10^8$$$ times. My code is here https://atcoder.jp/contests/arc136/submissions/29758496

My approach was a bit different than the editorial.

First calculate for each $$$1 \leq j \leq 1000000$$$, $$$dp[j]$$$ where $$$dp[j]$$$ means the number of elements in the array which have all digits greater than or equal to $$$j$$$. This part can be done by PIE.

Let's now calculate the number of bad pairs instead. For each element, lets do inclusion-exclusion over the digits which will lead to carry-over. For example, in $$$21631$$$, digits $$$6$$$ and $$$2$$$ will lead to carry over if and only if the number to be added is of the form $$$y_{1}x y_{2} xx$$$ where $$$x$$$ can be any digit and $$$y_{1} \geq 8$$$ and $$$y_{2} \geq 4$$$. The number of such integers is stored in $$$dp[80200]$$$. Hence we perform PIE.

Code

I used a 6-dimensional prefix sum, which can solve this problem in $$$O(N)$$$ time.

Here is my code: D

I also had bad difficulties to solve B and C. Both where not simple because they looked like we could implement simulation, but turns out simulation is comlecated and actually not needed at all...

That where kind of "better think twice" problems, which are not so bad, I think.

lol, I am : 42 AC ; 1 WA

UPD : JUST GOT AC

There are two numbers that are equal to YES.

B can be solved in O(n^2) time (when counting inversions).

If we had to use some kind of tree (eg. Fenwick) to get nlogn it would have been way harder.

https://www.geeksforgeeks.org/counting-inversions/

Thanks. In the past few hours, I was trying to look for this problem 1591D. I remember such a question appeared which is like today's ARC 136B, and was trying to find out where did I see it.

It means that two numbers less than 10 add up to more than 10

Could I ask why the solution counts the absolute differences of adjacent elements?

Maybe you can try USACO2022 Dec Bronze. The second problem is similar with C.

What does this s.pop(i) ? Does this like cut a char out of the string? If yes, it is most likely not O(1) operation.