PROBLEM LINK:
Author: valiant_vidit
Tester: hellb0y_suru
Editorialist: valiant_vidit
DIFFICULTY:
MEDIUM
PROBLEM:
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.
Prerequisites:
- knowledge of basic dp and its applications.
- A little amount of brain to be applied while solving or understanding the editorial
QUICK EXPLANATION:
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.
EXPLANATION:
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 , but if there is any confusion or query regarding the editorial or approach feel free to ping me 
!!
SOLUTIONS:
Setter's Solution
/*author : vidit shukla
(valiant_vidit)*/
#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;
if(k==0&&i==n)
return prevans;
if(k<0||i>=n)
return -1;
if(k==0)
return -1;
ll ans = 0;
if(dp[i][k][prevans]!=-2)
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.
bhaago;
ll tc=1;
cin>>tc;
while(tc--)
{
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});
}
mxk=10;
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++) {
if(dp[i][j][0]==-2)
{
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
printclock
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--){
if(dp[i][x][k]){
ans[i][k] = x;
break;
}
}
}
}
while(q--){
int id,k; cin >> id >> k;
cout << ans[id][k] <<"\n";
}
return;
}
int main(){
fastio;
int tc=1; cin >> tc;
while(tc--) __sol();
return 0;
}