You are not logged in. Please login at www.codechef.com to post your questions!

×

HMAPPY2 - EDITORIAL

0
1

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. :)

This question is marked "community wiki".

asked 13 Feb, 23:56

taran_1407's gravatar image

6★taran_1407
4.0k31104
accept rate: 22%

edited 16 Feb, 16:50

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 17 Feb, 11:08

javegzav's gravatar image

2★javegzav
21
accept rate: 0%

edited 18 Feb, 10:26

This Question is Having Weak Test Cases.

See this Discussion FEB19 HMAPPY2 Wrong Logic Gives AC (100/100) !!

link

answered 18 Feb, 17:14

mj_13's gravatar image

3★mj_13
153
accept rate: 0%

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

link

answered 18 Feb, 20:43

iamosama's gravatar image

1★iamosama
1
accept rate: 0%

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?

link

answered 23 Feb, 19:20

hax0r's gravatar image

2★hax0r
1
accept rate: 0%

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.

link

answered 06 Mar, 23:23

george_py's gravatar image

0★george_py
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,688
×1,220
×321
×189
×11

question asked: 13 Feb, 23:56

question was seen: 1,471 times

last updated: 15 Mar, 19:41