Codeforces 914B : Conan and Agasa play a Card Game Problem Analysis

Problem Statement: https://codeforces.com/problemset/problem/914/B

The key point in this problem is no one can pick more than one cards in every turn.
Because of this, if there are multiple cards with same big numbers it is a matter of sequence and decides the winning professor/detective depending whether the number of cards of same big numbers are even or odd.

Example 1:

6
4 5 2 5 4 5

Case 1. odd number of cards having same & highest number:

Turn 1:
5c 5  5       //Nc --> Conan picks card with value N
4  4 //Na --> Agasa picks card with value N
2

Turn 2:
5c 5a 5
4  4
2

Turn 3:
5c 5a 5c //All highest value cards have been
4  4 //picked up. No cards left for
2 //Agasa in next turn

//Conan wins.

Example 2:

9
3 9 3 5 9 5 9 5 9

Case 2. odd number of cards having same (but not highest) number:

Turn 1:
9  9  9  9   //There is an even number of 9s. Conan predicts
5c 5  5 //his defeat. So he picks second highest card
3  3 //that has an odd number of counts. Conan
// always has this advantage because he is
// picking first. Because both Conan & Agasa
//playing optimally, they can not make mistakes.

Turn 2,3:
9  9  9  9
5c 5a 5c //All 5s and 3s are now gone. Leaving 4 9s onboard.
3  3

Turn 4:
9a  9  9  9      //Agasa is now forced to pick these even
//number of 9s.

Turn 5,6,7:
9a  9c  9a  9c

//Conan wins.

In our example Case 1 in fact belongs within Case 2.


Example 3:

12
8 6 4 8 4 8 6 8 6 6 8 8

Case 3. even number of cards having same number:

8  8  8  8  8  8 //There are no odd number of occurances
6  6  6  6 //of cards with same value (Conan's
4  4 //only chance to change sequence of
//turns)
//Agasa wins.

Solution (.CPP) Codeforces compiler C++ 17 (7.3.0):
==============================================

#include <iostream>

using namespace std;

int cardCounts[100005];       // we can have a 1-dimensional array for storing every card count
                                              // since a <= 10^5 ( < 10^8 )

int main() {

  int n;
  cin >> n;

  while(n--) {
    int a;
    cin >> a;
    cardCounts[a]++;
  }

  for (int i = 1; i <= 1e5; i++) {
    if (cardCounts[i] % 2) {
      cout << "Conan\n";
      return 0;
    }
  }

  cout << "Agasa\n";
  return 0;
}