Cats and Dogs(CATSDOGS): Solution with Hints


Hint 1:

Click to view

We know that cats and dogs have four legs. So whatever be the number of legs must be a multiple of 4, otherwise the configuration is invalid. This is the first and trivial check for invalidity.

Hint 2:

Click to view

Now let’s come to the other check for invalidity. What is the minimum number of legs possible given the number of dogs and cats?

Hint 3:

Click to view

Well since dogs cannot ride on anyone and each dog has 4 legs therefore (4*number of dogs) legs is the minimum. What about the cats? To make the number of legs minimum we will try to make as many cats ride on a dog as possible. And each dog can carry at most two cats.

Hint 4:

Click to view

So let’s put 2 cats on every dog. So we are putting a total of (2*D) cats. And subtracting this from the number of cats C will give us the number of cats remaining who could not be put on a dog. These cats’ legs needs to be added. But it may so happen that 2*D may exceed the number of cats. In that case C-(2*D) will come out to be negative. In that case no need to add the legs of the cats because it would mean all the cats were put on the available dogs. So max(0,C-(2*D))*4 is the number of legs of the cats that needs to be added at least.[maximum can be found out using inbuilt max() or if statement]

Hint 5:

Click to view

Now what is the maximum number of legs this configuration can achieve. This is simple.

Hint 6:

Click to view

The maximum number of legs will be achieved if none of the dogs carry a cat. That is 4*(C+D). It is the case where all the animals are standing on their own.

Hint 7:

Click to view

Now any number of legs that is between these extremes and are divisible by 4 is valid.

Hint 8:

Click to view

If you are still unable to figure out the solution by yourself look at the detailed editorial for this problem here: Link