PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Anton Trygub
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
2075
PREREQUISITES:
Bitwise Operation
PROBLEM:
You are given an array [A_1, \dots, A_N]. You want to split it into several (\ge 2) subarrays so that the following condition holds:
- Calculate the sum of elements in each subarray. Then, the AND of all these sums is nonzero, where AND denotes the bitwise AND operation.
Determine if it’s possible. If it’s possible, find one such split. You don’t have to minimize the number of subarrays.
EXPLANATION:
Instead of blindly trying out each split, let’s systematically try to find a split that has non-zero AND. We can do this by iterating over each bit and try whether if we can find a split such that the AND of all subarray sums has this bit on.
First we try whether we can do this strategy with the least-significant bit (0-th bit). We have some observation:
- If there are at least 2 elements in A with the 0-th bit on (in other words, at least 2 elements in A is odd), we can split the array such that AND of the subarray sums has the 0-th bit on. For example, if N = 7, and A_3 and A_5 are odd, then we can split A into [1, 3] and [4, 7].
- Otherwise, there is at most 1 element in A with the 0-th bit on. Then, we know that the 0-th bit is insignificant to other larger bits (the only way this bit is significant to other bits is by having at least two elements such bits on in the same subarray, which when added can mess up the bits in other places, but this is not the case here). Therefore, we simply ignore the 0-th bit and move on to the 1-st bit.
With those two observations, we can iterate through least-significant to most-significant bits, counting the occurences of each bit being on in the array A, and check whether this occurence is larger or equals to 2. If yes, we know there exists a construction; if not, we continue with the iteration.
TIME COMPLEXITY:
Time complexity is O(N \log \max{A}) for each test case.
SOLUTION:
Setter's Solution
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace __gnu_pbds;
using namespace std;
using ll = long long;
using ld = double;
typedef tree<
pair<int, int>,
null_type,
less<pair<int, int>>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define mp make_pair
int MOD = 998244353;
int mul(int a, int b) {
return (1LL * a * b) % MOD;
}
int add(int a, int b) {
int s = (a+b);
if (s>=MOD) s-=MOD;
return s;
}
int sub(int a, int b) {
int s = (a+MOD-b);
if (s>=MOD) s-=MOD;
return s;
}
int po(int a, ll deg)
{
if (deg==0) return 1;
if (deg%2==1) return mul(a, po(a, deg-1));
int t = po(a, deg/2);
return mul(t, t);
}
int inv(int n)
{
return po(n, MOD-2);
}
mt19937 rnd(time(0));
const int LIM = 1000005;
vector<int> facs(LIM), invfacs(LIM), invs(LIM);
void init()
{
facs[0] = 1;
for (int i = 1; i<LIM; i++) facs[i] = mul(facs[i-1], i);
invfacs[LIM-1] = inv(facs[LIM-1]);
for (int i = LIM-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
for (int i = 1; i<LIM; i++) invs[i] = mul(invfacs[i], facs[i-1]);
}
int C(int n, int k)
{
if (n<k) return 0;
if (n<0 || k<0) return 0;
return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}
struct DSU
{
int n;
vector<int> sz;
vector<int> parent;
vector<int> pos; //From parent
vector<int> gcd;
void make_set(int v) {
parent[v] = v;
sz[v] = 1;
}
int find_pos(int v)
{
if (v==parent[v])
return 0;
return (pos[v] + find_pos(parent[v]))%n;
}
int find_set(int v) {
if (v == parent[v])
return v;
return find_set(parent[v]);
}
ll eval(int v)
{
v = find_set(v);
return gcd[v];
}
void union_sets(int a, int b, int d) {
int da = find_pos(a);
int db = find_pos(b);
int diff = (da + d - db + n)%n;
//cout<<"DIFF: "<<diff<<endl;
if (find_set(a) == find_set(b))
{
a = find_set(a);
gcd[a] = __gcd(gcd[a], diff);
}
else
{
a = find_set(a);
b = find_set(b);
if (sz[a] < sz[b])
{
swap(a, b);
diff = (n - diff)%n;
}
parent[b] = a;
sz[a] += sz[b];
pos[b] = diff;
gcd[a] = __gcd(gcd[a], gcd[b]);
}
}
DSU (int N)
{
n = N;
parent.resize(n);
sz.resize(n);
gcd = vector<int>(n, n);
pos = vector<int>(n);
for (int i = 0; i<n; i++) make_set(i);
}
};
void print(vector<int> a)
{
for (auto it: a) cout<<it<<' ';
cout<<endl;
}
void print(vector<bool> a)
{
for (auto it: a) cout<<it<<' ';
cout<<endl;
}
void print(vector<pair<ll, ll>> a)
{
for (auto it: a) cout<<it.first<<' '<<it.second<<"| ";
cout<<endl;
}
void print(vector<pair<int, int>> a)
{
for (auto it: a) cout<<it.first<<' '<<it.second<<"| ";
cout<<endl;
}
/*const int mod = 998244353;
template<int mod>
struct NTT {
static constexpr int max_lev = __builtin_ctz(mod - 1);
int prod[2][max_lev - 1];
NTT() {
int root = find_root();//(mod == 998244353) ? 31 : find_root();
int rroot = power(root, mod - 2);
vector<vector<int>> roots(2, vector<int>(max_lev - 1));
roots[0][max_lev - 2] = root;
roots[1][max_lev - 2] = rroot;
for (int tp = 0; tp < 2; ++tp) {
for (int i = max_lev - 3; i >= 0; --i) {
roots[tp][i] = mul(roots[tp][i + 1], roots[tp][i + 1]);
}
}
for (int tp = 0; tp < 2; ++tp) {
int cur = 1;
for (int i = 0; i < max_lev - 1; ++i) {
prod[tp][i] = mul(cur, roots[tp][i]);
cur = mul(cur, roots[tp ^ 1][i]);
}
}
}
template<bool inv>
void fft(int *a, int lg) const {
const int n = 1 << lg;
int pos = max_lev - 1;
for (int it = 0; it < lg; ++it) {
const int h = inv ? lg - 1 - it : it;
const int shift = (1 << (lg - h - 1));
int coef = 1;
for (int start = 0; start < (1 << h); ++start) {
for (int i = start << (lg - h); i < (start << (lg - h)) + shift; ++i) {
if (!inv) {
const int y = mul(a[i + shift], coef);
a[i + shift] = a[i];
inc(a[i], y);
dec(a[i + shift], y);
} else {
const int y = mul(a[i] + mod - a[i + shift], coef);
inc(a[i], a[i + shift]);
a[i + shift] = y;
}
}
coef = mul(coef, prod[inv][__builtin_ctz(~start)]);
}
}
}
vector<int> product(vector<int> a, vector<int> b) const {
if (a.empty() || b.empty()) {
return {};
}
const int sz = a.size() + b.size() - 1;
const int lg = 32 - __builtin_clz(sz - 1), n = 1 << lg;
a.resize(n);
b.resize(n);
fft<false>(a.data(), lg);
fft<false>(b.data(), lg);
for (int i = 0; i < n; ++i) {
a[i] = mul(a[i], b[i]);
}
fft<true>(a.data(), lg);
a.resize(sz);
const int rn = power(n, mod - 2);
for (int &x : a) {
x = mul(x, rn);
}
return a;
}
private:
static inline void inc(int &x, int y) {
x += y;
if (x >= mod) {
x -= mod;
}
}
static inline void dec(int &x, int y) {
x -= y;
if (x < 0) {
x += mod;
}
}
static inline int mul(int x, int y) {
return (1LL * x * y) % mod;
}
static int power(int x, int y) {
if (y == 0) {
return 1;
}
if (y % 2 == 0) {
return power(mul(x, x), y / 2);
}
return mul(x, power(x, y - 1));
}
static int find_root() {
for (int root = 2; ; ++root) {
if (power(root, (1 << max_lev)) == 1 && power(root, (1 << (max_lev - 1))) != 1) {
return root;
}
}
}
};
NTT<mod> ntt;
*/
void solve()
{
int n; cin>>n;
vector<int> a(n); for (int i = 0; i<n; i++) cin>>a[i];
vector<int> pos;
for (int bit = 0; bit<30; bit++)
{
pos.clear();
for (int i = 0; i<n; i++) if (a[i]&(1<<bit)) pos.push_back(i+1);
if (pos.size()>=2)
{
cout<<"YES"<<endl;
int K = pos.size();
cout<<K<<endl;
cout<<1<<' '<<pos[0]<<endl;
for (int i = 1; i<K-1; i++) cout<<pos[i-1]+1<<' '<<pos[i]<<endl;
cout<<pos[K-2]+1<<' '<<n<<endl;
return;
}
}
cout<<"NO"<<endl; return;
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(nullptr);
int t; cin>>t;
while (t--) solve();
}
/*
5
4
1 9 8 4
3
0 0 0
2
16 15
5
1 2 6 24 120
7
8 6 0 16 24 0 8
*/
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e6+1;
int n,k;
ll a[N];
void solve(){
ll s=0;
ll mx=0;
vector<int>v;
v.push_back(0);
for(int i=1; i<=n ;i++){
mx=max(mx,a[i]);
if(a[i]%2==1) v.push_back(i);
}
if(mx==0){
cout << "NO\n";
return;
}
if(v.size()>=3){
cout << "YES\n";
cout << v.size()-1 << '\n';
v.back()=max(v.back(),n);
for(int i=1; i<v.size() ;i++){
cout << v[i-1]+1 << ' ' << v[i] << '\n';
}
return;
}
for(int i=1; i<=n ;i++) a[i]/=2;
solve();
}
int main(){
ios::sync_with_stdio(false);
int t;cin >> t;
while(t--){
cin >> n;
for(int i=1; i<=n ;i++) cin >> a[i];
solve();
}
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
bool ok = false;
for (int b = 0; b < 30; b++) {
vector<int> xd = {-1};
for (int i = 0; i < n; i++) {
if (a[i] >> b & 1) {
xd.push_back(i);
}
}
if (xd.size() >= 3) {
xd.back() = n - 1;
cout << "YES\n";
cout << xd.size() - 1 << '\n';
for (int i = 0; i < xd.size() - 1; i++) {
cout << xd[i] + 2 << " " << xd[i + 1] + 1 << '\n';
}
ok = true;
break;
}
}
if (!ok) {
cout << "NO\n";
}
}
}
