E. Hieroglyph Sequences

Codeforces

IDCF10275E

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Sylvia has been fascinated with Ancient Egypt and used her brand-new time machine to go back in time to the era of her favorite king, Ramses II. While King Ramses II was a highly successful leader, he was also highly eccentric and during her adventures, Sylvia found out that he had a very particular property that all hieroglyph sequences should follow in order for him to read it. Each hieroglyph in the alphabet was assigned a unique number and King Ramses only accepted the message if the bit-wise XOR of all the numbers in the sequence was equal to $0$. Unfortunately, Sylvia did not know this before traveling back in time so she doesn't know if the message that she wrote for him satisfies his eccentric request. She also doesn't have too much time before her meeting with the King. Thus, she decides she will replace the minimum hieroglyphs possible in order to make the sequence fit his constraints. Given the numerical representation of the hieroglyphs that Sylvia has written, help her figure out the minimum number of elements in the sequence that need to be replaced in order to make the bitwise XOR of the sequence equal to $0$. Note: The XOR between two bits is defined as a function that returns 1 if *exactly* one of the bits is a 1 and 0 otherwise. The bitwise XOR between two numbers is applying the XOR function on each of the corresponding bits (the last bit of the output is the XOR between the last bits of each of the input numbers and the second-to-last bit of output is the XOR of second-to-last bits of input and so on). The first line of input will be a single integer $n$ (where $2 <= n <= 10^4$). The second line of input will contain $n$ space-separated integers representing the elements in the sequence where $1 <= h_i <= 10^9$. Output a single integer representing the minimum number of elements in the sequence that need to be replaced in order to make the bitwise XOR of the sequence equal to 0. In the first sample test case, we can replace the first element with a 12 and then the bitwise XOR of the elements in the sequence is zero so the answer is 1. In the second test case, the bitwise XOR of the elements is already zero so the answer is 0. ## Input The first line of input will be a single integer $n$ (where $2 <= n <= 10^4$).The second line of input will contain $n$ space-separated integers representing the elements in the sequence where $1 <= h_i <= 10^9$. ## Output Output a single integer representing the minimum number of elements in the sequence that need to be replaced in order to make the bitwise XOR of the sequence equal to 0. [samples] ## Note In the first sample test case, we can replace the first element with a 12 and then the bitwise XOR of the elements in the sequence is zero so the answer is 1. In the second test case, the bitwise XOR of the elements is already zero so the answer is 0.

**Definitions** Let $ n \in \mathbb{Z} $ be the length of the sequence. Let $ H = (h_1, h_2, \dots, h_n) $ be a sequence of positive integers, where $ h_i \in \mathbb{Z}^+ $. Let $ X = \bigoplus_{i=1}^n h_i $ denote the bitwise XOR of all elements in $ H $. **Constraints** 1. $ 2 \leq n \leq 10^4 $ 2. $ 1 \leq h_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Find the minimum number of elements in $ H $ that must be replaced (with any positive integers) such that the XOR of the resulting sequence equals $ 0 $. That is, find the smallest $ k \in \mathbb{Z}_{\geq 0} $ such that there exists a sequence $ H' $ with exactly $ n - k $ elements unchanged from $ H $, and $ \bigoplus_{i=1}^n h_i' = 0 $.

API Response (JSON)

{
  "problem": {
    "name": "E. Hieroglyph Sequences",
    "description": {
      "content": "Sylvia has been fascinated with Ancient Egypt and used her brand-new time machine to go back in time to the era of her favorite king, Ramses II. While King Ramses II was a highly successful leader, he",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10275E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Sylvia has been fascinated with Ancient Egypt and used her brand-new time machine to go back in time to the era of her favorite king, Ramses II. While King Ramses II was a highly successful leader, he...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the sequence.  \nLet $ H = (h_1, h_2, \\dots, h_n) $ be a sequence of positive integers, where $ h_i \\in \\mathbb{Z}^+ $.\n\nLet $ X = \\bigoplus_...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments