127. Latin Squares

Codeforces

IDCF10269127

Time8000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

A _latin square_ is defined as a 4 by 4 grid of numbers, where all of the numbers in each row and column are distinct, i.e. no two pairs of elements in each row and column are equal. You're given a partially filled in latin square. Figure out how many valid latin squares can be formed by filling in the empty digits of the latin square. The input consists of 4 lines, each consisting of 4 integers: the digits in the latin square. For each digit, if it has already been filled in, it will be represented with a digit from 1 to 4, and if it hasn't been filled in yet, it will be represented with a "0". Output a single positive integer $n$: the number of ways to fill in the latin square as described above. ## Input The input consists of 4 lines, each consisting of 4 integers: the digits in the latin square. For each digit, if it has already been filled in, it will be represented with a digit from 1 to 4, and if it hasn't been filled in yet, it will be represented with a "0". ## Output Output a single positive integer $n$: the number of ways to fill in the latin square as described above. [samples]

**Definitions** Let $ L \in \{0,1,2,3,4\}^{4 \times 4} $ be a partial Latin square, where $ L_{i,j} \in \{1,2,3,4\} $ if filled, and $ L_{i,j} = 0 $ if empty. **Constraints** 1. For each row $ i \in \{1,2,3,4\} $, all non-zero entries are distinct. 2. For each column $ j \in \{1,2,3,4\} $, all non-zero entries are distinct. 3. Any complete filling must result in a Latin square: each row and each column is a permutation of $ \{1,2,3,4\} $. **Objective** Count the number of completions $ L' \in \{1,2,3,4\}^{4 \times 4} $ such that: - $ L'_{i,j} = L_{i,j} $ for all $ (i,j) $ where $ L_{i,j} \neq 0 $, - Each row of $ L' $ is a permutation of $ \{1,2,3,4\} $, - Each column of $ L' $ is a permutation of $ \{1,2,3,4\} $.

API Response (JSON)

{
  "problem": {
    "name": "127. Latin Squares",
    "description": {
      "content": "A _latin square_ is defined as a 4 by 4 grid of numbers, where all of the numbers in each row and column are distinct, i.e. no two pairs of elements in each row and column are equal.  You're given a ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10269127"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "A _latin square_ is defined as a 4 by 4 grid of numbers, where all of the numbers in each row and column are distinct, i.e. no two pairs of elements in each row and column are equal. \n\nYou're given a ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ L \\in \\{0,1,2,3,4\\}^{4 \\times 4} $ be a partial Latin square, where $ L_{i,j} \\in \\{1,2,3,4\\} $ if filled, and $ L_{i,j} = 0 $ if empty.\n\n**Constraints**  \n1. For each row $ i ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments