PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: dreadarceus
Preparer: errorgorn
Testers: iceknight1093, satyam_343
Editorialist: iceknight1093
DIFFICULTY:
2425
PREREQUISITES:
Dynamic programming
PROBLEM:
You have two counters a and b and a score S, all initially 0.
For N minutes, you need to increase a or b by 1.
There are also M events, each of one of two types:
- A type 1 event increases S by 1 if a \gt b, and sets a = b = 0 otherwise.
- A type 2 event increases S by 1 if a \lt b, and sets a = b = 0 otherwise.
What’s the maximum possible final score you can achieve?
EXPLANATION:
Let d = a - b denote the difference between a and b.
Note that each event checks whether the difference is positive or negative, then either increases the score by 1 or resets d to 0.
Also, in each minute, we can either increase or decrease d by 1.
Now, ideally we’d like to keep d somewhat close to 0 so we can quickly flip its sign if needed for an event.
In fact, it’s enough to keep -2 \leq d \leq 2 at all times.
Proof
Consider some optimal sequence of moves that has |d| \gt 2 at some point. Without loss of generality, let’s say d reaches 3. We can construct a new sequence of operations as follows:
Consider the first time we make the move 2 \to 3.
Instead, let’s make the move 2 \to 1 in this step. Note that this essentially subtracts 2 from all later values of d.
Now,
- If the original sequence of moves never has the move 3 \to 2 after this point, then we don’t modify anything more.
- The original sequence and new sequence both remain always positive after the change, and are the same before the change, so the new sequence has the same score as the original.
- If the original sequence of moves has the move 3 \to 2 at some point, it corresponds to the move 1 \to 0 in the new sequence.
- Replace the first instance of such a move with the move 1 \to 2 in the new sequence. Once again, it’s not hard to see that the score doesn’t change.
By continually repeating this process, we can ensure the entire sequence has |d| \leq 2 at all times while still remaining optimal.
Armed with this knowledge, let’s actually solve the problem.
We’ll use dynamic programming: let dp(i, x) denote the maximum score after i minutes if d = x.
Transitions are as follows:
- First, we need to either increase or decrease d by 1. That is, dp(i, x) = \max(dp(i-1, x-1), dp(i-1, x+1)).
- Then, we need to process an event at this time point, if there is one.
- Suppose there is a type 1 event. That changes the values as follows:
- If x \gt 0, then add 1 to dp(i, x)
- dp(i, 0) = \max(dp(i, 0), dp(i, -1), dp(i, -2)) since negative values are forced to 0
- dp(i, x) = -\infty for x \lt 0, since it’s impossible to have a negative value of d after this minute.
- A type 2 event can be handled similarly.
The base cases for this function are dp(0, 0) = 0 and dp(0, x) = -\infty for x \neq 0.
The final answer is the maximum value of dp(N, x) for some x.
Since only -2 \leq x \leq 2 matters, we have 5N states and \mathcal{O}(1) transitions for each, leading to a \mathcal{O}(N) solution.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
int n,m;
int arr[100005];
int brr[100005];
int typ[100005];
int dp[2][5];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin.exceptions(ios::badbit | ios::failbit);
int TC;
cin>>TC;
while (TC--){
cin>>n>>m;
rep(x,1,n+1) typ[x]=-1;
rep(x,0,m) cin>>arr[x];
rep(x,0,m) cin>>brr[x];
rep(x,0,m) typ[arr[x]]=brr[x];
int a=0,b=1;
memset(dp,128,sizeof(dp));
dp[a][2]=0;
rep(x,1,n+1){
memset(dp[b],128,sizeof(dp[b]));
rep(x,0,5){
if (x!=0) dp[b][x-1]=max(dp[b][x-1],dp[a][x]);
if (x!=4) dp[b][x+1]=max(dp[b][x+1],dp[a][x]);
}
if (typ[x]==1){
dp[b][2]=max({dp[b][0],dp[b][1],dp[b][2]});
dp[b][0]=-1e9;
dp[b][1]=-1e9;
dp[b][3]++;
dp[b][4]++;
}
if (typ[x]==2){
dp[b][2]=max({dp[b][2],dp[b][3],dp[b][4]});
dp[b][0]++;
dp[b][1]++;
dp[b][3]=-1e9;
dp[b][4]=-1e9;
}
swap(a,b);
}
int ans=0;
rep(x,0,5) ans=max(ans,dp[a][x]);
cout<<ans<<endl;
}
}
Editorialist's code (Python)
inf = 10**9
for _ in range(int(input())):
n, m = map(int, input().split())
times = list(map(int, input().split()))
types = list(map(int, input().split()))
dp = [[-inf, -inf, -inf, -inf, -inf] for _ in range(n+2)]
dp[0][2] = 0
ptr = 0
for i in range(1, n+1):
for dif in range(5):
if dif > 0: dp[i][dif] = max(dp[i][dif], dp[i-1][dif-1])
if dif < 4: dp[i][dif] = max(dp[i][dif], dp[i-1][dif+1])
if ptr < m and times[ptr] == i:
if types[ptr] == 1:
dp[i][4] += 1
dp[i][3] += 1
dp[i][2] = max(dp[i][:3])
dp[i][0] = -inf
dp[i][1] = -inf
else:
dp[i][0] += 1
dp[i][1] += 1
dp[i][2] = max(dp[i][2:])
dp[i][3] = -inf
dp[i][4] = -inf
ptr += 1
print(max(dp[n]))
