REVCOSTS - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Combinatorics, string algorithms (any one of KMP/Z-algo/hashing/suffix structures)

PROBLEM:

For two arrays A and B of length N, define f(A, B) to be the maximum integer s such that A can be transformed into B using the following operation several times:

  • Choose a subarray of length at least s in A, and reverse it.

If A = B then f(A, B) = N + 1, and if it’s impossible to make them equal then f(A, B) = 0.

Given A, compute the sum of f(A, B) across all rearrangements B of A.

EXPLANATION:

First, let us compute f(A, B) for a given A and B.

Smaller values of s are certainly more powerful, so it makes sense to look at the larger values of s first and see what happens.

If A = B then f(A, B) = N+1 by definition, so we assume this is not the case.

If we choose s = N, then the only allowed operation is to reverse the entirety of A.
So, f(A, B) = N if and only if B = \text{reverse}(A).

Next, consider s = N-1.
Here, we can either reverse A, or we can reverse one of A[1, N-1] or A[2, N].
Consider the following combination of operations:

  • First, reverse A[1, N-1].
    • This turns the array into [A_{N-1}, \ldots, A_2, A_1, A_N].
  • Then, reverse the entire array.
    • This turns the array into [A_N, A_1, A_2, \ldots, A_{N-2}, A_{N-1}].

Observe that the result is that we’ve essentially right-rotated the array A by one step!

So, it’s certainly possible to reach all arrays that are either:

  1. Rotations of A, or
  2. Reverses of rotations of A.

Further, these are the only reachable arrays with s = N-1, because it can be observed that the reversal operations on A[1, N-1] or A[2, N] will convert A to one of the cyclic rotations of its reverse.

Thus, f(A, B) = N-1 if and only if B is either a cyclic rotation of A or a cyclic rotation of \text{reverse}(A), but also B \ne A and B \ne \text{reverse}(A).

Next, we look at s = N-2.

Here, it turns out that we have quite a lot of power indeed!
In particular, consider the following sequence of operations:

  • Reverse A[2, N].
    • The array is now [A_1, A_N, A_{N-1}, \ldots, A_2].
  • Reverse A[2, N-1].
    • The array is now [A_1, A_3, A_4, \ldots, A_{N-1}, A_N, A_2].
  • Right-rotate the array one step using subarrays of length \ge N-1.
    • The array is now [A_2, A_1, A_3, A_4, \ldots, A_{N-1}, A_N].

Notice that we’ve managed to swap the values in the first two positions without affecting any of the other elements!

In particular, we can in fact perform \text{swap}(A_i, A_{i+1}) for any index i we wish, by:

  1. Left-rotate the array i-1 times to bring these two elements to the first two positions.
  2. Swap the values of the first two positions using the above procedure.
  3. Finally, right-rotate the array i-1 times to bring the two elements to their initial positions.

Because we can swap any adjacent pair of elements, we can in fact reach any rearrangement of A that we wish to do so.

Thus, for all arrays B that are not covered by the above cases of answer \ge N-1, we have f(A, B) = N-2.

We can now use this fact to solve the problem of summing up all answers.

Let T denote the total number of rearrangements of A that are possible.
This is given by

T = \frac{N!}{\prod_{x=1}^N (\text{freq}[x])!}

We can start off with the answer being (N-2) \cdot T, because every rearrangement certainly has its answer be at least 2.

Next, let’s count the number of rearrangements for which the answer is at least N-1.

This, as noted above, is all distinct rotations of A and of \text{reverse}(A).

Counting the number of distinct rotations of A quickly is not too hard, and can be done with any one of the variety of string algorithms.
To do this, create the array A+A (i.e. A concatenated with itself), then the answer is the number of distinct subarrays of length N contained in (A+A).

Then a couple of different things can be done:

  1. Use the Z-function to compute Z_i, the longest common prefix of the entire string and the suffix starting at index i.
    Let j \gt 1 be the smallest index such that Z_j \ge N.
    Then, the answer is (j-1).
  2. Alternately, you can simply compute the hashes of each substring of length N and insert them all into a set, and then look at the size of the set.
  3. Other string structures/algorithms should work too if you know what you’re doing, such as hashing or suffix arrays/trees/automatons.

Suppose there are K distinct rotations of A.
Then,

  • If \text{reverse}(A) is itself a rotation of A, then there are a total of only K distinct arrays among (rotations of A, rotations of \text{reverse}(A)).
  • Otherwise, \text{reverse}(A) will itself have K distinct rotations (none of which are rotations of A), and the total will be 2K instead.

So, there are either K or 2K arrays for which the answer is (at least) N-1.
Add this values to the answer.

There are only two arrays for which the answer is at least N, namely A and \text{reverse}(A).
Note that if A = \text{reverse}(A) then there’s only one distinct array.
Add either 1 or 2 to the answer appropriately.

Finally, add 1 to the answer to account for the single array with answer N+1, that being A itself.

TIME COMPLEXITY:

\mathcal{O}(N) or \mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("Ofast,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

const int mod = 998244353;

// Z[i] -> longest prefix of s[i:] that is also a prefix of s[0:], but s[0] = 0
vector<int> Z_func(auto S) {
	vector<int> z(S.size());
	int l = -1, r = -1;
	for (int i = 1; i < S.size(); ++i) {
		z[i] = i >= r ? 0 : min(r - i, z[i - l]);
		while (i + z[i] < S.size() && S[i + z[i]] == S[z[i]])
			z[i]++;
		if (i + z[i] > r)
			l = i, r = i + z[i];
	}
	return z;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);

    vector fac(200005, 1);
    for (int i = 1; i < 200005; ++i) fac[i] = (1ll * i * fac[i-1]) % mod;
    auto inv = fac;
    inv.back() = 921633914;
    for (int i = 200003; i >= 0; --i) inv[i] = (1ll * (i+1) * inv[i+1]) % mod;

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        vector a(n, 0);
        for (int &x : a) cin >> x;

        vector freq(n+1, 0);
        for (int &x : a) ++freq[x];

        ll tot = fac[n];
        for (auto x : freq) tot = (tot * inv[x]) % mod;

        ll ans = tot * (n-2) % mod;

        // ans >= n-1
        // all cyclic rotations and reverse cyclic rotations
        auto b = a;
        for (int i = 0; i < n; ++i) b.push_back(a[i]);
        auto Z = Z_func(b);

        int rots = 1;
        for (int i = 1; i < 2*n; ++i) {
            if (Z[i] >= n) break;
            ++rots;
        }

        b = a;
        b.push_back(INT_MAX);
        for (int i = n-1; i >= 0; --i) b.push_back(a[i]);
        for (int i = n-1; i >= 0; --i) b.push_back(a[i]);
        Z = Z_func(b);
        bool rev = true;
        for (int i = n; i < 3*n+1; ++i) {
            if (Z[i] >= n) rev = false;
        }

        if (rev) ans += 2*rots;
        else ans += rots;

        // ans >= n
        // only string and its reverse
        ans += 1;
        b = a; ranges::reverse(b);
        if (a != b) ans += 1;

        // ans = n+1
        ans += 1;

        cout << ans % mod << '\n';
    }
}