Problem link :
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.