CCC '04 S1 - Fix

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig
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
    evanzhao  commented on Dec. 31, 2019, 12: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?


    • 1
      geese  commented on Dec. 31, 2019, 11:36 a.m.

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


  • 1
    andisong  commented on March 23, 2019, 9:38 a.m.

    Are the three words in a set all distinct?


    • 0
      Rimuru  commented on March 23, 2019, 1:21 p.m. edited

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


  • 5
    Ken_Shi  commented on Feb. 14, 2017, 10:19 a.m.

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


    • 0
      Dordor1218  commented on March 24, 2018, 11:26 a.m.

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


  • 17
    Kirito  commented on Feb. 11, 2017, 11:44 a.m.

    N \le 5.


    • -5
      TheCool1James  commented on Oct. 3, 2018, 2:08 p.m.

      This comment is hidden due to too much negative feedback. Click here to view it.


      • 2
        HyperNeutrino  commented on Jan. 16, 2019, 9:08 a.m.

        Not everyone will find problems like these easy. Also, this is an S1...