WSC- Editorial

Problem link :

Contest
Practice

Difficulty : CakeWalk

Pre-requisites : Basic programming language constructions

Problem : Determine whether it is possible to solve the generalized version of the Wolf-Sheep-Cabbage puzzle

Explanation

This is the easiest problem, and its’ solution is fairly easy. At first, it is easy to see that we can safely throw away from our consideration all the creatures that don’t eat anybody and don’t get eaten by anybody. It can be reasoned in the following way: in case there is a solution, you can move some part of creatures to the opposite shore in such a way that on the both shores nobody eats anybody. After this is done, you can move all these “isolated” creatures to the opposite shore.

So now let’s solve the version of the problem, where there are not any “isolated” creatures. Let’s consider all the particular cases:

  • There is one creature. Obviously, the answer is “YES”;
  • There are two creatures. First, you move the first one, then you move the second one. There is also no problem at all, so the answer is also “YES”;
  • There are three creatures. One can simply prove that the answer is “YES” only in case the number of pairs where one creature eats another one is 2. Otherwise you will always obtain the case when one creature will eat another after you’ve made the first boat trip.
  • There are four and more creatures. By simply writing out all the possible cases for 4 creatures, and even 3 edges, it is easy to convince that it is impossible to move all the creatures to the opposite shore.

So the solution is no more than throwing away all the “isolated” creatures and checking these four statements for the remaining ones.

Solutions : setter tester

2 Likes

Someone please explain the 4th case when there are 4 or more creatures. Its not that trivial

2 Likes

I cannot open the solution. There is an error :
This XML file does not appear to have any style information associated with it. The document tree is shown below.

AccessDenied
Access Denied
9FAEA60FD52A3EB7

2XXHbsc2BJiiQS4s9/VrWMwRHH7phuPY+hYVaPyjheS/KWpAfKCOV+fCnwcBRSff

1 Like

I do not understand for m>2.
In this accepted solution for m>2 answer is always no. What about the following case-

4 3

1 2

2 3

2 4

and also similarly for more than 3 also,

5 4

1 3

3 2

3 4

3 5

The answers to both of the above should be yes. Can someone explain me something?

No… For cases that you’ve mentioned, the answer should be NO… Try it :slight_smile:

Assume another creature X. Take 3 cases. One, where X eats W; another, where X eats S; and the third case, where X eats C. Try to find a solution for each of the cases. (You’ll not find any!) Therefore, if there’s any more extra creature, it should not eat anyone. Otherwise, the answer will be NO. :slight_smile:

if(m>2)print NO
else
print YES

IS this right??

As always solution not available. What the flying fuck.