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
Output For each test case, output one line containing " Case #x: followed by ible" if there is no answe k of the the latter case, on the next line, print the k vertices of C order, separated by spaces. If there are multiple answers, ample Inpu Sample output Case #1:1 12 ible 0 23 34 Problemsetter: Igor Naverniouk 6
6 Output For each test case, output one line containing "Case #x:" followed by either "Impossible" if there is no answer or the size k of the set C. In the latter case, on the next line, print the k vertices of C in increasing order, separated by spaces. If there are multiple answers, print the lexicographically smallest one. Sample Input Sample Output 4 2 1 1 2 0 0 10 0 4 4 1 2 2 3 3 4 4 1 Case #1: 1 1 Case #2: 0 Case #3: Impossible Case #4: 2 1 3 Problemsetter: Igor Naverniouk
Problem d Ri ngs n Roi Time Limit: 3 seconds Well that seems to be the situation But I don'twant that, and you don' t want that and Ringo here definitely doesn t want that Jules Winnfield I have n tiny rings made of steel. I also have m pieces of rope, all of exactly the same length. The two ends of each piece of rope are tied to two different rings I am going to take one of the rings, L, into my left hand, and another ring, R into my right hand. Then I will pull the whole structure apart as hard as I can. Some of the ropes will be streched horizontally because of this. Others will hang down or bend out of shape. If I want the number of horizontally stretched ropes to be as large as possible, which l and R should I pick? Assume that the stretching of ropes in negligible, they all have negligible thickness and are free to slide around the rings that they are tied to. The thickness and radius of each ring is negligible, too Input The first line of input gives the number of cases, N. n test cases follow Each one starts with two lines containing n(2<=n<=120)and m (0<=m<=n(n-1)/2). The next m lines will each contain a pair of different [0,n-1]) connected by at most one rope Output For each test case, output the line containing Case #x:, followed by the largest number of ropes that I can stretch horizontally by pickin a pair of rings, L and r S ple inp Sample output
7 Problem D Rings'n'Ropes Time Limit: 3 seconds "Well, that seems to be the situation. But, I don't want that, and you don't want that, and Ringo here definitely doesn't want that." Jules Winnfield I have n tiny rings made of steel. I also have m pieces of rope, all of exactly the same length. The two ends of each piece of rope are tied to two different rings. I am going to take one of the rings, L, into my left hand, and another ring, R into my right hand. Then I will pull the whole structure apart as hard as I can. Some of the ropes will be streched horizontally because of this. Others will hang down or bend out of shape. If I want the number of horizontally stretched ropes to be as large as possible, which L and R should I pick? Assume that the stretching of ropes in negligible, they all have negligible thickness and are free to slide around the rings that they are tied to. The thickness and radius of each ring is negligible, too. Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with two lines containing n (2<=n<=120) and m (0<=m<=n(n-1)/2). The next m lines will each contain a pair of different rings (integers in the range [0, n-1]). Each pair of rings will be connected by at most one rope. Output For each test case, output the line containing "Case #x:", followed by the largest number of ropes that I can stretch horizontally by picking a pair of rings, L and R. Sample Input Sample Output 4 Case #1: 1
Case #3:6 Case #4: 7 330 0 266.00 15346700 53422 1534 534422 Problemsetter: Igor Naverniouk
8 2 1 0 1 3 3 0 1 1 2 2 0 6 6 0 1 0 5 1 3 5 4 3 2 4 2 6 7 0 1 0 5 1 3 1 4 5 4 3 2 4 2 Case #2: 1 Case #3: 6 Case #4: 7 Problemsetter: Igor Naverniouk
Problem e Sending email Time Limit: 3 seconds A new internet watchdog is creating a stir in ringfield. Mr: X, if that is his real name, has come up with a sensational scoop. There are n SMTP servers connected by network cables. Each of the m cables connects two computers and has a certain latency measured in milliseconds required to send an email message What is the shortest time required to send a message from server s to server t along a sequence of cables? Assume that there is no delay incurred at any of the servers. Input The first line of input gives the number of cases, N.n test cases follow. Each one starts with a line containing n(2<=n<20000),m(0<=m<50000) S(O<=S<n)and T(0<=T<n. S!=T. The next m lines will each contain 3 integers: 2 different servers (in the range [0, n-l) that are connected by a bidirectional cable and the latency, w, along this cable (0<=W<=10000 Output For each test case, output the line"Case #x: followed by the number of milliseconds required to send a message from s to T. Print"unreachable f there is no route froms to t Sample Input Sample output Case#1:100 2101 Case#2:150 011 Case #3: unreachable 3320 01100 02200 1250 2001
9 Problem E Sending email Time Limit: 3 seconds "A new internet watchdog is creating a stir in Springfield. Mr. X, if that is his real name, has come up with a sensational scoop." Kent Brockman There are n SMTP servers connected by network cables. Each of the m cables connects two computers and has a certain latency measured in milliseconds required to send an email message. What is the shortest time required to send a message from server S to server T along a sequence of cables? Assume that there is no delay incurred at any of the servers. Input The first line of input gives the number of cases, N. N test cases follow. Each one starts with a line containing n (2<=n<20000), m (0<=m<50000), S (0<=S<n) and T (0<=T<n). S!=T. The next m lines will each contain 3 integers: 2 different servers (in the range [0, n-1]) that are connected by a bidirectional cable and the latency, w, along this cable (0<=w<=10000). Output For each test case, output the line "Case #x:" followed by the number of milliseconds required to send a message from S to T. Print "unreachable" if there is no route from S to T. Sample Input Sample Output 3 2 1 0 1 0 1 100 3 3 2 0 0 1 100 0 2 200 1 2 50 2 0 0 1 Case #1: 100 Case #2: 150 Case #3: unreachable
Problemsetter: Igor Naverniouk 10
10 Problemsetter: Igor Naverniouk
