Mr. Biscuit is in trouble. He accidentally deleted all the programs in his server and his database is corrupted as a result. There was a graph contained in the database. The graph had a source node and the shortest paths from the source node to the other nodes was calculated using a function called SSSP. Mr. Biscuit has found the pseudocode of the function in his notebook. The pseudocode is given below:
Input: A weighted graph G with vertices V and edges E
procedure SSSP(G,source):
1 Let N ← number of nodes in G
2 Let D[] ← 100000000 // D is an one dimensional array of size N
3 D[source] = 0
4 for step from 1 to N
5 for all edges from (u,v) in E
6 if D[u] + cost[u][v] < D[v]
7 D[v] = D[u] + cost[u][v]
8 end if
9 end for
10 end for
11 return D
While running the function to achieve the result, the array was stored in the database after each iteration of the loop starting at line . So, if the loop iterates times, the database will save copies of , possibly with different values. Thus, after each iteration, the array may be updated with the information about the shortest path of each node from the source.
Now, the database has been corrupted and Mr. Biscuit has lost the results regarding the shortest paths of the nodes. He also lost the original graph, but remembers that none of the weights of the edges of that graph had an absolute value over . After a few days of relentless effort, he managed to salvage the values of all the indices of after each iteration of the loop. Mr. Biscuit has saved all these data in a temporary backup server. It could be the case that the shortest paths may be retrievable from the data that has been salvaged.
You will have to find if there exists shortest paths from the source node to all the other nodes in the original graph. For retrieving the result, you can perform some queries from the data that Mr. Biscuit has salvaged. Since the backup server has limited resources, you can only perform a limited number of such queries to make your decision correctly.
You can make three types of interactions in this problem:
: The contestant will start the interaction by printing a , the contestant will receive the value of as a response after this interaction. This type of interaction will occur only once at the start of the communication.
The contestant will ask for a sub-array from index to () after the t’th () iteration of the loop at line of the pseudocode. In response, the contestant will get the values from index to index of the array after the t’th iteration of the function SSSP. A contestant can make at most interactions of this type. Each interaction should be valid.
3 result: After all the interactions of type and type , a contestant will print the result in the last line of interaction. The result should be , if there are shortest paths from the source to all the other nodes of the graph. Otherwise, the result should be .
Subtask #1 (10 points)
Subtask #2 (10 points)
Subtask #3 (25 points)
Subtask #4 (55 points)
After at most queries of type , you will have to answer if there exists shortest paths from the source node to all the other nodes in the original graph or otherwise. The result should be printed in the format mentioned in the interaction section. If you give an invalid query of any type, or if you request for an invalid query, you will receive a verdict of Wrong Answer.
For example, if , a sample interaction can be as follows:
input: 1
response: 3
input: 2 2 1 2
response: 7 12
input: 2 3 0 2
response: 0 7 12
input: 3 1
“Since this is an interactive problem, please don’t forget to flush your output after printing each line. You may use fflush(stdout) for printf/cout in C/C++, import sys and sys.stdout.flush() in Python to flush the output. If you use some other programming language, consult its documentation.
To learn more about Interactive Problems: https://help.toph.co/toph/interactive-problems” - reborn
In the pseudocode, the cost[u][v] indicates the weight of the directed edge connecting the nodes u and v.