B. Smiley Faces (B)

Codeforces

IDCF10140B

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Mr. Light now have a string that consists only of the three characters: ':', '(', and ')'. Mr. Light considers a colon ‘:’ followed by a closing bracket ')' as a smiley face. So ":)" is a smiley face while "(:" is not. Now he wants to choose exactly one prefix (one or more characters at the beginning) of this string and mirror it (reverse it and flip the brackets). For example, the string ":):((" mirrored is ")):(:". What is the maximum number of smiley faces Mr. Light can get in the string after mirroring exactly one prefix? 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 get after mirroring exactly one prefix. ## 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 get after mirroring exactly one prefix. [samples]

**Definitions** Let $ s \in \{':', '(', ')'\}^* $ be the input string of length $ n $. Let $ \text{smiley}(s) $ denote the number of occurrences of the substring ":)" in $ s $. For any prefix length $ k \in \{1, 2, \dots, n\} $, define the operation $ M_k(s) $: - Mirror the prefix $ s[1..k] $: reverse it and flip each bracket: - $ '(' \leftrightarrow ')' $, - $ ':' $ remains unchanged. - Let $ s'_k = M_k(s) $ be the resulting string. **Constraints** $ 1 \leq n \leq 2 \times 10^5 $ **Objective** Maximize the number of smiley faces: $$ \max_{k \in \{1, \dots, n\}} \text{smiley}(s'_k) $$

API Response (JSON)

{
  "problem": {
    "name": "B. Smiley Faces (B)",
    "description": {
      "content": "Mr. Light now have a string that consists only of the three characters: ':', '(', and ')'. Mr. Light considers a colon ‘:’ followed by a closing bracket ')' as a smiley face. So \":)\" is a smiley face",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10140B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Mr. Light now have a string that consists only of the three characters: ':', '(', and ')'.\n\nMr. Light considers a colon ‘:’ followed by a closing bracket ')' as a smiley face. So \":)\" is a smiley face...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\{':', '(', ')'\\}^* $ be the input string of length $ n $.  \nLet $ \\text{smiley}(s) $ denote the number of occurrences of the substring \":)\" in $ s $.  \n\nFor any prefix l...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments