PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: yash_daga
Tester: wasd2401
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Binary search, sorting
PROBLEM:
The h-index of an array A is the maximum integer H such that at least H elements of A are \geq H.
You’re given A and K. In one move, you can choose indices i and j such that A_i is a multiple of K and A_j is not, then divide A_i by K and multiply A_j by K.
Find the maximum possible h-index of A.
EXPLANATION:
It’s fairly obvious that the answer is binary-searchable: if we can get H values \geq H, surely we can get H-1 values \geq H-1.
So, the meat of the task is really just figuring out a check function: for a fixed H, is there a way to perform operations such that at least H elements end up \geq H?
For this, let’s define a couple of quantities.
- Let \text{have}_i denote the number of powers of K in A_i.
That is, the number of times you can divide A_i by K till you reach something not divisible by K. - Let \text{base}_i denote the number remaining after dividing A_i by K repeatedly.
- Let \text{req}_i denote the minimum power of K required, such that \text{base}_i \cdot K^{\text{req}_i} \geq H.
That is, the minimum power of K required for A_i to be one of the elements \geq H.
All of these arrays can be computed directly, by dividing/multiplying by K as long as necessary.
Since K\geq 2 and everything is \leq 10^9, this is pretty fast: at most 30 divisions and multiplications are needed.
Now, observe that:
- If \text{req}_i \gt \text{have}_i, and \text{have}_i \gt 0, there no way to ever make A_i \geq H$.
- This is because A_i is already a multiple of K, so we cannot give it more powers; yet it needs more powers to reach H.
- If \text{have}_i = 0 and \text{req}_i \gt 1, again it’s impossible to make A_i \geq H.
- The reason is the same: after we give A_i one power of K, it’s not possible to give it any more.
- If \text{have}_i = 0 and \text{req}_i = 1, it’s possible to make A_i \geq H (if we want to) by giving it one power of K.
- If \text{have}_i \geq \text{req}_i, it’s possible to keep A_i \geq H if we wish to (note that it starts out \geq H, so we only need to ensure that we don’t divide out K too many times).
Let’s call an index i valid if it’s possible to make A_i \geq H (i.e, it satisfies the third or fourth point above).
We are now able to ‘distribute’ up to \sum_i \text{have}_i powers of K.
At least H valid indices should have their \text{req}_i requirements satisfied - and intuitively, it makes sense to choose the H of them with smallest \text{req}_i values.
This indeed works.
That is, choose the smallest H \text{req}_i values among valid indices, and check if you have enough powers of K to satisfy them.
A proof can be found below.
Note that implementing this isn’t too hard.
- H can be binary searched for.
- The \text{have}, \text{req} arrays can be computed with bruteforce, in \mathcal{O}(N\log\max A) time.
- Isolating valid indices and sorting them to find the smallest H \text{req}_i values can be done in \mathcal{O}(N\log N) (or even \mathcal{O}(N) by utilizing the fact that the numbers are small).
The overall complexity is \mathcal{O}(N\log N \cdot (\log N + \log\max A)).
Proof of correctness
Consider two valid indices i and j such that \text{req}_i \lt \text{req}_j, but after making moves, A_i \lt H and A_j \geq H.
Note that since the inequality is strict, \text{req}_j \gt 0, meaning A_j has several powers of K with it.
Let’s look at a couple of cases.
- If \text{have}_i = 0 and \text{req}_i = 1, A_i is not a multiple of K.
Simply perform one move transferring a power of K from A_j to A_i, and A_i \geq H will be true.
The total number of values \geq H at least remains the same, so this is not worse. - If \text{have}_i \gt 0, then the only reason for A_i \lt H is that too many powers were removed from A_i.
Importantly, these powers can’t have gone to A_j, which was already a multiple of K.
So, every power removed from A_i when it has exactly \text{req}_i powers left, could instead have been removed from A_j - and A_j will always have enough powers of K for this since \text{req}_j \gt \text{req}_i.
So, this again makes A_i \geq H in the end, while A_j may or may not change its state; either way it isn’t worse off.
So, there always exists a solution where we choose the smallest H \text{req}_i values.
TIME COMPLEXITY:
\mathcal{O}(N\log N \cdot (\log N + \log\max A)) per testcase.
CODE:
Author's code (C++)
//clear adj and visited vector declared globally after each test case
//check for long long overflow
//Mod wale question mein last mein if dalo ie. Ans<0 then ans+=mod;
//Incase of close mle change language to c++17 or c++14
//Check ans for n=1
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#define int long long
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);cout.precision(dbl::max_digits10);
#define pb push_back
#define mod 998244353ll
#define lld long double
#define mii map<int, int>
#define pii pair<int, int>
#define ll long long
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define rep(i,x,y) for(int i=x; i<y; i++)
#define fill(a,b) memset(a, b, sizeof(a))
#define vi vector<int>
#define setbits(x) __builtin_popcountll(x)
#define print2d(dp,n,m) for(int i=0;i<=n;i++){for(int j=0;j<=m;j++)cout<<dp[i][j]<<" ";cout<<"\n";}
typedef std::numeric_limits< double > dbl;
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
//member functions :
//1. order_of_key(k) : number of elements strictly lesser than k
//2. find_by_order(k) : k-th element in the set
const long long N=300005, INF=2000000000000000000;
const int inf=2e9 + 5;
lld pi=3.1415926535897932;
int lcm(int a, int b)
{
int g=__gcd(a, b);
return a/g*b;
}
int power(int a, int b, int p)
{
if(a==0)
return 0;
int res=1;
a%=p;
while(b>0)
{
if(b&1)
res=(1ll*res*a)%p;
b>>=1;
a=(1ll*a*a)%p;
}
return res;
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int getRand(int l, int r)
{
uniform_int_distribution<int> uid(l, r);
return uid(rng);
}
int32_t main()
{
IOS;
int t;
cin>>t;
while(t--)
{
int n, k, tot_k=0;
cin>>n>>k;
vector <pair <pii, int> > a(n);
rep(i,0,n)
{
cin>>a[i].ss;
int z=0, temp=a[i].ss;
while(temp%k==0 && k>1)
{
temp/=k;
z++;
}
a[i].ff={temp, z};
tot_k+=z;
}
sort(all(a));
reverse(all(a));
int lb=1, ub=n, ans=0;
while(lb<=ub)
{
int md=(lb+ub)/2;
int ex=0, cur=0, lef=tot_k;
for(auto p:a)
{
int req=0, temp=p.ff.ff;
while(temp<md)
{
req++;
temp*=k;
}
if(req<=lef && (req<=p.ff.ss || (req==p.ff.ss+1 && p.ff.ss==0)))
{
lef-=req;
cur++;
}
}
if(cur>=md)
{
ans=md;
lb=md+1;
}
else
ub=md-1;
}
cout<<ans<<"\n";
}
}
Tester's code (C++)
/*
* * * *** * *****
* * * * * * * *
* * * *** ***** *
* * * * * * * * *
* * * * * * **
*
* *
*****
* *
***** * *
_* *_
| * * * * | ***
|_* _ *_| * *
* * *
***** * **
* * ***
{===* *===}
* IS * ***
* IT * * *
* RATED?* *
* * * **
* * ***
* *
***** * *
* *
* *
* *
***
*/
// 2 Years Tribute to Competitive Programming
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define osl tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ll long long
#define ld long double
#define forl(i, a, b) for(ll i = a; i < b; i++)
#define rofl(i, a, b) for(ll i = a; i > b; i--)
#define fors(i, a, b, c) for(ll i = a; i < b; i += c)
#define fora(x, v) for(auto x : v)
#define vl vector<ll>
#define vb vector<bool>
#define pub push_back
#define pob pop_back
#define fbo find_by_order
#define ook order_of_key
#define yesno(x) cout << ((x) ? "YES" : "NO")
#define all(v) v.begin(), v.end()
const ll N = 2e5 + 4;
const ll mod = 1e9 + 7;
// const ll mod = 998244353;
ll modinverse(ll a) {
ll m = mod, y = 0, x = 1;
while (a > 1) {
ll q = a / m;
ll t = m;
m = a % m;
a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0) x += mod;
return x;
}
ll gcd(ll a, ll b) {
if (b == 0)
return a;
return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
return (a / gcd(a, b)) * b;
}
bool poweroftwo(ll n) {
return !(n & (n - 1));
}
ll power(ll a, ll b, ll md = mod) {
ll product = 1;
a %= md;
while (b) {
if (b & 1) product = (product * a) % md;
a = (a * a) % md;
b /= 2;
}
return product % md;
}
void panipuri() {
ll n, m = 0, k = -1, c = 0, sum = 0, q = 0, ans = 0, p = 1;
string s;
bool ch = true;
cin >> n>>k;
vl a(n);
vl a1,a2;
forl(i, 0, n) {
cin >> a[i];
if(a[i]%k) a1.pub(a[i]);
else a2.pub(a[i]);
}
sort(all(a1));
reverse(all(a1));
ll l=0,r=n+1;
while(l+1<r){
m=(l+r)/2;
// cout<<m<<' ';
vl b1;
sum=0;
fora(x,a2){
c=0;
q=0;
ll y=x;
while(x%k==0){
sum++;
q++;
x/=k;
if(x>=m) c++;
}
if(y>=m) b1.pub(q-c);
}
sort(all(b1));
if(b1.size()>=m){
l=m;
continue;
}
p=0;
ch=0;
ll sz=b1.size();
forl(i,0,sz) p+=b1[i];
ll k1=0;
c=0;
q=0;
while(k1<m-sz){
if(k1==a1.size()) break;
ll x=a1[k1];
if(x<m){
x*=k;
c++;
}
if(x>=m) q++;
k1++;
}
if(c<=sum-p && sz+q==m) ch=1;
rofl(i,sz-1,-1){
if(k1==a1.size()) break;
p-=b1[i];
ll x=a1[k1];
if(x<m){
x*=k;
c++;
}
if(x>=m) q++;
k1++;
if(c<=sum-p && q+i==m) ch=1;
}
if(ch) l=m;
else r=m;
}
cout<<l;
return;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int laddu = 1;
cin >> laddu;
forl(i, 1, laddu + 1) {
// cout << "Case #" << i << ": ";
panipuri();
cout << '\n';
}
}
Editorialist's code (Python)
for _ in range(int(input())):
n, k = map(int, input().split())
a = list(map(int, input().split()))
have = [0]*n
for i in range(n):
while a[i]%k == 0:
a[i] //= k
have[i] += 1
tot = sum(have)
lo, hi = 1, n
while lo < hi:
mid = (lo + hi + 1)//2
req = [0]*n
for i in range(n):
x = a[i]
while x < mid:
x *= k
req[i] += 1
ind = list(range(n))
ind.sort(key = lambda x: req[x])
rem, done = tot, 0
for i in ind:
if req[i] > rem: break
if req[i] > have[i]+1: continue
if req[i] == have[i]+1 and have[i] > 0: continue
rem -= req[i]
done += 1
if done >= mid: lo = mid
else: hi = mid-1
print(lo)
