Chef and Deque Problem Code: CHEFDQESubmit

Read problem statements in Mandarin, Russian, and Vietnamese as well.

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}, \dots, 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?

Input Format

The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $M$ .
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$ .

Output Format

For each test case, print a single line containing one integer --- the minimum number of required operations or $- 1$ if it is impossible to achieve the goal.

Constraints

$1 \leq T \leq 100$
$1 \leq N \leq 2 \cdot 10^{5}$
$1 \leq M \leq 10^{9}$
$1 \leq A_{i} \leq 10^{9}$ for each valid $i$
the sum of $N$ over all test cases does not exceed $3 \cdot 10^{5}$

Subtasks

Subtask #1 (15 points):

$N \leq 2, 000$
the sum of $N$ over all test cases does not exceed $5, 000$

Subtask #2 (20 points): if it is possible to achieve the goal, at most $4$ operations are needed

Subtask #3 (65 points): original constraints

Sample Input 1

4
4 7
8 6 4 6 
7 13
10 2 3 8 1 10 4 
7 1
7 3 7 2 9 8 10 
3 11
3 4 8

Sample Output 1

Explanation

Example case 1: The only possible way is to keep the first two elements $8$ and $6$ , since $8 + 6 = 14$ , which is divisible by $7$ . Hence we must delete $2$ elements from the end in $1$ operation.

Example case 3: The sum of all elements is already divisible by $1$ .

Example case 4: It is impossible to achieve the goal.

Search This Blog

Code with Kianae

Chef and Deque Problem Code: CHEFDQE Codechef Solutions