F - 1122 Subsequence Editorial by en_translator Editorial for printing
Note that “subsequence” in this article is not necessary contiguous.
This problem can be solved with bit DP.
Note that the maximum possible subsequence of \(A\) that is a 1122 sequence is \(2\times 20=40\), because \(1\leq A_i\leq 20\).
First, for a (possibly empty or whole) subset \(S\) of \(\{1,2,\ldots,20\}\), define \(dp[S]\) as the minimum non-negative integer \(r\) such that \((A_1, A_2,\ldots, A_r)\) has a subsequence that is a 1122 sequence such that the integers in \(S\) exactly comprise that subsequence. (If \((A_1, A_2,\ldots, A_N)\) has no such subsequence, define it \(\infty\).) (Here, DP stands for Dynamic Programming.)
What we want is the maximum \(2\times \lvert S\rvert\) for \(S\) with \(dp[S]\neq \infty\), where \(\lvert S\rvert\) denotes the number of elements in \(S\).
Also, for \(0\leq i\leq N\) and \(1\leq x\leq 20\), let \(f(i,x)\) be the minimum \(j\) with \(i\bm{<}j\leq N\) and \(A_j=x\) (or \(\infty\) if there is no such \(j\)). For convenience, let \(f(\infty,x)=\infty\) for all \(1\leq x\leq 20\).
For \(dp[\phi]\) (\(\phi\) means the empty set), we always have \(r=0\).
Now let \(S=\{e_1,e_2,\ldots, e_{\lvert S\rvert}\}\), and assume that we already know \(dp[S']\) for all subsets \(S'\) of \(S\) except for \(S\) itself. Then \(dp[S]\) can be computed as follows, doing a casework on the last two terms on a 1122 sequence that contains all integers in \(S\).
For \(1\leq i\leq \lvert S\rvert\), define a set \(T_i\) to be \(S\) excluding \(e_i\) (i.e. \(T_i\equiv S-\{ e_i\}\)). Then, the minimum \(r\), such that \((A_1, A_2,\ldots, A_r)\) contains a 1122 sequence that contains the integers in \(S\) and that ends with two copies of \(e_i\), can be found as \(f(f(dp[T_i],e_i),e_i)\). Therefore, \(\displaystyle dp[S]=\min_{1\leq i\leq \lvert S\rvert} f(f(dp[T_i],e_i),e_i)\).
This way, \(dp[S]\) can be filled in ascending order of the number of elements in \(S\).
Regarding the complexity, \(f(i,x)\) can be precalculated and stored in a table, to enable \(O(1)\) evaluation. Thus, \(dp[S]\) can be evaluated in \(O(\lvert S\rvert)\) time for each set \(S\), for a total of \(O(M\cdot 2^M)\) time, where \(M=\max(A_i)\).
Besides, the precalculation of \(f(i,x)\) table costs \(O(NM)\), which can be done in descending order of \(i\); therefore, the total complexity is \(O(M(N+2^M))\), which is fast enough under the current constraints \(N\leq 2\times 10^5\) and \(M\leq 20\).
Therefore, the problem has been solved.
Sample code in C++:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define N 200000
#define M 20
int main(void){
int n;
int a[N];
int nxt[N+2][M];
int r[(1<<M)];
int ans=0,cnt;
cin>>n;
rep(i,n)cin>>a[i];
rep(j,M)nxt[n][j]=n+1,nxt[n+1][j]=n+1; //n+1=\infty
for(int i=n-1;i>=0;i--){
rep(j,M)nxt[i][j]=nxt[i+1][j];
nxt[i][a[i]-1]=i+1;
}
rep(i,(1<<M))r[i]=n+1;
r[0]=0;
rep(i,(1<<M)){
cnt=0;
rep(j,M){
if((i>>j)&1){
cnt+=2;
r[i]=min(r[i],nxt[nxt[r[i^(1<<j)]][j]][j]);
}
}
if(r[i]<=n)ans=max(ans,cnt);
}
cout<<ans<<endl;
return 0;
}
posted:
last update: