Cost of Lineups

Problem Statement

Cost of Lineups Problem Description In a sports league, each player is assigned a rank from 1 to k . You are analyzing all possible ways to arrange n players in a lineup, where each player's rank is an integer from 1 to k . A team is a group of k consecutive players (a contiguous subarray of length k ). A team is perfect if it contains every rank from 1 to k exactly once, i.e. the team is a permutation of {1, 2, ..., k} . The cost of a lineup is the maximum number of non-overlapping perfect teams that can be selected from it. Each player can belong to at most one selected team. For example, suppose n = 10 , k = 3 and the lineup is [1, 2, 1, 3, 2, 3, 2, 3, 1, 3] . Its cost is 2: we can choose the players from position 2 to position 4 ( [2, 1, 3] ) and the players from position 7 to position 9 ( [2, 3, 1] ), and it is impossible to choose 3 non-overlapping perfect teams. There are k^n different lineups of length n (all arrays of length n with elements from 1 to k ). Calculate the sum of