PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Easy
PREREQUISITES:
(Optional) Dynamic Programming
PROBLEM:
An array A consisting of ones and twos is said to be stable if the following holds:
- Consider an array B of the same length as A, initially filled with zeros.
- You can choose an index i, and:
- If A_i = 1, add 1 to B_i.
- If A_i = 2, add 1 to B_{i-1}, B_i, B_{i+1}.
- If B can be made a palindrome using these operations, A is stable.
Given an array A, count the number of its subarrays that are stable.
N \leq 300 in this version.
EXPLANATION:
Since N \leq 300, an acceptable complexity is \mathcal{O}(N^3).
There are \mathcal{O}(N^2) subarrays, so if we can solve each of them in linear time, we’ll have a solution that’s fast enough.
There are a couple of different ways to achieve this: either dynamic programming, or by analyzing the problem deeper to find structure.
Of the two methods, dynamic programming is maybe conceptually easier (though perhaps requires a bit more code), but unfortunately doesn’t extend to a solution to the harder problem.
Dynamic Programming
The main reason dynamic programming can be applied here, is that each operation affects only a small range around its respective index - specifically, adjacent indices at best.
We want B to be a palindrome, so suppose we try performing operations from the outside in to achieve this - that is, try to make B_1 = B_N, then B_2 = B_{N-1}, then B_3 = B_{N-2}, and so on.
Of course this is trivially possible by just doing nothing, but we have the additional constraint that some operation must be performed.This allows us to use the following setup.
Define dp[i][\text{state}] to be a boolean value, which is true if we can process indices 1, 2, 3, \ldots, i as well as N, N-1, N-2, \ldots, N-i+1, to end up at \text{state}.
What exactly is \text{state}? Well, that’s what we need to capture in it.If we’ve performed operations till index i (and its opposite), then indices before i can no longer be touched at all by future operations.
This means we must already have B_1 = B_N, B_2 = B_{N-1}, \ldots, B_{i-1} = B_{N-i+2}.Our next operation is with the indices i+1 and N-i, and this can affect indices [i, i+2] and [N-i-1, N-i+1] only.
So, our \text{state} can capture exactly this information: what are the current values of B_i, B_{i+1}, B_{N-i+1}, B_{N-i}?
Further, the \text{state} can also hold a boolean flag, denoting whether an operation has been performed or not.From each \text{state}, there are four options, depending on which of i+1 and/or N-i we choose to operate on.
For each option, update the state appropriately, and perform the requisite transition to the state in dp[i+1].There are a constant number of states at each index - certainly we’ll have B_i \leq 3 always, so a trivial upper bound on the number of states is 4^4 \cdot 2, and there are four transitions from each.
This constant factor is quite large, but can be greatly improved by noting that the actual B_i values don’t really matter much at all - in fact, what really matters is the difference between opposing B_i values (which should end up being 0 in the end).
So, rather than store B_i and B_{N+i-1} separately in the state, we can store their difference B_i - B_{N+i-1}.
Similarly, we can store the difference B_{i+1} - B_{N-i}.Further, note that performing operations with indices i+1 and/or N-i can only change the difference B_i - B_{N+1-i} (or any other difference, really) by either -1, 0, or 1.
So, states with differences \gt 1 or \lt -1 are of no use to us (since our goal is to make the difference reach 0.)This brings the number of states down to 3^2 \cdot 2, since it suffices to store differences \{-1, 0, 1\} for the two index pairs, as well as a boolean denoting whether an operation has been performed or not.
This is now fast enough to pass.
Ad-hoc
Let’s analyze when exactly an array A can be stable.
An immediate case that comes to mind should be if there exists an index i such that A_i = A_{N+1-i}, i.e. some pair of opposite equal elements.
If this happens, we can operate with the two indices i and N+1-i, and since they’re equal but opposite, they’ll have symmetric effects on B resulting in a palindrome.An extension of this idea is to note that when N is odd, the condition A_i = A_{N+1-i} is always satisfied by the middle element; and indeed, for odd N operating on the middle element results in B being a palindrome.
So, any odd-length array is a stable, and also any even-length array containing some pair of equal elements at opposite indices is stable.
We now have even-length arrays such that every pair of opposite elements differ.
For convenience, let X denote the first half and Y denote the reversed second half of the array A.
So if A = [1, 1, 2, 1, 2, 2] then X = [1, 1, 2] and Y = [2, 2, 1].
Note that |X| = |Y| = \frac{N}{2}, and X_i \neq Y_i for all i.Let’s look at the left border.
We know X_1 \neq Y_1, so w.l.o.g. let X_1 = 1 and Y_1 = 2.
Now, if X_2 = 1, we can choose indices 1 and 2 in X and index 1 in Y (so index N in the original array) to obtain a palindrome.If this doesn’t happen, we must have X_2 = 2 and Y_2 = 1.
Now, if X_3 = 2 as well, so that Y_3 = 1, we can choose index 2 in X and indices 1, 3 in Y (so N, N-2 in the original array) to obtain a palindrome.Now let’s look at the general case of some elements in the “middle” of the array, i.e. not really near its borders.
If we have three consecutive occurrences of 1, say X_i = X_{i+1} = X_{i+2} = 1, then again forming a palindrome is possible: choose all three of these indices, and also index i+1 in Y (which will contain a 2).
That leaves us with arrays that don’t contain any three consecutive elements.
Playing around with such arrays, it can be seen that if [1, 1, 2, 2] appears as a subarray in one half, with its opposing subarray being [2, 2, 1, 1], it’s again possible to obtain a palindrome, by choosing one 1 and one 2 in each half.
Luckily for us, this is the end of the casework - if all the above cases fail, the array will never be stable.
The only exceptions to this are the arrays [1, 2] and [2, 1] which don’t fall into the above cases for length issues, but it’s easy to see that they’re stable.Proof
Let’s look at the arrays X and Y again.
We consider the case where X_i \neq Y_i for all i, there are no three equal consecutive elements, and [1, 1, 2, 2]/[2, 2, 1, 1] don’t appear as subarrays.Some operation must be performed, which in turn means that some operation must be performed in both X and Y.
Let L denote the leftmost index in X that’s operated on.
W.l.o.g, we have X_L = 1 and Y_L = 2 (if not, swap X and Y and nothing changes).Since X_L = 1, we have Y_L = 2, and we cannot operate on Y_L (since it would affect index L-1, which X has no way of doing given that L is its leftmost operation).
This forces Y_{L+1} = 2 to be the only way to affect index L in Y. Of course, this then gives X_{L+1} = 1.Following similar logic, we’re forced into X_{L+2} = 2 and Y_{L+2} = 1, which then forces X_{L+3} = 2 and Y_{L+2} = 1 and so on.
In general, you’ll find that the process can never “end” with the restrictions in place to us.The one thing we might want to be careful about is the middle, since that’s the only place where operations can “cross over” from X into Y and vice versa.
However, it’s not hard to show that this can never happen if [1, 1, 2, 2]/[2, 2, 1, 1] are not present as a subarrays, since that forces the middle four elements to be [1, 2, 1, 2] at which point it can be shown that it’s never possible to operate on either of the middle two elements; which then forces the first/second halves to be completely independent since no other operations can cross the middle.To summarize, we have the following list of cases, and an array will be stable if and only if at least one one of them is true:
- N is odd or N = 2.
- A_i = A_{N+1-i} for some index i.
- A contains three consecutive equal elements.
- A contains [1, 1, 2, 2] as a subarray.
- A starts with [1, 1] or [1, 2, 2] (or ends with their reverse).
All the cases are easily checked in linear time, so applying this to each subarray individually results in a solution in \mathcal{O}(N).
TIME COMPLEXITY:
\mathcal{O}(N^3) per testcase.
CODE:
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n; cin >> n;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
auto go = [&](vector<ll> b) -> bool{
ll siz = sz(b);
b.insert(b.begin(),0);
if(siz&1) return 1;
if(siz == 2) return 1;
rep1(i,siz){
if(b[i] == b[siz-i+1]){
return 1;
}
}
if(b[1] == 2 and b[siz] == 1 and b[siz-1] == 1) return 1;
if(b[siz] == 2 and b[1] == 1 and b[2] == 1) return 1;
if(b[siz/2] == 2 and b[siz/2+2] == 1) return 1;
if(b[siz/2+1] == 2 and b[siz/2-1] == 1) return 1;
rep1(i,siz-3){
if(b[i] == b[i+1] and b[i+2] == b[i+3] and b[i] != b[i+2]){
return 1;
}
}
ll curr_cnt = 0;
b[1] = 1, b[siz] = 1;
rep1(i,siz){
if(b[i] == 1){
curr_cnt++;
}
else{
curr_cnt = 0;
}
if(curr_cnt >= 3){
return 1;
}
}
return 0;
};
ll ans = 0;
rep1(l,n){
vector<ll> b;
for(int r = l; r <= n; ++r){
b.pb(a[r]);
ans += go(b);
}
}
cout << ans << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}