LCIPC Summer '99 Problems Choose a topic: Home --1998--     Problems     Rules     Results&Solutions     Test Cases --1999 Winter--     Problems     Rules --1999 Summer--     Announcement     Rules     Problems     Query Board     Contestants

Jon McAlister:Problem Writer, Test Data, Grading

Send all queries to: lchs3@hotmail.com
Query Board

Problem 1: LifeguardMeetings

Lifeguard Captain John has a problem. His lifeguards aredemanding paved sidewalks connecting their lifeguard towers sothat they can roller skate to and from their posts. John needs tocreate a system of sidewalks so that each tower is accessiblefrom every other tower via sidewalk. John also wants to minimizethe total length of sidewalk that is used as to minimize costs.

For example, consider four lifeguard towers called A, B, C, andD. The cost of creating a sidewalk between any two of thesetowers is given by the symmetric matrix below:

Therefore, the optimal solution for this matrix would be to buildsidewalks connecting A to C, B to C, and C to D. This results ina minimum cost of 13.

At certain times, Lifeguard Captain John needs to call anemergency meeting for his crew. John is located at the lifeguardbase and must either stay at the base and wait for the lifeguardsto reach him, or he must go to one of the lifeguard towers andwait for the other lifeguards to meet him there. If he stays atthe base, the time until the meeting starts is the time it takesfor every lifeguard to reach the base as the meeting cannot startuntil every lifeguard is present. If he decides to leave thebase, he can first alert his lifeguards through CB radio as towhere the meeting place will be. As he travels to the meetingplace, the other lifeguards will also be traveling to the meetingplace.

As each lifeguard travels to the meeting place, be it either thebase or one of the lifeguard towers, he or she will automaticallychoose the shortest path as determined by the length of theconnecting sidewalks. The length of the connecting sidewalks orsand paths is given by the distance matrix. In our example, thedistance matrix is:

@ indicates the base; A-D indicate the lifeguard towers. Forexample, the distance from the base to tower C is 3 units. Afterbuilding a system of sidewalks connecting the lifeguard towers,John also built a sidewalk connecting the base to the closestlifeguard tower, disregarding the cost. So in our example, thereis a sidewalk connecting the base to tower C. If two towers areequally close to the base, John will choose the tower which hasthe lower number (ex: If B and E are tied, he will choose tower Bto connect to).

While traveling, the lifeguards will only travel on the providedsidewalks, but John will take any path in his route to themeeting place.

Also, each lifeguard has a different speed. The speeds of ourexample lifeguards is given by the below table:

Also, L.C. John has a speed. In our example, John has thefollowing speeds.

Through sand: 1 units/min
On sidewalk: 3 units/min

So in our example, if the meeting is held at the base, it willtake 1.4 minutes for the meeting to start. If the meeting is heldat tower A, it will take 1.67 min for the meeting to start. Ifthe meeting is held at B, it will take 1.33 minutes for themeeting to start. If the meeting is held at C, it will take 1minute for the meeting to start. And if the meeting is held at D,it will take 2.33 minutes for the meeting to start.

In our example, the meeting should be held at tower C as thiswill minimize the amount of time required for the crew oflifeguards to come together.

INPUT: (from MEETING.IN)

In the input and output, the towers are numbered instead ofassigned letters such that Tower A is referred to as Tower1, Tower B is Tower 2, etc. Also, the base is referred to asTower 0.

The input starts with N (2<=N<=120) where N is the numberof towers. On the following line will be the speed of John onpavement followed by the speed of John on sand.

The following line will contain the speeds of the lifeguards onsidewalk.

All speeds will be positive integers less than or equal to 10000.

The following N lines will contain the cost matrix for thepavement such that the jth column of the ith row contains thecost of building a sidewalk from i to j. The following N+1 linescontain the distance matrix which is formatted like above.

All costs and distances will be less than or equal to 10000 andnonnegative.

SAMPLE INPUT:
4
3 1
4 7 3 5
0 6 3 9
6 0 2 11
3 2 0 8
9 11 8 0
0 5 8 3 10
5 0 3 2 4
8 3 0 1 6
3 2 1 0 4
10 4 6 4 0

OUTPUT: (to MEETING.OUT)

Your program must determine three answers:

• Find the minimum cost of connecting the lifeguard towers.
• Find and print the number of the lifeguard tower where the meeting should occur.
• Finally, your program should report how long that it will take for the lifeguard crew to meet at the optimal meeting place. The last line should be reported with exactly two decimal digits of precision.

Note: There will always be one optimal meeting location.

13
3
1.00

Problem 2: Don't forget thebeer

Surfer John and his buddies are planning a trip to the beach, butthey first have to stop at the Stop-n-Go and buy some coolers andsome beer. At the Stop-n-Go are M types of coolers, each of whichhas two important characteristics: the size of the cooler and thenumber of cans of beer that it can hold. John and his friends aretaking N cars to the beach and need to decide how many of eachkind of cooler to buy in order to maximize the total amount ofbeer that the group of cars brings.

Each car has a given trunk capacity, and the driver of each carwill buy the coolers that will fit in that car's trunk. At theend of buying the coolers, the group of surfers will buy thebeer, load the coolers into the cars, and leave for the beach.

One bad thing about the Stop-n-Go is that it has limits as to theamount of things that a customer can buy. For example, onecustomer cannot buy more than a preset limit of coolers of eachtype.

So, given the number of cars, the capacities of the cars, thetypes of coolers, and the amount of coolers that one customer canbuy, determine how much beer can be put into each car assumingthat the surfers do not swap coolers.

For example, consider 3 cars with capacities of 10, 5, and 12respectively. The Stop-n-Go has three types of coolers:

So, the driver of car 1 cannot buy 3 coolers of type 3 becausethat would exceed the limit/customer. Also, he cannot buy 3coolers of type 2 because that would exceed the capacity of hiscar.

To maximize his beer capacity, Driver 1 should buy 2 coolers oftype 3 and 1 cooler of type 2. This would give him the ability tostore 17 beers in his car. Driver 2 should buy one cooler of type1 giving him an 8 beer capacity. Driver 3 should buy 3 coolers oftype 2 giving him a 21 beer capacity.

INPUT: from (BEER.IN)

The first line of input will contain M and N. M(1<=M<=1000) denotes the types of coolers available at theStop-n-Go. N (1<=N<=1000) denotes the number of cars.

The following N lines contain the capacities of the N cars.

Subsequently, the following M lines contain the descriptions ofeach cooler type. Each of these lines contains three integers:the size of the cooler, the beer capacity of the cooler, and themaximum quantity of this cooler that each customer can buy.

All integers in the input will be less than or equal to 10000.

SAMPLE INPUT:
3 3
10
5
12
5 8 2
4 7 3
3 5 2

OUTPUT: to (BEER.OUT)

Your program should output the optimal beer capacity of each car.The i-th line should contain the amount of beer that Driver i canload in his car if he buys coolers optimally. For a correctanswer, no numbers in the output will exceed 2 billion.

17
8
21

Problem 3: Cooler Stacking

It's time for Surfer John to go home, and he has been given thepainful task of stacking up the coolers on the ground. Thecoolers are lying on the sand in one horizontal row. They need toend up in one vertical row. Each cooler in this program isexactly the same size, and more importantly, the heights of thecoolers are all equal to 1 length unit although each cooler has adifferent mass since the coolers have items of different weightsinside of them.

In this example, there are six coolers on the ground.

Cooler# 1 2 3 4 5 6

Mass 5 3 6 1 8 4

At any point in time, John can lift any cooler and place it ontop of one of the coolers which is either immediately to the leftor immediately to the right. John can also move stacks of anynumber of coolers on top of each other immediately to the left orto the right. Although moving stacks may create empty spacesbetween stacks of coolers, moving a stack of coolers horizontallyinto an empty space expends no energy.

Since this task may take a lot of energy if executed poorly, Johnneeds to know how to stack these coolers so that minimal energyis spent.

For the purpose of this program, the energy required to lift acooler or stack of coolers is determined by the product of themass of the cooler/coolers and the height that the cooler/stackneeds to be lifted.

Energy = Mass of cooler stack * Height of the vertical movement

One simple way to stack these coolers in our example is to stack1 onto 2, 1+2 onto 3, 1+2+3 onto 4, and so on.

Thus, the total energy required to stack the coolers in thismanner is 65 (=5+8+14+15+23). The resulting stack would have themasses from top to bottom in the following order corresponding tothe example masses:

5, 3, 6, 1, 8, 4

However, the optimal way for John to stack these coolers would beto do the following moves:

Thus, John can stack the coolers optimally using only a total of48 units of energy and save his strength. The resulting stackwould have the masses from top to bottom in the following order:

1, 3, 5, 6, 4, 8

INPUT: from (COOLERS.IN)

The first line of the input file contains N (1<N<=100),denoting the number of coolers. The following N lines contain themasses of the N coolers in the order in which they are lined upon the sand. Each of the masses will be positive and less than orequal to 40,000.

Sample Input:
6
5
3
6
1
8
4

OUTPUT: to (COOLERS.OUT)

The first line of output contains the minimum amount of energyrequired to stack the coolers. The following line will containthe information from which John can stack the coolers. This willbe a fully parenthesized infix expression where the simplestoperation will be in the form 3->5 denoting that a cooler ofmass 3 is being stacked on top of a cooler of mass 5. This lineof output will contain only parens, digits, and the charactersnecessary to make the arrow. The output should be on one linefollowed by a newline character.

There will always be one unique optimal solution to any inputset.

Sample Output:
48
((1->((3->5)->6))->(4->8))

Problem 4: Ultimate Frisbee

When Surfer John and his friends play ultimate frisbee, theyfirst choose the teams in a semi-bizarre fashion.

First, the players line up on the sand in a row.

Next, two players are arbitrarily chosen among the group. Thesetwo players are known as Captain1 and Captain2. These twocaptains then leave the line. As they leave the line, theremaining players shift and fill in the spaces where the twocaptains used to stand.

Captain1 begins the team selection by choosing one person amongthe remaining players who will then leave the line and joinCaptain1. As this selected player leaves the line, the remainingplayers shift and fill in the empty spaces.

Captain2 then picks two players from among the group. These twoplayers leave the line and join Captain2. However, Captain2 canonly pick players which are standing next to each other. Afterthese two leave, the line again shifts.

Each captain continues picking two players at a time, as long asthe two players are standing next to each other.

If one player is left in the line, he goes to the captain whoseturn it is to choose.

Team selection stops when there are no players left in the line.

Each individual player has an associated skill level. Each team'sskill level is equal to the sum of the skill level of all of theplayers on the team combined.

The combined team skill level of team 1 is termed TS1. Thecombined team skill level of team 2 is termed TS2.

Your program will determine the greatest disparity in team skilllevels.

For example, consider that these six players #1 thru 6, have thefollowing skill levels in order: 1 8 9 7 4 4. The answer to thisexample would involve the following processes:

The resulting teams would have players with the following skilllevels:

Team 1: 9 8 7
Team 2: 1 4 4

Thus, TS1 = 24 and TS2 = 9 the optimal disparity is 15.

INPUT: from (FRISBEE.IN)

Input will begin with N (1<=N<=40) denoting the number ofplayers. The following N lines contain the skill level of the Nplayers in the order in which they are standing in the line. Allskill levels will be less than or equal to 100.

Sample Input:
6
1
8
9
7
4
4

OUTPUT: to (FRISBEE.OUT)

Your program should output the value of the largest possible teamskill difference of the two teams. That is, the largest possiblevalue of abs(TS1 - TS2) where abs denotes the absolute valuefunction.

Sample Output:
15

Challenge Problem: Checkingout the Babes

Stewart Beach hosts a lot of hot women in addition to a number ofphysical obstructions such as cars, signs, tents, and vendors.Surfer John has just arrived with his binoculars and is decidingwhere to park his rotating chair. Your program will help SurferJohn to decide where to sit.

At each location, Surfer John is able to see certain babes asdetermined by line of sight. As Surfer John is an avidmathematician, he has learned over time that his happiness at aposition (x,y) is directly proportional to the function f(x,y):

a(x,y) = (the sum of the squares of the distances to the visiblebabes)

The babes that are visible by John are visible if there is adirect line of sight between Surfer John and the babe and thedistance between the babe and the Surfer is less than or equal toa certain value. The convex hull is the convex polygon of minimalperimeter that encloses all of the babes and the vertices of theconvex hull are chosen from the babes themselves.

The visible obstructions are rectangles whose edges are parallelto the
coordinate axes. The babes are located at lattice points.

Consider the following example:

In this example, let us assume that the maximum distance at whichJohn is
able to still see his target is 15 units.

There are 4 babes on the beach sitting at the following points:
(1,4) (1,-4) (-3,3) (-3,-3)

There are 2 sight obstructions. One is a rectangle with lowerleft corner
(-6,0) and upper right corner(-2,2). The other has a lower leftcorner
(2,-2) and upper right corner(6,5).

Now, let's evaluate f(0,0) for these parameters:

There are 3 visible babes: (1,4) (1,-4) and (-3,-3)
NOTE: (-3,3) is not visible as the line of sight between John andher
intersects the first obstruction.
a(0,0) = 17 + 17 + 18 = 52
The convex hull for is a triangle, with perimeter = 20.185.

Thus, f(0,0) = 3^3 / (52*20.185 + 10) = 0.0254

Now let's evaluate f(1,1):

All 4 babes are visible.
a(1,1) = 9 + 20 + 32 + 25 = 86
The convex hull is actually a trapezoid, with perimeter = 22.246.

Thus, f(1,1) = 4^3 / (86*22.246 + 10) = 0.0333

Therefore, (1,1) is a better place to sit than (0,0), althoughneither
of those two are the best values.

INPUT: from (BABES.IN)

The first line of input contains B, O, and M. B(1<=B<=1000) is the number of babes located on the beach. O(1<=O<=100) is the number of rectangular obstructions. M isthe maximum distance at which John can see a babe (used indetermining if a babe is visible from a given location).

The following B lines contain an x, y pair describing thelocation of babe #i. The following O lines describe therectangular obstructions which are described by two x, y pairsdescribing the bottom left and top right corners of therectangle. All coordinates are integers between -10000 and 10000

Sample Input:
4 2 15
1 4
1 -4
-3 3
-3 -3
-6 0 -2 2
2 -2 6 5

OUTPUT: to (BABES.OUT)

Your program will output the optimal x and y locations formattedto 4 decimal places. Your programs score is the sum of the valuesof f(x,y) using the x and y coordinates given by your program.

Also, very important: Surfer John cannot put his chair in or onthe edge of an obstruction. For (x,y) points which lie in or onan obstruction, the value of f(x,y) is 0.

Values are to considered equal if the absolute difference of thetwo numbers is less than 1 x 10^-4.

Sample Output:

1.0000 1.0000

Note: this particular answer would receive a score of0.0333, as
f(1.0000,1.0000) in this case is equal to 0.0333.

Back to top

Query Board | Rules | LCIPC Main