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. 
