Question F: You are given relations A is greater than B. You create a graph, in which all such pairs form a directed edge (A,B). Thus, we want to find for each bead, how many beads it can rach, and how many can reach it. This graph is acyclic, and thus, a DAG. Do a topological sort. Then, use dynamic programming, from bottom to top(that is, in reverse order of the topological sort), and calculating how many beads each bead can reach. Then, mark the ones with more than (N-1)/2 beads it can reach. Now, reverse the edges of the graph, and do the same. Resulting complexity: linear.
On Jul 10, 5:48 am, Spiritus <[email protected]> wrote: > I have an idea for D as well. > > First, suppose we are given an upper bound T on the projects finish > time. we thus want to assign jobs for each employee that this > employees total time doesn't exceed this upper bound T. > This we can do using dynamic programming in O(m^2 * n) > We maintain a table A[i,m] that holds - "Using employee's 1 .. i, what > is the maximum number of subprojects i can finish in project A, > holding I still did m subprojects in project B". > > To calculate a cell, first notice, that given T, an employee can do C > subprojects from A, and D subprojects from B, iff C*x+D*y<=T (where x > and y are as in the input, the time it take to do a subproject from A, > B respectively). Thus, if he's doing D B-subprojects, he can do at > most floor((T-D*y)/C) B-subprojects. so, we we have at most m+1 > options we want to check, for D=0..m. > Thus, the recurrence relation is: A[i,m] = max_{0<=D<=floor(T/y)} [A > [i-1,m-D] + floor((T-D*y)/C)] > (Of course, we need to check if we go off the array boundaries). > We can satisfy all the projects iff A[n,m]>=m (or something similar). > > this is done in O(N*M) * O(M) which is array size * time to compute a > cell. this is about 1,000,000. > All that we have to do now is to binary search the value for T, this > adds a log T, so overall, we have O(M^2 * N * lg T) > > On Jul 10, 5:15 am, Spiritus <[email protected]> wrote: > > > Problem B: > > My idea is to have a set(can be implemented using STL's std::set) with > > key being a pair (dx,dy). > > now, i go through all pairs of points, and i construct the key(x_1- > > x_0,y_1,y_0) for them. The idea is that if i have L pairs each with > > the same (dx,dy), every two pairs make a parallelogram. And so, after > > putting them all inside, i go through the set and say that if I have L > > pairs with the same (dx,dy), i add L*(L-1)/2 to a counter, and in the > > end i divide by 2, since i counted each parallelogram twice. > > Now, this is not accurate, because this way i count 4 points on a > > straight line as a parallelogram. So, instead of just counting how > > many pairs are with this (dx,dy), i count how many different lines are > > with this slope. that is, for a specific slope, (dx,dy), i maintain a > > second level set that contains the intersections with the y axis, and > > in the end, i use inclusion exclusion on each slope, and i end up with > > a (N log N) algorithm. > > > Sincerely, > > Shahar Papini > > > On Jul 8, 11:58 am, Davood Vahdati <[email protected]> > > wrote: > > > > it is an Acm programming competition Questions in year 2004-2005 . could > > > you > > > please solve problems is question ? thank you . > > > > 29th ACM International Collegiate > > > > Sponsored by > > > > Programming Contest, 2004-2005 > > > Sharif Preliminary Contest > > > Sharif University of Technology, 28 Oct. 2004 > > > > Problem B > > > (Program filename: B.CPP, B.DPR, B.PAS or B.java) > > > > Parallelogram Counting > > > > There are n distinct points in the plane, given by their integer > > > coordinates. Find the number of parallelograms whose > > > vertices lie on these points. In other words, find the number of 4-element > > > subsets of these points that can be written as > > > {A, B, C, D} such that AB || CD, and BC || AD. No four points are in a > > > straight line. > > > > Input (filename: B.IN) > > > > The first line of the input file contains a single integer t (1 £ t £ 10), > > > the number of test cases. It is followed by the input > > > > data for each test case. > > > The first line of each test case contains an integer n (1 £ n £ 1000). > > > Each > > > of the next n lines, contains 2 space-separated > > > integers x and y (the coordinates of a point) with magnitude (absolute > > > value) of no more than 1000000000. > > > > Output (Standard Output) > > > > Output should contain t lines. > > > Line i contains an integer showing the number of the parallelograms as > > > described above for test case i. > > > > Sample Input > > > > 2 > > > 6 > > > 0 0 > > > 2 0 > > > 4 0 > > > 1 1 > > > 3 1 > > > 5 1 > > > 7 > > > -2 -1 > > > 8 9 > > > 5 7 > > > 1 1 > > > 4 8 > > > 2 0 > > > 9 8 > > > > Sample Output > > > > 5 > > > 6 > > > > ---------------------------------------------------------------------------------------------------------------------- > > > Problem B-Page 1 of 1 > > > > 28th ACM International Collegiate > > > > Sponsored by > > > > Programming Contest, 2003-2004 > > > Sharif Preliminary Contest > > > Sharif University of Technology, 14 Nov. 2003 > > > > Problem C > > > (Program filename: C.CPP or C.PAS or C.DPR or C.java) > > > > Toy Storage > > > > Mom and dad have a problem: their child, Reza, never puts his toys away > > > when > > > he is finished playing with them. > > > They gave Reza a rectangular box to put his toys in. Unfortunately, Reza > > > is > > > rebellious and obeys his parents by simply > > > throwing his toys into the box. All the toys get mixed up, and it is > > > impossible for Reza to find his favorite toys anymore. > > > > Reza's parents came up with the following idea. They put cardboard > > > partitions into the box. Even if Reza keeps > > > throwing his toys into the box, at least toys that get thrown into > > > different > > > partitions stay separate. The box looks like this > > > from the top: > > > > We want for each positive integer t, such that there exists a partition > > > with > > > t toys, determine how many partitions > > > have t, toys. > > > > Input (filename: C.IN) > > > > The input consists of a number of cases. The first line consists of six > > > integers n, m, x1, y1, x2, y2. The number of > > > cardboards to form the partitions is n (0< n £ 1000) and the number of > > > toys > > > is given in m (0<m £ 1000). The > > > coordinates of the upper-left corner and the lower-right corner of the box > > > are (x1, y1) and (x2, y2), respectively. The > > > following n lines each consists of two integers Ui Li, indicating that the > > > ends of the ith cardboard is at the coordinates > > > (Ui, y1) and (Li, y2). You may assume that the cardboards do not intersect > > > with each other. The next m lines each consists > > > of two integers Xi Yi specifying where the ith toy has landed in the box. > > > You may assume that no toy will land on a > > > cardboard. > > > A line consisting of a single 0 terminates the input. > > > > Output (filename: C.OUT) > > > > For each box, first provide a header stating “Box” > > > on a line of its own. After that, there will be one line of output per > > > count (t> 0) of toys in a partition. The value t will be followed by a > > > colon > > > and a space, followed the number of > > > > partitions containing t toys. Output will be sorted in ascending order of > > > t > > > for each box. > > > > Sample Input > > > > 4 10 0 10 100 0 > > > 20 20 > > > 80 80 > > > 60 60 > > > 40 40 > > > 5 10 > > > 15 10 > > > 95 10 > > > 25 10 > > > 65 10 > > > 75 10 > > > 35 10 > > > 45 10 > > > 55 10 > > > 85 10 > > > 5 6 0 10 60 0 > > > > 4 3 > > > 15 30 > > > 3 1 > > > 6 8 > > > 10 10 > > > 2 1 > > > 2 8 > > > 1 5 > > > 5 5 > > > 40 10 > > > 7 9 > > > 0 > > > > Sample Output > > > > Box > > > > 2: 5 > > > Box > > > 1: 4 > > > 2: 1 > > > ---------------------------------------------------------------------- > > > 29th ACM International Collegiate > > > Sponsored by > > > Programming Contest, 2004-2005 > > > Sharif Preliminary Contest > > > Sharif University of Technology, 28 Oct. 2004 > > > > Problem D > > > (Program filename: D.CPP, D.DPR, or D.java) > > > > Software Company > > > A software developing company has been assigned two programming projects. > > > As > > > > both projects are within the same contract, both must be handed in at the > > > same > > > time. It does not help if one is finished earlier. > > > > This company has n employees to do the jobs. To manage the two projects > > > more > > > > easily, each is divided into m independent subprojects. Only one employee > > > can > > > work on a single subproject at one time, but it is possible for two > > > employees to > > > work on different subprojects of the same project simultaneously. > > > > Our goal is to finish the projects as soon as possible. > > > > Input (filename: D.IN) > > > The first line of the input file contains a single integer t (1 £ t £ 11), > > > the > > > number of test cases, followed by the input data for each test case. The > > > first > > > line of each test case contains two integers n (1 £ n £ 100), and m (1 £ > > > m £ > > > > 100). The input for this test case will be followed by n lines. Each line > > > contains two integers which specify how much time in seconds it will take > > > for > > > the specified employee to complete one subproject of each project. So if > > > the > > > > line contains x and y, it means that it takes the employee x seconds to > > > complete > > > a subproject from the first project, and y seconds to complete a > > > subproject > > > from > > > the second project. > > > Output (Standard Output) > > > There should be one line per test case containing the minimum amount of > > > time > > > in > > > seconds after which both projects can be completed. > > > > Sample Input > > > 1 > > > 3 20 > > > 1 1 > > > 2 4 > > > 1 6 > > > > Sample Output > > > 18 > > > > Problem D -Page 1 of 1 > > > > 29th ACM International Collegiate > > > Sponsored by > > > Programming Contest, 2004-2005 > > > Sharif Preliminary Contest > > > Sharif University of Technology, 28 Oct. 2004 > > > ---------------------------------------------------------------------- > > > Problem F > > > (Program filename: F.CPP, F.DPR, or F.java) > > > > Median Weight Bead > > > There are N beads which of the same shape and size, but with different > > > weights. > > > N is an odd number and the beads are labeled as 1, 2, ..., N. Your task is > > > to > > > find the bead whose weight is median (the ((N+1)/2)th among all beads). > > > The > > > following comparison has been performed on some pairs of beads: > > > A scale is given to compare the weights of beads. We can determine which > > > one > > > is > > > heavier than the other between two beads. As the result, we now know that > > > some > > > beads are heavier than others. We are > > ... > > read more » --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
