HMAPPY2 - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Himanshu Mishra
Tester: Alexey Zayakin and Yash Chandnani
Editorialist: Taranpreet Singh

DIFFICULTY:

Cakewalk.

PREREQUISITES:

Greatest Common Factor and Least Common Multiple.

PROBLEM:

Given four numbers N, A, B and K. There are N problems labelled from 1 to N. Appy solves each problem whose label is divisible by A but not B, while Chef solves all problems whose label is divisible by B but not by A. Check if Appy and Chef together solve at least K problems or not.

QUICK EXPLANATION

  • Number of problems solved by Appy is N/A - N/lcm(A, B).
  • Number of problems solved by Chef is N/B - N/lcm(A,B).
  • Total number of problems solved become N/A+N/B-2*N/lcm(A,B). We can simply check if it is at least K or not.

EXPLANATION

Number of multiples of x in range [1, N] is given by \lfloor N/x \rfloor.

Appy solves all problems whose label is divisible by A, which are N/A problems. But this also includes problems whose labels are divisible by both A and B. We know, all such problems are the multiples of lcm(A, B). So, we can just subtract it from N/A to get N/A - N/lcm(A, B) which is the number of problems solved by Appy.

Chef solves all problems whose label is divisible by B, which are N/B problems. But this also includes problems whose labels are divisible by both A and B. We know, all such problems are the multiples of lcm(A, B). So, we can just subtract it from N/B to get N/B - N/lcm(A, B) which is the number of problems solved by Chef.

The total number of problems solved by Chef and Appy is N/A+N/B-2*N/lcm(A, B). We can simply use an if statement to check if this exceeds K or not.

As an exercise, solve the problem, where problems are not labeled from 1 to N, but from L to R which is given in the problem.

Finding LCM of two numbers is just the product of two numbers divided by its Greatest Common Factor, which can be easily found using Euclid’s GCD method.

Time Complexity

Time complexity is O(1) per test case.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution
Tester’s solution
Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

4 Likes

the links to the solutions are not working, please fix it and where is L and R in the problem statement?

shiit that LCM thing did not even come in my mind ._.

2 Likes

Please correct me if I’m wrong but the Euclid’s GCD algorithm doesn’t have O(1) time complexity, then how is the time complexity O(1) per test case?

3 Likes

Working on a different approach, not passing submit, but not sure why yet. Anyway, my method is to do a N mod A and a N mod B, setting results to boolean variables. I then do an XOR on the two booleans and increment win counter if xor is (true=1). Only increment win counter if 1 of the two is dividable.

Hi,
With all due respect, the following code is AC.
https://www.codechef.com/viewsolution/23681716
But it should not.
Try it for the below test case
60 6 9 13
Expected output is “Lose” (checked with the author and tester’s solution) but this would print “Win” still its AC.
Please check.

Agreed! but can not open the discussion with the link.

Please find it here, FEB19 HMAPPY2 Wrong Logic Gives AC (100/100)!

Thanks for your reply
I’ve updated the link

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int gcd (ll a, ll b)
{
if (a == 0)
return b;
return gcd(b % a, a);
}

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

for (ll i = 0; i < t; i++)
{
    ll n, a, b, k;
    cin >> n >> a >> b >> k;

    pair <ll, pair <ll, ll> > p;

    p.first = n / a;
    p.second.first = n / b;
    p.second.second = (a * b) / gcd(a, b);

    ll result = p.first + p.second.first - 2 *  n / p.second.second;

    string ans = result >= k ? "Win" : "Lose";
    cout << ans << endl;

}

}

What’s wrong in my code??

Why does this only give partial AC?

from math import gcd

def lcm(a,b):
    return (a*b)//gcd(a,b)

for i in range(int(input())):
    n,a,b,k = [int(x) for x in input().split()]
    m = int((n/a) + (n/b) -2*(n/lcm(a,b)))
    if m>= k:
        print("Win")
    else:
        print("Lose")

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t,n,a,b,k;
int count=0;
cin>>t;
while(t)
{
t–;
cin>>n>>a>>b>>k;
for(int i=1;i<=n;++i)
{
if ((i%a==0 && i%b!=0) || (i%a!=0 && i%b==0)) count++;
}

    if(count>=k) cout<<"Win\n";
    else cout<<"Lose\n";
}
return 0;

}

Why is this not working

Cause its wrong, see?

Your line

    m = int((n/a) + (n/b) -2*(n/lcm(a,b)))

can accumulate fractional parts in the divisions that throw the answer off when you take the integer part.

Better to use the integer division operator

    m = (n//a) + (n//b) - 2*(n//lcm(a,b))

although this is equivalent for this problem:

    m = int(n/a) + int(n/b) - 2*int(n/lcm(a,b)))

Why partial AC in my code CodeChef: Practical coding for everyone

bro 36 being the lcm of 6,9. appy(6) will do 9 question and chef(9) will do 5 questions which sums up to 14>13. so it is a win case.

@itsmeetesh

For the test case : 60 6 9 13
By the given logic answer will be Lose
Here is My Code -
import java.util.*;

class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while (t-- > 0) {
		    long n = sc.nextLong();
		    int a = sc.nextInt();
		    int b = sc.nextInt();
		    long k = sc.nextLong();
		    long appyCount = n/a, chefCount = n/b;
		    long subtract = n / lcm(a, b);
		    if (chefCount + appyCount - 2 * subtract >= k) {
		        System.out.println("Win");
		    } else {
		        System.out.println("Lose");
		    }
		} 
	}
	
	static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }
     
    static int lcm(int a, int b)
    {
        return (a / gcd(a, b)) * b;
    }
}

I got the logic but my doubt is why did I get wrong answer when I did (2n/lcm) but the correct answer with 2(n/l)?

Consider the test input:

1                  
5 2 3 2
1 Like