Seat Swapping
Time limit2sMemory limit128 MB
Given N students each with a team label (K up to 8), find the minimum adjacent swaps to group each team into one contiguous block in some chosen team order.
- Level
Medium7 of 10
- Topics
- Dynamic programming, Bit manipulation, Combinatorics
- Solved
- No attempts yet
Problem
Tomorrow is team match day. Each of the N students belongs to exactly one team numbered from 1 to K, but the students are currently sitting in one mixed line.
They want to rearrange the seats so that students on the same team can study together. To avoid confusion, one swap may exchange only two students sitting in adjacent positions.
Find the minimum number of adjacent swaps needed so that, for every team, all students on that team occupy one consecutive segment. The order of the team segments may be chosen freely.
Input
The first line contains the number of students N and the number of teams K. (1 <= N <= 300,000, 1 <= K <= 8)
Each of the next N lines contains one integer: the team number of the student in that position. Each team number is between 1 and K, inclusive.
Output
Print the minimum number of adjacent swaps required to make every team's students sit in consecutive positions.
Hint
Suppose the initial seating order is 2 2 3 2 1 3 1. If the students in positions 3 and 4 swap, and then the students in positions 5 and 6 swap, the order becomes 2 2 2 3 3 1 1.
Now every team sits consecutively. Other team orders, such as 1 1 2 2 2 3 3, are also possible, but no arrangement can be reached in fewer than 2 swaps.