CCC '04 S1 - Fix - DMOJ: Modern Online Judge

CCC '04 S1 - Fix

View as PDF

Submit solution

All submissions

Best submissions

Points: 5 (partial)

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$ $3 N + 1$ lines: the first line will be the number $N$ $N$ , and the remaining $3N$ $3 N$ 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

Copy

2
abba
aab
bab
a
ab
aa

Sample Output

Copy

Yes
No

Comments

0

studentcsaa7 commented 15 days ago

this stupud question had to put "yes" and "no" in capitals so i wasted like 20 minutes trying to figure otu the error, only to find that i did not use capitals.

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?

6

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 \leq 5$ .