C. Smiley Faces (C)

Codeforces

IDCF10140C

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Mr. Light is not satisfied with the number of smiley faces in his string. Now he wants to mirror exactly one substring (one or more consecutive characters in the string) to increase the number of smiley faces as possible. Can you find the maximum number of smiley faces he can achieve? The input contains a non-empty string of no more than 2 × 105 characters. Each character is either ':', '(', or ')'. Print the maximum number of smiley faces Mr. Light can achieve by mirroring exactly one substring. ## Input The input contains a non-empty string of no more than 2 × 105 characters. Each character is either ':', '(', or ')'. ## Output Print the maximum number of smiley faces Mr. Light can achieve by mirroring exactly one substring. [samples]

**Definitions** Let $ s \in \{':', '(', ')'\}^* $ be the input string of length $ n \leq 2 \times 10^5 $. A *smiley face* is a substring `":)"`. Let $ \text{count}(s) $ denote the number of occurrences of `":)"` in $ s $. **Operation** For any substring $ s[i:j] $ (inclusive indices, $ 1 \leq i \leq j \leq n $), define its *mirror* as the reversed substring: $ \text{mirror}(s[i:j]) = s[j]s[j-1]\dots s[i] $. Let $ s' $ be the string obtained by replacing $ s[i:j] $ with $ \text{mirror}(s[i:j]) $. **Objective** Maximize $ \text{count}(s') $ over all possible choices of substring $ s[i:j] $ to mirror: $$ \max_{1 \leq i \leq j \leq n} \text{count}\left( s[1:i-1] + \text{mirror}(s[i:j]) + s[j+1:n] \right) $$

API Response (JSON)

{
  "problem": {
    "name": "C. Smiley Faces (C)",
    "description": {
      "content": "Mr. Light is not satisfied with the number of smiley faces in his string. Now he wants to mirror exactly one substring (one or more consecutive characters in the string) to increase the number of smil",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10140C"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mr. Light is not satisfied with the number of smiley faces in his string. Now he wants to mirror exactly one substring (one or more consecutive characters in the string) to increase the number of smil...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{':', '(', ')'\\}^* $ be the input string of length $ n \\leq 2 \\times 10^5 $.  \nA *smiley face* is a substring `\":)\"`.  \nLet $ \\text{count}(s) $ denote the number of occu...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments