haku's blog

By haku, 9 years ago, In English

Let's discuss problems here.

It would be interesting to hear some good solutions for C and D.

  • Vote: I like it
  • +26
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    ehm.

    How can you solve B like this on sample test case?

    5
    2 4
    1 5
    2 6
    6 7
    4 8
    

    (I sorted segments for you).

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it
      int n;
      cin >> n;
      VC<PII> vp;
      REP(i, n) {
      	int a, b;
      	cin >> a >> b;
      	vp.PB(MP(b, a));
      }
      sort(ALL(vp));
      REP(i, n) swap(vp[i].X, vp[i].Y);
      int posa = -(1<<30);
      int posb = -(1<<30);
      int rv = 0;
      REP(i, n) {
      	if (vp[i].X >= posb) {
      		posb = vp[i].Y;
      		rv++;
      	} else if (vp[i].X >= posa) {
      		posa = vp[i].Y;
      		rv++;
      	}
      	if (posa > posb) swap(posa, posb);
      }
      cout << rv << endl;
      
»
9 years ago, # |
Rev. 8   Vote: I like it +13 Vote: I do not like it

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.

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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!

»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Is reversing a path helping anything? Time intervals are pretty short, so it is very likely that we won't be able to reverse a path consisting of >=2 vertices (and of course reversing path with 1 vertex is doing nothing).

    What do you mean by "the loading of the current solution."? I didn't get it.

    And one more additional question just out of curiosty — how big were ratios c/k and t0/t in your solutions?

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Is reversing a path helping anything? Time intervals are pretty short, so it is very likely that we won't be able to reverse a path consisting of >=2 vertices (and of course reversing path with 1 vertex is doing nothing).

      Probably doesn't do anything (due to time intervals as you mentioned, but I didn't really look at the tests during the contest). Actually it's >= 4, since lengths 2 & 3 are handled by a single swap.

      What do you mean by "the loading of the current solution."? I didn't get it.

      I'm saving my best solution every second or so. When I kill my program, I can start my (new) program from my last solution.

      I'm pasting top line from my solutions (i.e. number of vehicles & fuel consumption). The first two doesn't correspond with my best submission:

      9 3670
      24 9490
      137 222178
      779 2399650
      653 5297886
      112 1177490
      278 3854464
      538 8038050
      815 18140862
      1106 63087606
      

      In general, the priority was to minimize the number of vehicles, since minimizing fuel consumption was somewhat independent of vehicle number. The only problem was that the tempo of reducing the fuel consumption was lower (in case of my algo), when you had fewer redundant vehicles.

»
9 years ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

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.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.