MAXDMGE - Editorial

PROBLEM LINK:

Practice
Div-1 Contest
Div-2 Contest
Div-3 Contest

Author: Ansh Gupta
Tester: Miten Shah
Editorialist: Ansh Gupta

DIFFICULTY:

SIMPLE

PREREQUISITES:

Bit Manipulation

PROBLEM:

Nasir and two of his henchmen are planning to attack N shops of the Qureshi clan. The shops are conveniently lined up, and numbered from 1 to N. The i-th shop contains A_i kg of coal. For each shop (1\leq i\leq N), find the damage caused when Nasir bombs it.

QUICK EXPLANATION:

Given an array of n numbers, for each index we have to select a subarray of size greater than 1 including that index such that we can get the maximum Bitwise & possible.

EXPLANATION:

Let suppose a number x, if we take Bitwise & of x with another number y, the resultant will be less than or equal to x i.e ( x&y ) \leq x.
So increasing the size of subarray will not increase the resultant. So we will select Subarray of minimum size i.e 2 including the index itself, which means we have to select one more index either from left or to the right of that index.
Pseudo code

for(ll i=1;i<=n;i++){
    if(i==1)cout<<(shop[i]&shop[i+1])<<" ";
    else if(i==n)cout<<(shop[i-1]&shop[i])<<" ";
    else cout<<max((shop[i]&shop[i+1]),(shop[i-1]&shop[i]))<<" ";
}

TIME COMPLEXITY:

Overall time complexity would be be: O(n) per test case, where n is the number of shops

SOLUTIONS:

Setter's Solution

#include "bits/stdc++.h"
using namespace std;
#define ll long long
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    assert(1 <= t && t <= 10000);
    ll sum = 0;
    while (t--) {
        ll n;
        cin >> n;
        sum += n;
        assert(n > 1 && n <= 200000);
        assert(n < 1000000000);
        assert(sum <= 200000);
        ll arr[n + 2];
        for (ll i = 0; i < n; i++)cin >> arr[i + 1];
        arr[0] = 0;
        arr[n + 1] = 0;
        for (ll i = 1; i <= n; i++)cout << max(arr[i]&arr[i + 1], arr[i - 1]&arr[i]) << " ";
        cout << endl;

    }

}

Tester's Solution
// created by mtnshh

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define rb pop_back
#define ti tuple<int, int, int>
#define pii pair<int, int>
#define pli pair<ll, int>
#define pll pair<ll, ll>
#define mp make_pair
#define mt make_tuple
 
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
 
#define err() cout<<"--------------------------"<<endl; 
#define errA(A) for(auto i:A)   cout<<i<<" ";cout<<endl;
#define err1(a) cout<<#a<<" "<<a<<endl
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<endl
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<endl
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<endl

#define all(A)  A.begin(),A.end()
#define allr(A)    A.rbegin(),A.rend()
#define ft first
#define sd second

#define V vector<ll>
#define S set<ll>
#define VV vector<V>
#define Vpll vector<pll>
 
#define endl "\n"

long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        // char g = getc(fp);
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
            
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
            // cerr << x << " " << l << " " << r << endl;
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        // char g=getc(fp);
        assert(g != -1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}

const int max_q = 1e4;
const int max_n = 2e5;
const int max_ai = 1e9;

const ll N = 200005;
const ll INF = 1e12;

void solve(ll n){
    ll A[n];
    rep(i,0,n){
        if(i!=(n-1))
            A[i] = readIntSp(0, max_ai);
        else
            A[i] = readIntLn(0, max_ai);
    }
    rep(i,0,n){
        ll ans = 0;
        if(i!=0)
            ans = max(ans, A[i]&A[i-1]);
        if(i!=(n-1))
            ans = max(ans, A[i]&A[i+1]);
        cout << ans << " ";    
    }
    cout << endl;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    ll q = readIntLn(1, max_q);
    ll sum_n = 0;
    while(q--){
        ll n = readIntLn(1, max_n);
        solve(n);
        sum_n += n;
    }
    assert(sum_n <= max_n);
    assert(getchar()==-1);
}
Editorialist's Solution

#include "bits/stdc++.h"
using namespace std;
#define ll long long
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    int t;
    cin >> t;
    assert(1 <= t && t <= 10000);
    ll sum = 0;
    while (t--) {
        ll n;
        cin >> n;
        sum += n;
        assert(n > 1 && n <= 200000);
        assert(n < 1000000000);
        assert(sum <= 200000);
        ll arr[n + 2];
        for (ll i = 0; i < n; i++)cin >> arr[i + 1];
        arr[0] = 0;
        arr[n + 1] = 0;
        for (ll i = 1; i <= n; i++)cout << max(arr[i]&arr[i + 1], arr[i - 1]&arr[i]) << " ";
        cout << endl;

    }

}

8 Likes

I wrote the same exact code. How was I getting WA’s b2b ??
I would have posted my code but can’t even find my submission in my profile or in Submissions .

1 Like

This simple code can help to python coder

#PYTHON CODE


def maxDamage(n):
    global a
    if n == 0:
        return a[0]&a[1]
    elif n == len(a)-1:
        return a[n]&a[n-1]
    else:
        return max(a[n]&a[n-1], a[n]&a[n+1])

for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    ans = []
    for i in range(n):
        ans.append(maxDamage(a, i))
    print(*ans)

3 Likes