n-Way Tie

Codeforces

IDCF10074K

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

In the country of Tieland, there is an annual tie tying tournament that hosts n participants numbered with integers from 1 to n. Each two participants meet exactly once and have a match in tie tying. There is a winner and a loser in each of the matches. A participant obtains a point for each match victory, and the loser gets zero points for that match. The score of the participant is the total number of points he earned. However, the jury is worried of the scenario in which all participants have exactly the same score; in other words, there is an n-way tie. In that case any participant would be both the winner and the loser of the competition, which is absurd! Alas, the jury is tied up with the organisation of the tournament; help them and find out whether such a situation might occur! The single line of the input contains an integer n (1 ≤ n ≤ 1000), the number of participants. If such a scenario is possible, output "_Yes_" in the first line. Then output n - 1 lines, the i-th containing n - i space-separated integers. The j-th number of the i-th line aij should denote the outcome of the match between participants with numbers i and i + j: If such a scenario is not possible, output "_No_" in a single line. ## Input The single line of the input contains an integer n (1 ≤ n ≤ 1000), the number of participants. ## Output If such a scenario is possible, output "_Yes_" in the first line. Then output n - 1 lines, the i-th containing n - i space-separated integers. The j-th number of the i-th line aij should denote the outcome of the match between participants with numbers i and i + j: aij = 1, if the i-th participant won the match; aij = 0, if the (i + j)-th participant won the match. If multiple solutions exists, output any of them.If such a scenario is not possible, output "_No_" in a single line. [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of participants. Let $ G = (V, E) $ be a complete directed graph with $ V = \{1, 2, \dots, n\} $, where each directed edge $ i \to j $ ($ i \ne j $) represents a match with $ i $ defeating $ j $. **Constraints** 1. $ 1 \le n \le 1000 $ 2. Each pair $ (i, j) $ with $ i < j $ has exactly one directed edge: either $ i \to j $ or $ j \to i $. 3. The out-degree of each vertex $ i $ (i.e., number of wins) must be equal for all $ i \in V $. **Objective** Determine whether there exists a tournament orientation of $ K_n $ such that every vertex has out-degree $ \frac{n-1}{2} $. If possible, output: - "Yes" - For each $ i \in \{1, \dots, n-1\} $, output $ n - i $ integers: for each $ j \in \{1, \dots, n-i\} $, output $ 1 $ if $ i $ beats $ i+j $, else $ 0 $. If not possible, output: - "No"

API Response (JSON)

{
  "problem": {
    "name": "n-Way Tie",
    "description": {
      "content": "In the country of Tieland, there is an annual tie tying tournament that hosts n participants numbered with integers from 1 to n. Each two participants meet exactly once and have a match in tie tying. ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10074K"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In the country of Tieland, there is an annual tie tying tournament that hosts n participants numbered with integers from 1 to n. Each two participants meet exactly once and have a match in tie tying. ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of participants.  \nLet $ G = (V, E) $ be a complete directed graph with $ V = \\{1, 2, \\dots, n\\} $, where each directed edge $ i \\to j $ ($ i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments