Author: Praveen Dhinwa
Tester: Istvan Nagy
Editorialist: Misha Chorniy
Difficulty:
Cakewalk
Pre-Requisites:
None
Problem Statement
There are C cats and D dogs, and L legs touching the ground. Some of the cats can ride on dogs, but every dog can’t have more than 2 cats on his back. Can this be true?
Explanation
Let’s make some obvious observations:
- Every cat has 4 legs.
- Every dog has 4 legs.
If we have X cats and Y dogs staying on the ground then, the number of legs in the barn equal 4 * (X+Y). Therefore if L not divisible by 4, the answer is “no”.
Subtask 1 and 2
Constraints are chosen in such way that solutions with complexity O(D+C) per test case can pass.
Iterate over possible numbers of the cats on Chef’s dogs back G(G must be in the range between 0 and 2*D due to the condition of the dog and 2 cats on his back, and not more than the total number of cats). Hence in the barn 4*(C-G+D) legs on the ground, if 4*(C-G+D) = L for some G, then the answer is “yes”, and “no” otherwise.
Subtask 3
There is possible to solve problem with O(1) solution per test case.
Let G number of the cats on the backs of the dogs, 0 ≤ G ≤ min(C,2*D)
4*(C-G)+4*D = L , there are C-G cats on the ground, therefore total number of legs = 4*(C-G)+4*D
C-G+D = L/4 , divide both parts of the equation by 4
C+D-L/4 = G , add G-L/4 to both parts of the equation
if G will be in the range between 0 and 2*D answer is “yes”, and “no” otherwise.
The overall time complexity of this approach is O(1) per test case.
Solution:
Setter’s solution can be found here
Tester’s solution can be found here
Please feel free to post comments if anything is not clear to you.