WARRIORS - Editorial

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

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 :stuck_out_tongue: ) . Suggestions are welcomed as always had been. :slight_smile:

4 Likes

Logic I worked out:
I’m maintaining an ArrayList for powers, in each query minimum power will be searched for the target to battle with, it’s then removed from array list updating the power of fighter, this is iterated until unless either list is empty or remaining powers are greater than fighter’s current power.

But i am getting WA Verdict…even when the code is giving correct output for sample test case…why?

Below is my JAVA code:

/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
    	static class FastScanner{
        BufferedReader br ;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        String next(){
            while(st==null || !st.hasMoreElements()){
                try {
                    st = new StringTokenizer(br.readLine()) ;
                } catch (IOException ex) {
                    System.out.println("error") ;
                }
            }
            
            return st.nextToken() ;
        }
        
        int nextInt(){
            return Integer.parseInt(next()) ;
        }
        
        Long nextLong() {
            return Long.parseLong(next());
        }
    }
    
    
    //main program
	public static void main (String[] args) throws java.lang.Exception
	{
       FastScanner s = new FastScanner();

        int t = s.nextInt();

        while (t-- > 0) {
            int n = s.nextInt();
            int q = s.nextInt();

            ArrayList<Long> pwr = new ArrayList<Long>();
            while (n-- > 0) {
                pwr.add(s.nextLong());
            }
            ArrayList<Long> army;
            while (q-- > 0) {
                army = (ArrayList<Long>) pwr.clone();
                long x = s.nextLong();
                long y; //here minimum power of the list army will be stored
                int kills = 0;
                while (!army.isEmpty()) {
                    y = Collections.min(army);
                    if (x > y) {
                        x = 2 * (x - y);
                        army.remove(y);
                        ++kills;
                    } else {
                        army.clear();
                        break;
                    }
                }

                System.out.println(kills);

            }
        }
	}
}

I know there is some learning hidden in this issue as I’m a newbie…kindly help me grasp that…

I’ve also asked it here->https://discuss.codechef.com/t/warriors-problem-why-getting-wa/35473

Why doesn’t a simple binary search for the number of people killed in a query for a given x work :thinking: @taran_1407
My submission
We know that the optimal ordering of warriors to fight is non-decreasing, so for a given x if we cannot defeat the first mid warriors then surely we cannot defeat the first mid+1 warriors ( so we set hi=mid-1 ) ,also if we can defeat the first mid warriors we know the answer will be surely greater than mid ( so we can set lo=mid). This means we can use binary search ! (with minimum number of kills possible lo=0 and maximum hi=n).

ll lo=0,hi=n;
while(hi-lo>1)
{
    ll mid=(hi+lo)/2;
    if(check(mid,x)) lo=mid;
    else             hi=mid-1;
}

if(check(hi,x)) cout<<hi<<endl;
else            cout<<lo<<endl;

Implementaion Note in My submission : If isOverflow() returns True then 2*cur will be greater than 10^{18} so as max(P_i)=10^9 ,max(N)=10^5 , max(N*P_i)=10^{14} so no matter what we will always be able to defeat remaining warriors.

https://www.codechef.com/viewsolution/26071168
Can anyone tell why I am getting runtime error please

can somebody explain the setter solution ,i am not getting what he is doing please

1 Like

After struggling for few days, finally solved today

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

Not using binary search and it is simple to understand

You are absolutely right. The thing is, if in eval, you are considering warriors from 1 to mid, then its better to directly loop since it saves time.

@taran_1407 can you please explain setter’s solution??

Setter basically does the reverse of what i did. I tried to calculate the maximum number of warriors that can be killed with power x, he calculated the minimum power needed to beat first i warriors using same relation i explained, for each i and then ran binary search (upper_bound).

In his solution, rem denotes our current power after fighting i-1 warriors in first i-1 iterations and st denote the initial power before fighting these warriors. Whenever we have rem \leq A_i meaning current power is insufficient to beat ith warrior, we find t, the minimum increase in initial power needed so that current power is sufficient to beat warrior i.

1 Like

Could someone plz provide some typical test cases where a code with binary search implementation may fail. Thanks in advance :~) . Here is the link if u want to look into my code:-
https://www.codechef.com/viewsolution/25995534

code given by you is not running if we use cout and cin instead of printf() and scanf(). why is it so?
can someone think of some reason?

getting accepted(TLE)

If you are getting TLE, it is because printf and scanf are faster than cout and cin. My approach is simpler, not optimal. If you want to use cin/cout, you need to follow binary search approach or find a faster input / output mechanism (I am not sure how to make cin/cout faster).

If you are getting WA, I am not sure why.

i have heard that this particular code snippet:
"
ios_base::sync_with_stdio(false);
cin.tie(NULL);
"
in c++ increases the input output speed by a slight degree. Not sure about how true this is but I always include this code snippet in main().