PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: Utkarsh Gupta
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra
DIFFICULTY:
2759
PREREQUISITES:
None
PROBLEM:
Chef has an array A of length N.
In one operation, Chef can do the following:
- Select any non-empty subsequence S = \{S_1, S_2, S_3, \ldots S_k\} of A (where the S_i are the indices of the array representing the chosen subsequence)
- Then, choose one index from this subsequence, say S_j
- Finally, either add A_{S_j} to every element of the subsequence, or subtract A_{S_j} from every element of the subsequence. Formally, Chef must choose to do exactly one of:
- Set A_{S_i} = A_{S_i} + A_{S_j} for every 1 \leq i \leq k, or
- Set A_{S_i} = A_{S_i} - A_{S_j} for every 1 \leq i \leq k
Chef’s task is to make all the elements of the array equal within 100 operations.
Note that after each operation, -10^{18} \leq A_i \leq 10^{18} should hold for every element of the array.
See output details for instructions regarding the output format.
EXPLANATION:
We can observe that none of the numbers in the array is greater than 2^{30} so what we can do is to go through ranges from 2^{29}-2^{30}, to 2^{28}-2^{29} and so on and for each range say 2^{i-1}-2^i, select all the numbers that fall in this range as our set S and choose the minimum number, say X among them and subtract all the numbers in S by X. In each such step we reduce all the selected numbers to atleast half of its value so we can reduce all the numbers to 0, in less than 100 steps.
In order to further optimise this, instead of going through the ranges in order, in each step we can select the maximum element, say M of the array and select the range as (\frac{M}{2},M).
TIME COMPLEXITY:
O(Nlog(M)), where M = max(A_i), 1 \leq i \leq N
SOLUTION:
Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution