B. Associativity Degree

Codeforces

IDCF10212B

Time6000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Consider a binary operation $compose$ defined on numbers $1$ through $n$: $$\circ : \{1,\dots,n\} \times \{1,\dots,n\} \to \{1,\dots,n\}\text{.}$$ Let us define its _associativity degree_ as the number of triplets $i, j, k in {1, \\dots, n}$ for which $compose$ is associative: $$i \circ (j \circ k) = (i \circ j) \circ k\text{.}$$ Your task is, given $n$ and $k$, to construct an operation $compose$ such that its associativity degree is exactly $k$. The first line of input contains two integers $n$ and $q$ ($1 <= n <= 64$, $1 <= q dot.op n^2 <= 10^6$). The $i$-th of the next $q$ lines contains a single integer $k_i$ ($0 <= k_i <= n^3$). It is guaranteed that all $k_i$ are distinct. For each given value of $k_i$, do the following: If there is no operation $compose$ with associativity degree $k_i$ for given $n$, output "_NO_" on a single line. Otherwise, output "_YES_" on the first line, followed by $n$ lines containing $n$ integers each. The $j$-th integer in the $i$-th line must be equal to $i compose j$. The operation from the first sample can be concisely described as $i compose j = 1 + ((i -1) dot.op (j -1)) bmod 3$, and it is fully associative. ## Input The first line of input contains two integers $n$ and $q$ ($1 <= n <= 64$, $1 <= q dot.op n^2 <= 10^6$).The $i$-th of the next $q$ lines contains a single integer $k_i$ ($0 <= k_i <= n^3$). It is guaranteed that all $k_i$ are distinct. ## Output For each given value of $k_i$, do the following:If there is no operation $compose$ with associativity degree $k_i$ for given $n$, output "_NO_" on a single line.Otherwise, output "_YES_" on the first line, followed by $n$ lines containing $n$ integers each. The $j$-th integer in the $i$-th line must be equal to $i compose j$. [samples] ## Note The operation from the first sample can be concisely described as $i compose j = 1 + ((i -1) dot.op (j -1)) bmod 3$, and it is fully associative.

**Definitions** Let $ n \in \mathbb{Z}^+ $, $ n \leq 64 $. Let $ \circ : \{1,\dots,n\} \times \{1,\dots,n\} \to \{1,\dots,n\} $ be a binary operation. The *associativity degree* of $ \circ $ is: $$ \left| \left\{ (i,j,k) \in \{1,\dots,n\}^3 \mid i \circ (j \circ k) = (i \circ j) \circ k \right\} \right| $$ **Given** For each query $ k_i \in \mathbb{Z} $, $ 0 \leq k_i \leq n^3 $, determine if there exists an operation $ \circ $ with associativity degree exactly $ k_i $. **Objective** For each $ k_i $: - If no such $ \circ $ exists, output "NO". - Otherwise, output "YES" followed by an $ n \times n $ matrix $ M $, where $ M[i][j] = i \circ j $.

API Response (JSON)

{
  "problem": {
    "name": "B. Associativity Degree",
    "description": {
      "content": "Consider a binary operation $compose$ defined on numbers $1$ through $n$: $$\\circ : \\{1,\\dots,n\\} \\times \\{1,\\dots,n\\} \\to \\{1,\\dots,n\\}\\text{.}$$ Let us define its _associativity degree_ as the numb",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 6000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10212B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Consider a binary operation $compose$ defined on numbers $1$ through $n$: $$\\circ : \\{1,\\dots,n\\} \\times \\{1,\\dots,n\\} \\to \\{1,\\dots,n\\}\\text{.}$$\n\nLet us define its _associativity degree_ as the numb...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ n \\leq 64 $.  \nLet $ \\circ : \\{1,\\dots,n\\} \\times \\{1,\\dots,n\\} \\to \\{1,\\dots,n\\} $ be a binary operation.  \nThe *associativity degree* of $ \\circ $ is:...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments