gl! btw 400-500-600 seems challenging!

is $$$C$$$ prefix-sum dp?

Feeling stupid for messing 7 times on B :)

D was very nice.

Can someone explain why this doesn't work for b

ll n, i, j, ans = 0;
        cin >> n;
        ll d[n][11];
        for (i = 0; i < n; i++)
        {
            for (j = 0; j <= 10; j++)
                d[i][j] = -1;
        }
        vi s(11, 0), v(n);
        for (i = 0; i < n; i++)
            cin >> v[i];
        for (i = 1; i < n; i++)
        {
            for (j = s[v[i]]; j < i; j++)
            {
                d[j][v[i]] = i;
            }
            s[v[i]] = i;
        }
        ll l = -1;
        for (i = 0; i < n; i++)
        {
            ll x, y, z, iy, iz, c = 1e9;
            x = v[i];
            for (j = 1; j <= 10; j++)
            {
                iy = d[i][j];
                if (iy == -1)
                    continue;
                y = v[iy];
                z = 2ll * y - x;
                if (z < 1 || z > 10)
                    continue;
                iz = d[iy][z];
                if (iz == -1)
                    continue;
                c = min(c, iz);
            }
            if (c != 1e9)
            {
                ans += (i - l) * (n - c);
                l = i;
            }
        }
        cout << ans << nl;

How to do D?

I have a different idea for B:

Lets precompute for every index i the value j, where j is the smallest index more than i such that you can form an arithmetic subsequence of length 3 from values i...j. Call this value as nearest_end[i].

To do this we can brute force the difference of the AP from -9 to 9 and greedily choose the smallest next index.

Once this precomputation is done, consider f[i]=number of pairs ending at i. The naive idea to compute this would be to iterate j from i to 1 and find the rightmost j such that nearest_end[j]<=i, then f[i]=j. To optimise this we can use binary search and range minimum queries to find rightmost such j. The ans is just sum of all f[i] from i=1 to n

I know this is an overkill compared to editorials solution but I felt like sharing

link to submission :https://atcoder.jp/contests/arc170/submissions/49553096

B can be reduced to Rectangle Union Area

49545573

There's a simpler and faster solution for problem E (the complexity is the same, but without matrix operations).

The solution is the same as the official editorial until the last step. Here we need to calculate the sum for every pair of positions, the probability of them being equal in the LR sequence.

Let's say we fix the two positions $$$x<y$$$. Now, what we choose before $$$x$$$ and what we choose after $$$y$$$ doesn't matter. For the part from $$$x$$$ to $$$y$$$, there is a probability of $$$p$$$ that a character stays the same as the previous one, and $$$1-p$$$ otherwise.

If we want $$$x$$$ to be equal to $$$y$$$, then there should be an even number of positions where the character differs from the previous one, so it boils down to the following problem:

There is a $$$01$$$ sequence of length $$$m$$$, where each position is $$$0$$$ with probability $$$p$$$ and $$$1$$$ with probability $$$1-p$$$. Calculate the probability that this sequence has an even number of $$$1$$$. The answer to the original problem when we fix $$$x,y$$$ is the answer to this problem when $$$m=y-x$$$.

Let $$$q=1-p$$$ and a polynomial $$$f(x)=(p+qx)^m$$$, then we need to calculate $$$\sum_{i=0}^m[i\bmod 2=1][x^i]f(x)$$$. Using the well-known trick to split the even and odd coefficient, this number equals to $$$\frac{f(1)+f(-1)}2$$$, as the odd coefficients will be eliminated while the even ones are counted twice. So the answer to this problem is $$$\frac{1+(2p-1)^m}2$$$.

Now back to the original problem, after iterating through all pairs of $$$(x,y)$$$, the answer is $$$\sum_{x=1}^{n-1}\sum_{y=x}^{n-1}\frac{1+(2p-1)^{y-x}}2$$$. Now we fix $$$y-x$$$ first, then we need to calculate $$$\frac12\sum_{i=0}^{n-2}(n-i-1)(1+(2p-1)^i)$$$. This can be calculated in $$$O(\log n)$$$ time after some deduction to the geometric series sum.

can anyone explain the approach of A please?

Can anyone give counter test for B https://atcoder.jp/contests/arc170/submissions/49553730

How is this solution accepted for B? Isn't the time complexity O(n^2) at the least?

#49543170

Can someone explain which corner case I missed as I got 2 WAs.

https://atcoder.jp/contests/arc170/submissions/49543465

AtCoder, please provide test cases after contest, its very difficult to check all corner cases after contests also

When I was thinking of the problem D, I came up with using random.

Distinctly, the N^2 log N algorithm is common.

And after that, I considered using random. In more detail, I ramdomly chose 100 num (I called it as x) and checked if there is j satisfies (a[i],a[j],b[x]) is possible to form a triangle.

My program (https://atcoder.jp/contests/arc170/submissions/49557854) was accepted, but I wonder if anyone could hack it.

My English is not good, please forgive me for some naive syntax errors.

Thanks for your reading!

In the editorial of C , it is mentioned that when M >= N — 1 and N >= 2 , the answer is M^c , c -> number of zeroes. I don't think it is quite right. for eg. take S = 00100 , and M >= 5. As per above answer shall be M^4 , but it is actually (M-1)^4. I guess you meant (M — 1)^c ?

I finally upsolved A. Damn was it hard !!

I'm disappointed the official editorial don't provide "counter exemple" testcase to understand parentheses trick.

Example:

S:BAAAABBBBA
T:ABBBBAAAAB

I'm also disappointed no code solution is provided. Since ABC335, the editorial are often incomplete, i.e. with textual explanation and solution code.

x: textual explanation.
X: textual explanation + solution code.

--------A-B-C-D-E-F-G
ARC170:-x-x-x-x-x-x-x
ABC337:--------------
ABC336:-------X-x-x--
ABC335:---------X-x-X
ABC334:-X-X-X-X-X-X-X

Complete editorial is essential to upsolve and keep motivation.

I realized that in E you can just use Berlekamp directly on the answer and the recurrence even has size at most $$$4$$$...

You can probably pass by calculating the first $$$8$$$ terms in $$$2^n$$$ or even by precalculating this recurrence offline. Now I find it more interesting that so little people ACed this problem

My code: https://atcoder.jp/contests/arc170/submissions/49586277 I was really about to bash the genfunc when I realized that this will just give me $$$O(1)$$$ linear reccurence

can somebody explain which testcase I am missing in problem A

https://atcoder.jp/contests/arc170/submissions/50050697