Overview

Assign a presentation order (a permutation of \(1\) through \(N\)) to \(N\) employees, satisfying all constraints of the form “employee \(U_k\) presents before employee \(V_k\),” while maximizing \(\sum A_i \times P_i\).

Analysis

Understanding the Problem Structure

When assigning presentation order \(P_i\) to each employee \(i\), assigning a larger \(P_i\) (later presentation order) to employees with larger presentation skill \(A_i\) increases the product \(A_i \times P_i\), thus increasing the total score.

For example, with \(N = 3\), \(A = (1, 3, 2)\) and no constraints, it intuitively seems best to assign \(P_2 = 3\) (present last) to employee \(2\) who has the largest \(A_i\). Indeed, having employees present in increasing order of \(A_i\) is optimal.

Impact of Constraints

However, due to the ordering constraints “employee \(U_k\) presents before employee \(V_k\),” simply assigning later presentation slots to employees with larger \(A_i\) may violate the constraints.

Focusing on the Constraint \(N \leq 8\)

Since \(N\) is at most \(8\), the number of permutations of the presentation order is at most \(8! = 40320\). We can enumerate all permutations and find the maximum score among those satisfying the constraints using brute-force search, which is well within the time limit.

Algorithm

1. Enumerate all permutations of \((1, 2, \ldots, N)\). Each permutation \(\text{perm}\) means “the presentation order of employee \(i\) (0-indexed) is \(\text{perm}[i]\).”
2. For each permutation, check whether \(\text{perm}[U_k] < \text{perm}[V_k]\) holds for all constraints \((U_k, V_k)\).
3. For permutations satisfying all constraints, compute the total score \(\sum_{i=0}^{N-1} A[i] \times \text{perm}[i]\).
4. Output the maximum score among all permutations satisfying the constraints.

Concrete Example

For \(N = 3\), \(A = (1, 3, 2)\), with the constraint “employee 1 presents before employee 2” (\(P_1 < P_2\)):

Permutation \((P_1, P_2, P_3)\)	\(P_1 < P_2\)?	Score \(1 \times P_1 + 3 \times P_2 + 2 \times P_3\)
\((1, 2, 3)\)	✓	\(1 + 6 + 6 = 13\)
\((1, 3, 2)\)	✓	\(1 + 9 + 4 = 14\)
\((2, 3, 1)\)	✓	\(2 + 9 + 2 = 13\)
\((3, 2, 1)\)	✗	—
…	…	…

We select the maximum score among those satisfying the constraints.

Complexity

• Time complexity: \(O(N! \times (N + M))\)
  • For each of the \(N!\) permutations, we perform \(M\) constraint checks (\(O(M)\)) and a score calculation (\(O(N)\)).
  • Since \(N \leq 8\), this is approximately \(8! \times (8 + 28) = 40320 \times 36 \approx 1.5 \times 10^6\), which is sufficiently fast.
• Space complexity: \(O(N + M)\)

Implementation Notes

• Employee numbers are \(1\)-indexed in the problem statement, but Python arrays are \(0\)-indexed, so \(U_k\) and \(V_k\) are decremented by \(1\) during input to convert to \(0\)-indexed.

• Using itertools.permutations(range(1, N+1)) directly generates all permutations of presentation orders \(1\) through \(N\), making the implementation simple.

• When a constraint violation is found, we break and move to the next permutation, avoiding unnecessary computation.

  Source Code

import sys
from itertools import permutations

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    A = []
    for i in range(N):
        A.append(int(input_data[idx])); idx += 1
    constraints = []
    for _ in range(M):
        u = int(input_data[idx]) - 1; idx += 1
        v = int(input_data[idx]) - 1; idx += 1
        constraints.append((u, v))
    
    best = -1
    for perm in permutations(range(1, N + 1)):
        # perm[i] = P_{i+1}, the presentation order of person i (0-indexed)
        valid = True
        for u, v in constraints:
            if perm[u] >= perm[v]:
                valid = False
                break
        if valid:
            score = sum(A[i] * perm[i] for i in range(N))
            if score > best:
                best = score
    
    print(best)

main()

---

This editorial was generated by claude4.6opus-thinking.