I. Abu Tahun Mod problem

Codeforces

IDCF10203I

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Abu Tahun loves palindromes. An array is palindrome if it reads the same backwards and forwards, for example arrays ${1}$, ${1, 1, 1}$, ${1, 2, 1}$ , ${1, 3, 2, 3, 1}$ are palindrome, but arrays ${11, 3, 5, 11}$, ${1, 12}$ are not. Abu Tahun has an array of $n$ integers $A$. He wants his array to be palindrome. He can choose an integer $m$, then change the value of all $A_i$ $(1 <= i <= n)$ to ($A_i mod m$). what is the maximum value of $m$ he can choose, such that the array becomes palindrome? The first line of input contains a single integer $n$ $(1 <= n <= 10^5)$ The second line contains integers $A_1$,$A_2$,...,$A_n$ $(1 <= A_i <= 10^9)$ Print the maximum value of $m$ Abu Tahun can choose, if $m$ is arbitrarily large print -1. ## Input The first line of input contains a single integer $n$ $(1 <= n <= 10^5)$The second line contains integers $A_1$,$A_2$,...,$A_n$ $(1 <= A_i <= 10^9)$ ## Output Print the maximum value of $m$ Abu Tahun can choose, if $m$ is arbitrarily large print -1. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the length of the array. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of positive integers. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 1 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $ **Objective** Find the maximum integer $ m \geq 1 $ such that the array $ B = (a_1 \bmod m, a_2 \bmod m, \dots, a_n \bmod m) $ is a palindrome. If no such maximum exists (i.e., $ m $ can be arbitrarily large), output $ -1 $. **Key Condition** For $ B $ to be a palindrome: $$ a_i \bmod m = a_{n+1-i} \bmod m \quad \forall i \in \{1, \dots, \lfloor n/2 \rfloor\} $$ This is equivalent to: $$ m \mid (a_i - a_{n+1-i}) \quad \forall i \in \{1, \dots, \lfloor n/2 \rfloor\} $$ Let $ D = \{ |a_i - a_{n+1-i}| \mid i = 1, \dots, \lfloor n/2 \rfloor \} \setminus \{0\} $. Then $ m $ must divide $ \gcd(D) $ if $ D \neq \emptyset $. If $ D = \emptyset $, then $ a_i = a_{n+1-i} $ for all $ i $, so the array is already a palindrome, and $ m $ can be arbitrarily large → output $ -1 $. Otherwise, the maximum such $ m $ is $ \gcd(D) $.

API Response (JSON)

{
  "problem": {
    "name": "I. Abu Tahun Mod problem",
    "description": {
      "content": "Abu Tahun loves palindromes. An array is palindrome if it reads the same backwards and forwards, for example arrays ${1}$, ${1, 1, 1}$, ${1, 2, 1}$ , ${1, 3, 2, 3, 1}$ are palindrome, but arrays ${11",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10203I"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Abu Tahun loves palindromes.\n\nAn array is palindrome if it reads the same backwards and forwards, for example arrays ${1}$, ${1, 1, 1}$, ${1, 2, 1}$ , ${1, 3, 2, 3, 1}$ are palindrome, but arrays ${11...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the array.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of positive integers.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $  \n2. $ ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments