PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given an array containing only ones and twos.
It’s said to be good if none of its prefix sums are multiples of 3.
Is it possible to reverse at most one prefix of the array to make it good?
EXPLANATION:
There are a couple of different ways to solve the problem: either look at the array itself, or look at the prefix sum array.
Solution 1
What does a good array (i.e. an array with no prefix sum being a multiple of 3) look like?
Suppose the first element is 1.
Then, note that the second element cannot be 2, since that would result in a prefix sum of 3. So, the second element has to be 1.
Now, the third element cannot be 1 (since the prefix sum will become 3), so the third element has to be 2.
The fourth element then cannot be 2, and so has to be 1, and so on.That is, if the first element is 1, then the array must look like
[1, 1, 2, 1, 2, 1, 2, \ldots]
i.e. starting from the second element, it’s alternating ones and twos.If the first element is 2 instead, the array must look like
[2, 2, 1, 2, 1, 2, 1, \ldots]
instead - the same pattern just with ones and twos flipped.So, our task is to figure out whether some prefix of A can be reversed to form this array.
Observe that a nice characterization of the above array is: the first two elements are equal, and then no other pair of adjacent elements are equal.Let i be the smallest index of A such that A_i = A_{i-1}.
Observe that the only possible candidate for the reversal is then the prefix till i.
To see why, suppose we reverse the prefix till j. Then,
- If j \lt i, the first two elements of the array after reversal will be A_j and A_{j-1}.
However, we know for sure that A_j \neq A_{j-1} (because i is the smallest index where that happens).
So, the first two elements of the array after reversal are not equal, meaning it can’t be either [1, 1, 2, 1, 2, \ldots] or [2, 2, 1, 2, 1, \ldots].- If j \gt i, then after the reversal both A_i and A_{i-1} will still be adjacent to each other but won’t be the first two elements - so the resulting array won’t be of the required form either.
So, index i is the only candidate for reversal at all.
This means we can just find i, then reverse the array till i and check if the condition holds in this new array.There’s one small detail here: what if no valid i exists at all?
This happens exactly when the array is fully alternating, i.e. [1, 2, 1, 2, \ldots] or [2, 1, 2, 1, \ldots].
In both these cases, it’s easy to see that no reversal can work (since it’s impossible to reverse a prefix and make the first two elements equal).
So, if no valid i exists then the answer is also immediately"No"(unless N = 1).
Solution 2
We look at the prefix sum array of A.
Let P_i = (A_1 + A_2 + \ldots + A_i)\bmod 3.
It’s enough to consider P_i modulo 3 since we only care about whether this value is 0 or not.
Our goal is to make P contain no zeros.Consider what happens when we reverse the prefix till k.
- For i \geq k, P_i doesn’t change at all, since the set of elements being summed up remains the same.
- For i \lt k, the new value of P_i is P_k - P_{k-i}, modulo 3.
So, for a choice of k to be valid (meaning no P_i equals 0 after the reverse),
- All indices i such that P_i = 0 must be \lt k.
- P_k should not equal P_i for any i \lt k.
This is because, if P_k = P_i, then after the reversal the prefix sum till the (k-i)-th index will be P_k - P_{i} modulo 3 which is 0.This means all we need to do is find the position of the last 0 in P, and then check all indices after it for validity.
To check for validity quickly, we only want to know if some prior index has the same prefix sum as this one; the simplest way is to just store the leftmost occurrence of each prefix sum and compare against that (since if some occurrence exists to the left, certainly the leftmost occurrence will).
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3, Solution 1)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
i = 0
while i+1 < n:
if a[i] == a[i+1]: break
i += 1
if i+1 < n:
a = list(reversed(a[:i+2])) + a[i+2:]
p = [0]
for x in a: p.append((p[-1] + x) % 3)
print('Yes' if min(p[1:]) > 0 else 'No')
else:
print('Yes' if n == 1 else 'No')
Tester's code (C++, Solution 2)
#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];
vector<ll> p(n+5);
rep1(i,n) p[i] = (p[i-1]+a[i])%3;
ll mxz = 0;
rep1(i,n) if(!p[i]) mxz = i;
vector<bool> came(3);
came[0] = 1;
rep1(i,n){
if(!came[p[i]] and i > mxz){
yes;
return;
}
came[p[i]] = 1;
}
no;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}