E. Collection

Codeforces

IDCF10159E

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

Alan recently started collecting the cards of the well known "Famous Computer Scientists" card game by the ACM. As buying cards is starting to get expensive, he would like to start trading. To do this, he needs to know the number of duplicate cards in his collection. Write a program to help him calculate this number. The first line contains a single integer n, the number of cards in Alan's collection. The second line contains n integers ci, where ci is the id of the i-th card. It holds that 1 ≤ n ≤ 200'000 and 0 ≤ ci ≤ 109. Print a single integer denoting the number of duplicates, that is the number of cards he can safely trade whilst still having the same number of unique cards. ## Input The first line contains a single integer n, the number of cards in Alan's collection. The second line contains n integers ci, where ci is the id of the i-th card. It holds that 1 ≤ n ≤ 200'000 and 0 ≤ ci ≤ 109. ## Output Print a single integer denoting the number of duplicates, that is the number of cards he can safely trade whilst still having the same number of unique cards. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the number of cards in Alan's collection. Let $ C = (c_1, c_2, \dots, c_n) $ be a sequence of integers representing card IDs, where $ c_i \in \mathbb{Z} $ and $ 0 \leq c_i \leq 10^9 $. **Constraints** 1. $ 1 \leq n \leq 200{,}000 $ 2. $ 0 \leq c_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Compute the number of duplicate cards, defined as: $$ n - |\{c_1, c_2, \dots, c_n\}| $$

API Response (JSON)

{
  "problem": {
    "name": "E. Collection",
    "description": {
      "content": "Alan recently started collecting the cards of the well known \"Famous Computer Scientists\" card game by the ACM. As buying cards is starting to get expensive, he would like to start trading. To do this",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10159E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Alan recently started collecting the cards of the well known \"Famous Computer Scientists\" card game by the ACM. As buying cards is starting to get expensive, he would like to start trading. To do this...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of cards in Alan's collection.  \nLet $ C = (c_1, c_2, \\dots, c_n) $ be a sequence of integers representing card IDs, where $ c_i \\in \\mathbb{Z}...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments