Zeroing array elements using a specific set of rules?
Given n numbers, you can do the following operation any number of times: select any subset of numbers, none of which is 0. Decrease the numbers in the subset by 1 and increase the numbers not in the subset by K.
Is it possible to perform operations so that all numbers, except for one of them, become 0?
Input: The first line contains the number of test cases T. 2 * T lines, 2 for each case. The first line of the test case contains the numbers n and K. The next line contains n numbers, a_1 ... a_n.
Output: Output T lines corresponding to each test case. For a test case, output "YES" if there is a sequence of operations as described, and "NO" otherwise.
Input example:
3
2 1
10 10
3 2
1 2 2
3 2
1 2 3
Output example:
YES
YES
NO
Limitations:
1 <= T <= 1000
2 <= n <= 100
1 <= K <= 10
0 <= a_i <= 1000
I have a solution taken with the following algorithm ---
a[i] is value in ith cell
n[i] is number of times it is selected in subset
T is total number of times the operation is done
=> a[i] - n[i] + (T - n[i])*K = 0 for all except 1
=> a[i]= n[i] (K+1) -TK
=> a[i] = (K+1)(n[i]-T) + T
Therefore, the remainder should be the same for all a [i] except 1 (which becomes zero) and T if divisible by K + 1. My doubt is that this condition is necessary, but how sufficient is it?
source to share
STEP 1
Imagine a movement consisting of:
- Select the subset A consisting of all numbers, where a [i]> = K + 1
- Choose a subset consisting of the whole set K times
The numbers in the subset A will be decremented K + 1 times, and the numbers outside the set A will remain unchanged (increased by K and then decreased K times).
Repeat this movement until all numbers are less than K + 1.
This step will modify the numbers to become their deduction modulo K + 1.
STEP 2
Now suppose all numbers are the same (except 1).
Now we can choose a subset consisting of the entire set (except the odd one).
This decreases all numbers by 1 (except the odd one). Repeat this selection until we decrease to 0.
Conclusion
So, if all numbers (except one) have the same remainder mod K + 1, we can use step 1 to bring them all down to one level, and then step 2 to reduce the overall level to 0.
source to share