Author: Praveen Dhinwa
Tester: Istvan Nagy
Editorialist: Misha Chorniy
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?
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.
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.
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.