# PROBLEM LINK:

**Setter:** Erfan Alimohammadi

**Tester:** Teja Vardhan Reddy

**Editorialist:** Taranpreet Singh

# DIFFICULTY:

Medium

# PREREQUISITES:

Greedy, Pointers, Precision. (Binary Search).

# PROBLEM:

Given powers of N warriors where P_i denote the power of the ith warrior, you can fight the warriors in any order. You have to answer Q queries wherein each query, your current power is given.

If your current power is x and you fight with a warrior of power y, the following happens.

- if x > y, you kill the warrior and your power changes to 2*(x-y)
- else you die.

For each query, find the maximum number of warriors you can kill.

# EXPLANATION

First of all, letâ€™s try to find the optimal ordering of warriors to fight, which maximize the number of wins.

Initially assume N = 2 and powers of warriors are P_1 and P_2 with P_1 < P_2 and our current power is X.

Assuming we fight P_1 first, To win first fight, we need X > P_1 and to win second fight, we need 2*(X-P_1) > P_2 which is same as X > P_1+P_2/2.

In other case, to win first fight, we need X > P_2 and to win second fight, we need 2*(X-P_2) > P_1 which is same as X > P_2+P_1/2.

For first fight, since P_1 < P_2, it is beneficial to fight with P_1 first.

For second fight, letâ€™s compare P_1+P_2/2 and P_2+P_1/2. Subtracting P_1/2+P_2/2 from both, we get P_1/2 and P_2/2 respectively. Since P_1 < P_2, it is beneficial to fight P_1 first.

If we extend this to N > 2, we can conclude that it is always beneficial to fight warriors with lower powers first.

Second thing, if we lose the ith fight, we cannot move to the (i+1)th fight, so, if B is the minimum power to win first i fights and C is minimum power to win first i+1 fights, then B \leq C holds.

Now, letâ€™s assume A_1, A_2 \ldots A_{N-1} denotes the powers of warriors arranged in non-decreasing order.

Following results arise.

To win the first fight, we need X - A_1 > 0. The current power changes to 2*(X-A_1).

To win the second fight, we need 2*(X-A_1) > A_2 which is 2*X-2*A_1-A_2 > 0. X changes to 2*(2*(X-A_1) - A_2) = 4*X-4*A_1-2*A_2.

We can observe, that to win ith fight, following inequality arise.

2^{i-1}*X - 2^{i-1}*A_1 - 2^{i-2}*A_2 - 2^{i-3}*A_3 \ldots -2^0*A_i > 0 which is 2^{i-1}*X - \sum_{j = 1}^{i}2^{i-j}*A_j > 0.

Letâ€™s assume that we are given initial power as X+h where h \geq 0, then this inequality becomes 2^{i-1}*X + 2^{i-1}*h - \sum_{j = 1}^{i}2^{i-j}*A_j > 0.

This is it. We are armed with enough information to form a nice solution.

Letâ€™s sort all queries in non-decreasing order of current powers. Now, Letâ€™s assume we can win x fights if our initial power was X. For current query, we have current power X+h for some h \geq 0. From our previous fights, we already have 2^{x-1}*X - \sum_{j = 1}^{x}2^{x-j}*A_j and we know, this is greater than 0. Now, If we change initial power from X to X+h, we just add 2^{x-1}*h to the left-hand expression, and we can see, this too is greater than 0.

We know we have already won previous x fights and also know our current power, so we can start from fight numbered x+1 and calculating y such that we can win first y fights with our initial power X+h.

This is it. We can see that once we win the fight, it is not considered again, so winning iterations are N in the worst case. We also do not lose more than Q times. This means that our inner loop is never executed more than N+Q times, making this solution work in time.

**About Precision issues and Overflow**

Some solutions tried dividing the inequality for the ith fight by 2^{i-1} which is not wrong and actually gives a nice binary search solution, but there are a lot of precision issues which double alone cannot handle.

Secondly, in the method explained in editorial, if at any point our power exceeds 2*10^9, we can simply set it to 2*10^9 since maximum power any warrior can have is 10^9 and after fighting a warrior, our power gets restored to 2*(2*10^9-10^9) = 2*10^9. Take care while calculating 2^{x-1}*h since 2^{x-1} itself may overflow.

If still facing issues, refer the implementations below.

# TIME COMPLEXITY

Time complexity is O(N*logN+Q*logQ) per test case due to sorting. The main algorithm takes time O(N+Q) which is dominated by sortings.

# SOLUTIONS:

## Setter's Solution

```
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const ll N = (ll)2e9;
int a[maxn];
void solve(){
int n, q;
cin >> n >> q;
for (int i = 0; i < n; i++)
cin >> a[i];
sort(a, a + n);
vector<ll> v;
ll st = 0, rem = 0;
for (int i = 0; i < n; i++){
if (rem <= a[i]){
ll diff = a[i] - rem + 1;
if (i >= 32){
st ++;
rem = N;
}
else{
ll t = (1ll * diff + (1 << i) - 1) / (1 << i);
st += t;
rem += t * (1ll << i);
}
}
rem = min(N, 2ll * (rem - a[i]));
v.push_back(st);
}
for (int i = 0; i < q; i++){
ll x;
cin >> x;
cout << upper_bound(v.begin(), v.end(), x) - v.begin() << '\n';
}
}
int main(){
ios_base::sync_with_stdio (false);
cin.tie(0), cout.tie(0);
int tc;
cin >> tc;
while (tc --){
solve();
memset(a, 0, sizeof a);
}
}
```

## Tester's Solution

```
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
#define int ll
int p[123456];
int iinf;
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n,q;
cin>>n>>q;
int i;
iinf=inf;
iinf*=100;
vii vec;
vii::iterator it;
int val,haha;
rep(i,n){
cin>>p[i];
}
sort(p,p+n);
int sofar,left,mult;
sofar=0;
left=0;
mult=2;
rep(i,n){
if(left>iinf){
left=iinf;
}
if(mult>iinf){
mult=iinf;
}
if(left>p[i]){
left-=p[i];
left*=2;
}
else{
val=2*(p[i]-left);
haha=val/mult;
haha++;
vec.pb(mp(sofar,i));
sofar+=haha;
left=mult*haha-val;
}
mult*=2;
}
vec.pb(mp(sofar,n));
rep(i,q){
cin>>val;
it=lower_bound(all(vec),mp(val,iinf));
it--;
cout<<it->ss<<'\n';
}
}
return 0;
}
```

## Editorialist's Solution (Commented)

```
import java.util.*;
import java.io.*;
import java.text.*;
class WARRIORS{
//SOLUTION BEGIN
void pre() throws Exception{}
void solve(int TC) throws Exception{
int n = ni(), q = ni();
long[] p = new long[n];
for(int i = 0; i< n; i++)p[i] = nl();
Arrays.sort(p);
long[][] qq = new long[q][];
int[] ans = new int[q];
for(int i = 0; i< q; i++)qq[i] = new long[]{i, nl()};
//Queries sorted in non-decreasing order of initial power
Arrays.sort(qq, (long[] l1, long[] l2) -> Long.compare(l1[1], l2[1]));
//prev -> initial power in previous query
//rem -> Current power
//curAns -> Number of fights won in previous query
long prev = 0;long rem = 0;
int curAns = 0;
long mx = (long)2e9;
for(int i = 0; i< q; i++){
if(qq[i][1]-prev > 0){
//checking if 2^x > mx) since 2^32 > mx
if(curAns > 32)rem = mx;
else rem += (qq[i][1]-prev)*(1l<<curAns); //increasing power by h*2^(x-1)
prev = qq[i][1];
while(curAns < n){
if(rem > p[curAns]){
rem = Math.min(mx, 2*(rem-p[curAns]));
curAns++;
}else break;
}
}
ans[(int)qq[i][0]] = curAns;
}
for(int i:ans)pn(i);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
DecimalFormat df = new DecimalFormat("0.00000000000");
static boolean multipleTC = true;
static double eps = 1e-8;
FastReader in;PrintWriter out;
void run() throws Exception{
in = new FastReader();
out = new PrintWriter(System.out);
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
new WARRIORS().run();
}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
```

Feel free to share your approach, if you want to. (even if its same ) . Suggestions are welcomed as always had been.