Yuhang's Blog

Educational Codeforces Round 118 - D. MEX Sequences Solution

2021-12-02 Coding

View the problem here.

Suppose xi is a MEX-correct sequence. For all i(1in), it is easy to see that MEX(x1,x2,,xi) is non-decreasing. So the constraint that |xiMEX(x1,x2,,xi)|1 basically says that xi should be “roughly” non-decreasing as well. Further analysis shall formalize this idea.

Let us denote Si={xj:1ji} for each position i. Then the value of MEX(x1,x2,,xi) and hence the choice of xi is determined by the elements in Si1.

Let us start by considering values that x1 may take, with S0 being an empty set.

If x1=0, then MEX(x1)=1 which satisfies our constraint. Then S1={0} and let us consider possible values of x2:

  • x2=0. Then we have MEX(x1,x2)=1. Further, S2={0} which is unchanged from S1. Similarly, it is always possible to append xi+1=xi to the sequence so that Si+1=Si and MEX(x1,x2,,xi+1)=MEX(x1,x2,,xi).
  • x2=1. Then we have MEX(x1,x2)=2. Further, S2={0,1}. Similarly, we can see for Si={0,1,2,,j}, it is always possible to append xi+1=j+1 to the sequence to get MEX(x1,x2,,xi+1)=j+2.
  • x2=2. Then we have MEX(x1,x2)=1. Further, S2={0,2}. In this case, we cannot append x3=1 because that would lead to MEX(x1,x2,x3)x3=31=2>1. We cannot append x33 either since that way MEX(x1,x2,x3) remains 1 and is at least 2 from x3. From this point on, the only possible values to append to the sequence are 0 and 2. Similarly, for Si={0,1,2,,j,j+2}, where a “jump” has taken place at some previous position, the only possible values of xi+1 to append to the sequence are j and j+2.
  • No other values of x2 are possible.

If x1=1, then MEX(x1)=0. It is obvious that in this case we can only repeatedly append 1 to the sequence with no other values possible.

No other values of x1 are possible.

As we can see, there are three patterns of a valid MEX-correct sequence:

1
2
3
(pattern 1) 1+
(pattern 2) 0+, 1+, 2+, ...
(pattern 3) 0+, 1+, 2+, j+, (j+2)+, (j+, (j+2)+)*

where + and * are used similarly as in regular expression.

Let us consider how to solve the original problem, namely counting the number of MEX-correct subsequences of a given sequence ai.

For the first pattern, we only need to count the number of 1’s in ai, say m, then the answer is 2m1.

For the second and third patterns, define three functions as follows:

fi(x): the number of subsequences of the sequence a1,a2,,ai following pattern 2 and ending with x.

gi(x): the number of subsequences of the sequence a1,a2,,ai following pattern 3, with a “jump” from x2 to x and ending with x.

hi(x): the number of subsequences of the sequence a1,a2,,ai following pattern 3, with a “jump” from x2 to x and ending with x2.

We use three arrays to represent these functions, omitting the i-dimension.

Initially, we have f0(x)=g0(x)=h0(x)=0 for all x. Then we traverse all the terms of ai whilst updating the values of the three arrays.

Then for f, if ai=0,
fi(0)=2(fi1(0)+1)1.
The explicit solution is 2r1 where r is the number of 0’s in a1,a2,,ai.

Otherwise,
 fi(ai)=fi1(ai1)+2fi1(ai).
Because we can either append ai to a sequence that ends in ai1 or ai, or directly use a sequence that already ends in ai.

Notice that all other values of fi(x) remains the same as fi1(x), which is why the i-dimension is omitted in our representation.

For g, if ai2,
gi(ai)=fi1(ai2)+2gi1(ai)+hi1(ai).
Because we can

  • append ai to a sequence following pattern 2 ending with ai2;
  • append ai to a sequence following pattern 3 ending with ai;
  • directly use a sequence following pattern 3 ending with ai; or
  • append ai to a sequence following pattern 3 ending with ai2.

Similarly, for h,
hi(ai+2)=gi1(ai+2)+2hi1(ai+2).
Then the answer is
2m1+x=0nf(x)+g(x)+h(x).
(Notice that 0ain.)

C++ code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
#define rep(i,from,to) for(int i=(int)(from);i<=(int)(to);++i)
#define rev(i,from,to) for(int i=(int)(from);i>=(int)(to);--i)
#define For(i,to) for(int i=0;i<(int)(to);++i)
typedef long long ll; typedef long double ld; typedef double db;
const int N = 512345;
const ll M = 998244353ll;
ll f[N], g[N], h[N];
ll n, a[N];
void solve() {
cin >> n;
ll res = 1;
rep(i,1,n) {
cin >> a[i];
if (a[i] == 1) res = (res * 2) % M;
}
rep(i,0,n) {
f[i] = g[i] = h[i] = 0;
}
res--;
rep(i,1,n) {
int u = a[i];
if (u >= 2) {
g[u] = (f[u - 2] + g[u] * 2 % M + h[u]) % M;
}
h[u + 2] = (g[u + 2] + h[u + 2] * 2) % M;
if (u > 0) {
f[u] = (f[u - 1] + 2 * f[u] % M) % M;
}
else f[0] = ((((f[0] + 1) * 2) % M) - 1 + M) % M;
}
rep(i,0,n) {
res += (f[i] + g[i] + h[i]) % M;
res %= M;
}
cout << ((res+M)%M) << endl;

}
int main() {
int T; cin >> T;
while (T--) {
solve();
}
return 0;
}