Obligatory Assignment 4

  • Read the instructions in the preface

  • Groups can differ from those in the previous assignments.

  • Deadline: Saturday, May 31, 2025, at 23:59

Candle Race

The following problem was posed by Carlos Fonseca and Alexandre Jesus at the SIGEVO Summer School 2024.

In a race, there is a set of villages to be visited, \(V\), and there is a candle in each village. Villages and the corresponding candles are identified by an index, \(i = 1, \ldots , n\), and different candles may have different properties. In particular, each candle \(i\) has a length, \(h_i\), and a burning rate, \(b_i\). For each minute that passes, the length \(h_i\) is reduced by \(b_i\), until it eventually reaches \(0\). There is also a village with index \(0\) where the race starts. This village has no candle. At the beginning of the race, the candles are lit. The goal is to visit each village and blow out the candles. When a candle is blown out, the player scores points equal to the remaining length of the candle. Given the properties of each candle, and the minimum travelling time between the villages, the problem consists in finding a route that maximizes the player’s score.

Input

The first line of the input contains an integer \(n\) denoting the number of villages. The following line contains two integers denoting the \(x\) and \(y\) coordinates of the starting village. The following \(n - 1\) lines each give four space-separated integers corresponding to the information pertaining to each village:

  • \(x\) coordinate
  • \(y\) coordinate
  • Initial candle height, \(h_i\)
  • Burning rate per unit of time, \(b_i\)

The time in minutes between two villages is given by the Manhattan distance.

Output

Print the indices of the villages in the order that they should be visited (excluding the starting village), one index per line. It is assumed that, once the player arrives at a village, they immediately blow out the candle (there is no point in waiting after all).

Note: The player does not need to visit every village.

Example

Input:

5
0 0
16 25 464 2
10 34 696 6
28 17 302 5
19 57 523 10

Output (Score 502):

1
3
2
4

Problem Instances

Three instances of the problem are available in this archive.

Remarks

  • The assignment is about Randomized Optimization Heuristics and you must follow the ROAR specification. An implementation thereof for the TSP has been made availabe in Unit 7. A more complete implementation for the SMTWTP is available as solution to Sheet 11.

  • In the report you must provide information about your specific implementation of the problem modeling operations. In case of need to show algorithm sketches, use pseudo-code rather than Python snippets.

  • For the algorithms implemented (ie, metaheuristics) specify whether the implementation is yours or whether you used the handed out template.

  • If you have compared different algorithms give account of this in the report.

  • Use a time limit of 60 seconds per run. Report the results of your best algorithm on each instance in a table in the report.

  • The quality of the final solution has an impact on the grade of this assignment.

  • The code submitted must execute your best algorithm taking as input the filename of the instance and outputting the solution in the format described above in a file with the same name as the instance but with the extension .out placed in the same directory where the program is executed.