B. A Lot of Joy

Codeforces

IDCF10018B

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

Two boys Gena and Petya wrote on two strips of paper the same string s that consisted of lowercase Latin letters. Then each boy took one strip, cut it into small pieces so that each piece contained exactly one letter and put all pieces into his pocket. After that Gena and Petya repeated the following procedure until their pockets became empty: they took one piece from their pockets and rejoiced if the letters on these pieces were equal. Determine the expected number of times the boys rejoiced during this process. The input contains the only string s which was initially written on Gena's and Petya's strips. The string has length between 1 and 200000, inclusively, and consists of lowercase Latin letters. Output the only real number — the expected number of times Gena and Petya rejoiced during their business. The absolute or relative error of the answer should not exceed 10 - 9. ## Input The input contains the only string s which was initially written on Gena's and Petya's strips. The string has length between 1 and 200000, inclusively, and consists of lowercase Latin letters. ## Output Output the only real number — the expected number of times Gena and Petya rejoiced during their business. The absolute or relative error of the answer should not exceed 10 - 9. [samples]

**Definitions** Let $ s = s_1 s_2 \dots s_n $ be a string of length $ n $, where $ s_i \in \{a, b, \dots, z\} $ for all $ i \in \{1, \dots, n\} $. Let $ X $ be the random variable denoting the number of times Gena and Petya draw the same letter during the process, where each independently permutes their $ n $ letter pieces uniformly at random and draws them one-by-one in order. **Objective** Compute $ \mathbb{E}[X] $, the expected number of matches between the two random permutations of $ s $. **Key Insight** For each position $ i \in \{1, \dots, n\} $, define indicator random variable: $$ X_i = \begin{cases} 1 & \text{if the } i\text{-th drawn letters from Gena and Petya are equal} \\ 0 & \text{otherwise} \end{cases} $$ Then $ X = \sum_{i=1}^n X_i $, and by linearity of expectation: $$ \mathbb{E}[X] = \sum_{i=1}^n \mathbb{E}[X_i] $$ For each $ i $, $ \mathbb{E}[X_i] = \mathbb{P}(\text{Gena's } i\text{-th letter} = \text{Petya's } i\text{-th letter}) $ Since both permutations are uniform and independent, for a fixed letter $ c $ appearing $ f_c $ times in $ s $, the probability that both draw $ c $ at position $ i $ is: $$ \sum_{c \in \Sigma} \left( \frac{f_c}{n} \cdot \frac{f_c}{n} \right) = \sum_{c \in \Sigma} \left( \frac{f_c}{n} \right)^2 $$ Thus: $$ \mathbb{E}[X] = n \cdot \sum_{c \in \Sigma} \left( \frac{f_c}{n} \right)^2 = \sum_{c \in \Sigma} \frac{f_c^2}{n} $$ **Final Expression** $$ \boxed{\mathbb{E}[X] = \frac{1}{n} \sum_{c \in \Sigma} f_c^2} $$ where $ f_c $ is the frequency of character $ c $ in string $ s $, and $ n = |s| $.

API Response (JSON)

{
  "problem": {
    "name": "B. A Lot of Joy",
    "description": {
      "content": "Two boys Gena and Petya wrote on two strips of paper the same string s that consisted of lowercase Latin letters. Then each boy took one strip, cut it into small pieces so that each piece contained ex",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10018B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Two boys Gena and Petya wrote on two strips of paper the same string s that consisted of lowercase Latin letters. Then each boy took one strip, cut it into small pieces so that each piece contained ex...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ s = s_1 s_2 \\dots s_n $ be a string of length $ n $, where $ s_i \\in \\{a, b, \\dots, z\\} $ for all $ i \\in \\{1, \\dots, n\\} $.  \n\nLet $ X $ be the random variable denoting the nu...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments