PROBLEM LINK :
[Practice] (CPP2108 Problem - CodeChef)
[Contest] (CodeChef: Practical coding for everyone)
Author : Shriram
Editorialist : Shriram
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming
PROBLEM:
We are given a sequence of n elements, with the i^{th} element having value a_i. We need to choose the n elements in a specific order, under the condition that for all 1 \leq i < j \leq n, choosing the i^{th} element before the j^{th} changes the value of the j^{th} by b_{ij}.
SOLUTION:
The above problem can be proven to be NP-Complete. However, the constraint gives us a lifeline; we can do off with an exponential algorithm, and thus let us try to build an incremental solution.
Let us consider the current set of elements that have already been chosen as S. Clearly, S \subseteq N = \{1,2,...,n\}. Thus, the next food to be eaten is to be chosen from the set N - S.
Let us assume we have to choose the j^{th} element next, where j \in N - S. Also, let us define p(S) as the maxmimum value that can be obtained by eating foods from the set S.
Thus, p(S\cup \{j\} )=max(p(S\cup \{j\}), p(S) + a_j + \sum_{i\in S}b_{ij}). Why max? because the set S\cup \{j\} can be obtained by selecting j earlier and choosing some other element instead of j in the end. Thus, for the given set S\cup \{j\}, let us take the maximum over all possibilties.
How do we encode the sets? To do this, let us use bitmasks; Consider an integer N that has n bits, and the i^{th} bit is 1 if and only if the i\in S. Let us also consider a dynamic programming dp, where dp_i=p(S), where i is the bitmask corresponding to the set S.
Thus, we get the following DP solution:
dp_i = max(dp_i, dp_{i \oplus 2^j} + a_j + \sum_{k=1}^{n}b_{ij} * sign(i \oplus 2 ^ j \oplus 2 ^ k)))
The last term. sign(i \oplus 2 ^ j \oplus 2 ^ k) will become 0 if k=j or k^{th} bit is not set in i. Thus, this ensures that only the b_{ij} for elements already included in i are added. This can be implemented using simple bitwise operators, as in the code below.
The answer is dp_{2^n-1}. The time complexity of the solution is O(n^22^n), while the memory complexity is O(2^n).
LINK TO CODE (in C++):
(https://drive.google.com/file/d/1SpRuXr970_qJBuWGvFcCSXZs4R6ejqp8/view?usp=sharing)