H. Happy game

Codeforces

IDCF10270H

Time1000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Teresa and Fabio are wandering in the UNAL campus waiting for Nick to get out of classes for lunch. They are getting bored, Teresa came up with a game. They will play on the only street of the campus, the street is a straight line divided by labeled cells. The game consists of many rounds. In each round, both of them will select 2 different cells from the street. They will stand at each chosen cell watching to each other, then they will start walking to each other $1$ step at a time until they meet at some point, either inside a cell or at the border of a cell. A round is called happy if at each step the label of both cells where they are standing is the same, and they meet inside a cell, not at the border. Nick could go out of class at any moment, so to maximize their fun, they are not gonna do rounds that are not happy. Also, they don't want to repeat any round, two rounds are considered equal if the labels while walking are the same in both rounds for Teresa and Fabio. For example, if the labels on the street are _ababa_ a round with Fabio selecting cell 1 and Teresa selecting cell 3 is equal to a round with Fabio selecting cell 5 and Teresa selecting cell 3. Can you determine the maximum number of happy rounds they would do? The first line contains an integer $n$ ($1 <= n <= 10^5$) — The number of cells on the street. Following line will contains $n$ lowercase english letters, which correspond to the labels of the street in order (from cell $1$ to cell $n$). Print one integer that represents the maximum number of rounds the game could last. ## Input The first line contains an integer $n$ ($1 <= n <= 10^5$) — The number of cells on the street.Following line will contains $n$ lowercase english letters, which correspond to the labels of the street in order (from cell $1$ to cell $n$). ## Output Print one integer that represents the maximum number of rounds the game could last. [samples]

**Definitions** Let $ s \in \Sigma^n $ be a string of length $ n $, where $ \Sigma $ is the set of lowercase English letters, representing the labels of the $ n $ cells in order. **Constraints** $ 1 \le n \le 10^5 $ **Objective** Count the number of unordered pairs of distinct indices $ (i, j) $, $ 1 \le i < j \le n $, such that: 1. $ s[i] = s[j] $, and 2. $ j - i $ is even (so they meet inside a cell, not at a border). That is, compute: $$ \sum_{\substack{1 \le i < j \le n \\ s[i] = s[j] \\ (j - i) \text{ even}}} 1 $$

API Response (JSON)

{
  "problem": {
    "name": "H. Happy game",
    "description": {
      "content": "Teresa and Fabio are wandering in the UNAL campus waiting for Nick to get out of classes for lunch. They are getting bored, Teresa came up with a game. They will play on the only street of the campus",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10270H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Teresa and Fabio are wandering in the UNAL campus waiting for Nick to get out of classes for lunch. They are getting bored, Teresa came up with a game.\n\nThey will play on the only street of the campus...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s \\in \\Sigma^n $ be a string of length $ n $, where $ \\Sigma $ is the set of lowercase English letters, representing the labels of the $ n $ cells in order.\n\n**Constraints**  \n...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments