F. A Poet Computer

Codeforces

IDCF10093F

Time2000ms

Memory64MB

Difficulty—

English · Original

Formal · Original

The ACM team is working on an AI project called (Eih Eye Three) that allows computers to write poems. One of the problems they stumbled upon is finding words with the same suffix. The ACM team constructed a dictionary of words, They are interested only in the longest common suffix, That is, a suffix common to three or more words in the dictionary… A suffix is any substring that starts from some arbitrary position in the string and reaches the end of the string. As the ACM team was also preparing for the ACM-TCPC2015 contest, they figured that the contestants can help in solving this problem. Your task is to write a program that finds a longest common suffix in a dictionary of words. An entry in the dictionary is a word of English letters only. Small letters are the same as capital letters. You can assume that there is exactly one unique solution for every test case. The first line of the input contains an integer T, the number of test cases. Each test case starts with a line containing one integer K, then K lines follow, each containing one string “Si” that represents an entry in the dictionary. 0 < T ≤ 50 |Si| ≤ 100 0 < K ≤ 1000 For each test case, print on the first line “Case c:” where ‘c’ is the test case number. On the second line you should print an integer denoting the length of the longest common suffix and another integer denoting how many words have the suffix appeared in. ## Input The first line of the input contains an integer T, the number of test cases. Each test case starts with a line containing one integer K, then K lines follow, each containing one string “Si” that represents an entry in the dictionary. 0 < T ≤ 50 |Si| ≤ 100 0 < K ≤ 1000 ## Output For each test case, print on the first line “Case c:” where ‘c’ is the test case number. On the second line you should print an integer denoting the length of the longest common suffix and another integer denoting how many words have the suffix appeared in. [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ c \in \{1, \dots, T\} $: - Let $ K \in \mathbb{Z} $ be the number of words. - Let $ S = \{s_1, s_2, \dots, s_K\} $ be a set of strings over the alphabet of English letters (case-insensitive). A **suffix** of a string $ s $ is any substring $ s[i:] $ for $ 0 \leq i < |s| $. Let $ \text{SuffixSet}(s) = \{ s[i:] \mid 0 \leq i < |s| \} $. **Constraints** 1. $ 1 \leq T \leq 50 $ 2. For each test case: - $ 1 \leq K \leq 1000 $ - $ 1 \leq |s_i| \leq 100 $ for all $ s_i \in S $ 3. All strings contain only English letters; case-insensitive comparison applies. 4. There exists **exactly one** longest common suffix shared by **three or more** words. **Objective** For each test case $ c $: - Find the longest suffix $ \sigma \in \bigcap_{i \in I} \text{SuffixSet}(s_i) $ such that $ |I| \geq 3 $, and for any other suffix $ \sigma' $ with $ |\{ j \mid \sigma' \in \text{SuffixSet}(s_j) \}| \geq 3 $, it holds that $ |\sigma| \geq |\sigma'| $. - Output: - The length $ L = |\sigma| $ - The count $ C = |\{ j \mid \sigma \in \text{SuffixSet}(s_j) \}| $

API Response (JSON)

{
  "problem": {
    "name": "F. A Poet Computer",
    "description": {
      "content": "The ACM team is working on an AI project called (Eih Eye Three) that allows computers to write poems. One of the problems they stumbled upon is finding words with the same suffix. The ACM team constru",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 65536
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10093F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "The ACM team is working on an AI project called (Eih Eye Three) that allows computers to write poems. One of the problems they stumbled upon is finding words with the same suffix. The ACM team constru...",
      "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 $ c \\in \\{1, \\dots, T\\} $:  \n- Let $ K \\in \\mathbb{Z} $ be the number of words.  \n- Let $ S = \\{s_1, s_2, \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments