C. Triangles

Codeforces
IDCF10097C
Time2000ms
Memory256MB
Difficulty
English · Original
Formal · Original
There is a set of n segments with the lengths li. Find a segment with an integer length so that it could form a non-degenerate triangle with any two segments from the set, or tell that such segment doesn't exist. The first line contains a single integer n (2 ≤ n ≤ 200000) — the number of segments in the set. The second line contains n integers li separated by spaces (1 ≤ li ≤ 109) — the lengths of the segments in the set. If the required segment exists, in the first line output «_YES_» (without quotes). In this case in the second line output a single integer x — the length of the needed segment. If there are many such segments, output any of them. If the required segment doesn't exist, output «_NO_» (without quotes). ## Input The first line contains a single integer n (2 ≤ n ≤ 200000) — the number of segments in the set.The second line contains n integers li separated by spaces (1 ≤ li ≤ 109) — the lengths of the segments in the set. ## Output If the required segment exists, in the first line output «_YES_» (without quotes). In this case in the second line output a single integer x — the length of the needed segment. If there are many such segments, output any of them.If the required segment doesn't exist, output «_NO_» (without quotes). [samples]
**Definitions** Let $ n \in \mathbb{Z} $ be the number of segments, with $ 2 \leq n \leq 200000 $. Let $ L = \{l_1, l_2, \dots, l_n\} $ be a multiset of positive integers representing the lengths of the segments, where $ 1 \leq l_i \leq 10^9 $. **Constraints** All $ l_i \in \mathbb{Z}^+ $. **Objective** Determine whether there exists an integer $ x \in \mathbb{Z}^+ $ such that for every pair of distinct segments $ l_i, l_j \in L $, the triple $ (l_i, l_j, x) $ forms a non-degenerate triangle. That is, for all $ i \neq j $, the triangle inequalities hold: $$ l_i + l_j > x, \quad l_i + x > l_j, \quad l_j + x > l_i. $$ Equivalently, $ x $ must satisfy: $$ x > \max_{i \neq j} \left( |l_i - l_j| \right) \quad \text{and} \quad x < \min_{i \neq j} (l_i + l_j). $$ But since the condition must hold for **all pairs**, it suffices to require: $$ x > \max_{1 \leq i < j \leq n} |l_i - l_j| = \max L - \min L, $$ and $$ x < \min_{1 \leq i < j \leq n} (l_i + l_j). $$ Let $ M = \max L $, $ m = \min L $, and $ s = \min_{i \neq j} (l_i + l_j) $. Then, such an integer $ x $ exists if and only if: $$ M - m < s - 1, $$ and in that case, any integer $ x \in (M - m,\, s) $ is valid (e.g., $ x = M - m + 1 $). **Output** If such $ x $ exists, output: ``` YES x ``` Otherwise, output: ``` NO ```
API Response (JSON)
{
  "problem": {
    "name": "C. Triangles",
    "description": {
      "content": "There is a set of n segments with the lengths li. Find a segment with an integer length so that it could form a non-degenerate triangle with any two segments from the set, or tell that such segment do",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10097C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There is a set of n segments with the lengths li. Find a segment with an integer length so that it could form a non-degenerate triangle with any two segments from the set, or tell that such segment do...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of segments, with $ 2 \\leq n \\leq 200000 $.  \nLet $ L = \\{l_1, l_2, \\dots, l_n\\} $ be a multiset of positive integers representing the lengths ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}
Full JSON Raw Segments