E. Going in Circles

Codeforces

IDCF10108E

Time2000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

During the SCPC2015 celebration, and as Noura likes to keep everyone entertained, she wanted to play a game with the students and volunteers. She asked them to stand in a circle in order to assign them into 2 groups. The rules for forming the two groups are: Given a string that you should treat as a circle (which means that the last letter is a neighbor to the first one), calculate the number of ways to choose two ordered, non - overlapping substrings that represent the two groups and satisfy the given rules. The first line of input contains an integer T (1 ≤ T ≤ 256), the number of test cases. Each test case will consist of a single line that contains a string S (2 ≤ |S| ≤ 104). |S| represents the length of the string S. For each test case, print the number of ways on a single line. Warning: large Input/Output data, be careful with certain languages. ## Input The first line of input contains an integer T (1 ≤ T ≤ 256), the number of test cases.Each test case will consist of a single line that contains a string S (2 ≤ |S| ≤ 104).|S| represents the length of the string S. ## Output For each test case, print the number of ways on a single line. [samples] ## Note Warning: large Input/Output data, be careful with certain languages.

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case, let $ S = s_0 s_1 \dots s_{n-1} $ be a string of length $ n = |S| $, with indices taken modulo $ n $ (circular string). **Constraints** 1. $ 1 \leq T \leq 256 $ 2. For each test case: $ 2 \leq n \leq 10^4 $ **Objective** Count the number of ordered pairs $ (U, V) $ of non-overlapping substrings of $ S $ (treated circularly), such that: - $ U $ and $ V $ are contiguous substrings of $ S $, - $ U \cap V = \emptyset $ (no shared character positions in the circular string), - The substrings are **ordered**: $ (U, V) \neq (V, U) $ if $ U \neq V $, - Each substring has length at least 1. Formally, let $ U = S[i:i+\ell_1] $, $ V = S[j:j+\ell_2] $, with $ \ell_1, \ell_2 \geq 1 $, and the sets of indices $ \{i, i+1, \dots, i+\ell_1-1\} \mod n $ and $ \{j, j+1, \dots, j+\ell_2-1\} \mod n $ are disjoint. Count all such distinct ordered pairs $ (U, V) $.

API Response (JSON)

{
  "problem": {
    "name": "E. Going in Circles",
    "description": {
      "content": "During the SCPC2015 celebration, and as Noura likes to keep everyone entertained, she wanted to play a game with the students and volunteers. She asked them to stand in a circle in order to assign the",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10108E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "During the SCPC2015 celebration, and as Noura likes to keep everyone entertained, she wanted to play a game with the students and volunteers. She asked them to stand in a circle in order to assign the...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case, let $ S = s_0 s_1 \\dots s_{n-1} $ be a string of length $ n = |S| $, with indices taken modulo $ n $ (circ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments