TWOCOUNTERS - Editorial

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]))
4 Likes

By making a and b closer like
iF(type==1) and if a already greater than b than we can increase score and if a not grater than b then try to make a increment every time.
as same for type 2
Why can we not do like this which test case is failing??
My solution - CodeChef | Competitive Programming | Participate & Learn

6 Likes

What’s wrong with a greedy approach like this?
https://www.codechef.com/viewsolution/83049854
Gives WA in 4 cases

3 Likes

We are trying to keep a and b as close as possible. in your case, suppose for type 1 event, a = 1, b=2 and increment = 7, then It will update a=8 and b=2 that we dont want. We also need to handle these cases

2 Likes

I am getting WA on some testCases. I tried greedy to solve this problem. Could someone please point out wrong TC
https://www.codechef.com/viewsolution/83108129

1 Like

Test case:
1
6 4
1 2 4 6
1 2 1 2

In my greedy approach my code scores on the minutes t = 1 and t = 4, with a score of 2, but the correct answer should be a score of 3 with the minutes t = 2, t = 4, and t = 6.

4 Likes

same thing, my greedy approach is failing for 4 test cases
https://www.codechef.com/viewsolution/83068144

Can the N value in this problem go higher than what it already is?
I mean, can we solve this problem just by seeing the difference between Ti and Ti+1, rather than going for each i [1,N] we can just traverse the time array, and check the difference (D) between two adjacent values, if it (D) is odd that means that we can change the difference(between a and b) by 1, or by 2, i.e ( if the difference (D) is 5, we will give a 4 and b 1). And if the difference (D) is even we have 2 choices again i.e. to let the difference (between a and b) be same (distribute evenly) or to change the difference by 2 (distributing 6 as a-> 4 b → 2).
Correct me if I am wrong, I tried this implementation during contest and failed. But I can’t prove it wrong. It seems to align with the idea that difference will have an absolute value of 2 at max.

1 Like

Thank you for the test case!

Hi, If you are using greedy approach, and at t=1 if you increase ‘a’ you score at t=1 and 4 with maximum score 2. But if you increase b at t=1, then you will score at t=2,4,6 with maximum score 3. For this problem, you have to verify all the possibilities (use DP to minimize the operations) and find the maximum score.
Please have a look at the image, where greedy approach for this problem fails.

2 Likes

Yes, it’s possible to solve the problem this way, with a complexity of \mathcal{O}(M) and so N can indeed be made much larger. You need to be a bit careful with the implementation though.

One way to simplify implementation is to note that if the distance between two consecutive timepoints is \geq 5, you can propagate a value from one difference to any other valid difference (even distance means you end up with the same parity difference, odd distance means you end up with the opposite parity difference).

Basically, if the distance is even and \geq 5 you can do dp(i, -2) = dp(i, 0) = dp(i, 2) = \max(dp(j, 0), dp(j, 2), dp(j, -2)) where j is the previous position; and similar things for 1 and -1; reverse this for odd distances.

When the distance is \leq 5 just update the dp manually using the transitions above, you do this for 5M timepoints at most so the complexity is still \mathcal{O}(M).

1 Like

what does the ‘X’ cross over type column signifies

The ‘X’ cross over type column signifies that there is no event at that time.

In question they mentioned " Your task is to maximise the score after N minutes have passed."

If Ti = N then the event will occur at N+0.5 minutes which is greater then N minutes.
So this means we should not consider the event whose Ti = N

dp(i,x)=−∞ for x<0, since it’s impossible to have a negative value of d after this minute.

@iceknight1093 can you please elaborate this line ?

The bolded part is important; if a \leq b (which would make d = a - b non-positive), then it is forced to a = b = 0, which gives d = 0.
Obviously, that means there is no way for you to finish that minute and have a negative d, no?

For a type 2 event you instead can’t have positive d.

1 Like

thanks champion

Thanks for the test case , during 2 hours of the contest I believed that greedy approach will work as I couldn’t find a counter case . How do you came up with this case ? Or in general how to build such cases ?