PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given an array A.
In one operation, you can choose an index i and replace A_i with \left\lfloor \frac{A_i}{2} \right\rfloor.
Find the minimum number of operations needed to make all the array elements equal.
EXPLANATION:
There are various approaches possible, but they generally all use the same key observation: division by 2 reduces a number very quickly, so there aren’t too many distinct values you can reach from a starting point before you reach 0 and never change again.
In particular, starting from X, after at most \log_2 X divisions by 2 (rounded up), you will reach the value 1, and then another division will take you to 0.
Here’s one way to use this fact.
Consider the value of A_1.
There aren’t too many distinct values it can take via repeated divisions by 2 - at most \log_2 A_1 of them, which is bounded by about 30 or so.
Suppose we fix the number of times we perform the operation on A_1.
Let Y denote the current value of A_1, after several operations.
For every index i \gt 1, we now have to make the value at this index equal Y since we want everything to be equal eventually.
This can be done as follows:
- If A_i \lt Y, it’s impossible, since division by 2 can only reduce the value of A_i.
- If A_i =Y, nothing more needs to be done at this index.
- If A_i \gt Y, we’re forced to perform a division at this index to reduce its value.
So, for each i \gt 1, simply repeatedly perform operations on that index till the value becomes \le Y.
If the value is exactly equal to Y, great - otherwise it’s impossible to make this index contain value Y.
If all indices are able to reach Y, update the answer with the total number of operations performed.
The time complexity of this approach is \mathcal{O}(N \cdot \log^2 \max(A)) because:
- There are \log A_1 choices of Y, those being all values reachable by dividing A_1 repeatedly.
- For each such choice, we perform several divisions on all the other elements.
- For each other index, we perform at most \log A_i divisions till its value becomes \le Y.
- So, the complexity of a single check is \mathcal{O}(N\log \max(A)).
This is easily fast enough.
For an alternate solution, consider the following:
- Sort the array A in non-decreasing order, so that A_1 \le A_2\le\ldots\le A_N.
- If A_1 = A_N, all elements are already equal so we’re done.
- Otherwise, A_1 \lt A_N.
- The operation cannot increase elements; so in any solution we must perform the operation on A_N to decrease it.
- Now repeat the process till all elements become equal, i.e. first sort the array and then operate on the largest element if needed.
This simple greedy algorithm is optimal because we always perform an operation that’s necessary.
As for the time complexity,
- Each operation takes \mathcal{O}(N\log N) time to perform because we’re sorting the array (though it’s possible to do in \mathcal{O}(N) time as well since only one element really moves.)
- Thus, the complexity is \mathcal{O}(N\log N \cdot \text{ans}) where \text{ans} denotes the answer.
- \text{ans} is bounded by \mathcal{O}(N\log\max(A)) since each A_i can change at most \log_2 A_i times.
- So, the overall complexity is \mathcal{O}(N^2 \log N \log\max(A)).
This is worse, complexity-wise, than the previous algorithm.
However, it’s conceptually simpler to reason about (and to implement!), and since N \le 100 is fast enough anyway.
TIME COMPLEXITY:
\mathcal{O}(N\log^2 \max(A)) or \mathcal{O}(N^2 \log N \log\max(A)) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans = 10**9
base = 0
while a[0] >= 1:
cost = base
for i in range(1, n):
x = a[i]
while x > a[0]:
x //= 2
cost += 1
if x != a[0]: cost = 10**9
ans = min(ans, cost)
print(ans)
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
void Solve()
{
int n; cin >> n;
vector <int> a(n);
for (auto &x : a) cin >> x;
int ans = 0;
while (true){
sort(a.begin(), a.end());
if (a[0] == a[n - 1]){
break;
}
a[n - 1] /= 2;
ans++;
}
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}