INSQ16H - Editorial

PROBLEM LINK:

Contest

Practice

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

SOLUTION:

Setter’s Solution