Codeforces Round #892, Problem C

Introduction 

In Another Permutation Problem, given a number n, the goal is to maximize an objective function over the set P(n) of all permutations of [1, n]:

max { cost(p), p in P(n) }

where

cost(p) = Sum(i * p(i), 1 <= i <= n) - Max(i * p(i), 1 <= i <= n)

Approaches

Brute force

Here are the max costs and associated optimal permutation for first n values

n cost p

2 2 [2, 1]

3 7 [1, 3, 2]

4 17 [1, 2, 4, 3]

5 35 [1, 2, 5, 4, 3]

6 62 [1, 2, 3, 6, 5, 4]

7 100 [1, 2, 3, 4, 7, 6, 5]

8 152 [1, 2, 3, 4, 8, 7, 6, 5]

9 219 [1, 2, 3, 4, 5, 9, 8, 7, 6]

10 303 [1, 2, 3, 4, 5, 6, 10, 9, 8, 7]

11 406 [1, 2, 3, 4, 5, 6, 7, 11, 10, 9, 8]

It took 17 sec to return the solution for n=11.

Since permutation set size is n!, enumerating all the states via backtracking does not scale as n value increases.

But it gives an intuition of the max solution pattern. From the data, the optimal solution for n depends on a 2nd index k, 1 <= k <= n. It has the following shape:

p = [1, 2, ..., k-1, n, n-1, ..., k]

Simplify the problem

To solve the original problem, we break it down into sub-problems that are simpler to solve.

The Max value M of the elements in the Sum / Max functions is fixed:

M = Max(i * p(i), 1 <= i <= n)

We restrict the set of permutations that are candidates for the optimization, from P(n) to P(n, M), to comply with the constraint M.

max { cost(p), p in P(n, M) }

For p in P(n, M), the new cost to maximize is now a linear combination minus a constant

cost(p) = Sum(i * p(i), 1 <= i <= n) - M

Greedy

Greedy approach efficiently computes the maximal solution of the subproblem. It assigns values starting at n down to 1. At each step i, n >= i >= 1, the rule is to assign the highest available value such that i * p(i) <= M.

The subproblem complexity is O(n log(n)). We use an ordered tree as the data structure. For each iterations, we query the DS and assign the returned value to the permutation current index. Finally we remove the allocated value from the DS.

Visualization

There is no need to solve all sub-problems for all values in the range [n, ..., n * n]. The candidates can be found by generating products i * j, 1 <= i <= n, 1 <= j <= n.

Here's the symmetric matrix of all possible product values, for n = 10:

[[ 1 2 3 4 5 6 7 8 9 10]

[ 2 4 6 8 10 12 14 16 18 20]

[ 3 6 9 12 15 18 21 24 27 30]

[ 4 8 12 16 20 24 28 32 36 40]

[ 5 10 15 20 25 30 35 40 45 50]

[ 6 12 18 24 30 36 42 48 54 60]

[ 7 14 21 28 35 42 49 56 63 70]

[ 8 16 24 32 40 48 56 64 72 80]

[ 9 18 27 36 45 54 63 72 81 90]

[ 10 20 30 40 50 60 70 80 90 100]]

The red lines constitute the wireframe of the surface. They are linear functions (straight lines) for each constant index i, 1 <= i <= n:

j: i * j

j: 1 * j

j: 2 * j

...

j: n * j

The blue lines are the "reverse" diagonals in the matrix. They are parabolic functions (curved lines), for each index i, 1<= i <= n:

j: (i+1-j) * j

j: (2 - j) * j
j: (3 - j) * j
...
j: (11 - j) * j

The list of unique product values from the matrix is

[ 1 2 3 4 5 6 7 8 9 10 12 14 15 16 18 20 21 24

25 27 28 30 32 35 36 40 42 45 48 49 50 54 56 60 63 64

70 72 80 81 90 100]

hence enumerating each subproblems we need to solve.

Operation Research

Finding the right permutation can be considered as an assignment problem: each index i should be assigned to a value j. The assignment should maximize the cost function while respecting the constraints. If i * j > M, remove associated edge in the bipartite graph.

3 important classes of OR problems, from most generic to most specific are

1. Min-Cost Flow problem
2. Transportation problem
3. Assignment problem

Linear Sum Assignment

This OR-tools guide describes how to solve an assignment problem to minimize the sum of the weights of the edges used in the perfect matching. 2 solvers are available

• Linear Assignment
• Hungarian

Integer Programming

The assignment problem can be formulated as a general Mixed-Integer Programming problem. Permutation p can be represented as a n*n matrix with n ones, having only 1 one per row and per column.

An example for n=3 is

[[0 1 0]

[1 0 0]

[0 0 1]]

The permutation vector can be obtained by multiplying the permutation matrix with the index vector [1, ..., n].

We can create a boolean 2d array d[i][j] for each elements in the matrix. The solver will find an optimal solution for p

p[i] = Sum(d[i][j] * j, 1 <= j <= n)

The MIP problem formulation is

Maximize

Sum(i * j * d[i][j], 1 <= i <= n, 1 <= j <= n)

With following constraints

For 1 <= i <= n, 1 <= j <= n,

d[i][j] in {0, 1}

For 1 <= j <= n,

Sum(d[i][j], 1 <= i <= n) = 1

For 1 <= i <= n,

Sum(d[i][j], 1 <= j <= n) = 1

For 1 <= i <= n,

Sum(i * j * d[i][j], 1 <= j <= n) <= M