REARRAN - Editorial

editorial
, , , ,
1

PROBLEM LINK

Practice
Contest

DIFFICULTY

HARD

PREREQUISITES

Simple Math, Brute Force, Meet in the Middle

PROBLEM

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.

EXPLANATION

A Visualisation

Let us first see what properties the re-arranged list will have.

The re-arranged list will be such that
( ∑i = 1 to KA[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)

An Approach

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 :slight_smile:

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*p instances of i
  • Keep R-L instances 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

Hence, |C| <= N / (p*(p+1))

We know, p = floor(N / K)

N <= (p+1)*K
N/(p+1) <= K
N/(p*(p+1)) <= K/p
Hence, |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.

SETTERS SOLUTION

Can be found here

TESTERS SOLUTION

Can be found here

1 Like
2

Please tell me what goes wrong in this logic.

  1. Create buckets mod m. If the number of buckets > k, there is no solution.

  2. Now check if the buckets can be split into (n%k) columns of size p+1 and (k-(n%k)) columns of size p. p is the same variable as defined in the editorial. If it is not possible, there is no solution. This can be checked using a greedy approach.

  3. Now we have the desired matrix, in which each column has same remainder mod m. The only thing that needs to be checked is if sum of a row of that matrix is divisible by m. If yes, then we have a solution else we don’t.

I will be glad, if you could tell me where i am going wrong or the test case(s) for which this code (http://www.codechef.com/viewsolution/1490909) fails.

Thanks.

3

The editorial also follows the same logic. It tries to split the items into two buckets.

It is the splitting which is non-trivial.

There are several elements that can be split in multiple ways among p+1 and p.

4

Yep. The splitting part is definitely non-trivial. I tried using DP - something like: after considering the first i different buckets mod M, can we obtain x columns of size p+1 and y columns of size p and with the sum (mod M) of the remainders of all the x+y columns equal to r ? (i.e. a tuple (i,x,y,r))

It’s a kind of knapsack-like DP, in which for every bucket mod M we need to consider all the possible ways of splitting it into columns of size p+1 and p (e.g. let’s say we have 24 values in one of the buckets mod M and p=3 ; we can write 24 = 3 * (p+1 = 4) + 4 * (p = 3) or 24 = 0 * (p+1 = 4) + 8 * (p=3) ; the first case uses 3 columns of size p+1 and 4 of size p, while the second case uses 0 columns of size p+1 and 8 columns of size p ; the correct case to use in the solution depends on the sizes of the other buckets mod M as well).

Initially we can obtain (0,0,0,0) and, in the end, we should be able to obtain (number of (buckets mod M), number of columns of size (p + 1), number of columns of size p, 0).

I was hoping that there wouldn’t be too many valid tuples reachable, but I was wrong, I guess (I get TLE).

2 Likes
5

I will be glad, if you could tell me where i am going wrong or the test case(s) for which this code (http://www.codechef.com/viewsolution/1490909) fails .

Well, I have made this request many times earlier, making it once again here, “Making the judge data public after the contest will definitely help learning of the contestant”

Thanks.

1 Like
6

Hey guys!

Gennady pointed out mistakes in the proof for |C| <= K/2.

I have made some changes to fix it. Hope it is fine now :slight_smile:

7

@blackBird

Refer to this for a discussion on why Codechef doesn’t.
TL;DR Codechef believes that the challenge in solving a problem (even while practicing) should not be artificial. Not revealing test cases, that challenge remains real.

( DISCLAIMER: Although I personally - and professionally - know the Chef, I do not work for Codechef. My word is not the Chef’s word )

8

That said, your solution fails in the following smallest case
(note that this is the smallest case depicting the complexity of this problem)

12 3 5
0 0 0 0 0 0 1 1 1 1 1 1

The answer should be
0 0 1 1 1 0 0 1 1 1 0 0