Problem: fourth_player (2022 round3)

Four friends are playing a card game with two teams of two players each. Team \(A\) consists of players \(A1\) and \(A2\) while team \(B\) consists of players \(B1\) and \(B2\).

There is a deck of \(N\) cards (where \(N\) is always a multiple of \(4\)), numbered from \(1\) to \(N\), with all cards visible to all players at all times. First, the cards are dealt out evenly to each player:
- Player \(A1\) has cards \(A1_1\), ..., \(A1_{N/4}\).
- Player \(B1\) has cards \(B1_1\), ..., \(B1_{N/4}\).
- Player \(A2\) has cards \(A2_1\), ..., \(A2_{N/4}\).
- Player \(B2\) has cards \(B2_1\), ..., \(B2_{N/4}\).

The game proceeds for \(N/4\) rounds. In each round, each player plays a card. Player \(A1\) plays first, then player \(B1\), then player \(A2\), then player \(B2\). A player may choose to play any of their cards when it’s their turn. After all four players have played a card, the team who played the highest card will score \(1\) point. Once a round is complete, the four played cards are removed from the game, and then the next round starts. This continues until all cards have been played.

For example, the first round of the second sample case might be played as follows, with player \(B2\) winning a point for team \(B\):

{{PHOTO_ID:1558229151280116|WIDTH:600}}

Assuming each team plays to maximize its score, how many points will team \(A\) score?


# Constraints

\(1 \le T \le 500\)
\(4 \le N \le 4{,}000{,}000\)
\(N\) is a multiple of \(4\).
Each card from \(1\) to \(N\) is guaranteed to exist in exactly one player’s hand.

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


# Input Format

Input begins with a single integer \(T\), the number of test cases. For each test case, there is first a line containing a single integer \(N\). Then there are \(4\) lines containing the players' cards:
- Line 1: \(N/4\) space-separated integers, \(A1_1, ..., A1_{N/4}\). 
- Line 2: \(N/4\) space-separated integers, \(B1_1, ..., B1_{N/4}\). 
- Line 3: \(N/4\) space-separated integers, \(A2_1, ..., A2_{N/4}\). 
- Line 4: \(N/4\) space-separated integers, \(B2_1, ..., B2_{N/4}\). 


# Output Format

For the \(i\)th test case, output a line containing `"Case #i: "` followed by a single integer, the number of points that team \(A\) will score.


# Sample Explanation

In the first case, one possible way the cards can be played optimally is:
- Round 1: \([2, 7, \textbf{8}, 5]\)
- Round 2: \([1, 3, \textbf{6}, 4]\)

Team \(A\) will score \(2\) points, and team \(B\) can do no better by playing differently.

In the second case, one possible way the cards can be played optimally is:

- Round 1: \([1, 6, 2, \textbf{9}]\)
- Round 2: \([\textbf{13}, 5, 3, 8]\)
- Round 3: \([12, 15, \textbf{16}, 10]\)
- Round 4: \([\textbf{14}, 7, 4, 11]\)

Team \(A\) will score \(3\) points.

In the third case, one possible way the cards can be played optimally is:

- Round 1: \([11, \textbf{12}, 9, 4]\)
- Round 2: \([13, 2, 8, \textbf{14}]\)
- Round 3: \([6, 1, 5, \textbf{10}]\)
- Round 4: \([15, \textbf{16}, 7, 3]\)

Team \(B\) can always prevent team \(A\) from scoring any points.


Sample input:
5
8
1 2
3 7
6 8
4 5
16
14 13 12 1
15 5 6 7
16 2 3 4
8 9 10 11
16
15 13 11 6
16 12 1 2
5 9 7 8
14 10 3 4
8
5 2
8 4
7 3
6 1
24
7 6 14 22 18 12
20 23 13 8 16 11
24 21 4 9 1 19
15 5 10 17 3 2


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


Solution: It's helpful to work through an example, so let's use the third sample case. We'll sort each player's hand in decreasing order for convenience:

- \(A1: [15, 13, 11, 6]\)
- \(B1: [16, 12, 2, 1]\)
- \(A2: [9, 8, 7, 5]\)
- \(B2: [14, 10, 4, 3]\)

Note that the order that player \(A1\) plays their cards has no effect on the strategy of other players. In fact, since all players have perfect information, it helps to imagine reorganizing the game in a slightly different way: player \(A1\) plays all of their cards at once, one each into \(N/4\) different stacks. Then player \(B1\) plays all of their cards, again one each onto each of the stacks, and so on. After all cards are played, the team with the highest card in a stack scores a point for that stack.

We'll keep track of the highest card in each stack, and which team it belongs to. In our example, after player \(A1\) plays, the stacks are: \((15, A)\), \((13, A)\), \((11, A)\), \((6, A)\).

The general strategy for the other players is:
- First priority: cover as many of the opposing team's highest cards as possible
- Second priority: cover as many of your own team's lowest cards as possible

Here "cover" means "play a card higher than". As we'll see, this second priority is only meaningful to player \(A2\).

Player \(B1\) will cover as many of player \(A1\)'s highest cards as they can, using their own highest cards. In this example, \(B1\) will cover the \(15\) with the \(16\) and the \(11\) with the \(12\). Now the stacks are: \((16, B)\), \((13, A)\), \((12, B)\), and \((6, A)\).

Player \(A2\) similarly wants to cover as many cards owned by team \(B\) as possible, which in this case is none of them. \(A2\)'s second priority is to cover their *own* team's *lowest* cards with the highest cards possible. In this case \(A2\) can cover the \(6\) with the \(9\), and now the stacks are: \((16, B)\), \((13, A)\), \((12, B)\), \((9, A)\).

Player \(B2\) now finishes up by covering as many of team \(A\)'s cards as possible: \((16, B)\), \((14, B)\), \((12, B)\), \((10, B)\). In the end, team \(B\) scores every point.

This approach can be implemented in \(\mathcal{O}(N \log N\)\) time by sorting the initial hands and then resorting the stacks after each player plays.


Code: #include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int solve() {
  int N;
  cin >> N;
  vector<vector<int>> C(2);
  for (int i = 0; i < 4; i++) {
    vector<int> H(N/4);
    for (int j = 0; j < N/4; j++) {
      cin >> H[j];
    }
    sort(H.begin(), H.end());
    if (i == 0) {
      C[0] = H;
    } else {
      int us = i % 2, them = 1 - us;
      vector<vector<int>> C2(2);
      // Cover as many of their team's highest cards as possible.
      for_each(C[them].rbegin(), C[them].rend(), [&](int card) {
        if (!H.empty() && H.back() > card) {
          C2[us].push_back(H.back());
          H.pop_back();
        } else {
          C2[them].push_back(card);
        }
      });
      // Cover as many of our team's lowest cards as possible.
      for (int card : C[us]) {
        if (!H.empty() && H.back() >= card) {
          C2[us].push_back(H.back());
          H.pop_back();
        } else {
          C2[us].push_back(card);
        }
      }
      C = C2;
      sort(C[us].begin(), C[us].end());
      sort(C[them].begin(), C[them].end());
    }
  }
  return C[0].size();
}

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