SPLITANDSUM - Editorial

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";
        }
    }
}
5 Likes

Any suggesting where it is going wrong?

https://www.codechef.com/viewsolution/66187155

2 Likes

It did not occur to me that if we iterate from LSB to MSB, nothing afterward can be messed up - that’s clever

4 Likes

Good video editorial :slight_smile:

2 Likes

I think I am also doing the same thing.
Please tell me, is there anything which I am not doing correctly?
https://www.codechef.com/viewsolution/66150385

Got the error! I was not printing the size of answer! :smiling_face_with_tear:

You are not printing the total number of subarrays. Just print “v.size()” before the for loop and it will be fine

1 Like

:frowning:
These silly mistakes ruins my contest.

https://paste.ofcode.org/Lgyxxqk5QWAv4ueNKXFNns

Can anyone tell me why this is giving wa

https://paste.ofcode.org/Lgyxxqk5QWAv4ueNKXFNns
Can anyone tell me why this is giving wa

Note that I don’t use cpp, but there is a section that looks very wrong to me:

for(int bit=0;bit<=31;bit++){
    int sb=0;
    for(int i=0;i<n;i++){
        if((v[i]>>bit)&1){
            sb++;
        }
    }
    if(sb>=2) {
        check=bit; //THIS!
    }
}

you remember the bit that has more than 2 occurrences. But this is not completely correct, you need to find the FIRST bit that has more than 2 occurrences. meaning the moment you find a bit that works, you break out of the for-loop.

example why it has to be the first bit:
[1, 1, 2, 2]

if you go for the first bit, your subarrays will look like this:
[1], [1, 2, 2] (this works)

if you go for the second bit, your subarrays will look like this:
[1, 1, 2] [2] (this won’t work)

Can anyone please tell me why I am getting WA?

#include<bits/stdc++.h>
using namespace std;
#define ll long long
void solve(){
	ll n;
	cin>>n;
	vector<ll> v(n);
	for(auto &x:v){
		cin>>x;
	}

	vector<pair<ll,ll>> vp;
	ll and_value=v[0];
	ll start=1;
	for(ll i=1;i<n;i++){
		if((and_value & v[i]) == 0){
			// cout<<and_value<< " and "<< v[i]<< " = 0"<<endl;
			and_value+=v[i];
		}
		else{
			vp.push_back({start,i});
			start=i+1;
			and_value=v[i];
		}
	}
	vp.push_back({start,n});

	if(vp.size()<=1)cout<<"NO"<<endl;
	else {
		cout<<"YES"<<endl;
		cout<<vp.size()<<endl;
		for(auto x:vp){
			cout<<x.first<<" "<<x.second<<endl;
		}
	}
}
int main(){
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

I am getting wrong answers but I wrote it from the editorial :frowning:

(Solution: 66259063 | CodeChef)

can anyone tell what is wrong in my code

#include <bits/stdc++.h>
#define ull unsigned long long int
#define ui unsigned int
#define ll long long int
#define f(i, n) for (ll i = 0; i < n; i++)
const ll m = 10e9 + 7;
// const ll N = 10e5 + 5;
using namespace std;
int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(0);

    ll t;

    cin >> t;

    while (t--)

    {

        ll n;

        cin >> n;

        vector<int> arr(n);

        f(i, n) cin >> arr[i];

        int count = 0;

        bool flag = false;

        int pos = -1;

        f(p, 32)

        {

            count = 0;

            f(i, n)

            {

                if (arr[i] & 1 << p)

                    count++;

            }

            if (count >= 2)

            {

                flag = true;

                pos = p;

                break;

            }

        }

        if (!flag)

            cout << "No" << '\n';

        else

        {

            vector<int> temp;

            f(i, n)

            {

                if (arr[i] &( 1 << pos))

                {

                    temp.push_back(i);

                }

            }

            cout << "Yes" << '\n';

            cout << count << '\n';

            f(i, temp.size())

            {

                if (i != temp.size() - 1)

                {

                    cout << temp[i] + 1 << " " << temp[i + 1] << '\n';

                }

                else

                {

                    cout << temp[i] + 1 << " " << n << '\n';

                }

            }

        }

    }

    return 0;

}

hello, can anyone please tell me what is wrong in my approach ,instead of taking a subarray with sum i am considering a single element and checking if there is other element in the array for which both the numbers have position where both their bits are set!
#include <bits/stdc++.h>

using namespace std;
#define int long long
#define endl " \n"
#define mod 1000000007
/void checkprime(bool isprime[],int n){
isprime[0]=false;
isprime[1]=false;
for(int i=2;i
i<=n;i++){//logic of iterating till sqaure root of n and not n
if(isprime[i]==true){//if a number is prime it’s multiples will not be prime
for(int j=ii;j<=n;j=j+i){//observation step
isprime[j]=false;
}
}
}
}
/

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t–){
int n;
cin>>n;

int a[n];
for (int i = 0; i < n; ++i)
{
 cin>>a[i];
}
int flag=0;

for (int i = 0; i < 32; ++i)
{
  int count=0;
  vector<int> v;
  for (int j = 0; j< n; ++j)
  {
    if(a[j]&(1<<i)){
      count++;
      v.push_back(j+1);
      if(count>=2){
        break;
      }

    }


  }
  if(count>=2){
    flag=1;
    cout<<"yes"<<endl;
    cout<<v.size()<<endl;
    cout<<v[0]<<" "<<v[0]<<endl;
    cout<<v[1]<<" "<<v[1]<<endl;
      break;
    }
}
if(flag==0){
  cout<<"no"<<endl;
}

}

return 0;

}

Can someone help me in identifying the mistake in this program? As far as I know, I implemented the same logic as mentioned in the editorial, and it seems to be working fine for most of the testcases I put on it. Please help. :slight_smile:

#include <iostream>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i<n; i++)
#define repc(i, a, b) for(int i = a; i<b; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define fast_io std::ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define pb push_back
#define MOD 1000000007
#define sortv(v) sort(v.begin(), v.end())
#define reversev(v) sort(v.begin(), v.end())
#define all(v) (v.begin(), v.end())

using namespace std;
#define show(x) cout << #x <<" is " << x << "\n";

typedef long long int ll;
typedef unsigned long long int ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvl;
typedef vector<bool> vb;
typedef set<int> si;
typedef set<ll> sll;
typedef map<int, int> mi;
typedef pair<int, int> pi;
typedef map<ll, ll> mll;
typedef pair<ll, ll> pll;
int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;

        

        vll v;

        ll t;
        cin >> t;

        ll a = t;
        ll o = t;
        ll x = t;

        ll mx = LONG_LONG_MIN;
        v.pb(t);

        rep(i,n-1){
            ll temp;
            cin >> temp;

            a &= temp;
            o |= temp;
            x ^= temp;

            if(mx < temp)
                mx = temp;

            v.pb(temp);
        }

        ll ct = 0;
        ll check = 0;
        // show(mx)
        ll bt = 0;
        while(mx > 0){
            
           
            // show(bt)
            // show((1<<bt))
            for(ll l : v){
                if(l & (1 << bt))
                    ct++;
            }

            // cout << ct << '\n';

            if(ct >= 2){
                check = 1 << bt;
                break;
            }
                

            bt++;
            mx >>=1;
            ct = 0;
        }


        if(a != 0){
            cout << "YES\n" << n << '\n';

            rep(i,n){
                cout << i << ' ' << i << '\n';
            }
        }else{
            if(check == 0){
                cout << "NO\n";
                continue;
            }

            vi part;

            ll sum = 0;
            bool started = 0;

            // show(check);

            rep(i,n){
                sum += v[i];

                
                // show((sum & check));


                if((sum & check) && (!started)){
                    started = true;
                }

                if(!(sum & check) && started){
                    part.pb(i-1);
                    sum = v[i];
                    started = true;
                }
            }

            part.pb(n-1);

            int prev = 1;

            
                cout << "YES\n";
                cout << part.size() << '\n';

                rep(i,part.size()){
                    cout << prev << ' ' << (part[i] + 1) << '\n';
                    prev = part[i] + 2;
                }
            
            
        }

    }
    return 0;
}

Cananyone explain reason/intution behind working of this logic?SPLITANDSUM problem

can anyone tell me reason/intution why this logic is working? SPLITANDSUM problem

can anyone suggest where my logic is wrong?

#include <iostream>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    int a[n];
	    for(int i=0;i<n;i++) cin>>a[i];
	    int bit[32];
	    for(int i=0;i<32;i++) bit[i]=-1;
	    int temp=1,c=0,flag=0;
	    while(c<31){
	        temp = 1<<c;
	        for(int i=0;i<n;i++){
	            if(temp&a[i] && bit[c]==-1) bit[c] = i+1;
	            else if(temp&a[i] && bit[c]!=-1){
	                cout<<"YES\n";
	                cout<<"2\n";
	                cout<<"1 "<<i<<"\n";
	                cout<<i+1<<" "<<n<<"\n";
	                flag = 1;
	                break;
	            }
	        }
	        if(flag) break;
	        c+=1;
	    }
	    if(!flag) cout<<"NO\n";
	}
	return 0;
}

Isn’t it invalid for array = [1,3,4,6] ?