Limits 1s, 512 MB

The birthday party is near to an end now. You, Sohel bhai and all his others friends are playing a game called “Dot Hunter”.

There will be some dots on a one dimensional axis. Let’s define, distance between two dots X, Y as D(X, Y) and any 4 dot’s position A, B, C and D. You will be given a number K. You have to choose and take 4 different dots from position A, B, C, D in a way such that it satisfies the following:

  1. Distance between A and D will be maximum and it won’t be greater than K

  2. Distance between B and C will be the minimum and A < B < C < D

  3. (D(A, B) + D(C, D)) % D(B, C) = 0

If a group of 4 dots are found with above conditions you have to take them and then no other dots between [A, D] can be taken further. You have to find out the minimum number of remaining dots after all the valid groups are taken.


Input starts with an integer T (T ≤ 10), denoting the number of test cases. Each case starts with a line contains an integer N (1 ≤ N ≤ 105) and K (1 ≤ K ≤ 1017), means the number of dots and range. The next line will contain N integers separated by spaces which denote the position of dots. Positions will be between [1, 1017]. It is assured that dots will be given in ascending order and no two dots will lie on same position.


For each case, print the case number and minimum total number of remaining dots after all valid group dots are taken.



12 30
1 3 6 9 12 15 17 24 28 33 35 39

7 10
1 2 3 4 5 6 7
Case 1: 8
Case 2: 3

In the first case, inside range 30 there is a group (A, B, C, D) = (1, 15, 17, 28) but D(1,15) + D(17,28) is not divisible by D(15,17). Thus, this group can’t be taken. Another group can be (3,15,17,33) which is valid according to the necessary conditions. As this group will be taken, dots from position 6, 9, 12, 24 and 28 can’t be taken further. The total number of remaining dots are 8.


Login to submit.


43% Solution Ratio
sgtlaughEarliest, Aug '16
nusuBotFastest, 0.1s
bqi343Lightest, 5.8 MB
bqi343Shortest, 1195B
Toph uses cookies. By continuing you agree to our Cookie Policy.