CHEFWARS - Editorial

editorial
, , , , ,
1

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

2

if any one wants video editorail in hindi

1 Like
3

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

1 Like
4
5

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

6

Check out Screencast Tutorial for this problem: Codechef - CHEFWARS | Contest Screencast/Tutorial | August Challenge 2020 - YouTube

7

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

8

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

9

#include

using namespace std;

int main() {

int t;

cin>>t;

while(t--){

    int d,c;

    cin>>d>>c;

    while(d>0 && c>0){

        d-=c;

        c/=2;

    }

    if(c==0)   cout<<0<<endl;

    else cout<<1<<endl;

   

}

return 0;

}

WHY IT IS SAYING WRONG ANSWER

10

/* 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
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
for(int i=1;i<=t;i++){
int h=sc.nextInt();
int p=sc.nextInt();
while(h!=0&&p!=0&&p!=h){
if(h>p&&p!=h){
h=h-p;
p=p/2;
}
else if(p>h&&p!=h){
h=p-h;
p=p/2;
}

	    }
	   
	    if(p>0){
	        System.out.println("1");
	        
	    }
	    else if(p==h){
	     System.out.println("1");   
	    }
	    else{
	       System.out.println("0");
	    }
	}
}

}
why this code is wrong answer?