This is unofficial editorial for atCoder abc178.

A - Not

Just print \(1-x\).

Time complexity \(O(1)\).

Code

B - Product Max

Always \(x\) should be equal to either \(a\) or \(b\). Same thing for \(y\) it should be equal to either \(c\) or \(d\).

Time complexity \(O(1)\).

Code

C - Ubiquity

dp solution

As the value of \(n\) is small, we can use dp to solve the problem, let dp[i][f0][f9] be the number of arrays of length \(i\), \(f_0\) determine if their exist some \(j < i\) such that \(a_j = 0\). Same thing for \(f_9\). The transactions are simple, from dp[i][f0][f1] we can go to dp[i + 1][f0][f9] of dp[i + 1][1][f9] or dp[i + 1][f0][1].

Time complexity \(O(n)\).

Code

inclusion exclusion principle

We can find out that the solution is: \(ans = 10^n -2 * 9^n + 8^n\).

Time complexity \(O(log(n))\).

Code

D - Redistribution

Combinatorics solution

Using stars and bars theorem we know that the number of ways to chose \(k\) positive integer numbers that sum up to \(n\) can be found using: \({n + k - 1}\choose{k - 1}\). Let’s try to use this to solve the problem.

We can write that:

\[a_1 + a_2 + \dots + a_k = n\]

But \(a_i \ge 3\), so we can write \(b_i = a_i + 3.\)

\(b_1 + b_2 + \dots + b_k = n - 3 \times k\).

Now to solve the problem we just need to iterate over all \(k\) such that \(3 \times k \le n\) and add to the answer \({n - 2\times k - 1}\choose{k - 1}\)

Time complexity \(O(n)\).

Code

Formula

If you try some small values you can find out that the solution follows a formula, more precisely: dp[i] = dp[i-1] + dp[i-3] and dp[3] = 1, dp[i] = 0 for \(i \le 2\).

Time complexity \(O(n)\).

Bonus: can you solve the problem in \(O(log(n))\)?

Code

E - Dist Max

The Manhattan distance between tow points \(A(x_a, y_a)\) and \(B(x_b, y_b)\) can be written as: \(dis = \lvert x_a - x_b \rvert + \lvert y_a - y_b \rvert\) This can be one of the four cases:

\[(x_a - x_b) + (y_a - y_b)\] \[(x_a - x_b) + (-y_a + y_b)\] \[(-x_a + x_b) + (y_a - y_b)\] \[(-x_a + x_b) + (y_a + y_b)\]

Let’s consider the first case: \((x_a - x_b) + (y_a - y_b) = (x_a + y_a) + (-x_b - y_b)\)

When we iterate over all points we can find that part of the solution comes from the point \(A\) the other part comes from other point, so if we just consider the first case then the Maximum Manhattan distance is \((x_a + y_a ) + max((-x_b - y_b))\) for any point \(B \ne A\).

To find the max value we use 4 multiset for x + y, x - y, -x + y and -x -y. First we add all the points to our multisets, then for every point \(i\) we query our multisets to find the better solution.

Time complexity \(O(n \times log(n))\).

Code

F - Contrast

The problem has no solution if there is some number \(x\) that \(cnt[x] > n\) for all \(x\) in \(a, b\). The proof is simple, because there are just \(n\) indexes to fill.

Let’s reverse array \(b\), then the indexes where \(a_i = b_i\) will form a contentious segment between \([l, r]\), also these values will be equal. So we just need to change these values with other values out of the range.

Time complexity \(O(n)\).

Code