YSU hosts 165 students for international computer programming contest

icpc_logo_bigMore than 160 students representing 21 universities across the region will come to Youngstown State University Friday and Saturday, Nov. 7 and 8, to participate in the International Collegiate Programming Competition.

Students will write computer programs to solve a series of seven problems, from landing aircraft safely at a busy airport to figuring out how much food you need for a walking trip across a desert. (See below for examples of problems at past competitions.)

Winners advance to the world finals in Morocco in May 2015.

YSU is among four sites throughout the East Central region hosting the contest. Robert Kramer, associate professor of Computer Science and Information Systems at YSU, is the regional director, overseeing sites at YSU, the University of Cincinnati, Grand Valley State University (Michigan) and the University of Windsor (Ontario, Canada.) Robert Gilliland, instructor of CSIS at YSU, and Bonita Sharif, assistant professor of CSIS at YSU, are co-site directors.

Among the schools represented at the YSU contest are Carnegie Mellon University, Allegheny College, Cleveland State, College of Wooster, Duquesne University, Edinboro State University, Penn State, the University of Toledo and the University of Pittsburgh.

The contest is sponsored by IBM. Each three-student team has access to one computer workstation, and is given (on paper) a set of independent problems to solve. Each solution is a program, composed by the team at the workstation. Contest Itinerary

The YSU event is in Meshel Hall, with registration the afternoon and evening of Friday, Nov. 7. The actual contest is set for 10 a.m. to 3 p.m. Saturday, Nov. 8, in Meshel Hall, with an awards banquet at 4 p.m. in the Chestnut Room of Kilcawley Center on the YSU campus.

For more information, or to make arrangement for media interviews and coverage, contact Gilliland at 330-941-2808 (office) or 330-259-1246 (cell). For more information on the East Central contest, visit http://acm-ecna.ysu.edu/. And for more details about the world finals, including links to past problems, visit http://acm-ecna.ysu.edu/.

Examples of past problems

se_project_reachnewheights1A 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:00am, 10:05am, and 10:15am, 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.

DSC_0388Balloons 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.

119046989_Desert_369520cCrossing the Desert: In this problem, you will compute how much food you need to purchase for a trip across the desert on foot. At your starting location, you can purchase food at the general store and you can collect an unlimited amount of free water. The desert may contain oases at various locations. At each oasis, you can collect as much water as you like and you can store food for later use, but you cannot purchase any additional food. You can also store food for later use at the starting location. You will be given the coordinates of the starting location, all the oases, and your destination in a two-dimensional coordinate system where the unit distance is one mile. For each mile that you walk, you must consume one unit of food and one unit of water. Assume that these supplies are consumed continuously, so if you walk for a partial mile you will consume partial units of food and water. You are not able to walk at all unless you have supplies of both food and water. You must consume the supplies while you are walking, not while you are resting at an oasis. Of course, there is a limit to the total amount of food and water that you can carry. This limit is expressed as a carrying capacity in total units. At no time can the sum of the food units and the water units that you are carrying exceed this capacity. You must decide how much food you need to purchase at the starting location in order to make it to the destination. You need not have any food or water left when you arrive at the destination. Since the general store sells food only in whole units and has only one million food units available, the amount of food you should buy will be an integer greater than zero and less than or equal to one million.