To us, C was very tough to code. So we just tried to place say around 2k house+garden and every time we randomly picked (r, c) for anchor and random orientation of house+garden. It gave us around 600+ score.

I would be interested to hear about B

A: some matrix exponentiation

B: sort the segments by their right border, then choose them greedily

These were ACM-style tasks. We got 12th place in C by the following algorithm:

totalScore = 0
failsInARow = 0
while true {
  bestScore = -1
  for (int i = 0; i < 500; i++) {
    build a house randomly
    if it fits {
      foreach (all possible garden positions) {
        build that garden
        if it fits too {
          try to update bestScore
        }
      }
    }
  }
  if bestScore > 0 {
    update totalScore, build the chosen house and garden
    failsInARow = 0
  } else {
    failsInARow++
  }
  if failsInARow > 25 {
    // there is nothing we can do here
    break
  }
}
print totalScore and a certificate

D was completely written by Slamur and craus, I don't know about their algorithm, but they managed to get the 2nd place in 7th test, and the 6th place in total.

We got 5th place with D. It was about 2 hour coding and 2 hour calibration to maximise score. The idea is to concentrate on minimising K. Sort all cities by the end of the time interval. Visit cities in this order. For each city find if there is a car anywhere that can reach it with enough goods and take the car that is closest. If there isn't a car, then send a new car from depot. That's it. Tests were such that there weren't that many cars at any time sent from depo and it ran very quickly, without having to bound the number of cars.

Calibration. Try changing the sorting method for cities — didn't help much. Try looking ahead for cities, rather then just taking the next one. Execution time was reasonable, but number of cities to look ahead had to be bounded to about a 100. Take the minimim distance from all combinations of car — city mapping. From here you could further see a number of ways to optimise in addition to what we tried.

We have also written a more optimal solution, but less efficient. It gave better answer for the first 2 tests. We finished 9th overall.

Problem D by Charles University Legion (1st place):

1. Build initial solution (similarly to problem B):

   • sort clients by end of time interval
   • we are now processing clients in the sorted order and creating the initial car paths:
     • append the client to closest car path that can be extended
     • if no existing car path can be extended by current client, create a new car path

2. Iterate:

   • choose randomly 1/10th of the existing car paths and cut them in two smaller paths on random places
   • while possible, pick two closest car paths, that can be concatenated and concatenate them

Step 2. is also called on the best solution found so far.

1. Insert some random decisions into the above algorithm and run it thousands of times.

2. Profit!

D (2nd place) with a simple solution:

Initialize with a simple solution — one vehicle to one client.

Till the end of time do a hill climbing. The state is a path for each vehicle. There are 4 transition functions: (1) swap within single path (2) reverse within single path (3) swap in two paths (4) move one client to a different path and destroy the path if it's empty. Accept move if it increases the score or with some small probability.

The last thing was an addition of a special "move" that tries to remove a path (vehicle), and distributes the clients to the remaining vehicles. I think we would still have the 2nd place without this, but only due to big margin between 2nd & 3rd place.

Probably the most important idea was the loading of the current solution. I didn't optimize the code at all (lot's of pointless memory allocations, etc.) and it took really long (around 1h) to get a decent solution on bigger tests. That way I could tweak some stuff without having to start from scratch.

We used a simple greedy approach in problem C: find a position+orientation for pair house+garden which gives the most points, fix these house+garden at the position; then find the best position for another pair house+garden (including that we have already pasted previous pairs) and so on while the bonus from new house is positive. It gave 3rd-5th places for most test before the frozing. A way to improve it: try to remove one pair house+garden and place another pair (with probably better result) on the field and repeat such operations while possible. This increases result only by 2-5% but it was enough to be placed 1st-2nd on the big tests (5-10) at the final scoreboard, 997 points in total.

Who the hell came up with an idea of making time negative in B :P? That is so wrong, I wasted more time in finding that than actually solving the problem :P.