Simple Math, Brute Force, Meet in the Middle
You are given N numbers in a list A.
Rearrange the numbers such that for each contiguous sequence of K numbers, the sum of the numbers in the sequence is divisible by M.
Let us first see what properties the re-arranged list will have.
The re-arranged list will be such that
i = 1 to K
A[i] ) % M = 0, and
A[i] % M = A[i-K] % M, for all
i > K
Using the above inferences, we can visualise N slots as divided into several buckets of size K, and one bucket of size less than K. This visualisation for N = 34, K = 6 can be seen as follows
1 2 3 4 5 6 1 # # # # # # 2 # # # # # # 3 # # # # # # 4 # # # # # # 5 # # # # # # 6 # # # #
As shown above, there are 5 buckets (rows) of size 6, and one bucket (row 6) of size 4.
We have to fill values in the buckets such that
- The modulo M of all the values in a column, in the above visualisation, is equal.
- The sum of values in each bucket, modulo M, should be 0.
If both the above constraints are satisfied, we will have a perfect re-arrangement of the original array.
For example, consider the following Sample Case
8 2 3
2 5 0 9 1 9 9 4
This can be re-arranged as
5 2 9 9 4 9 1 0
As you can see, the values in a column, modulo 2 are equal, and the sum of values in the first row 5+2+9 = 16 is equal to 0, modulo 2.
Another way to interpret the above visualisation is
- You need to fill N % K columns with p+1 values which are equal modulo M
- You need to fill K - (N % K) columns with p values which are equal modulo M
Where p = floor(N/K)
From now on, we assume that we have stored each number, modulo M. Once the grid above is filled with the modulo of the numbers, we can extract the original numbers. We will no longer mention that the values are being stored modulo M, it is implicitly assumed.
Let us construct a dictionary D of values. D[i] is equal to the count of times i appears in the list.
Let us take a bucket B of K values. Filling a slot in B is equivalent to saying that we have selected a value to appear in some column, for the first p rows.
When we are done selecting K values for B, we would have filled the
p*K grid above (first p rows) with values such that
- All rows in a column have the same value
- Each row has a sum that is equal to 0, modulo M
Don’t worry about the remaining values, we will come to that later
Now, consider each i in D.
- i will occupy at the least L = ceil(D[i] / (p+1)) columns.
- i will occupy at most R = floor(D[i] / p) columns.
- Fill L slots in B, with i
- Thus we have used
L*pinstances of i
R-Linstances of i, to a list C
Now, C represents candidate values that can be used to fill more columns of the grid; or, the candidates to fill more slots in B. This is because if we use a value from C, we know that we have at least p instances of it unused, which can be used to fill another column of the grid
Let the number of slots filled in B till now be equal to K’, and the sum of the values that are filled in B be equal to S, modulo M.
We have to choose
K-K' values from C such that, the sum of the values is equal to (M-S), modulo M.
This can be done through brute force. Wonder, Why?
|C| ≤ K/2
for all i in D C has I = floor(D[i] / p) - ceil(D[i] / (p+1)) instances of i floor(D[i] / p) <= D[i] / p ceil(D[i] / (p+1)) >= D[i] / (p+1) floor(D[i] / p) - ceil(D[i] / (p+1)) <= D[i] / (p*(p+1))
We know that the sum of D[i]'s is N
|C| <= N / (p*(p+1))
p = floor(N / K)
N <= (p+1)*K
N/(p+1) <= K
N/(p*(p+1)) <= K/p
|C| <= K/p
We know from the problem statement that p will be at least 2.
The Brute Force
This is a classical subset sum like brute force.
The naive approach will fail for sure, since K/2 can be as much as 35. But here meet-in-the-middle comes to rescue!
- Split C into two lists of almost equal size. Say, X and Y.
- Find the sum (modulo M) of each subset in X and store in SX the corresponding count of values that could reach it.
- There might be multiple counts that reach the same sum, hence use a bitset to store the count.
- Iterate through all subsets of Y
- Let s be the sum (modulo M) of values in the current subset of Y
- Let c be the count of values in the current subset of Y
- if M-S-s exists in SX AND it could be reached with count K-K’-c
- WE HAVE FOUND AN ANSWER!
The Remaining Values?
The items that remain, must be used in the last row of our grid. Hence, we must fix the first such columns with the same value, and the remaining we can fill anyway we please. If this is possible, then we have an answer, otherwise, we never had an answer.
Can be found here
Can be found here