CCC '04 S1 - Fix

View as PDF

Submit solution

Points: 5
Time limit: 2.0s
Memory limit: 256M

Problem type
Canadian Computing Competition: 2004 Stage 1, Senior #1

A collection of words is prefix-free if no word is a prefix of any other word. A collection of words is suffix-free if no word is a suffix of any other word. A collection of words is fix-free if it is both prefix-free and suffix-free.

For this problem, a word is a sequence of lower-case letters of length between 1 and 25. A word X is a prefix of word Y if X consists of the first n characters of Y, in order, for some n. That is, the word cat has prefixes c, ca, and cat. Similarly, a word X is a suffix of Y if X consists of the last n characters of Y, in order, for some n.

Your input will be 3N+1 lines: the first line will be the number N, and the remaining 3N lines will be the N collections of 3 words each. (That is, lines 2, 3, and 4 compose the first collection, lines 5, 6, and 7 compose the second collection, and so on). Your output will be N lines, each line containing either Yes (if that collection of words is fix-free) or No (if that collection is not fix-free).

Sample Input

2
abba
aab
bab
a
ab
aa

Sample Output

Yes
No

Comments


  • -1
    Evang  commented on Dec. 31, 2019, 5:35 a.m.

    I do not see why, in the example output, that the first collection is fix-free. The first two words in the input have the letter "a" as a common prefix, and the last two words in the first collection have the letter "b" as a common suffix. Can anyone help explain to me why my thinking is incorrect?


    • 5
      geese  commented on Dec. 31, 2019, 4:36 p.m.

      The common fixes have to be fellow words in the list.


  • 0
    andisong  commented on March 23, 2019, 1:38 p.m.

    Are the three words in a set all distinct?


    • 3
      Rimuru  commented on March 23, 2019, 5:21 p.m. edited

      I don't think the problem statement guarantees them to be distinct.


  • 7
    Ken_Shi  commented on Feb. 14, 2017, 3:19 p.m.

    I got different results on ideone.com and dmoj.ca, using same code. Any hint?


    • 2
      Dordor1218  commented on March 24, 2018, 3:26 p.m.

      I'm guessing you didn't initialize a variable which may cause it to initialize a random integer/string/char


  • 38
    Kirito  commented on Feb. 11, 2017, 4:44 p.m.

    N \le 5.