BCLGBIT - Editorial

editorial
,
1

PROBLEM LINK:

Practice

Author: vaibhav_0318
Tester: zombiedub
Editorialist: vaibhav_0318

DIFFICULTY:

SIMPLE-EASY

PREREQUISITES:

bit-manipulation

PROBLEM:

Apply operation of flipping the bits of all numbers between a range of indices L and R.(flipping here means after MSB of the number i.e. for example if the no. is 5(101_2) and applying operation to it will make it 2(010_2). We have to make the whole array equal to zero.
Cost of one operation R-L+1. We need to minimize no. of operations such that cost is minimum.

EXPLANATION:

The no. of operations for making any element equal to zero is fixed(for example - if the no. is 5(101_2) it will require 3 operations to make it equal to 0(5(101_2) → 2(010_2) → 1(001_2) → 0(000_2)).

So we can modify the given array with its number of operations. Now the operation on the chosen number is modified to decrement it by 1 until it becomes 0 .

Since the elements of the modified array cannot exceed 32 we can do it simply in O(N*32).

SOLUTIONS:

Solution 
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define all(v,i) v.begin()+i,v.end()
#define en "\n"
#define mem(a,b) memset(a,b,sizeof(a));
#define F first
#define S second
#define mod 1000000007
#define mod2 998244353

typedef long long int ll;

void applyOperation(ll &a){
    ll op=0;
    while(a){
        op++;
        ll t=a;
        t|=(t>>1);
        t|=(t>>2);
        t|=(t>>4);
        t|=(t>>8);
        t|=(t>>16);
        a=a^t;
    }
    a=op;
}

int main() {
    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    ll T=1,I;
    cin>>T;
    for(I=1;I<=T;I++){
        ll n;
        cin>>n;
        ll a[n];
        for(ll i=0;i<n;i++){
            cin>>a[i];
            applyOperation(a[i]);
        }
        ll op=0,c=0;
        for(ll i=0;i<=30;i++){
            ll l=-1;
            for(ll j=0;j<n;j++){
                if(a[j] && l==-1){
                    l=j;
                    op++;
                }
                if(a[j]==0 && l!=-1){
                    c+=j-l;
                    l=-1;
                }
                if(l!=-1)a[j]--;
            }
            if(l!=-1){
                c+=n-l;
            }
        }
        cout<<op<<' '<<c;
        cout<<en;
    }
    return 0;
}