Problem:


Score : 400 points

Problem Statement

Snuke has decided to play a game using cards.
He has a deck consisting of N cards. On the i-th card from the top, an integer A_i is written.

He will perform the operation described below zero or more times, so that the values written on the remaining cards will be pairwise distinct. Find the maximum possible number of remaining cards. Here, N is odd, which guarantees that at least one card can be kept.

Operation: Take out three arbitrary cards from the deck. Among those three cards, eat two: one with the largest value, and another with the smallest value. Then, return the remaining one card to the deck.

Constraints

3 ≦ N ≦ 10^{5}

N is odd.

1 ≦ A_i ≦ 10^{5}

A_i is an integer.

Input

The input is given from Standard Input in the following format:

N
A_1 A_2 A_3 ... A_{N}

Output

Print the answer.

Sample Input 1

5
1 2 1 3 7

Sample Output 1

3

One optimal solution is to perform the operation once, taking out two cards with 1 and one card with 2. One card with 1 and another with 2 will be eaten, and the remaining card with 1 will be returned to deck. Then, the values written on the remaining cards in the deck will be pairwise distinct: 1, 3 and 7.

Sample Input 2

15
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1

Sample Output 2

7



Sample input:
5
1 2 1 3 7


Sample output:
3

Submission status: Runtime Error

Solution code:
import sys

def main():
    n = input()
    a = input().split()
    n = int(n)
    a = list(map(int, a))


    lst = [0]* 20
    dup = 0
    ans =0

    for i in a:
        lst[i]+=1

    for i in lst:
        if i >0:
            ans+= 1
        if i > 1:
            dup = dup + i - 1

    if dup % 2 == 0:
        print(ans)
    else:
        print(ans-1)

if __name__ == "__main__":
        main()

Submission status: Runtime Error

Solution code:
import sys
import numpy as np
from collections import deque
import copy

from math import *
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

class card:
    def __init__(self, value, count):
        self.value = value
        self.count = count

    def __lt__(self, other):
        return self.count < other.count

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N] = [int(input_raw[0])]
    input_raw = list(read_func().strip().split())
    num_dict = {}
    for i in range(N):
        if int(input_raw[i]) not in num_dict:
            num_dict[int(input_raw[i])] = 1
        else:
            num_dict[int(input_raw[i])] += 1

    card_cnt_list = []
    for num in num_dict:
        card_cnt_list.append(card(num, num_dict[num]))

    card_cnt_list.sort(reverse = True)
    while card_cnt_list[0].count  > 1:
        card_cnt_list[0].count -= 1
        if card_cnt_list[1].count >= 1:
            card_cnt_list[1].count -= 1
        else:
            card_cnt_list[0].count -= 1
        card_cnt_list.sort(reverse = True)

    cnt = 0
    for c in card_cnt_list:
        cnt += c.count

    print cnt



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))

num = int(1e5)

dp = [0]*(num+1)

for e in A:
  dp[e] += 1

cnt = 0
maxm = 0
for i in range(1, num+1):
  if dp[i] > 1:
    cnt += dp[i] - 1
    maxm = max(maxm, dp[i] - 1)

if maxm * 2 > N // 2:
  print(ans)
if maxm > cnt // 2:
  ans = N - (maxm-(cnt-maxm)) * 2
  if ans <= 0:
    ans = 1
else:
  ans = N - (cnt + (cnt%2)*2)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
A = list(map(int, input().split()))

num = int(1e5)

dp = [0]*(num+1)

for e in A:
  dp[e] += 1

cnt = 0
maxm = 0
for i in range(1, num+1):
  if dp[i] > 1:
    cnt += dp[i] - 1
    maxm = max(maxm, dp[i] - 1)

if maxm * 2 > N // 2:
  print(ans)
if maxm > cnt // 2:
  ans = N - (maxm-(cnt-maxm)) * 2
  print(cnt, maxm)
  if ans <= 0:
    ans = 1
else:
  ans = N - (cnt + (cnt%2)*2)
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
uniques = {}
count = 0
for i in range(N):
    a = int(input())

    if a not in uniques.keys():
        uniques[a] = True
    else:
        count += 1

if count % 2 == 0:
    print (N - count)
else:
    print (N - count - 1)

Submission status: Runtime Error

Solution code:
from itertools import groupby

N = input()
A = map(int, input().split())

B = [len(list(group)) for key, group in groupby(sorted(A))]
C = []
for i, val in enumerate(B):
	if val % 2 == 0: C.append(2)
	else: C.append(1)

D = [len(list(group)) for key, group in groupby(sorted(C))]

if D[1] % 2 == 0:
	answer = D[0] +D[1]
else:
	answer = D[0] +D[1] - 1

print(answer)

Submission status: Runtime Error

Solution code:
    N = int(input())
    A = input()
    list_A = A.split()
    set_A = set(list_A)
    i = 0

    for a in list_A:
        if a in set_A:
            i += 1
    i = i - len(set_A)
    if i % 2 == 0:
        print(N - i)
    else:
        print(N - (i +1))

Submission status: Runtime Error

Solution code:
N = int(input())
A = input()
list_A = A.split()
set_A = set(list_A)
 i = 0
for a in list_A:
  if a in set_A:
    i += 1
  i = i - len(set_A)
  if i % 2 == 0:
    print(N - i)
  else:
    print(N - (i +1))

Submission status: Runtime Error

Solution code:
int(raw_input())
print len(set(map(int, raw_input().strip())))

Submission status: Runtime Error

Solution code:
import numpy as np

N = int(input())
A = np.array(list(map(int, input().split())), dtype=np.int64)
U = list(np.unique(A, return_counts = True))
U[1] = np.subtract(U[1],1)
max(U[1])
len(U[1])
sum(U[1])

if max(U[1]) > (sum(U[1]) - max(U[1])):
    res = max(U[1]) * 2 - sum(U[1])
else:
    res = sum(U[1]) % 2
print(len(U[1]) - res)

Submission status: Runtime Error

Solution code:
#include <iostream>
#include <boost/algorithm/string.hpp>
#include <vector>
#include <map>
using namespace std;

int main(){
  int n;
  cin >> n;
  vector<int> v;
  for(int i = 0; i < n; i++){
    int t;
    cin >> t;
    v.push_back(t);
  }
  sort(v.begin(),v.end());

  map<int, int> counter;
  for(int i = 0; i < n; i++){
    if(counter.count(v[i]) != 0){
      counter[v[i]]++;
    }else{
      counter[v[i]] = 1;
    }
  }

  while(true){
    int l = -1;
    int r = -1;
    for(int i = 0; i < n; i++){
      if(counter[v[i]] > 1){
        if(l == -1){
          l = v[i];
        }
        r = v[i];
      }
    }
    if(r == -1){
      break;
    }
    counter[l]--;
    counter[r]--;
  }

  int result = 0;
  for(auto itr = counter.begin(); itr != counter.end(); ++itr){
    if(itr->second > 0){
      result++;
    }
  }

  cout << result << endl;
}