E. Snake Moves

Codeforces

IDCF10219E

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

You are playing the classical snake game on your phone, where a snake moves around on an infinite grid. However in this game, the snake has been programmed with a series of moves represented as a string. The characters 'U', 'D', 'L', and 'R' in the string cause the snake to move up, down, left, and right, respectively. The snake cannot visit the same cell twice in fear of colliding with itself. In this version of the game, you want to find out the longest substring of the string of moves such that the snake never visits the same cell twice. The first line of input is n (1 ≤ n ≤ 106), the length of the string of snake moves. The second line contains the string of snake moves where each character is in the set {'L', 'R', 'U', 'D'}. Output a single line with the length of the longest substring of moves such that the snake would not visit the same cell twice if it followed those moves. ## Input The first line of input is n (1 ≤ n ≤ 106), the length of the string of snake moves. The second line contains the string of snake moves where each character is in the set {'L', 'R', 'U', 'D'}. ## Output Output a single line with the length of the longest substring of moves such that the snake would not visit the same cell twice if it followed those moves. [samples]

**Definitions** Let $ s \in \{ \text{L}, \text{R}, \text{U}, \text{D} \}^n $ be a string of length $ n $, representing a sequence of moves. Let $ p: \{0, \dots, n\} \to \mathbb{Z}^2 $ be the position function, where $ p(0) = (0,0) $, and for $ i \geq 1 $: - $ p(i) = p(i-1) + \vec{v}(s_i) $, with $ \vec{v}(\text{L}) = (-1, 0) $, $ \vec{v}(\text{R}) = (1, 0) $, $ \vec{v}(\text{U}) = (0, 1) $, $ \vec{v}(\text{D}) = (0, -1) $. **Constraints** $ 1 \leq n \leq 10^6 $ **Objective** Find the maximum length $ \ell $ such that there exists a substring $ s[i:j] $ (with $ 0 \leq i < j \leq n $) of length $ \ell = j - i $, for which all positions $ p(i), p(i+1), \dots, p(j) $ are distinct. That is, maximize $ \ell = j - i $ subject to: $$ \left| \{ p(k) \mid k \in \{i, i+1, \dots, j\} \} \right| = j - i + 1 $$

API Response (JSON)

{
  "problem": {
    "name": "E. Snake Moves",
    "description": {
      "content": "You are playing the classical snake game on your phone, where a snake moves around on an infinite grid. However in this game, the snake has been programmed with a series of moves represented as a stri",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10219E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are playing the classical snake game on your phone, where a snake moves around on an infinite grid. However in this game, the snake has been programmed with a series of moves represented as a stri...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{ \\text{L}, \\text{R}, \\text{U}, \\text{D} \\}^n $ be a string of length $ n $, representing a sequence of moves.  \nLet $ p: \\{0, \\dots, n\\} \\to \\mathbb{Z}^2 $ be the posit...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments