INTERNATIONAL COLLEGIATE PROGRAMMING COMPETITION | Figuring out complex problems

The competition at YSU will require students to write computer programs to solve a series of seven problems. Here are examples of past problems:

A Careful Approach: If you think participating in a programming contest is stressful, imagine being an air-traffic controller. With human lives at stake, an air-traffic controller has to focus on tasks while working under constantly changing conditions as well as dealing with unforeseen events. Consider the task of scheduling the airplanes that are landing at an airport. Incoming airplanes report their positions, directions and speeds, and then the controller has to devise a landing schedule that brings all airplanes safely to the ground. Generally, the more time there is between successive landings, the “safer” a landing schedule is. This extra time gives pilots the opportunity to react to changing weather and other surprises. Luckily, part of this scheduling task can be automated — this is where you come in. You will be given scenarios of airplane landings. Each airplane has a time window during which it can safely land. You must compute an order for landing all airplanes that respects these time windows. Furthermore, the airplane landings should be stretched out as much as possible so that the minimum time gap between successive landings is as large as possible. For example, if three airplanes land at 10 a.m., 10 a.m. and 10:15 a.m., then the smallest gap is five minutes, which occurs between the first two airplanes. Not all gaps have to be the same, but the smallest gap should be as large as possible.

Balloons in a Box: You must write a program that simulates placing spherical balloons into a rectangular box. The simulation scenario is as follows. Imagine that you are given a rectangular box and a set of points. Each point represents a position where you might place a balloon. To place a balloon at a point, center it at the point and inflate the balloon until it touches a side of the box or a previously placed balloon. You may not use a point that is outside the box or inside a previously placed balloon. However, you may use the points in any order you like, and you need not use every point. Your objective is to place balloons in the box in an order that maximizes the total volume occupied by the balloons. You are required to calculate the volume within the box that is not enclosed by the balloons.