Optimal Touring

Dennis Shasha

Omniheurist Course

Computer Science


 

Description

You want to visit up to n sites over k days. Each site has certain visiting hours. You have fixed a time you want to spend at each site which must all happen in one day. The time to go from site to site in minutes is the sum of street and avenue differences between them. On each day, you can start at any site you like (as if you teleported from the previous place you visited and slept on the street).

No more than 10 days and 200 sites.

You will be told the statistics of the sites and the number of days on the day of the contest.

The format will be
site, x location, y location, desiredtime, value
site, day, beginhour, endhour

Here is a typical file.

Note that desiredtime is in minutes. beginhour and endhour is inclusive e.g. 10 to 17 means an opening time from 10 AM and closes at 5:59:59 PM. Distributions can be arbitrary. Sites may not be open every day. Assume there are no more days beyond which those indicated in the latter part of the data file.

You want to achieve the maximum possible value summed over all sites within the time constraints. Visiting a site twice or more times gives no more value than visiting it once.

Note that a pure greedy strategy wouldn't be so good. Such a strategy might have you visit a site and and then visit the next nearest site. That might lead to large number of sites being found the first day (e.g. a central circle), but then later days might not have sites close to one another.

Your output should simply give a sequence of sites in the order of visit per day, one line per day.

Architecture Team

Show the layout of the sites. Show the route of the tourist on each day. Then calculate the total value obtained. Please don't give partial credit for visiting a site only some of the time required. A visit might be cut short because of the opening/closing times of the site. Here is a a zip file of the architecture. Here is

Here is a a zip file from 2021 of the architecture by Sam Yuan.