ALIEN1 - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice

Contest

Author: Prajit Benerjee

Tester: Md Shahid

Editorialist: Md Shahid

DIFFICULTY:

Easy

PREREQUISITES:

Binary search

PROBLEM:

There are 10^{18} alien building numbered 1 through 10^{18} i.e, A_i = i. Power of the ith building is P_i,

P_i = \lceil{\frac{2A_i+M}{K}}\rceil , where M and K are positive integer constants.
You are given power X of human, it means that human can break those buildings whose power is less than equal to X and human can only win if they break more than 10^9 alien buildings.

QUICK EXPLANATION:

You need to first find the maximum number of building human can break using binary search. Take low = 1 and high = 10^{18} in binary search. if number of maximum building human can break is greater than 10^9 then print “YES” otherwise print “NO” with maximum number of building human have broken.

EXPLANATION:

It is a divide and conquer problem. As you can see number of building is numbered 1 to 10^{18}, so you can not find maximum number of building by iterating. If you carefully observe that building are of sorted order numbered from 1 to 10^{18}. As we already know binary search uses sorted order array but here we don’t need to use array of length 10^{18}, instead we can just use mid = \frac{low+high}{2}.Then check if power at point mid is less and equal X if it is less and equal X, then check for larger number by updating low=mid+1 because we want to find the maxium A_i . If power is greater than X, it means the maximum number lies below mid, then check for lower number by updating high=mid-1. Repeat this process untill high \geq low. When the loop exit, you get your maximum number of building human can break.

Algorithm :

power(mid, M, K, X) { 
     p = ceil((2 * mid + M) / 2); 
     if p <= X 
          return true;
     else 
          return false;
}

binarySearch(low, high, M, K, X) {
     ans = 0
     while(high >= low) {
         mid = (low + high) / 2; 
         if power(mid, M, K, X) == true
             low = mid + 1 
             ans = mid 
         else 
             high = mid - 1
    }
     if ans > 1000000000 
         print "YES" 
     else 
         print "NO" 
     print ans 
}

SOLUTIONS:

Author's Solution 
#include<bits/stdc++.h>
#define int long long int
#define ld long double
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
bool f(ld point,ld m,ld k,int x){
    int ans;
    ans=ceil((2*point+m)/k);
    if(ans<=x) return true;
    else return false;
}
 
signed main(){
    fast
    int t;
    cin>>t;
    while(t--) {
        int n,i,x;
        ld m,k;
        cin>>m>>k>>x;
        int lo=1,hi=(int)1e18,mid,ans=0;
        while(hi>=lo){
            mid=(hi+lo)/2;
            if(f(mid,m,k,x)==true){
                lo=mid+1;
                ans=mid;
            }
            else{
                hi=mid-1;
            }
        }
        if(ans>(int)1e9){
            cout<<"YES"<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
        cout<<ans<<endl;         
    }
    return 0;
}
Test's and Editorialist's Solution 
def power(mid, M, K, X):
	p = (2*mid+M)//K
	if (2*mid + M)%K!=0:
		p += 1
	if p <=X:
		return True 
	else:
		return False 

def binary_search(low, high, M, K, X):
	ans = 0 
	while(high >= low):
		mid = (low+high)//2 
		if power(mid, M, K, X):
			low = mid + 1
			ans = mid 
		else:
			high = mid - 1
	if ans > pow(10, 9):
		print("YES")
	else:
		print("NO")
	print(ans)

for _ in range(int(input())):
	M, K, X = map(int, input().split())
	low, high = 1, pow(10, 18)
	binary_search(low, high,M, K, X)

If you have better approach, please do not hesitate to share with us, we will love your approach. All the suggestions are welcome. :slight_smile:

4 Likes