## MWC '15 #6 P3: Magical Sets

View as PDF

Points: 7 (partial)
Time limit: 0.3s
Memory limit: 64M

Author:
Problem types
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

A mathematical set is a collection of distinct elements (integers). When you merge two sets, all the elements in each set are in the new set. Since each element is distinct, duplicate elements are turned into a single element.

A magical set is like a mathematical set, but with a magical merge. Instead of combining duplicate elements into a single element, a magical set, when merged, gets rid of both duplicates.

For example, sets and , when merged become . If the two sets were magical sets, the resulting merged magical set is . However, this only applies to merging of two magical sets. The magical merge is a commutative operation. To merge three sets, you would first merge two of them, then merge the third with the result of the first merge. Note: sets are not necessarily given in sorted order. It is guaranteed that no duplicates are given.

Create a program to simulate the merging of a number of magical sets. You may have to merge more than 2 magical sets together.

#### Input Specification

The first line contains two integers, the number of magical sets and , the number of magical set merge queries to perform.

The next lines start with integer , the size of the respective magical set (numbered to ), followed by integers in the magical set .

The next lines start with an integer , the number of magical sets to merge. integers follow, the ids of the sets to merge together.

Note: you will have to use fast input methods.

#### Output Specification

lines, each containing the size followed by the elements in each resulting magical set in ascending order.

#### Sample Input

3 3
4 1 5 6 10
3 2 5 6
3 4 3 7
2 1 2
1 2
3 1 2 3

#### Sample Output

3 1 2 10
3 2 5 6
6 1 2 3 4 7 10

#### Explanation for Sample Output

The first merge was explained above. Only one set participates in the second merge query, so the result is identical to the second magical set. All three magical sets are merged. Since the merge is commutative, we can merge the third set with the result of the first merge to get .

• commented on May 3, 2016, 12:00 p.m.

What are the bounds of M?

• commented on May 3, 2016, 4:54 p.m. edited

• commented on May 3, 2016, 4:42 p.m.

I'd assume M would be within the bounds of N (the number of sets).

• commented on April 30, 2016, 10:03 p.m.

What do we output if the merged magical set is empty?

• commented on May 1, 2016, 10:07 a.m.

r3mark is correct. It still follows the same format: size, followed by (no) elements.

0
• commented on April 30, 2016, 10:11 p.m.

Just "0" I think.