CCO '00 P1 - Subsets

View as PDF

Points: 10
Time limit: 1.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: 2000 Stage 2, Day 1, Problem 1

In this problem, you will write a program to find the minimal solution to a set of set inequalities. A set inequality has the format X contains S where may be any set name and may be a set name or set element. If is a set name the inequality means that is a superset or equal to . If is an element the inequality means that contains . Sets are named - and contain elements from -.

The first line of input specifies the number of set inequalities (). The next lines each contain one set inequality. For each set name that appears in the input, your program must determine its minimal set: the smallest set of elements that the name must take in order that all of the inequalities hold. Output, in alphabetical order, each set name followed its minimal set, with the elements in alphabetical order, in the format shown below.

Sample Input

9
A contains B
A contains c
B contains d
F contains A
F contains z
X contains Y
Y contains X
X contains x
Q contains R

Sample Output

A = {c,d}
B = {d}
F = {c,d,z}
Q = {}
R = {}
X = {x}
Y = {x}

• commented on Aug. 8, 2018, 7:42 p.m. edited

What is the maximum of N in this question?

edit: The maximum of N ended up being irrelavent in my solution anyway :p

• commented on Feb. 14, 2018, 12:06 a.m.

When I submit my code in python2, it only scores 4/5, however, when I submit the same code in pypy2, I receive AC. If this isn't odd enough, the versions of python are both 2.7.13

Could someone please tell me what is going on?

• commented on April 21, 2019, 12:52 p.m.

pypy2 is faster but more memory-intensive

• commented on April 23, 2019, 10:00 p.m. edited

Thanks for the reply! This very true, however it shouldn't lead to the same solution producing different answers, especially given that the versions of python are the same. What I mean by this is that speed optimisation (albeit at the cost of some memory) should not result in identical programs running differently.

In order to be proactive regarding diagnosing diagnose this problem (you may notice that I haven't submitted to this question in over a year!), what I will do is resubmit my code in Python 3, and then PyPy3 to see if I receive the same issue.

• commented on Oct. 24, 2017, 5:46 p.m.

Is my TLE for the last case because of an infinite loop or is my algorithm too slow?

• commented on May 4, 2017, 5:20 a.m.

Is it guaranteed the sets won't be cyclic? i.e; if A contains B can B contain A

• commented on May 4, 2017, 9:33 a.m. edited

No. They can be cyclic.

• commented on April 5, 2017, 12:05 p.m.

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

• commented on April 4, 2017, 4:01 p.m.

When will judging be available for this problem?

• commented on April 4, 2017, 10:56 p.m.

Judges are back up.