PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Author: Pratik Kumar
Tester: Anay Karnik
Editorialist: Mohan Abhyas
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
None
PROBLEM:
Chef and one of his friends were practicing for ICPC together by giving each other programming problems.
In Chef’s turn, Chef gave his friend a modified deque (double-ended queue), initially with N elements A_1, A_2, \ldots, A_N, which supported performing operations of the following type:
- Choose an integer K, which must be a power of 2 (possibly 2^0 = 1). Additionally, each particular value of K can only be chosen if it has not been chosen in any previous operation.
- Delete K elements from the end of the deque.
- Then, you may also decide to delete K elements from the beginning of the deque.
- However, the deque is not allowed to become completely empty.
Chef also gave his friend a special integer M and asked him to find the minimum number of operations needed such that the sum of the elements remaining in the deque is divisible by M, or determine that it is impossible to achieve this goal.
Chef’s friend could not solve the problem and asked for your help. Can you solve it for him?
EXPLANATION:
The operations are such that we can remove any number of elements of array from the end (use binary representation of number). If we want to delete R elements from the end then the values of integers(Ks) used in the operations is uniquely determined by binary representation of R.
The no of elements deleted from the beginning(L) will be such that L\&R = L and L+R < N.
Maintain prefix sums of array to get \sum_{k=i}^{k=j}A_k in \mathcal{O(1)}.
Iterate over value of R = 0,\dots,N-1
For each value of R iterate over L such that L\&R = L and L+R < N. This can be done efficiently in \mathcal{O}(3^{log_2(N)}) using this kind of iteration
for(int r = 0; r < N; r++)
{
for(int l = r; l > 0; l = (l-1)&r)
{
//check here
}
}
TIME COMPLEXITY:
\mathcal{O}(3^{log_2(N)}) per testcase.
SOLUTIONS:
[details = “Setter’s Solution”]
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vl vector<ll >
const int INF = 1e9;
int calc(vl &pref,int mx,int cur)
{
for(int i = cur; ; i = (i-1)&cur)
{
if(i<mx && pref[i]==pref[mx])
{
int x = __builtin_popcount(cur);
return x;
}
if(i==0)break;
}
return INF;
}
void solve()
{
int n,m;
cin >> n >> m;
int arr[n+1];
for(int i = 0; i<n; i++)cin >> arr[i+1];
vl pref(n+1,0);
int ans = INF;
for(int i = 1; i<=n; i++)
{
pref[i] = pref[i-1]+arr[i];
pref[i] %= m;
ans = min(ans,calc(pref,i,n-i));
}
if(ans==INF)cout << "-1\n";
else
{
cout << ans << "\n";
}
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);
int t = 1;
cin>> t;
for(int i = 1; i<=t; i++) {
solve();
}
return 0;
}
