Problem: runway (2021 round2)

TFW it's Toronto Fashion Week. There are \(T\) fashion shows to be held, during which runway models will showcase the latest outfits from top designers. Dorothy the dresser has been designated the difficult duty of dressing them all!

A given fashion show features \(M\) models wearing a variety of outfits. Each outfit has a style, denoted by a positive integer. Before the show begins, each model \(i\) is required to arrive at the venue wearing an outfit of style \(S_i\).

Then, \(N\) rounds will follow. A round consists of a lineup of the \(M\) models walking the runway in turn, each showcasing an outfit. The ordering of models can differ among different rounds' lineups, but must be some permutation of the same \(M\) models each time. The show also has a predetermined program: the \(j\)th outfit showcased in the \(i\)th round's lineup must be of style \(P_{i,j}\).

Dorothy's job is to dress all of the models backstage, in accordance to the program requirements. A model's outfit may be changed into one of any other style, at any time while the model is not on the runway.

Being resourceful, Dorothy came up with a small trick to make her job less hectic: She can instruct each model to wear another outfit underneath the initial outfit they arrive in, making it easy for the model to change into a different style, just once, without Dorothy's help. In other words, if a model needs to change \(n\) different times throughout the entire show, then Dorothy will only need to personally change the model \(\max(n-1, 0)\) times.

Now, Dorothy would like to organize models for each round to minimize her own work. Can you help determine the minimum total number of times that Dorothy will need to personally change a model, while satisfying the program requirements for all \(N\) rounds?


# Constraints

\(1 \le T \le 70\)
\(1 \le N, M \le 1{,}000{,}000\)
\(1 \le N*M \le 1{,}000{,}000\)
\(1 \le S_i, P_{i,j} \le 10^9\)

The sum of \(N*M\) across all test cases is at most \(5{,}000{,}000\).


# Input

Input begins with an integer \(T\), the number of fashion shows. For each show, there is first a line containing the space-separated integers \(N\) and \(M\). Then, there is a line containing \(M\) space-separated integers, \(S_{1..M}\). Then, \(N\) lines follow, the \(i\)th of which contains \(M\) space-separated integers, \(P_{i,1..M}\).


# Output

For the \(i\)th fashion show, output a line containing *"Case #i: "* followed by a single integer, the minimum number of times that Dorothy must personally change the models.


# Sample Explanation

In the first show, there are \(3\) rounds with only \(1\) model. The model is initially wearing style \(1\), and the program requires styles \([2, 2, 1]\) to be showcased in sequence. Dorothy can direct the model to arrive wearing style \(2\) underneath style \(1\), so that it may be uncovered before round \(1\) with no work from Dorothy herself. After the model does so and showcases style \(2\) for the first two rounds, Dorothy will have to personally change the model back into style \(1\) for round \(3\).

In the second show, there are \(4\) rounds and \(2\) models. The models arrive wearing styles \(1\) and \(11\), respectively. The program requires each round to showcase styles \(1\) and \(11\) in alternating order. The models can simply alternate positions from round to round, requiring no work from Dorothy.

In the third show, the two models arrive wearing styles \(1\) and \(11\), respectively, but \(8\) other different styles then need to be showcased (\(4\) by each model). Each model can change into \(1\) more style by wearing it underneath their initial outfit, but Dorothy will have to personally change them for the remaining \(3\) each, for a total of \(6\).

In the fourth show, one possible optimal way to organize the fashion show is as follows:

- Initially, model \(1\) wears style \(30\) underneath style \(10\), model \(2\) wears style \(30\) underneath style \(20\), and model \(3\) wears style \(10\) underneath style \(20\).
- For round \(1\), the models go in order \([2, 1, 3]\). Models \(2\) and \(1\) already fit the program, while model \(3\) changes into style \(10\) independently.
- For round \(2\), keep the same lineup. Models \(2\) and \(1\) each change themselves into style \(30\), while Dorothy personally changes model \(3\) into style \(20\).




Sample input:
5
3 1
1
2
2
1
4 2
1 11
11 1
1 11
11 1
1 11
4 2
1 11
2 12
3 13
4 14
5 15
2 3
10 20 20
20 10 10
30 30 20
4 5
1 4 4 10 1
4 8 1 7 5
10 1 7 3 6
7 7 3 1 1
2 3 1 8 5


Sample output:
Case #1: 1
Case #2: 0
Case #3: 6
Case #4: 1
Case #5: 6


Solution: Models wearing the same style are indistinguishable aside from whether or not they have already changed at least once (as each model's first change is free). We can therefore represent the set of models before/after each round by a pair of numbers per style \(s\): the number of models \(W_s\) currently wearing that style, and the number of those models \(U_s\) who have not yet changed at all. Note that we only need these entries per style currently being worn by at least one model.

We'll process one round at a time, following a greedy approach based on the set of models before the round to determine the new set of models after the round (as well as the number of new changes which must be performed by Dorothy). Let \(R_s\) be the number of models required to wear style s in the current round. The greedy approach is then based on the following list of priorities:

  1. *As few models as possible should change at all.* For each style \(s\), \(\min(W_s, R_s)\) models might as well remain unchanged in style \(s\), as it cannot be better for them to change out of it and others to change into it. This means that \(C_s = W_s - \min(W_s, R_s)\) models will change out of style \(s\).
  2. When choosing exactly which models should change, *those who have never changed should be prioritized*. Such models can be changed for free, and it cannot be better to change different models in the current round instead and save the previously-unchanged models for later. This means that \(\min(C_s, U_s)\) previously-unchanged models will change out of style \(s\) (by themselves), while \(C_s - \min(C_s, U_s)\) other models will change out of style \(s\) (with Dorothy's help).
  
These ideas are sufficient to describe an optimal approach, and can be used to efficiently simulate the sequence of events. Assuming we use hash tables (keyed by style) to represent the above values, each round may be processed in \(O(M)\) time, given that there will be at most \(M\) distinct styles before it and at most \(M\) after it. The overall time complexity is therefore \(O(NM)\).

[See David Harmeyer (SecondThread)'s solution video here.](https://youtu.be/3iT1vv_Tdpo)


Code: #include <iostream>
#include <map>
#include <utility>
using namespace std;

int N, M;

int solve() {
  map<int, pair<int, int>> curr, next;
  cin >> N >> M;
  for (int i = 0, s; i < M; i++) {
    cin >> s;
    int v = curr[s].first + 1;
    curr[s] = make_pair(v, v);
  }
  int ans = 0;
  for (int i = 0, p; i < N; i++) {
    map<int, int> req;
    for (int j = 0; j < M; j++) {
      cin >> p;
      req[p]++;
    }
    next.clear();
    for (auto [k, v] : curr) {
      auto it = req.find(k);
      int num_to_change = max(0, v.first - (it != req.end() ? it->second : 0));
      int num_to_change_for_free = min(num_to_change, v.second);
      ans += num_to_change - num_to_change_for_free;
      curr[k].second -= num_to_change_for_free;
    }
    for (auto [k, v] : req) {
      auto it = curr.find(k);
      next[k] = make_pair(v, min(v, it != curr.end() ? it->second.second : 0));
    }
    curr = next;
  }
  return ans;
}

int main() {
  int T;
  cin >> T;
  for (int t = 1; t <= T; t++) {
    cout << "Case #" << t << ": " << solve() << endl;
  }
  return 0;
}