PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
Maps
PROBLEM:
On an array A, you can perform the following operation:
- Choose an integer x, delete two occurrences of x from A, and append one occurrence of 2x.
Define f(A) to be the minimum possible length of A after performing this operation.
Given A, find the value of f([A_1, A_2, \ldots, A_i]) for every prefix of A.
EXPLANATION:
Let’s try to compute the value of f(A) for a fixed array A.
Since each operation involves taking two copies of x and converting them to one copy of 2x, each operation reduces the length of A by 1, meaning we want to perform as many operations as possible.
It’s not hard to see that it’s optimal to just perform operations in ascending order of x.
That is, convert as many 1's to 2's as possible, then 2's to 4's, then 3's to 6's, and so on.
Why?
Suppose we operate on x, and then on y, where x \gt y.
Since x \gt y, the operation on x cannot have changed the frequency of y.
So, it’s safe to swap their order, and perform the operation on y (which is smaller) first.
Repeatedly applying this swap operation to an optimal sequence of operations shows that we can perform moves in ascending order while remaining optimal.
For convenience, we represent the set of elements we have in terms of their frequency: so \text{freq}[x] denotes the number of copies of x, and our operation is to reduce \text{freq}[x] by 2 and increase \text{freq}[2x] by 1.
In the end, \text{freq}[x] \leq 1 will hold for every x, and the answer is the number of ones in \text{freq}.
Suppose we’ve computed f(A[1\ldots i]) in terms of frequencies. Let’s see how this changes when one copy of A_{i+1} is added in.
- First, clearly there’s no change in what happens with values \lt A_{i+1}.
- Next \text{freq}[A_{i+1}] itself increases by 1.
- If it’s now 2, we can perform one operation with it and instead obtain an occurrence of 2A_{i+1}.
- Otherwise, there will be no further changes; since nothing beyond A_{i+1} will be affected either - so we can stop immediately.
- If we do perform an operation and obtain a copy of 2A_{i+1}, note that the next interesting value is 2A_{i+1} itself: everything strictly between A_{i+1} and 2A_{i+1} won’t see any changes.
So, we can then perform the same check with 2A_{i+1}, then 4A_{i+1}, 8A_{i+1}, \ldots till no more operations are possible.
This brute force process is, in fact, quite fast!
In particular, you need to perform at most \mathcal{O}(\log N) operations each time.
This is because, to obtain a single copy of x\cdot 2^k starting from x (which is k doubling steps starting from x), you require 2^k copies of x.
We can have at most N copies of a number, so we can’t go beyond \log_2 N steps.
So, the brute force described above will terminate within \mathcal{O}(\log N) steps for each index.
If the \text{freq} values are stored in a map, they can be changed in \mathcal{O}(\log N) time too, so the overall complexity is \mathcal{O}(N\log^2 N), fast enough.
There are other approaches too.
For instance, one way is to also allow for “reversing” the process, meaning we can break a copy of 2x into two copies of x (which doesn’t make the answer any worse).
Repeatedly perform this reverse operation till every number in the array is odd.
Then, for an odd number that appears k times, simulating the forward process should show you that the number of distinct values you end up with is exactly \text{popcount}(k), that is, the number of bits set in k.
TIME COMPLEXITY:
\mathcal{O}(N\log^2 N) or \mathcal{O}(N\log (\max A)) per testcase.
CODE:
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;
map <int, array<int, 55>> mp;
auto f = [&](int x){
auto v = mp[x];
int ans = 0;
int curr = 0;
for (int i = 0; i < 55; i++){
curr += v[i];
if (curr & 1){
ans++;
curr--;
}
curr /= 2;
}
return ans;
};
int ans = 0;
for (auto x : a){
int y = x;
int v = 1;
while (y % 2 == 0) y /= 2, v++;
ans -= f(y);
mp[y][v] += 1;
ans += f(y);
cout << ans << " ";
}
cout << "\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;
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
void solve(int test_case){
ll n; cin >> n;
vector<ll> a(n+5);
rep1(i,n) cin >> a[i];
map<ll,ll> mp;
ll ans = 0;
rep1(i,n){
ll x = a[i];
while(true){
if(mp[x] == 1){
mp[x] = 0;
x <<= 1;
ans--;
}
else{
mp[x]++;
ans++;
break;
}
}
cout << ans << " ";
}
cout << endl;
}
int main()
{
fastio;
int t = 1;
cin >> t;
rep1(i, t) {
solve(i);
}
return 0;
}
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
ans, cur = [], 0
val = {}
for x in a:
ct = 1
while x%2 == 0:
x //= 2
ct *= 2
if x not in val: val[x] = 0
cur -= bin(val[x]).count('1')
val[x] += ct
cur += bin(val[x]).count('1')
ans.append(cur)
print(*ans)