Category Archives: Patterns

Inverse permutation problem

This problem is from code forces. If you want to try this problem, follow this link.
Here is the simplified problem statement.
Given a group of N friends, each one has given a gift to other friend or themselves. An input array is given which indicates from whom each one has received their gifts. We have to print an array which shows to whom each one has given their gifts.

For example,
 
Let us consider a group of 5 friends. The input array {3, 1, 5, 2, 4} indicates that the ‘1’ has received the gift from ‘3’, and ‘2’ has received the gift from ‘1’, and so on…

The output should be {2, 4, 1, 5, 3}. This indicates that 1 has given gift to 2, 2 has given gift to 4, and so on…

This problem of finding the inverse permutation of a given sequence. The solution is described below.

Let us allocate a separate array B for output. For each A[i], fill  B[A[i]] with i by iterating through all the elements. At the end of the iteration, B has the required answer. This method runs in O(n) time.

Here is the C++ implementation of the above approach.

A simple problem pattern in competitive programming

Consider the following two problems appeared in two different competitions, which underlies the same pattern.

Given a number of chocolates (N). For each of M wrappers, we will get a chocolate free. How can one have the maximum number of chocolates by following an optimum strategy?

Given a number of candles (N) each of them burn for 1 hours. Assume that from the remaining wax of M burning candles we can make another candle. What is the maximum number of hours for which we can lit the candles by following the optimum strategy?


The solution is simple. As long as we have more chocolates than M, we continue to eat them and produce N/M wrappers which again fetch some more chocolates. Add it to the remaining chocolates and repeat this procedure until we have less number of chocolates than
M.

Following is the simple C++ program which implements the above algorithm.