Is It Eziee

Author: valiant_vidit
Tester: hellb0y_suru
Editorialist: valiant_vidit




Lets define a beauty of subarray , as the sum of all the elements in it.

Given an array A and Q different queries of the form ind K, such that you have to divide the array (a_{ind} a_{ind+1} …. a_{n−1}) into K contiguous subarrays such that the bitwise XOR of all the beauty of K subarrays is maximum considering each subarray is consisting of no more than L elements in it.


  • knowledge of basic dp and its applications.
  • A little amount of brain to be applied while solving or understanding the editorial :wink:


It is a kind of good implementation of dynamic programming where the states can be in the form i,j,x, i.e., dp[i][j][x] will store the value where you can make j cuts between i and n the index of array such that value of dp[i][j][x]^x is maximum.


Here, the recurrence relation will be of the form:
dp[i][j][x]=max(dp[h+1][j-1][x^(arr[i]+arr[i+1]+arr[i+2]...arr[h])]) for all h belonging to [i,max(i+l-1,n-1)].

To understand it better we can think it of in the way that the states are i_{th} index from which we will consider the array till last index, remaining j cuts and x is the current answer till now, that is bitwise XOR of total-j subarrays till index i-1 such that all having no more than l elements in it.

So, now the answer will be such that we iterate from i to i+l-1 elements, and will consider all array from given index and j-1 cuts and having answer=((sum of array elements from i to given index) ^ x).

As the complexity of our code is
Time Complexity: O(T*L*N*K*Maxsum+T*Q)= 10*20*100*10*10^3+10*10^5= O(2*10^8)= 2 seconds approximately, which will satisfy the required constraints.

I hope the solution was helpful :wink: , but if there is any confusion or query regarding the editorial or approach feel free to ping me :+1:!!


Setter's Solution
/*author : vidit shukla
#pragma  GCC optimize("O3")
#include <bits/stdc++.h>
#define ll               long long int
#define ld               long double  
#define bhaago           ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define loop(a,b,i)      for(ll i=a;i<b;i++)
#define loop1(a,b,i)     for(ll i=a;i>b;i--)

#define printclock       cerr<<"Time : "<<1000*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define endl              '\n'
#define Endl              '\n'
#define all(v)           (vector.begin(),vector.end())
#define az(i)            for(auto it:i)cout<<it<<" ";cout<<Endl;
#define mpaz(i)          for(auto it:i)cout<<it.first<<"->"<<it.second<<endl;cout<<Endl;
#define araz(arr,i)      loop(0,i,j)cout<<arr[j]<<" ";cout<<Endl;
#define setin(s,i)       for(auto it:i)s.insert(it);
#define mpin(mp,i)       for(auto it:i)mp[it]++;
#define yy               cout<<"YES"<<endl
#define nn               cout<<"NO"<<endl
#define prn1(tk,ans)      cout<<"Case #"<<tk<<": "<<ans<<endl
#define prn(tk)          cout<<"Case #"<<tk<<": "
#define init(dp,i)       memset(dp,i,sizeof dp)
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
const double pi = std::acos(-1);
using namespace std;
const ll mod = 1000000000+7;

 ll rc1(ll i,ll k,ll prevans,ll l,ll arr[],ll n,vector<vector<vector<ll>>> &dp){
    ll gbans = -1;

       return prevans;
       return -1;

       return -1;
    ll ans = 0;
  return dp[i][k][prevans];
    for (ll h = i; h <= min(i + l-1,n-1);h++)
        ans += arr[h];
        gbans=max(gbans,rc1(h + 1, k - 1, ans^prevans,l,arr,n,dp));
    return dp[i][k][prevans]=gbans;
int main() {
//see if tcs are present or not.
   ll tc=1;
       ll n, k, l, q;
       cin>>n>>q>>l; ll arr[n];
       ll mxsum = 0;
       loop(0, n, i) {cin >> arr[i];
       mxsum += arr[i];}
       vector<pair<ll, ll>> vc;
       ll mxk = 0;
       loop(0, q, i){
           ll p1,p2;// i index with j cuts 
           cin >> p1 >> p2;
           mxk = max(mxk, p2);
           vc.push_back({p1, p2});
       vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(mxk + 1, vector<ll>((1LL<<11), -2)));
        for (ll i = 0; i < n; i++) {
            for (ll j = 1; j <= mxk; j++) {
                       rc1(i, j, 0, l, arr, n,dp);

            loop(0, q, i)
               cout << dp[vc[i].first][vc[i].second][0] << "\n";

   // your code goes here
   return 0;
Tester's Solution
/*  Jai Shree Ram 🚩🚩🚩 */
#include "bits/stdc++.h"
#define ll long long int
#define oo 1000000000000000000
#define forr(i,n) for(int i=0;i<n;i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define all(x) x.begin(),x.end()
#define unique(v) sort(all(v)); v.resize(distance(v.begin(),unique(all(v))))
#define eb emplace_back
#define FF first
#define SS second
#define mem(a,v) memset(a,v,sizeof(a))
#define pb push_back
#define popcount(x) __builtin_popcount(x)

using namespace std;

template<typename T>
ostream &operator<<(ostream &output,const vector<T> &v){ 
   if(v.empty()) return output;
   for(int i=0;i<v.size()-1;i++) output << v[i] <<" ";
   output << v.back();
   return output;
template<typename T>
istream &operator>>(istream &input,vector<T> &v){ 
   for(auto &i: v) cin >> i;
   return input;            

const int rg = (1<<12);

bool dp[102][rg][12];

void __sol(){
   int n,q,l; cin >> n >> q >> l;
   for(int i=0;i<=n;i++){
       for(int seg=0;seg<=10;seg++){
           for(int j=0;j<rg;j++){
               dp[i][j][seg] = 0;
   vector<int> v(n); cin >> v;
   dp[n][0][0] = 1;
   for(int i=n-1;i>=0;i--){
       int sum = 0;
       for(int j = i; j < n && j - i + 1 <= l; j++){
           sum += v[j];
           for(int seg=1;seg<=10;seg++){
               for(int x=0;x<rg;x++){
                   if( (sum^x) < rg && dp[j+1][sum ^ x][seg - 1]){
                       dp[i][x][seg] = 1;
   vector<vector<int>> ans(n , vector<int>(11,-1));
   for(int i=0;i<n;i++){
       for(int k=1;k<=10;k++){
           for(int x=rg-1;x>=0;x--){
                   ans[i][k] = x;
       int id,k; cin >> id >> k;
       cout << ans[id][k] <<"\n";

int main(){ 
   int tc=1; cin >> tc;
   while(tc--) __sol();
   return 0;