Editing 2015 Dec Gold Problem 1 High Card Low Card (Gold)

== Official Problem Statement ==

[http://www.usaco.org/index.php?page=viewproblem2&cpid=573 High Card Low Card (Gold)]

== Problem ==

In this problem, the goal is to maximize the number of points a player named Bessie can get in a game of "High Card Low Card".

In this game, there are 2N cards (2<=N<=50000) with distinct values from 1 to 2N. Each player, Bessie and Elsie, have N cards. In each round, a player from both sides plays a card, and the player with the highest card gets a point.

There is a twist in the game. For the first N/2 rounds, the player who gets the point is the one with the lowest card. For the next N/2 rounds, the player with the highest card gets the point. Both Bessie and Elsie play optimally to maximize their own points.

Bessie knows the cards that Elsie has. The problem asks to determine the maximum points Bessie can get.

== Solution ==

The solution to this problem involves sorting and binary search.

* Sort the cards of both Bessie and Elsie.
* For the first half of the game, Bessie tries to use her lowest card that can beat Elsie's current lowest card. If no such card exists, she plays her lowest card.
* For the second half, Bessie tries to use her lowest card that can beat Elsie's current highest card. If no such card exists, she plays her highest card.

Implementing this strategy ensures Bessie scores as many points as possible.

Here's the pseudocode:

* Sort the cards of Bessie and Elsie.
* Initialize pointers for Bessie and Elsie's current cards and a counter for Bessie's points.
* Repeat for the first N/2 rounds:
** If Bessie's lowest card can beat Elsie's lowest card (found using binary search), increment the counter, and move the pointers.
** If not, play Bessie's lowest card and only move Bessie's pointer.
* Repeat for the next N/2 rounds:
** If Bessie's lowest card can beat Elsie's highest card (found using binary search), increment the counter, and move the pointers.
** If not, play Bessie's highest card and only move Bessie's pointer.
* The counter for Bessie's points is the answer.

== Code ==

=== C++ ===
<pre>
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    ifstream fin("cardgame.in");
    ofstream fout("cardgame.out");

    int N; 
    fin >> N;

    vector<bool> used(2 * N);
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        fin >> A[i];
        A[i]--;
        used[A[i]] = true;
    }
    
    // Sort and rearrange A
    sort(A.begin(), A.begin() + N / 2);
    sort(A.begin() + N / 2, A.end());
    rotate(A.begin(), A.begin() + N / 2, A.end());

    // Gather unused cards into B
    vector<int> B;
    for (int i = 0; i < 2 * N; i++) {
        if (!used[i]) {
            B.push_back(i);
        }
    }

    // Count wins for the two halves of the game
    int res = 0;
    for (int i = N / 2, j = N / 2; i < N; i++, j++, res++) {
        while (j < N && B[j] < A[i]) {
            j++;
        }
        if (j == N) {
            break;
        }
    }
    for (int i = N / 2 - 1, j = N / 2 - 1; i >= 0; i--, j--, res++) {
        while (j >= 0 && B[j] > A[i]) {
            j--;
        }
        if (j == -1) {
            break;
        }
    }
    fout << res << endl;

    return 0;
}
</pre>

=== Java ===
<pre>
import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner fin = new Scanner(new File("cardgame.in"));
        PrintWriter fout = new PrintWriter(new BufferedWriter(new FileWriter("cardgame.out")));

        int N = fin.nextInt();
        ArrayList<Integer> A = new ArrayList<>();
        boolean[] used = new boolean[2 * N];

        for (int i = 0; i < N; i++) {
            int card = fin.nextInt();
            card--;
            A.add(card);
            used[card] = true;
        }

        Collections.sort(A.subList(0, N/2));
        Collections.sort(A.subList(N/2, N), Collections.reverseOrder());
        Collections.rotate(A, N/2);

        ArrayList<Integer> B = new ArrayList<>();
        for (int i = 0; i < 2 * N; i++) {
            if (!used[i]) {
                B.add(i);
            }
        }

        int res = 0;
        int j = N / 2;
        for (int i = N / 2; i < N; i++, res++) {
            while (j < N && B.get(j) < A.get(i)) {
                j++;
            }
            if (j == N) {
                break;
            }
        }

        j = N / 2 - 1;
        for (int i = N / 2 - 1; i >= 0; i--, res++) {
            while (j >= 0 && B.get(j) > A.get(i)) {
                j--;
            }
            if (j == -1) {
                break;
            }
        }

        fout.println(res);
        fout.close();
    }
}
</pre>

=== Python ===
<pre>
from bisect import bisect_left, bisect_right

with open('cardgame.in', 'r') as fin:
    N = int(fin.readline().strip())
    A = list(map(int, fin.readline().split()))

A = [a - 1 for a in A]
used = [False] * (2 * N)

for a in A:
    used[a] = True

A[:N//2] = sorted(A[:N//2])
A[N//2:] = sorted(A[N//2:])
A = A[N//2:] + A[:N//2]

B = [i for i in range(2 * N) if not used[i]]

res = 0
j = N // 2
for i in range(N // 2, N):
    while j < N and B[j] < A[i]:
        j += 1
    if j == N:
        break
    res += 1
    j += 1

j = N // 2 - 1
for i in range(N // 2 - 1, -1, -1):
    while j >= 0 and B[j] > A[i]:
        j -= 1
    if j == -1:
        break
    res += 1
    j -= 1

with open('cardgame.out', 'w') as fout:
    fout.write(str(res) + '\n')
</pre>


[[Category:Yearly_2015_2016]]
[[Category:Gold]]
[[Category:Arrays]]
[[Category:Greedy]]
[[Category:Two Pointer]]