AIOC Banner

Problem: Optimal Delivery

Want to try solving this problem? You can submit your code online if you log in or register.


Optimal Delivery

Time Limit: 8 seconds
Memory Limit: 256 MB

Module (courier.h)
Module (courier.c)
Template (C)
Template (C++)

You have just moved to a new city, and started a job as a courier with OPTIMAL DELIVERY. The city is laid out on a grid of squares with R rows and C columns, with squares labelled from (0, 0) in the north-west corner to (R-1, C-1) in the south-east corner. It is only possible to travel between squares that are adjacent either horizontally or vertically.

Being new here, you haven't quite figured out the travel times between squares. A more experienced colleague tells you that all the travel times were chosen uniformly at random between 0 and 1 minute when the city was built, and have since been kept constant for tax purposes.

In order to avoid embarrassing your employer, you must first complete some mandatory training. You are to propose up to Q routes (one at a time), each between any two squares of your choice, and you will be told how much longer your route takes than the fastest route between those two squares.

Once you have completed your training, you will be asked to deliver a series of M parcels. For each parcel, you will be told the pickup square and the destination square. For each parcel, you may assume that the pickup square was chosen uniformly at random among all R*C squares in the city and that the destination square was then chosen uniformly at random among the remaining R*C-1 squares in the city. You must propose a route to deliver the parcel as fast as you can. You will be given points based on how much longer your route takes than the fastest route between those two squares.

Be warned though, OPTIMAL DELIVERY has high expectations of its new recruits, and will immediately fire you if you propose a route that passes through the same square more than once, or a route that passes outside the city grid, both during training and on the job.

Input / Output

This task has no input or output files. Instead your solution must interact with the functions the header file "courier.h". The provided functions are described in detail in the next section.

Do not output anything to stdout, or you will receive 0 points for the test case.

Module

Your program must interact with functions in "courier.h" as follows:

Experimentation

In order to experiment with your code on your own machine, first download the provided courier.h and courier.c files to the same folder as your code file, and add #include "courier.h" to the top of your code. A sample solution is also available to assist you. Compile your C solution with

gcc -O2 -Wall -static yourcode.c courier.c -o courier -lm

or, if you use C++,

g++ -std=c++11 -O2 -Wall -static yourcode.cpp courier.c -o courier

where yourcode.c/cpp is the name of your code file. Note that you should still use courier.c even if your solution is in C++. The compiled executable courier will read 4 whitespace-separated integers R C M Q from standard input, followed by 2R-1 lines describing the travel times, where even-numbered lines contain C-1 whitespace-separated decimal numbers between 0 and 1 (inclusive), and odd-numbered lines contain C whitespace separated decimal numbers between 0 and 1 (inclusive). This should be followed by M lines of the form RSi CSi REi CEi, where (RSi, CSi) is the starting square and (REi, CEi) is the ending square for the ith call that the module will make to the solve function. Such an input file will look something like this:



where hi, j is the travel time between square (i, j) and square (i, j+1), and vi, j is the travel time between square (i, j) and square (i+1, j).

Note: the input as illustrated here contains extra whitespace for clarity. This is not required by the module, but will be safely ignored if provided.

The executable will print M lines to standard output, where the ith line contains a decimal number si, the score your program receives for query i. This will be followed by a line containing Total score: S, where S is the total score for the test case. See the Scoring section for more details.

Sample Input

3 4 1 2
    0.5     1.0     0.9
0.1     0.6     0.7     0.4
    0.0     1.0     0.3
0.3     0.2     0.4     0.6
    0.0     1.0     0.5

2 1 0 2

Sample Session

  1. The module calls init(3, 4, 1, 2).
  2. You call query(0, 0, 3, "EEE"). The function returns 0.6 since the proposed route takes 2.4 minutes, while the fastest possible route "SEEEN" takes 1.8 minutes.
  3. You call query(1, 0, 2, "ES"). This path takes 0.2 minutes and is the fastest route, so the function returns 0.
  4. Your init function returns.
  5. The module calls solve(2, 1, 0, 2, &length, path), as specified in the input, asking you to find as quick a route as you can between squares (2, 1) and (0, 2).

    You set *length = 3 and path[0] = `N', path[1] = `E', path[2] = `N'. The module outputs 33 to standard output, the score for this query.

  6. The module outputs Total score: 33 to standard output, the total score for this test case.

Subtasks & Constraints

For all calls to solve, 0 ≤ rStart, rEnd < R and 0 ≤ cStart, cEnd < C, and length and path will always be non-NULL pointers. Also note that for all cases within a subtask, the values of R, C, M and Q are fixed, as specified:

Scoring

Your score for this problem will be the maximum score among all your submissions to the problem. For each submission, your score for each subtask will be the minimum score among all test cases in that subtask. Your score for each test case will be

where t, tF, and tM are the sums of all ti, tFi, and tMi, respectively. For the ith call to solve:

If you propose a route that results in you being fired, you will receive 0 points for the test case.

If you output anything to stdout, you will receive 0 points for the test case.

 


Privacy statement
© Australian Mathematics Trust 2001-2019

Contact: training@orac.amt.edu.au
Page generated: 15 November 2019,  5:31am AEDT