Overview

This problem asks us to determine the presentation order of \(N\) employees to maximize the total score (the sum of each employee’s presentation skill multiplied by their presentation position). However, we must satisfy \(M\) constraints of the form “employee \(U\) must present before employee \(V\).”

Analysis

Since the problem constraints specify \(N \leq 8\), which is very small, a brute-force approach that enumerates all possible presentation orders (permutations), checks the constraints, and computes the total score is effective. For \(N=8\), the total number of permutations is \(8! = 40320\), which is well within a manageable range. Since we check \(M\) constraints for each permutation, the overall time complexity is \(O(N! \times M)\), and since \(M\) is at most about 28, this can be computed in a practical amount of time.

Algorithm

1. Generate all possible presentation orders (permutations of \(1\) through \(N\))
2. For each permutation, check whether all given constraints are satisfied
   • For each constraint \((U, V)\), verify that \(U\)’s position in the permutation comes before \(V\)’s position
3. For permutations that satisfy the constraints, compute the total score \(\sum_{i=1}^{N} A_i \times P_i\)
4. Output the maximum total score obtained

Complexity

• Time complexity: \(O(N! \times M \times N)\)
  • Number of permutations: \(N!\)
  • Constraint checking per permutation: \(M\) times (each check requires \(O(N)\) index lookup)
  • Score computation: \(O(N)\)
• Space complexity: \(O(N! \times N)\)
  • It is not necessary to hold all permutations in memory; by processing them one at a time, the actual space required is \(O(N)\)

Implementation Notes

• Use Python’s itertools.permutations to efficiently generate all permutations

• Convert constraints to 0-indexed for processing

• Use the index method to look up positions and check whether each permutation satisfies the constraints

• When computing the total score, convert 0-indexed order to 1-indexed (order+1)

• Update the maximum score as the search progresses

  Source Code

import itertools

def main():
    import sys
    data = sys.stdin.read().split()
    if not data:
        return
    
    n = int(data[0])
    m = int(data[1])
    A = list(map(int, data[2:2+n]))
    constraints = []
    index = 2 + n
    for i in range(m):
        u = int(data[index]); v = int(data[index+1])
        constraints.append((u-1, v-1))  # 0-indexedに変換
        index += 2
        
    # すべての順列を生成
    all_permutations = itertools.permutations(range(n))
    best_score = -1
    
    for perm in all_permutations:
        # 順列permが制約を満たすかチェック
        valid = True
        for (u, v) in constraints:
            pos_u = perm.index(u)
            pos_v = perm.index(v)
            if pos_u >= pos_v:
                valid = False
                break
        if not valid:
            continue
            
        # 総合スコアを計算
        score = 0
        for order, person in enumerate(perm):
            # orderは0-indexedの順番。実際の発表順はorder+1
            score += A[person] * (order+1)
            
        if score > best_score:
            best_score = score
            
    print(best_score)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.