WSCAGAIN- Editorial

Problem link :

Contest
Practice

Difficulty : Easy

Pre-requisites : BFS

Problem : Determine the minimal number of steps to solve the generalized version of the Wolf-Sheep-Cabbage puzzle.

Explanation

The key observation is that N is fairly small and we can encode all the arrangements of the creatures on the shores by positive integers from 0 through 2N-1, inclusive. One of the ways to do this is using bitmasks, where the i-th bit will be equal to 1 in case the creature is on the initial shore and 0 in case this creature is on the opposite shore.

Now we can construct a graph, where the nodes correspond to states of the form (current shore of the boatman, current arrangement of creatures). An edge in the graph corresponds to moving to the opposite shore with some set of no more than K creatures.

In order to construct the edges, we can just brute-force all the sub-masks of every mask. It is widely known that, for all t-bit bitmasks, there are 3t submasks in total.

When the graph is constructed, we can simply apply BFS, since all the edges have unit lengths. The total complexity of the solution is O(V + E), where V is the number of nodes in the obtained graph and E is the number of edges. So, finally, we can conclude that our solution has O(3N) time complexity, which is perfectly OK for the given constraints.

Solutions : setter tester

Can someone please explain how there are 3^t submasks in total?

Look at all bitmasks with k 1-bits. There are C(t,k) such bitmasks and each of them has 2k submasks. So the total number of submasks is sumk=0…(t-1) 2kC(t,k). That’s just an expansion of 3t=(2+1)t using the binomial theorem.

1 Like

A pseudo code would be very helpful, the setter and tester solutions are not available.