In the latest video game you are playing, you find yourself in a mysterious world. The world can be represented as a connected graph over n vertices, numbered from 0 to n - 1. There are m bidirectional edges in the graph, numbered from 0 to m - 1, each connecting a different pair of vertices. All edges have the same length. You have been told the exact layout of this graph.
To test your vast knowledge, you will have to solve t tests.
In each test, one vertex has been secretly chosen as the prime vertex, and your task is to identify which vertex it is. To help you do so, you have been given a device called the Nav. The Nav is designed to help you navigate to the prime vertex. It does so by allowing you to query it, in the following manner.
You input a vertex of your choosing, call it u. If u is the prime vertex, the Nav will return 1.
Otherwise, the Nav computes a shortest path from u to the prime vertex. Note that if there is more than one such path, the Nav can choose any of these.
The Nav returns an integer between 0 and m - 1, corresponding to a single edge that is a part of the computed shortest path.
Your task is to identify the prime vertex, using as few Nav queries as possible.
The fewer queries you use, the more points you will score for this problem. See the Subtasks and Constraints section below for further details.
For all subtasks, you are guaranteed that:
n ≥ 1
n - 1 ≤ m ≤ 100,000
The provided graph will be connected
Every edge will connect two different vertices
No two edges connect the same pair of vertices.
For each subtask, there is a maximum number q of queries you can make to the Nav per test. Your score for a testcase is computed as follows:
If you make more than q queries for any test, you will receive 0 points. This will be reported as
If your program exceeds the time limit, you will receive 0 points.
If your program does not successfully terminate, or fails to identify the prime vertex, you will receive a score of 0 points. This will be reported as
Otherwise, if your program correctly identifies the prime vertex in all cases:
For Subtasks 1 to 3: you will score 100% of the marks for that subtask. This will be reported as
For Subtask 4, your score is computed, based on the number of queries q_max that your program made in any test. Specifically, your score will be:
100%, if qmax ≤ 9;
70%, if 10 ≤ qmax ≤ 12; or
140/3×(30-q)/q %, if 13 ≤ q ≤ 30.
|Subtask||Points||Maximum t||Maximum n||q||Additional constraints|
|1||7||750||n ≤ 300||300|
|2||15||250,000||n ≤ 100,000||17||m = n - 1, and for each 0 ≤ j ≤ m - 1,|
|edge j connects vertex j and vertex j + 1.|
|That is, the graph is a line.|
|3||26||750||n ≤ 1000||10||m = n - 1. That is, the graph is a tree.|
|4||52||750||n ≤ 300||30|
Recall that your score for this problem is the sum of your scores for each subtask. Your score for a subtask is the maximum score obtained among any of your submissions. As such, you may wish to solve different subtasks in different submissions.
This task has no input or output files. Instead, your solution must interact with the functions in the header file
"nav.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.
You must not implement a
main function. Instead, you should
#include "nav.h" and implement the two functions
findPrime, described below:
void init(int subtask, int n, int m, std::vector<int> A, std::vector<int> B);
subtask is the subtask number
n is the number of vertices
m is the number of edges
For every 0 ≤ j ≤ m - 1, edge j connects vertices
This function will be called first to initialise your program.
This function should return an integer between 0 and n - 1: the number corresponding to the prime vertex.
The grader will call this function t times, once for each test. Your program is not told t.
In your implementation, you may call the following function.
int nav(int u)
u must be an integer, between 0 and n - 1, corresponding to the number of a vertex of your choosing.
If u is the prime vertex, the function returns −1. Otherwise, the function returns an integer between 0 and m - 1, corresponding to an edge along a shortest path between u and the prime vertex.
nav is called with an invalid value of u, the program will terminate, and you will score 0% for that testcase. This will be reported as
You may assume that over the course of a single test, the grader that is used does not change the identity of the prime vertex.
nav.cpp has been provided for your convenience.
In order to experiment with your code on your own machine, first download the provided files
grader.cpp, which should be placed in the same directory as your code. Please note that the grader that is used may have different behaviour to the provided grader.
Compile your solution with:
g++ -std=c++11 -O2 -Wall -static nav.cpp grader.cpp -o nav
This will create an executable
nav, which you can run with
./nav. If you have trouble compiling, please send a message in the Communication section of the contest website.
The compiled sample grader will read in the subtask number, n and m on the first line.
It will then read m more lines. From the i-th of these lines, the sample grader wil read two integers
On the next line, it will read in the integer t, the number of tests, followed by t lines. From the j-th of these lines, it will read in the secret prime vertex for the j-th test.
For each test, the sample grader will call
findPrime() and print out whether your program successfully found the prime vertex, along with the number of queries it made.
4 6 7 2 5 2 3 2 1 1 3 0 1 3 4 4 0 3 3 5 3
The grader begins by reading in the graph, and then interacts with your program.
One possible interaction is shown below:
||The grader initialises your program. This sample case is for Subtask 4.|
||The grader starts the first test. The prime vertex is vertex 3|
||Your program calls
||The grader picks the shortest path 0 → 4 → 3, and chooses to return edge 6 (the edge between 0 and 4).|
||Your program calls
||The grader picks the shortest path 2 → 3, and chooses to return edge 1 (the edge between 2 and 3).|
||Your program calls
||This is the prime vertex.|
|You return 3||Your program guesses the prime vertex is vertex 3. This is correct.|
||The grader starts the second test. The prime vertex is vertex 5|
||Your program calls
||The grader picks the shortest path 4 → 3 → 2 → 5, and chooses to return edge 1 (the edge between 2 and 3).|
|You return 1||Your program guesses the prime vertex is vertex 1. This is not correct.|
||The grader starts the third test. The prime vertex is vertex 3 again.|
|You return 3||Your program guesses the prime vertex is vertex 3, without making any calls to
In this example, you have solved two of the three cases correctly, so you would score 0% points.
The table below lists binary modules for this problem that are available for download. Please choose the version that best matches your platform, language and compiler. Be sure to download the files in binary mode (e.g., by right-clicking on the links and selecting Save As).
If you do not find a suitable module in this table, please contact firstname.lastname@example.org and we will see whether your environment can be added to the list.
|GNU/Linux||C/C++ (gcc)||grader.cpp, nav.cpp, nav.h|