PROBLEM LINK:
Contest - Division 3
Contest - Division 2
Contest - Division 1
DIFFICULTY:
SIMPLE
PROBLEM:
Given an array A of N integers. Determine the minimum number of operations to make every element of A divisible by 3.
In each operation, you must select two distinct indices i,j and increase/decrease A_i/A_j by 1, respectively.
EXPLANATION:
Claim: It is impossible to make all elements of A divisible by 3 if the sum of elements of A is not divisible by 3.
Proof
Making every element divisible by 3 would imply that the sum of all elements in the final array is divisible by 3.
It is clear that the sum of elements of A is unchanged when performing an operation. Thus, if the sum of elements is not divisible by 3, no sequence of operations will generate the required solution.
When the sum is divisible by 3, I claim that it is always possible to make every element divisible by 3. The rest of the solution is constructive.
Let X represent all elements A_i where A_i\equiv 1\pmod 3. Similarly, let $Y$represent all elements A_i where A_i\equiv 2\pmod 3. Our goal is then to make all elements in X and Y divisible by 3.
Step 1: While both X and Y are not empty, select one element from each set and decrement/increment it, respectively. It is clear that both the selected elements become divisible by 3 after this move.
If after this step, one set is still non-empty, proceed to step 2. It is guaranteed that the number of elements in the non-empty set is divisible by 3 (why?).
Without loss of generality, let us consider set X as the non-empty set (a similar technique can be used when set Y is non-empty).
Step 2: While X is non-empty, select three elements from it - call them a,b and c. Increment a and decrement b by 1. Then, increment a and decrement c by 1. It is easy to see that the operations make the three elements divisible by 3.
At the end of the two steps, all elements of A will be divisible by 3.
To summarise, let x and y represent the number of elements in A that leave a remainder of 1 and 2 when divided by 3, respectively. Then, the number of operations done is equal to:
- \min(x,y) in Step 1, and
- 2*(\frac{x-\min(x,y)}{3}+\frac{y-\min(x,y)}{3}) in Step 2.
The final answer is simply the sum of the two values!
TIME COMPLEXITY:
per test case.
SOLUTIONS:
Editorialist’s solution can be found here
Experimental: For evaluation purposes, please rate the editorial (1 being poor and 5 excellent)
- 1
- 2
- 3
- 4
- 5
0 voters