# KIND - Editorial

Author: yash_daga
Tester: wasd2401
Editorialist: iceknight1093

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;
}

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
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)


Can we multiply K to the same index multiple times? After the first time we multiply K to Ai, doesnt Ai become a multiple of K rendering it an invalid choice for further multiplication? Sorry if I am missing something.

Why does this greedy fail??? Can somebody come up with a counter example?

https://www.codechef.com/viewsolution/1053238328

can you please explain for following example i read editorial but i don’t get it for following example. which is being shown while debugging.

1
5 2
3 3 4 4 4

Expected o/p = 4
my o/p = 3

1 Like

By using 2 powers from one 4 we can make two 3’s into 6 so final array would be [1,4,4,6,6].

1 Like

after doing this operation first time it is no longer ‘not divisible by k’. so you can’t select any index as j multiple times(consecutively).

1 Like
#include <bits/stdc++.h>
using namespace std;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define int long long int
#define pb push_back
#define vl vector<int>
#define endl "\n"
#define mod 1000000007
bool cmp(pair<int,int>&a,pair<int,int>&b){
return a.first-a.second>b.first-b.second;
}
void solve(){
int n,k;
cin>>n>>k;
vl vec(n);
for(int i=0;i<n;i++) cin>>vec[i];
int low=2;
int high=n;
int mid;
int ans=-1;
while(high-low>=0){
mid=(low+high)/2;
int good=0;
vector<pair<int,int>>vecp;
for(int i=0;i<n;i++){
if(vec[i]>=mid){
if(vec[i]%k!=0) continue;
int op1=0;
int op2=0;
int carrier=vec[i];
while(carrier%k==0 &&carrier/k>=mid){
carrier/=k;
op1++;
}
carrier=vec[i];
while(carrier%k==0){
carrier/=k;
op2++;
}
vecp.pb({op2,op1});
}
else{
int carrier=vec[i];
while(carrier%k==0){
carrier/=k;
good++;
}
}
}
int sum=0;
int maxop=0;
for(auto ele:vecp) sum+=ele.second;
for(int i=0;i<n;i++){
if(vec[i]<mid){
if(vec[i]%k!=0){
int carrier=vec[i];
if(carrier*k>=mid){
maxop++;
}
}
}
}
sort(vecp.begin(),vecp.end(),cmp);
// vec[i]>=mid and not mutliple of k
int total=0;
for(int i=0;i<n;i++){
if(vec[i]>=mid&&vec[i]%k!=0){
total++;
}
}
total+=min(maxop,good);
maxop-=min(maxop,good);
total+=min(maxop,sum);
maxop-=min(maxop,sum);
int cnt=1;
int sumnow=0;
for(auto ele:vecp){
int var=total-cnt;
sumnow+=ele.first-ele.second;
var+=min(maxop,sumnow);
cnt++;
total=max(total,var);
}
if(total>=mid){
ans=mid;
low=mid+1;
}
else{
high=mid-1;
}
}
if(ans==-1) ans=1;
cout<<ans<<endl;
return;

}

signed main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t--){
solve();
}
}


Why my code is failing can anyone give any test case?

Its correct actually : 3 3 4 4 4 → I pick (3,4) which is a valid move and change array to 3 6 2 4 4 → now again pick (3,2) → yes you can pick “2” because it is divisible by 2; in shot a number can be divided by K again and again as long as it possible to do so :- 6 6 1 4 4. Only be careful that once you multiply a number by 2; then you can only decrease it

Found my error.
Thanks community for help

Yes we can’t multiply K further because after first multiplication the number will become a multiple of K

Another test case:

1
5 2
2 3 4 7 9


exp: 4

#include<bits/stdc++.h>
using namespace std;
#define ll long long

bool poss(ll arr[], ll h, ll n, ll k){
ll copy[n];
for(int i = 0;i<n;i++)
copy[i] = arr[i];
ll count = 0, hcount = 0;
for(int i = 0;i<n;i++){
if(arr[i] >= h){
while(arr[i] % k == 0 && arr[i] / k >= h){
arr[i] /= k;
count++;
}
}
else{
while(arr[i] % k == 0){
arr[i] /= k;
count++;
}
}
}
sort(arr, arr + n);
reverse(arr, arr + n);
for(int i = 0;i<n;i++){
if(arr[i] < h && count){
arr[i] *= k;
count--;
}
if(arr[i] >= h)
hcount++;
}

for(int i = 0;i<n;i++)
arr[i] = copy[i];

return hcount >= h;
}

void fun(){
ll n, k;
cin>>n>>k;
ll arr[n];
for(int i = 0;i<n;i++) cin>>arr[i];

ll l = 0, r = n, ans;
while(l <= r){
ll mid = (l + r)/2;
if(poss(arr, mid, n, k)){
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
cout<<ans<<"\n";

}
int main() {