CHEFWARS - Editorial

PROBLEM LINK:

Division 1
Division 2
Video Editorial

Author: Aryan Agarwala
Tester: Данило Мочернюк
Editorialist: Ritesh Gupta

DIFFICULTY:

CakeWalk

PREREQUISITES:

NONE

PROBLEM:

You are given two numbers A and B. You can perform several operations on it. In one operation:

  1. Update A = A - B
  2. Update B = B/2

If at any point of time A becomes non-positive before B then print 1 else 0.

QUICK EXPLANATION:

Since B becomes half in one operation, that implies in log B operations, it will become zero. Hence, we can optimally iterate over the value of B to find the answer.

EXPLANATION:

We just need to implement the process. Iterate over the number of operations and at each operation, first, A is decreased by B and then B becomes half of the current value.

  • A = A - B
  • B = B/2

Keep on iterating until B is greater than or equal to the A. So, if after this A becomes zero then answer is 1 else answer is 0.

TIME COMPLEXITY:

TIME: O(Log N)
SPACE: O(1)

SOLUTIONS:

Setter's Solution
Tester's Solution
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second    
#define sz(a) ((int)(a.size()))
using namespace std;
const int mod = 1000 * 1000 * 1000 + 7;
 
int main() 
{
    int T;
    cin >> T;
    while(T--)
    {
        int p , h;
        cin >> h >> p;
        int ans = 0;
        while(p != 0)
        {
            ans += p;
            p >>= 1;
        }
        cout << (ans >= h) << endl;
    }
}
Editorialist's Solution
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;

    while(t--)
    {
        int a,b;
        cin >> a >> b;

        while(a > 0 && b > 0)
        {
            a -= b;
            b /= 2;
        }

        cout << (a <= 0 ? 1 : 0) << endl;
    }
}

Video Editorial

if any one wants video editorail in hindi

1 Like

My AC code was literally: print(h<=2*p)

1 Like

lol! This should fail for p = 7, h = 12.
Expected answer is chef loses.

Check out Screencast Tutorial for this problem: https://www.youtube.com/watch?v=Rd_tkTg1wuk&list=PLz-fHCc6WaNIrJbPDdoWUscRqMZPEiqzQ

ys u are right but according to my logic condition is just be reversed if(h>p*2)
cout<<“0”;
else
cout<<“1”<<endl;

This would still fail for the above mentioned test case, no? We expect answer to be 1. you would give 0.