Homework 06 Solution

Description
The scientists from Oganesson Dynamics have found an alien computer than can input a graph and rapidly determine whether it contains a clique of K vertices. The possibilites are endless, since they should now be able to solve any NP-Complete problem!

For example: they found a set of wormholes (that form a graph!) with space stations at each vertex. To activate a wormhole, they must first power at least one neighboring space station. Will K activated space stations be enough to get the entire network up and running?

That's the vertex cover problem!

Given that you have a K-Clique solver, you can convert instances of the vertex cover problem to K-Clique such that it always returns the same YES/NO answer?

The conversion is easy. If you convert your K to N - K (that is, looking for the opposite of the vertex cover), you will have converted to the independent set problem. Then if you toggle all edges (that is, remove all edges that were present and add in all of the edges that were originally missing) to produce the complement graph, you will have converted from the independent set problem to the clique problem. Once these conversions are done, you merely need to output the resulting problem instance.

Input Format

The first line contains three values, N, M, K.
N is the number of vertices in the graph (with IDs 0 through N - 1)
M is the number of edges in the graph
K is the number of vertices being tested for
The next M lines each describe an edge with two values indicating the IDs of the vertices being connected.
Constraints

1 ≤ N ≤ 200
1 ≤ M ≤ 10,000
0 ≤ K ≤ N
Output Format

You must output the converted problem instance for the K-Clique problem that would have the same YES/NO answer as the original vertex cover problem. Otherwise, it should have the same format as the input.

NOTE: Each edge pair must have the lower ID first and be sorted in numerical order.

Example 0
Sample Input

5 6 3
0 1
0 2
0 4
1 4
2 3
2 4
Sample Output

5 4 2
0 3
1 2
1 3
3 4
Explanation

There are 5 vertices and 6 edges in the input graph; the question asks if 3 vertices can cover the graph.

To change this to independent set, we simply need to ask if the same graph has an independent set of size (5 - 3) = 2.

THEN to change this problem to K-Clique, we have to turn off the existing edges and turn on the ones that were missing in the original graph. There are (5 x 4 / 2) = 10 possible edges; 6 of them were in the original graph, but 4 were missing. We list only those four missing edges in out output.





Description
The second super-fast computer found by Oganesson takes a graph and outputs a series of vertices that describes a Hamiltonian Cycle. Or at least it often does; sometimes it makes a mistake. You must write a program that takes the input graph and a set of output cycles, and then verifies if each one is correct.

Input Format

The first line contains N and M, the number of vertices and the number of edges in the input graph, respectively.
The next M lines each describe an edge, providing the IDs of the two vertices it connects.
The next line provides T, the number of test cycles.
The final T lines each provides a test cycle with N vertex IDs in the proposed order of traversal.
Constraints

5 ≤ N ≤ 1000
5 ≤ M ≤ 50,000
1 ≤ T ≤ 10
0 ≤ vi < N (for all vi, as vertex IDs)
Output Format

T lines, each with the word "YES" or "NO", indicating whether the associated test cycle is valid.

Example 0
Sample Input

5 6
0 2
0 3
1 3
1 4
2 4
3 4
3
1 3 0 2 4
0 1 2 3 4
2 0 3 1 4
Sample Output

YES
NO
YES 



Description
Oganesson is now building huge star ships capable of multi-year long missions. These ships need to have a large crew where there are many skills represented. Can you help them determine who should go?

But wait! Haven't you already solved this problem? Technically, you have, but now the crews are much larger and your old algorithm is too slow. In fact, any classical algorithm is going to be too slow to find a perfect answer. As such, you just need to find the best answer that you can -- and print out the full answer.

For this problem, you will be graded on how close your answer comes to the correct answer. For every test case, you MUST return AN answer (i.e., timing out will result in no points for the given test case); the quality of your answer will determine how much credit you receive on the test case.

Input Format

The first line has two values, N and K.
N represents the number of potential crew members available (numbered 0 through N - 1), and K is the number of distinct skills that need to be included (numbered 0 through K - 1).
The next N pairs of lines each provide information about a single person.
The first line for person i indicates the number of skills that person has (Pi), and the second line has Pi values indicating the specific skill IDs.
Constraints

N == 1000
500 ≤ K ≤ 1200
8 ≤ Pi ≤ 200
Output Format

You should output two lines. The first line indicates S, the size of the best solution you could find (the minimum number of people). The next line has S space-separated values indicating the specific IDs of the people to recruit onto the team.

Example 0
Sample Input

3 5
2
1 3
3
0 1 2
3
0 2 4
Sample Output

2
0 2
Explanation

There are three people to choose from in the example input, and five total skills. These people are then presented in order. Person 0 has 2 skills: 1 and 3. Person 1 has 3 skills: 0, 1, and 2. Person 2 also has 3 skills: 0, 2, and 4.

The output provided indicates that two people are choosen for the team, person 0 and person 2. Since these two people comprise the full set of skills, this answer would be deemed "correct" and would receive points. Given that it is also the minimal answer, it would receive the maximum number of points. If, instead, all three people were included in the answer, it would still be correct (since all of the skills would be covered), but it would not be minimal so it would receive fewer points.