AND of Maximums CodeChef Solution – Queslers

Problem: AND of Maximums CodeChef Solution

You are given an array of NN integers [A1,A2,…,AN][A1,A2,…,AN] and an integer K≤NK≤N. You are going to split the array into KK consecutive nonempty subarrays, so that every element is included in exactly one subarray, then to find the maximum value in each subarray, and to calculate the bitwise AND of all these maximums. What is the largest possible integer you can obtain as a result?

Input Format

• The first line contains a single integer TT −− the number of test cases. The description of test cases follows.
• The first line of each test case contains two integers N,KN,K −− the length of the array and the required number of subarrays.
• The second line of each test case contains NN integers A1,A2,…,ANA1,A2,…,AN.

Output Format

For each test case, output a single integer −− the answer to the problem.

Constraints

• 1≤K≤N≤2000001≤K≤N≤200000
• 0≤Ai≤1090≤Ai≤109
• The sum of NN over all test cases doesn’t exceed 200000200000.

Sample Input 1 

3
5 1
100 10 1 1000 10000
6 2
7 8 9 10 11 12
5 3
26447356 268435455 56544987 1000000000 296823278

Sample Output 1 

10000
8
52087296

Explanation

Explanation of test case 1: We need to split the array into only 11 subarray, so the answer is just the maximum of the array.

Explanation of test case 2: One way to split the array into two parts to achieve 88 is: [7,8,9],[10,11,12][7,8,9],[10,11,12]. The maximums are 99 and 1212, and their AND is 88.

AND of Maximums CodeChef Solution in C++

#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")

#define ll long long
//#define int ll
#define ull unsigned ll
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define chkmin(a,b) (a=min(a,b))
#define chkmax(a,b) (a=max(a,b))
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define inf 1010000000
//#define inf 4000000000000000000
#define eps 1e-9
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define print0(a) cout << (a) << ' '
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#ifdef i_am_noob
#define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__)
template<typename T> void _do(vector<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(unordered_set<T> x){for(auto i: x) cerr << i << ' ';cerr << "\n";}
template<typename T> void _do(T && x) {cerr << x << endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);}
#else
#define bug(...) 777771449
#endif
template<typename T> void print(T && x) {cout << x << "\n";}
template<typename T, typename... S> void print(T && x, S&&... y) {cout << x << ' ';print(y...);}

const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
template <int mod>
struct Modint{
    int val;
    Modint(int _val=0){val=_val%mod;if(val<0) val+=mod;}
    Modint operator +(const Modint& o) const {
        Modint res;
        res.val=val+o.val;
        if(res.val>=mod) res.val-=mod;
        return res;
    }
    Modint operator +(const int& o) const {return Modint(val+o);}
    Modint operator -() const {
        Modint res;
        res.val=-val;
        if(res.val<0) res.val+=mod;
        return res;
    }
    Modint operator -(const Modint& o) const {
        Modint res;
        res.val=val-o.val;
        if(res.val<0) res.val+=mod;
        return res;
    }
    Modint operator -(const int& o) const {return Modint(val-o);}
    Modint operator *(const Modint& o) const {return Modint(val*o.val);}
    Modint operator *(const int& o) const {return Modint(val*(o%mod));}
    Modint operator +=(const Modint& o){*this=(*this)+o;return *this;}
    Modint operator -=(const Modint& o){*this=(*this)-o;return *this;}
    Modint operator *=(const Modint& o){*this=(*this)*o;return *this;}
    Modint Pow(int b) const {
        Modint tmp(val),ret(1);
        while(b){
            if(b&1) ret*=tmp;
            b>>=1;tmp*=tmp;
        }
        return ret;
    }
    Modint Pow(const Modint& a, int b) const {return a.Pow(b);}
    inline Modint inv() const {return (*this).Pow(mod-2);}
    Modint operator /(const Modint& o) const {return *this*o.inv();}
    Modint operator /(const int& o) const {return *this*Modint(o).inv();}
    bool operator ==(const Modint& o) const {return val==o.val;}
};
template<int mod>
ostream& operator << (ostream& o, Modint<mod> x){return o << x.val;}
template<int mod>
Modint<mod> operator +(const int& x, const Modint<mod>& y){return Modint<mod>(x+y.val);}
template<int mod>
Modint<mod> operator -(const int& x, const Modint<mod>& y){return Modint<mod>(x-y.val);}
template<int mod>
Modint<mod> operator *(const int& x, const Modint<mod>& y){return Modint<mod>(x%mod*y.val);}
#define modint Modint<MOD>
vector<modint> inv,fac,invfac;
void init_comb(int N){
    inv.resize(N),fac.resize(N),invfac.resize(N);
    inv[1]=1,fac[0]=1,invfac[0]=1;
    rep2(i,2,N) inv[i]=inv[MOD%i]*(MOD-MOD/i);
    rep2(i,1,N) fac[i]=fac[i-1]*i;
    rep2(i,1,N) invfac[i]=invfac[i-1]*inv[i];
}
inline modint C(int n, int m){return m>n||m<0?modint(0):fac[n]*invfac[m]*invfac[n-m];}
inline modint H(int n, int m){return C(n+m-1,n);}
template<typename T, T(*op)(T,T), T(*e)(), signed N>
struct segtree{
    static const signed maxn=1<<__lg(N-1)+1;
    T val[maxn<<1];
    segtree(){rep(maxn<<1) val[i]=e();}
    void pull(signed k){val[k]=op(val[k<<1],val[k<<1|1]);}
    void modify(signed p, T x){
        p+=maxn;
        val[p]=x;
        for(p>>=1; p; p>>=1) pull(p);
    }
    T query(signed l, signed r){
        T resl=e(),resr=e();
        l+=maxn,r+=maxn+1;
        while(l<r){
            if(l&1) resl=op(resl,val[l++]);
            if(r&1) resr=op(val[--r],resr);
            l>>=1,r>>=1;
        }
        return op(resl,resr);
    }
};
const int maxn=200005,maxm=50005,maxk=7777714;

//i_am_noob
#define wiwihorz  
int n,k,a[maxn],l[maxn],r[maxn],dp[maxn],val[maxn];
vector<vector<int>> vec(maxn);
bool alive[maxn];
constexpr int op(int x, int y){return max(x,y);}
constexpr int e(){return -1e9;}
segtree<int,op,e,maxn> tree;

void orzck(){
    //ld start=clock();
    cin >> n >> k;
    rep(n) cin >> a[i];
    vector<int> stk;
    rep(n){
        while(sz(stk)&&a[stk.back()]<=a[i]) stk.pop_back();
        l[i]=sz(stk)?stk.back():-1;
        stk.pb(i);
    }
    stk.clear();
    rep3(i,n-1,0){
        while(sz(stk)&&a[stk.back()]<=a[i]) stk.pop_back();
        r[i]=sz(stk)?stk.back():n;
        stk.pb(i);
    }
    int maxx=*max_element(a,a+n);
    int cur=0;
    //bug((clock()-start)/CLOCKS_PER_SEC);
    rep3(j,30,0) if(maxx>>j&1){
        cur^=pow2(j);
        rep(n+1) vec[i].clear();
        set<pii> st;
        memset(alive,0,n+2);
        dp[0]=0;
        tree.modify(0,0);
        //bug((clock()-start)/CLOCKS_PER_SEC);
        int c=0;
        rep(n){
            if((a[i]&cur)==cur){
                val[i]=tree.query(l[i]+1,i);
                //pq.push({val[i],i});
                st.insert({val[i],i});
                alive[i]=1;
                c++;
            }
            vec[r[i]].pb(i);
            for(auto t: vec[i]) alive[t]=0;
            //while((!pq.empty())&&!alive[pq.top().second]) pq.pop();
            while((!st.empty())&&!alive[(*st.rbegin()).second]) st.erase(--st.end());
            dp[i+1]=-inf;
            //if(!pq.empty()) dp[i+1]=pq.top().first+1;
            if(!st.empty()) dp[i+1]=(*st.rbegin()).first+1;
            tree.modify(i+1,dp[i+1]);
        }
        if(dp[n]<k) cur^=pow2(j);
        //bug(j,c);
        //bug((clock()-start)/CLOCKS_PER_SEC);
    }
    print(cur);
    //bug((clock()-start)/CLOCKS_PER_SEC);
}

signed main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    #ifdef i_am_noob
    freopen("input1.txt","r",stdin);
    freopen("output1.txt","w",stdout);
    freopen("output2.txt","w",stderr);
    #endif
    cout << fixed << setprecision(15);
    int t;
    #ifdef wiwihorz
    cin >> t;
    #else
    t=1;
    #endif
    while(t--) orzck();
    return 0;
}

AND of Maximums CodeChef Solution Review:

In our experience, we suggest you solve this AND of Maximums CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

AND of Maximums Problem is available on Hacker Rank for Free, if you are stuck anywhere between a compilation, just visit Queslers to get AND of Maximums CodeChef Solution.

Conclusion:

I hope this AND of Maximums CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Hacker Rank, Leetcode, Codechef, Codeforce Solution.

This Problem is intended for audiences of all experiences who are interested in learning about Data Science in a business context; there are no prerequisites.

Keep Learning!

More CodeChef Solutions >>

Olympics Ranking CodeChef Solution

Problem Difficulties CodeChef Solution

Chef and Bulb Invention CodeChef Solution

Array Filling CodeChef Solution

Special Triplets CodeChef Solution