G. Locked Out

Codeforces

IDCF10275G

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Gloria is a ravenous reader and has recently been enraptured by Shakespeare's 'Othello'. Lucky for her, this new time travel device provided her the perfect opportunity to go back in time to November 1, 1604, and watch her favorite play in person. Gloria dresses up in her finest Shakespearean-era attire and zooms back in time. To prevent the time travel machine from ending up in the wrong hands, each user is given a specific numeric password and a set of recovery codes in case they forget the password. Gloria reaches the Whitehall Palace just in time for the show and after an enthralling three and a half hours, she returned to her time travel machine only to realize that she has forgotten her password! Luckily, she had the foresight to bring her tablet with the recovery codes on her. However, the effect of time travel on such electronics was unfortunately still not completely mitigated so some of the bits in the tablet got shifted around. Fortunately, Gloria knows that each of the recovery code numbers was rearranged in the exact same way and that her password is the smallest possible difference between the maximum recovery code and the minimum recovery code. Help Gloria recover her password! That is, given the list of $n$ rearranged recovery codes, each of which is exactly $k$ digits, permute all of the numbers in the exact same way in order to get the minimum possible difference between the maximum and minimum recovery code after the permutation. The first line of the input will contain two space-separated integers, $n$ and $k$ (where $2 <= n <= 100$ and $1 <= k <= 9$). $n$ lines of input will then follow, each line containing a single integer $x_i$ ($0 <= x_i <= 10^k -1$) which will have exactly $k$ digits (the number can contain leading zeros). A single integer representing Gloria's password aka the minimum difference between the maximum and minimum recovery code after the permutation. ## Input The first line of the input will contain two space-separated integers, $n$ and $k$ (where $2 <= n <= 100$ and $1 <= k <= 9$).$n$ lines of input will then follow, each line containing a single integer $x_i$ ($0 <= x_i <= 10^k -1$) which will have exactly $k$ digits (the number can contain leading zeros). ## Output A single integer representing Gloria's password aka the minimum difference between the maximum and minimum recovery code after the permutation. [samples]

**Definitions** Let $ n, k \in \mathbb{Z} $ with $ 2 \leq n \leq 100 $ and $ 1 \leq k \leq 9 $. Let $ X = \{x_1, x_2, \dots, x_n\} $ be a set of $ n $ integers, each represented as a $ k $-digit string (with leading zeros allowed). **Constraints** Each $ x_i \in [0, 10^k - 1] $, and is padded to exactly $ k $ digits. **Objective** Find a permutation $ \pi $ of the digit positions $ \{0, 1, \dots, k-1\} $ (i.e., a reordering of the digits in each number) such that, when applied uniformly to all numbers in $ X $, the resulting set $ X' = \{x_1', x_2', \dots, x_n'\} $ minimizes: $$ \max(X') - \min(X') $$ Output the minimal possible value of $ \max(X') - \min(X') $.

API Response (JSON)

{
  "problem": {
    "name": "G. Locked Out",
    "description": {
      "content": "Gloria is a ravenous reader and has recently been enraptured by Shakespeare's 'Othello'. Lucky for her, this new time travel device provided her the perfect opportunity to go back in time to November ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10275G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Gloria is a ravenous reader and has recently been enraptured by Shakespeare's 'Othello'. Lucky for her, this new time travel device provided her the perfect opportunity to go back in time to November ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 100 $ and $ 1 \\leq k \\leq 9 $.  \nLet $ X = \\{x_1, x_2, \\dots, x_n\\} $ be a set of $ n $ integers, each represented as a $ k $-digit s...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments