Problem a roublemakel Time limit. l second [after seeing that the room is on fire; Ted has a needle in his hand while holding the leg of a dead woman; Sara hasa bottle of champagne in her hand, and Juancho is smoking Man: Did they misbehave? Robert Rodr iges, The Misbehavers Every school class has its troublemakers those kids who can make the teachers life miserable. On his own, a troublemaker is manageable, but when you put certain pairs of troublemakers together in the same room, teaching a class becomes very hard. There are n kids in Mrs. Shaida's math class, and there are m pairs of troublemakers among them. The situation has gotten so bad that Mrs. Shaida has decided to split the class into two classes. Help her do it in such a way that the number of troublemaker pairs is reduced by at least a half. Input The first line of input gives the number of cases, N. n test cases follow. Each one starts with a line containing n(0<=n<=100)and m(0<m<5000) The next m lines will contain a pair of integers u and v meaning that when kids u and v are in the same room, they make a troublemaker pair. Kids are numbered from 1 to n Output For each test case, output one line containing Case #x: followed by L the number of kids who will be moved to a different class (in a different room). The next line should list those kids. The total number of troublemaker pairs in the two rooms must be at most m/2. If that is impossible, print Impossible. instead of L and an empty line afterward Sample Input Sample output Case #1: 1 34 23 12
1 Problem A Troublemakers Time Limit: 1 second [after seeing that the room is on fire; Ted has a needle in his hand while holding the leg of a dead woman; Sara has a bottle of champagne in her hand, and Juancho is smoking] Man: Did they misbehave? Robert Rodrigues, "The Misbehavers." Every school class has its troublemakers - those kids who can make the teacher's life miserable. On his own, a troublemaker is manageable, but when you put certain pairs of troublemakers together in the same room, teaching a class becomes very hard. There are n kids in Mrs. Shaida's math class, and there are m pairs of troublemakers among them. The situation has gotten so bad that Mrs. Shaida has decided to split the class into two classes. Help her do it in such a way that the number of troublemaker pairs is reduced by at least a half. Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing n (0<=n<=100) and m (0<m<5000). The next m lines will contain a pair of integers u and v meaning that when kids u and v are in the same room, they make a troublemaker pair. Kids are numbered from 1 to n. Output For each test case, output one line containing "Case #x:" followed by L - the number of kids who will be moved to a different class (in a different room). The next line should list those kids. The total number of troublemaker pairs in the two rooms must be at most m/2. If that is impossible, print "Impossible." instead of L and an empty line afterwards. Sample Input Sample Output 2 4 3 1 2 2 3 Case #1: 1 1 3 4 Case #2: 2 1 2
34 46 34 Problemsetter: Igor Naverniouk 2
2 3 4 4 6 1 2 1 3 1 4 2 3 2 4 3 4 Problemsetter: Igor Naverniouk
Problem b Buy one, get the rest free Time Limit: 3 seconds Whoa!! It feels like I'm flying." It's year 2258, and the age of airplanes is coming to an end. Everyone is using teleporters now. In an effort to stay competitive, the last remaining air travel company, GetsJo, is offering the following deal to its customers. Instead of buying one plane ticket, you can rent a whole flight from a to B. Each flight can carry a certain number of people and costs a certain amount of money. If you do that, then you can rent all of the other flights of equal or lesser cost for free For example, if there are 4 flights with costs $10000, $25000, $30000 and $40000, and you rent the $30000 flight, then you get the $10000 and $25000 flights for free. The total cost to rent these 3 flights is $30000 You want to organize a large programming competition and would like to invite all of the participants to city n, where the competition will be held. Being a nice person, you decide to pay for everyone's airplane tickets. Given the locations of the participants and the list of available flights between now and the day of the competition, what is the cost of renting enough flights to get all of the participants to city n in the next d days? Input The first line of input gives the number of cases, N. n test cases follow. Each one starts with a line containing the number of cities (1<=n<=30) the number of days (1<=d<=10)until the competition and the number of flights(0<=m<=1000). m lines follow, each one containing 5 integers:u v, c, p and e(1<=u, v<=n, 1<=c<=100, 0<=e<d). This means that a flight that can carry c passengers and costs p dollars leaves city u on day in the evening and arrives next day in the morning to city v. today, and all of the participants need to be in city n in the evening of day e. Finally, n integers (zi, z3,..., Zn) follow, meaning that there are zi participants in city i on day 0(0<=Z1<=100). The maximum cost of a flight is 100000. There will never be two flights with the same u,v and e values
3 Problem B Buy one, get the rest free. Time Limit: 3 seconds "Whoa! It feels like I'm flying!" Lrrr It's year 2258, and the age of airplanes is coming to an end. Everyone is using teleporters now. In an effort to stay competitive, the last remaining air travel company, GetsJo, is offering the following deal to its customers. Instead of buying one plane ticket, you can rent a whole flight from A to B. Each flight can carry a certain number of people and costs a certain amount of money. If you do that, then you can rent all of the other flights of equal or lesser cost for free! For example, if there are 4 flights with costs $10000, $25000, $30000 and $40000, and you rent the $30000 flight, then you get the $10000 and $25000 flights for free. The total cost to rent these 3 flights is $30000. You want to organize a large programming competition and would like to invite all of the participants to city n, where the competition will be held. Being a nice person, you decide to pay for everyone's airplane tickets. Given the locations of the participants and the list of available flights between now and the day of the competition, what is the cost of renting enough flights to get all of the participants to city n in the next d days? Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing the number of cities (1<=n<=30), the number of days (1<=d<=10) until the competition and the number of flights (0<=m<=1000). m lines follow, each one containing 5 integers: u, v, c, p and e (1<=u,v<=n, 1<=c<=100, 0<=e<d). This means that a flight that can carry c passengers and costs p dollars leaves city u on day e in the evening and arrives next day in the morning to city v. Day 0 is today, and all of the participants need to be in city n in the evening of day e. Finally, n integers (z1 , z2 , ..., zn ) follow, meaning that there are zi participants in city i on day 0 (0<=zi <=100). The maximum cost of a flight is 100000. There will never be two flights with the same u, v and e values
Output For each test case, output one line containing Case #x: followed by the minimum required cost of flying all of the participants to city n before the end of day d. If no amount of money is enough, print Impossible instead Sample Input Sample output Case#1:30000 545 Case #2: Impossible 15100300000 2410100000 2410100001 4525250002 25100400003 12005100 1299104000 1000 Problemsetter: Igor Naverniouk Alternate solution: Yury Kholondyrev
4 Output For each test case, output one line containing "Case #x:" followed by the minimum required cost of flying all of the participants to city n before the end of day d. If no amount of money is enough, print "Impossible" instead. Sample Input Sample Output 2 5 4 5 1 5 100 30000 0 2 4 10 10000 0 2 4 10 10000 1 4 5 25 25000 2 2 5 100 40000 3 1 20 0 5 100 2 1 1 1 2 99 10400 0 100 0 Case #1: 30000 Case #2: Impossible Problemsetter: Igor Naverniouk Alternate solution: Yury Kholondyrev
Problem c Double np-hard Time limit. 2 second "Name and Class year Course to be Covered: (Course Number and Title) Reason for covering the course independently. Hami I ton College Appl ication for Independent Coverage of Course Work Definitions In this problem, a graph is a set of n vertices together with a set of m edges, where an edge is an unordered pair of different vertices(edges are undirected). The two vertices that comprise an edge are said to be that edges endpoints. a vertex cover of a given graph g is a subset c of its vertices, such that each edge of g has at least one of its endpoints in C. An independent set of a given graph G is a subset s of its vertices, such that no edge of g has both of its endpoints in The problem of finding a minimum vertex cover (that is, a vertex cover of the smallest possible size) for any graph is NP-hard. The problem of finding a maximum independent set of any graph is also NP-hard. That a formal way of saying that no one knows whether there exists an algorith that runs in time polynomial in n and solves any one of the two problems We want to define a class of problems that are even harder than the NP-hard problems. We are going to call them Double NP-hard"! Your job is to solve the first Double NP-hard problem Problem Given a graph G, find a subset C of its vertices that is both a minimum vertex cover and a maximum independent set Input The first line of input gives the number of cases, N.n test cases follow. Each one starts with two lines containing n(0<=n<=1000) and m (0<=m<=100000)as above. The next m lines will each describe an edge of G as a pair of different vertices, which are numbered from i to n
5 Problem C Double NP-hard Time Limit: 2 second "Name and Class Year: Course to be Covered: (Course Number and Title) Reason for covering the course independently:" Hamilton College Application for Independent Coverage of Course Work Definitions In this problem, a graph is a set of n vertices together with a set of m edges, where an edge is an unordered pair of different vertices (edges are undirected). The two vertices that comprise an edge are said to be that edge's endpoints. A vertex cover of a given graph G is a subset C of its vertices, such that each edge of G has at least one of its endpoints in C. An independent set of a given graph G is a subset S of its vertices, such that no edge of G has both of its endpoints in S. The problem of finding a minimum vertex cover (that is, a vertex cover of the smallest possible size) for any graph is NP-hard. The problem of finding a maximum independent set of any graph is also NP-hard. That is a formal way of saying that no one knows whether there exists an algorithm that runs in time polynomial in n and solves any one of the two problems. We want to define a class of problems that are even harder than the NP-hard problems. We are going to call them "Double NP-hard"! Your job is to solve the first Double NP-hard problem. Problem Given a graph G, find a subset C of its vertices that is both a minimum vertex cover and a maximum independent set. Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with two lines containing n (0<=n<=1000) and m (0<=m<=100000) as above. The next m lines will each describe an edge of G as a pair of different vertices, which are numbered from 1 to n