MWC '15 #6 P3: Magical Sets

View as PDF

Submit solution

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

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 A: \{1, 5, 6, 10\} and B: \{2, 5, 6\}, when merged become \{1, 2, 5, 6, 10\}. If the two sets were magical sets, the resulting merged magical set is \{1, 2, 10\}. 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, N (1 \le N \le 1000) the number of magical sets and Q (1 \le Q \le 1000), the number of magical set merge queries to perform.

The next N lines start with integer S_n (0 \le S_n \le 61), the size of the respective magical set (numbered 1 to N), followed by S_n integers in the magical set i_s (-30 \le i_s \le 30).

The next Q lines start with an integer M (0 \le M \le N), the number of magical sets to merge. M integers follow, the ids of the sets to merge together.

Note: you will have to use fast input methods.


Subtask 1 [5%]

1 \le N \le 100

1 \le Q \le 100

Subtask 2 [5%]

1 \le N \le 1000

1 \le Q \le 100

Subtask 3 [90%]

1 \le N \le 1000

1 \le Q \le 1000

Output Specification

Q 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 \{1, 2, 3, 4, 7, 10\}.


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

    What are the bounds of M?

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

      (0 \le M \le N)

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

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

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

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

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

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


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

      Just "0" I think.