And as quick as it all started, pre-IOI training camp is coming to an end. Tomorrow morning we fly to Brisbane.
The teams are currently sitting their last practice exam before the actual IOI, for which the first exam day is Monday. That's under 72 hours away!
Here's a problem from yesterday's exam which no one solved:
In today's exam, one of the problems requires students to help plan the NBN roll-out.
This is quite a difficult problem. Experienced readers might notice that this problem is very similar to finding a minimum spanning tree, which is a well-known problem with fast and relatively simple algorithms that solve it. Unfortunately because the number we're minimising is the product of total time and total cost, we can't easily build up our MST one cable at a time, the way we would if we were minimising only time or only cost. The first, and simplest observation students will have to make is that for a solution to potentially be optimal (the best), there can be no other solution with lower total time AND lower total money. How to exploit this is another matter...
The teams are currently sitting their last practice exam before the actual IOI, for which the first exam day is Monday. That's under 72 hours away!
Here's a problem from yesterday's exam which no one solved:
The students and leaders are going to a restaurant for dinner. The restaurant needs to set up two circular tables, which must be of equal size. The restaurant is represented as a convex polygon. What is the largest table size possible that the restaurant can fit two of within their walls?
(Given a convex polygon with up to 50,000 vertices, what is the largest radius r such that two r-radius circles can be placed inside the polygon without intersection?)
(Given a convex polygon with up to 50,000 vertices, what is the largest radius r such that two r-radius circles can be placed inside the polygon without intersection?)
In today's exam, one of the problems requires students to help plan the NBN roll-out.
NBN Co needs to build a network of fibre-optic cables to connect a set of (up to 200) towns in an outback region of Australia. One of the towns is already connected to the NBN, but all the others aren't yet. For every pair of towns, NBN Co has determined two values (each between 0 and 255): the time and the cost of building a direct line between them. Rather than just minimising time, or just minimising cost, NBN Co wants to minimise their product (ie. the total time multiplied by the total cost). Where should the fibre-optic cables be placed so that every town is connected by cable (either directly or indirectly) to the town with the NBN connection, at minimum time x cost?
This is quite a difficult problem. Experienced readers might notice that this problem is very similar to finding a minimum spanning tree, which is a well-known problem with fast and relatively simple algorithms that solve it. Unfortunately because the number we're minimising is the product of total time and total cost, we can't easily build up our MST one cable at a time, the way we would if we were minimising only time or only cost. The first, and simplest observation students will have to make is that for a solution to potentially be optimal (the best), there can be no other solution with lower total time AND lower total money. How to exploit this is another matter...
No comments:
Post a Comment