PROBLEM LINK:
Practice
Contest Division 3
Contest Division 2
Contest Division 1
Setter: Soumyadeep Pal
Tester: Aryan Choudhary
Editorialist: Hriday G
DIFFICULTY
Easy
PREREQUISITES
Dynamic Programming
PROBLEM
Given an array A of length N and an integer K, find the length of the longest good subsequence of A. A sequence is said to be good if the number of adjacent elements which differ by value is at most K.
EXPLANATION
Any subsequence ending at position i is obtained by either starting a new subsequence at i, or by extending some subsequence ending at a previous position j (1 \leq j \lt i). Likewise, a subsequence which is k beautiful can be obtained by either starting a new subsequence at i, or by extending a k' beautiful subsequence ending at a previous position j (1 \leq j \lt i). Here k' is k if A_j = A_i, else k-1 if A_j \neq A_i.
Slow solution
Letâs try a Dynamic Programming approach where \mathrm{dp}[i][k] denotes the length of the longest k beautiful subsequence ending at the i-th element.
Trying to extend subsequences ending at each position j \lt i to include A_i, we get the transition \displaystyle \mathrm{dp}[i][k] = 1 + \max_{j < i} \mathrm{dp}[j][k'] where k' is k if A_j = A_i, else k-1 if A_j \neq A_i.
The answer will be the maximum value in the whole DP table. The initial states can be defined by filling the DP table with 0 s.
Computing the answer for each state requires \mathcal{O}(N) transitions, and there are \mathcal{O}(NK) states. Hence this solution has time complexity \mathcal{O}(N^2K), which is too high for the given constraints.
Reducing the transitions
Letâs try to reduce the number of transitions required per state from \mathcal{O}(N) to \mathcal{O}(1).
Notice that when we are computing the value of \mathrm{dp}[i][k], we only care about the maximum value \displaystyle \max_{j < i} \mathrm{dp}[j][k']. To be precise, we need two values \displaystyle \max_{\substack{j < i\\ A_j = A_i}} \mathrm{dp}[j][k] and \displaystyle \max_{\substack{j < i\\ A_j \neq A_i}} \mathrm{dp}[j][k-1].
If we can keep track of these maximum values, we can reduce the number of transitions per state to \mathcal{O}(1).
Keeping track of transitions of the first kind
Consider a sequence S of indices \displaystyle j_1 \lt j_2 \lt \ldots \lt j_m such that A_{j_1} = A_{j_2} = \ldots = A_{j_m}. For any k, it follows that \displaystyle \mathrm{dp}[j_1][k] \leq \mathrm{dp}[j_2][k] \leq \ldots \leq \mathrm{dp}[j_m][k]. In other words, \displaystyle \mathrm{dp}[j_m][k] = \max_{j \in S} \mathrm{dp}[j][k].
Why?
Consider a pair of indices j and j' \displaystyle (j \lt j', A_j = A_{j'}). Then \mathrm{dp}[j'][k] may be obtained by extending the sequence ending at j, using A_{j'} instead of A_{j}. This implies that \mathrm{dp}[j'][k] will always be equal to (if not more than) \mathrm{dp}[j][k].
Thus for transitions of this form, it suffices to try and update \mathrm{dp}[i][k] with (1 + \mathrm{dp}[last_i][k]), where last_i denotes the maximum j such that j \lt i and A_j = A_i.
Keeping track of transitions of the second kind
We can maintain a separate array, letâs call it \displaystyle \mathrm{pref}[i][k], which stores the length of the longest k-beautiful subsequence ending at some position j (j \leq i). In other words, \displaystyle \mathrm{pref}[i][k] = \max_{j \leq i} \mathrm{dp}[j][k] = \max(\mathrm{pref}[i-1][k], \mathrm{dp}[i][k]).
Then for transitions of this form, it will be enough to try and update \mathrm{dp}[i][k] with (1 + \mathrm{pref}[i-1][k-1]).
What if \mathrm{pref}[i-1][k-1] = \mathrm{dp}[j][k-1] such that A_j = A_i?
It does not matter
If a sequence is k-1 beautiful, then it is also k beautiful. The transition \mathrm{dp}[i][k] = 1 + \mathrm{pref}[i-1][k-1] uses this fact.
Putting all of it together, we now have a solution with time complexity \mathcal{O}(NK) and space complexity \mathcal{O}(NK). We can further reduce the space complexity to \mathcal{O}(N) by changing the order of iteration with careful updates, as demostrated in one of the solutions below.
A slightly different approach
Letâs define our dp states slightly differently. Let \mathrm{dp}[a][k] denote the length of the longest k beautiful subsequence ending with an element whose value is a. Initially all states are 0.
Now for each i and k (say a = A_i), we can either start a new subsequence at i and set \mathrm{dp}[a][k] = 1, or try to extend some existing subsequence (1 + \mathrm{dp}[a][k]) or \displaystyle (1 + \max_{\forall a' \neq a} \mathrm{dp}[a'][k-1]).
The second type of transition can be reduced to \mathcal{O}(1) in a way similar to the one described in the section above (maintain \mathrm{pref}[k]).
This solution also has time complexity \mathcal{O}(NK) and space complexity \mathcal{O}(NK). You may find the implementation in one of the solutions below.
TIME COMPLEXITY
\mathcal{O}(NK) per test case
SOLUTIONS
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
void solve() {
int n, k; cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
}
int maxi = *max_element(a.begin(), a.end()), ans = 0;
vector<vector<int>> dp(n, vector<int>(k + 1, 1));
vector<int> last_idx(maxi + 1, -1);
vector<int> mx_ans(k + 1); // maximum answer upto (i-1) th index with j bad indices
for (int i = 0; i < n; i++) {
for (int j = k; j >= 0; j--) {
if (j >= 1) {
dp[i][j] = mx_ans[j - 1] + 1;
}
if (last_idx[a[i]] != -1) {
dp[i][j] = max(dp[i][j], dp[last_idx[a[i]]][j] + 1);
}
mx_ans[j] = max(mx_ans[j], dp[i][j]);
ans = max(ans, dp[i][j]);
}
last_idx[a[i]] = i;
}
cout << ans << '\n';
}
signed main() {
ios_base :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t; cin >> t;
while (t--) {
solve();
}
return 0;
}
Tester's Solution
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase
def main():
for _ in range(int(input())):
n,k=map(int,input().split())
a=[int(x)-1 for x in input().split()]
N=1000
dp=[[0]*(k+1) for _ in range(N)]
dp2=[0]*(k+1)
for x in a:
b=dp[x]
b[0]+=1
for i in range(k):
b[i+1]+=1
b[i+1]=max(b[i+1],1+dp2[i])
dp2[i]=max(dp2[i],b[i])
dp2[k]=max(dp2[k],b[k])
print(dp2[-1])
# region fastio
BUFSIZE = 8192
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
# endregion
if __name__ == "__main__":
main()
Editorialist's Solution
/**
đȘ the_hyp0cr1t3
đȘ 28.07.2021 00:37:21
**/
#ifdef W
#include "k_II.h"
#else
#include <bits/stdc++.h>
using namespace std;
#endif
#define pb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) static_cast<int32_t>(x.size())
auto chmax = [](auto& A, auto&& B) { return B > A? A = B, true : false; };
auto chmin = [](auto& A, auto&& B) { return B < A? A = B, true : false; };
const int64_t k_II = 2e18;
const int INF = 2e9, MOD = 1e9+7;
const int N = 1000 + 5;
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
int Q; cin >> Q;
while(Q--) []() {
int i, n, k;
cin >> n >> k; ++k;
vector<int> a(n);
for(auto& x: a) cin >> x;
vector<int> dp(n + 1), cur(N, n), nxt(n);
for(i = n-1; ~i; i--)
nxt[i] = cur[a[i]], cur[a[i]] = i;
while(k--) {
for(i = n; i; i--)
chmax(dp[i], dp[i-1] + 1);
for(i = 0; i < n; i++) {
if(nxt[i] < n)
chmax(dp[nxt[i] + 1], dp[i + 1] + 1);
chmax(dp[i + 1], dp[i]);
}
}
cout << *max_element(all(dp)) << '\n';
}();
} // ~W
Feel free to share your approach. Suggestions are welcomed.
