50186. Hitting set, part II

I'm a slow walker, but I never walk backwards.

Task description

This is the second part of "Hitting set". Please refer to "Hitting set, part I" for the description of hitting set.

Given a set $S$ and a set $T$, you need to write a main function to find the smallest hitting set $S'$ for $S$. There could be multiple solutions, so you need to output one according to the preprocessing flags.

  • When your program is compiled with flag LARGESTDICTIONARYORDER, you need to output the hitting set S' that appears latest in dictionary order.
  • When the program is compiled with flag SMALLESTDICTIONARYORDER, you have to output the hitting set S' that appears earliest in dictionary order.

Because the brutal force search is time-consuming, you have to prune the search tree to speedup your program in order to get all points. Nevertheless you can still get 85% of the points if you do not prune the search tree.

For easy implementation of pruning, we will sort the subsets in $T$ according to the largest element in each subset. For example, $T = \lbrace \lbrace 1, 2, 4\rbrace , \lbrace 1, 2\rbrace , \lbrace 1, 4, 5\rbrace \rbrace $ will be sorted to $T = \lbrace \lbrace 1, 2\rbrace , \lbrace 1, 2, 4\rbrace , \lbrace 1, 4, 5\rbrace \rbrace $ because the largest element in each subset are 2, 4, 5 respectively.

The pruning works as follows. We will examine the elements in increasing order. if you are considering an element i, then you can easily check if your current solution intersects with all the subsets that ends with an element no more than i, and your solution should intersect with all of them. The reason is that you will only consider elements greater than i in later recursion. If you cannot hit these sets now, you will never be able to do so in the future. As a result you can stop wasting time on the current solution.

Let $X$ denote that we do not have that element in the set. Let $S = \lbrace 1, 2, 3, 4, 5, 6\rbrace $ and $T = \lbrace \lbrace 1, 2\rbrace , \lbrace 1,4\rbrace , \lbrace 1, 2, 3, 4,5\rbrace \rbrace $. When we are considering elements 4, and our current solution is $\lbrace X, 2, 3, X\rbrace $, then we know that it CANNOT be the solution since it does not hit $\lbrace 1, 4\rbrace $. Therefore it will be waste of time to go into that search tree. For another example, let $S = \lbrace 1, 2, 3, 4, 5\rbrace $ and $T = \lbrace \lbrace 2\rbrace , \lbrace 1, 3\rbrace , \lbrace 3, 4, 5\rbrace \rbrace $ We are considering the element 2 and the current solution is $\lbrace 1, X\rbrace $. Again we cannot hit $\lbrace 2\rbrace $, so we do not waste time to search into $\lbrace 1, X\rbrace $.

You should include ta_set.h in your main.c and use those functions provided by TA. The following file is ta_set.h.

#include <stdio.h>
#include <stdbool.h>
 
typedef struct ta_set{
    /* TA's implementation */
}ta_Set;
 
void initializeSet(ta_Set* set, int numberOfElemnet);
void addElement(ta_Set* set, int element);
void removeElement(ta_Set* set, int element);
void printSet(ta_Set set);
bool intersect(ta_Set set1, ta_Set set2);

Note that you can copy the objects directly with TA's implementation. That is, the following example will make these two objects have exactly the same value.

ta_Set a;
ta_Set b = a;

Compile

We use the following commands to compile your code. Note that you are not supposed to have TA's implementation and run these commands.

gcc -DLARGESTDICTIONARYORDER -std=c99 -O2 main.c ta_set.c
gcc -DSMALLESTDICTIONARYORDER -std=c99 -O2 main.c ta_set.c

However, you can still find if there is any compilation error with the following command.

gcc -c -Wall main.c

Input Format

The first line is an integer $n$ (the number of elements in $S$), where $S = \lbrace 1 ,2 , 3 ... n\rbrace $.

  • $1 \le n \le 64$

The second line is an integer k that denotes the number of elements in T.

  • $1 \le k \le 100$

The following $k$ lines are the elements (subset of $S$) of $T$, and the first integer of each line denotes the length of the subset and the following integers denote the elements in the subset.

Output Format

Ouput the elements in $S'$.

Subtask

  • 30 poings: The program is compiled with flag LARGESTDICTIONARYORDER. gcc main.c set.c -std=c99 -O2 -DLARGESTDICTIONARYORDER
  • 25 points: The program is compiled with flag SMALLESTDICTIONARYORDER. gcc main.c set.c -std=c99 -O2 -DSMALLESTDICTIONARYORDER
  • 15 points: The program is compiled with flag LARGESTDICTIONARYORDER. You need to prune the tree to avoid TLE.

Sample input 1 (with flag LARGESTDICTIONARYORDER)

5
3
1 1
2 2 3
2 4 5

Sample output 1

1 3 5

Sample input 2 (with flag LARGESTDICTIONARYORDER)

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

Sample output 2

3 7

Sample input 3 (with flag LARGESTDICTIONARYORDER)

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

Sample output 3

3 7 10

Sample input 4 (with flag SMALLESTDICTIONARYORDER)

5
3
1 1
2 2 3
2 4 5

Sample output 4

1 2 4

Sample input 5 (with flag SMALLESTDICTIONARYORDER)

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

Sample output 5

3 6

Sample input 6 (with flag SMALLESTDICTIONARYORDER)

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

Sample output 6

1 7 10

Discussion