# CHEFDQE - Editorial

Author: Pratik Kumar
Tester: Anay Karnik
Editorialist: Mohan Abhyas

EASY-MEDIUM

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;
}

2 Likes

This problem is accepting simple brute force O(n^2) solutions, test cases are pretty weak

10 Likes

I came up with a solution of O(sqrt(N*logN) * N). First we calculate number of distinct prefix values modulo M. If the count is more than (sqrt(N/logN)), we do a brute force on all pair of prefix indices giving the same prefix sum modulo M. Otherwise, we still solve the problem in a different way for each distinct prefix sum modulo M. That can be done by building a minimum length mask dp, to store minimum length submask for each mask that has the corresponding prefix modulo value which can be done in somewhat similar way to that of SOS dp. For each mask we constraint on dp length we have calculated and whether that submask removed from the end gives the same modulo value as in the current iteration of modulo value.

4 Likes

Can some please tell me the reason why 3^log(n) (approx. 2*1e8 operations for each test case) is not giving TLE. Solution with this complexity is pretty much easy to think of but I haven’t implemented it because it was supposed to give TLE. I think test cases are very much weak for this problem.

5 Likes

my solution is giving TLE on two testcase
can anybody help?
https://www.codechef.com/viewsolution/50319959

I don’t think test cases are weak (based on the following submissions).

I can’t understand python. Sorry for that but lemongrab also mentioned that problem is accepting brute force solutions. So, I think tests are weak and even if they are not then how can one pass the solution with complexity given in editorial?

Test cases are fine. The time limit for the problem is 1.5s. It is pretty much sufficient for a solution with time complexity 3^{\log_2N}.

1 Like

From the Problem Statement:

1 Like

Why my solution failing for starting cases?
https://www.codechef.com/viewsolution/50298500

Exactly. I came up with this solution pretty early but didn’t implement it beacause it should give TLE.

I understand the time complexity is the upper bound. But can you explain what will be the worst case for this problem? I think it won’t be 3^(log n), as it will TLE.

No, they are actually weak.

This shouldn’t work unless there is some specific reason why your threshold works other than just using it to fix the time complexity, since you might be taking into account cases where you’re erasing at least N elements in the array.

For instance, suppose your block size is 3 (i.e., you revert to the SOS dp where the size is at least 3). Then consider the following test case:

1
9 11
2 1 1 8 4 1 6 6 5

A submission here (if you increase the size of dp from n to 2n or something to avoid segfault) gives WA on this test case, and I believe your solution is somewhat along these lines.

The solution you mentioned most probably fails because it doesn’t account for the cases when dp value is more than equal to n - i - 1. That’s why I said to build smallest length dp, the boolean dp doesn’t work if you want to check for this condition.

Great problem
Is there a name to this type of traversal?

Can someone pls explain little more about the traversal

This can be done efficiently in O(3 ^ (log2(N))) using this kind of iteration.

How is it O(3 ^ (log2(N))) ?

source - cp-algorithms

3 Likes