G. Letters Among Us

Codeforces

IDCF10274G

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Toast is currently a crewmate on the Skeld, and unfortunately, unbeknownst to him, there has been a new task added! He's struggling a lot with this new task, so much so that Toast is a bit suspicious that the imposters might have already claimed a few crewmates. Just as he wants to give up on the task to check out his fellow crewmates, he sees Abe walk up behind him. Obviously, he does not want to fake a task. Help Toast finish his task so he can win the game! The new task has a grid of $n times m$ consisting of lower case English letters. Toast is allowed to remove any column of letters. The goal here is to remove the smallest number of columns required such that after all the removals, the rows are ordered from top to bottom lexicographically. Specifically, any row cannot be lexicographically smaller than a previous one, but it can be equal. Determine the minimum number of columns required to be removed to make this the case. Note that it may be the case that every column needs to be removed. The first line contains two integers $n$ and $m$ $(1 <= n, m <= 10^2)$. The next $n$ lines each contain $m$ lowercase English letters, which are the characters in the grid. A single integer detailing the minimum number of columns that need to be removed. ## Input The first line contains two integers $n$ and $m$ $(1 <= n, m <= 10^2)$. The next $n$ lines each contain $m$ lowercase English letters, which are the characters in the grid. ## Output A single integer detailing the minimum number of columns that need to be removed. [samples]

**Definitions** Let $ n, m \in \mathbb{Z}^+ $ with $ 1 \leq n, m \leq 100 $. Let $ G = (g_{i,j}) \in \{a, b, \dots, z\}^{n \times m} $ be a grid of lowercase English letters, where $ g_{i,j} $ denotes the character in row $ i $, column $ j $. **Constraints** The grid has $ n $ rows and $ m $ columns. **Objective** Find the minimum number of columns to remove such that the resulting grid (after removal) has rows that are non-decreasing in lexicographical order: $$ \forall i \in \{1, \dots, n-1\}, \quad \text{row}_i \leq_{\text{lex}} \text{row}_{i+1} $$ where $ \text{row}_i = (g_{i,j_1}, g_{i,j_2}, \dots, g_{i,j_k}) $ for the remaining column indices $ j_1 < j_2 < \dots < j_k $. Equivalently, maximize the number of columns retained such that the above lexicographic condition holds, then return $ m - (\text{max retained columns}) $.

API Response (JSON)

{
  "problem": {
    "name": "G. Letters Among Us",
    "description": {
      "content": "Toast is currently a crewmate on the Skeld, and unfortunately, unbeknownst to him, there has been a new task added! He's struggling a lot with this new task, so much so that Toast is a bit suspicious ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10274G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Toast is currently a crewmate on the Skeld, and unfortunately, unbeknownst to him, there has been a new task added! He's struggling a lot with this new task, so much so that Toast is a bit suspicious ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, m \\leq 100 $.  \nLet $ G = (g_{i,j}) \\in \\{a, b, \\dots, z\\}^{n \\times m} $ be a grid of lowercase English letters, where $ g_{i,j} $ den...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments