Problem Summary#

You are given an array $a$ of length $n$ with $0 \leq a_i \leq 10^5$. Before the game starts, Alice may increment any single element any number of times, each increment counted as one step. Then Alice and Bob alternate turns, with Bob moving first. On Bob’s turn he picks two positions and swaps them (possibly the same position). On Alice’s turn: if $a_1$ is even, she picks the largest $j$ such that $a_i \bmod 2 = 0$ for all $i \leq j$, then divides every $a_i$ ($i \le j$) by $2$ — this counts as one step; otherwise she decreases $a_1$ by $1$, again one step. When any value becomes zero it is removed from the array. Bob wants to maximise Alice’s total number of steps, Alice wants to minimise it. Output the minimum number of steps Alice performs.

Approach#

First consider the version without the pre-game +1 operations. If there is any odd number, Alice cannot perform the global halving move, so the answer is $\sum_{i=1}^{n} \bigl(\text{popcnt}(a_i) + \lfloor \log_2 a_i \rfloor + 1 - 1\bigr) = \sum_{i=1}^{n} \text{popcnt}(a_i) + |a_i| - 1$, where $|a_i|$ denotes the bit-length of $a_i$. If every number is even, Alice can keep halving globally until some value becomes odd, and after that the cost above still applies.

This suggests fixing the number of global halvings we perform as $j$, then computing the minimum number of +1 operations required to make every $a_i$ a multiple of $2^j$. A naive choice is $\text{step} = 2^j - (a_i \bmod 2^j)$, but that isn’t always optimal — sometimes a few extra +1s can eliminate more $1$-bits from the binary representation. So we need to search a small window around $a_i$.

How wide should the window be? Notice that $\text{popcnt}(a_i) + |a_i| - 1$ is bounded by $17 + 17 - 1 = 33$ for $a_i \le 10^5$. That means increasing $a_i$ by more than $33$ is never worthwhile — the extra +1s would already exceed the entire remaining cost. So for every element we only need to try the $33$ values immediately above $a_i$, keep those divisible by $2^j$, and pick the minimum. Total complexity: $O(n \log^2)$.

Code#

1
#include<bits/stdc++.h>
2
using namespace std;
3

4
#define endl '\n'
5
#define fi first
6
#define se second
7
#define ll long long
8
#define lowbit(x) (x&(-x))
9
const int mod=998244353;
10
const double eps=1e-12;
11
const int inf=0x3f3f3f3f;
12
const ll INF=0x3f3f3f3f3f3f3f3f;
13
#define popcnt __builtin_popcount
14
int dcmp(double x){if(fabs(x)<eps)return 0;return x>0?1:-1;}
15

16
#define int ll
17

18
// mt19937 rnd(random_device{}());
19
// uniform_int_distribution<int>dist(0,1000000);
20

21
int a[100005];
22
int b[100005];
23
int jie[21];
24

25
int len(int x)
26
{
27
    int cnt=0;
28
    while(x)
29
    {
30
        cnt++;
31
        x>>=1;
32
    }
33
    return cnt;
34
}
35

36
void solve()
37
{
38
    int n;
39
    cin>>n;
40
    int ans=inf;
41
    for(int i=1;i<=n;i++)
42
    {
43
        cin>>a[i];
44
    }
45
    for(int j=0;j<=20;j++)
46
    {
47
        int res=j;
48
        for(int i=1;i<=n;i++)
49
        {
50
            int tmp=inf;
51
            for(int k=a[i];k<=a[i]+33;k++)
52
            {
53
                if(k%jie[j]==0)
54
                {
55
                    b[i]=k/jie[j];
56
                    tmp=min(tmp,k-a[i]+popcnt(b[i])+len(b[i])-1);
57
                }
58
            }
59
            b[i]=a[i]+jie[j]-a[i]%jie[j];
60
            tmp=min(tmp,b[i]-a[i]+popcnt(b[i]/jie[j])+len(b[i]/jie[j])-1);
61
            res+=tmp;
62
        }
63
        ans=min(ans,res);
64
    }
65
    cout<<ans<<'\n';
66
}
67

68
/*
69
 110
70
1000
71
  10
72
 100
73
   1
74
*/
75

76
#undef int
77

78
int main()
79
{
80
    ios::sync_with_stdio(false);cin.tie(nullptr);
81
    // cout<<fixed<<setprecision(10);
82

83
    jie[0]=1;
84
    for(int i=1;i<=20;i++)
85
    {
86
        jie[i]=jie[i-1]*2;
87
    }
88

89
    int _;cin>>_;while(_--)
90
    {
91
        solve();
92
    }
93
    return 0;
94
}