PROBLEM LINK:
Author: Amit Raj
Tester: Vikash Dubey
Editorialist: Amit Raj
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Number Theory, Min Cost Max Flow
EXPLANATION:
The question has two parts. First is to find the number of permutations of (ARR[1], ARR[2] … , ARR[i]) except the ones in which the condition (ARR[a] < ARR[b] < ARR[c]) is satisfied for any a,b,c such that 1 ≤ a < b < c ≤ i. The answer to this is the nth Catalan number. It doesn’t depent on ARR. This can be observed after writing a brute.
The second part is to maximize the profit. The number of persons that he can carry is limited. Also the number of persons wanting to go from one point to another is limited. This can be solved using Min Cost Max flow algorithm.
Create n*(n-1)/2 + n vertices for each possible combination of points. Use the negative of profit as cost for each edge and the number of people as flow.
For more details refer to this article