You are given NN strings S1,S2,…,SNS1,S2,…,SN. Consider a complete undirected graph with NN vertices (numbered 11 through NN), in which the weight of an edge between vertices uu and vv is equal to the length of the longest common substring of SuSu and SvSv. Find the maximum possible weight of a spanning tree of this graph.

Chef and Deque solution codechef

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 NN elements A1,A2,,ANA1,A2,…,AN, which supported performing operations of the following type: Chef and Deque solution codechef

  • Choose an integer KK, which must be a power of 22 (possibly 20=120=1). Additionally, each particular value of KK can only be chosen if it has not been chosen in any previous operation.
  • Delete KK elements from the end of the deque.
  • Then, you may also decide to delete KK 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 MM 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 MM, 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 Chef and Deque solution codechef

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains two space-separated integers NN and MM.
  • The second line contains NN space-separated integers A1,A2,,ANA1,A2,…,AN.

Output Format

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

Constraints Chef and Deque solution codechef

  • 1T1001≤T≤100
  • 1N21051≤N≤2⋅105
  • 1M1091≤M≤109
  • 1Ai1091≤Ai≤109 for each valid ii
  • the sum of NN over all test cases does not exceed 31053⋅105


Subtask #1 (15 points):

  • N2,000N≤2,000
  • the sum of NN over all test cases does not exceed 5,0005,000

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

Subtask #3 (65 points): original constraints

Sample Input 1  Chef and Deque solution codechef 

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 Chef and Deque solution codechef

Example case 1: The only possible way is to keep the first two elements 88 and 66, since 8+6=148+6=14, which is divisible by 77. Hence we must delete 22 elements from the end in 11 operation.

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

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

Leave a Comment