CCC '04 S1 - Fix - Olympiads Online Judge

CCC '04 S1 - Fix

View as PDF

Submit solution

All submissions

Best submissions

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$ ~1~ and $25$ ~25~. A word $X$ ~X~ is a prefix of word $Y$ ~Y~ if $X$ ~X~ consists of the first $n$ ~n~ characters of $Y$ ~Y~, in order, for some $n$ ~n~. That is, the word cat has prefixes c, ca, and cat. Similarly, a word $X$ ~X~ is a suffix of $Y$ ~Y~ if $X$ ~X~ consists of the last $n$ ~n~ characters of $Y$ ~Y~, in order, for some $n$ ~n~.

Your input will be $3N+1$ ~3N+1~ lines: the first line will be the number $N$ ~N~, and the remaining $3N$ ~3N~ lines will be the $N$ ~N~ collections of $3$ ~3~ words each. (That is, lines $2$ ~2~, $3$ ~3~, and $4$ ~4~ compose the first collection, lines $5$ ~5~, $6$ ~6~, and $7$ ~7~ compose the second collection, and so on). Your output will be $N$ ~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

0

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$ ~N \le 5~.