problem with implementing this question of HackerRank
// Can anyone help how to implement the below problem.
You are given a directed graph with 'n' nodes numbered 'i' from to 'n-1'. For every 'i' from '1' to 'n-1', there is an edge from node 'i' to node 'i+1' of weight 'wi', and there is an edge from node 'n' to node '1' of weight 'wn'. Thus, the 'n' nodes form a directed cycle.
You have to process 'm' queries of the following four types. In the following, 'x' denotes a node between '1' and 'n'. Also, some queries will attempt to add or delete nodes, but it's guaranteed that the original 'n' nodes will never be deleted.
. 1 x w : Let the farthest node from 'x' be 'y'. Add an edge of weight 'w' from 'y' to a new node.
. 2 x w : Add an edge of weight 'w' from 'x' to a new node.
. 3 x : Let the farthest node from 'x' be 'y'. Delete node 'y'.
. 4 x : Let the farthest node from 'x' be 'y'. Print the distance from 'x' to 'y'.
The distance from 'x' to 'y' is defined as the shortest total weight of any path from 'x' to 'y'. The farthest node from 'x' is the node 'y' with the largest distance from 'x'.
Note: If multiple nodes are farthest from 'x', choose the one that was added to the graph most recently.
Complete the function cyclicalQueries which takes in an integer array 'w' denoting the weights of the initial edges and an integer 'm' and returns a list of answers to queries of type '4'. You have to take the query information from standard input, as described in the input format section.
Input Format:-
The first line contains a single integer 'n'.
The next line contains 'n' space-separated integers 'w1','w2',...,'wn'.
The next line contains a single integer 'm' denoting the number of queries. 'm' lines follow, where the 'ith' line denotes the 'ith' query, each in the format described above.
Constraints
- 1 <= n,w <= pow(10,5)
- 1 <= w,wi <= pow(10,9)
- 1 <= x <= n
Output Format-:
For each query of type '4', print the answer in a single line.
Sample Input 0
5
1 1 1 1 1
4
1 1 5
4 2
3 2
4 2
Sample Output 0
8
4
Explanation 0
Query 1: A new node '6' is added from node '5', with an edge weight of '5'.
Query 2: Distance from node '2' to node '6' is printed.
Query 3: Node '6' is deleted.
Query 4: Distance from node '2' to node '5' is printed.
// Complete the cyclicalQueries function below.
vector<long> cyclicalQueries(vector<long> w, int m) {
// Return the list of answers to all queries of type 4. Take the query information from standard input.
}
You are given a directed graph with 'n' nodes numbered 'i' from to 'n-1'. For every 'i' from '1' to 'n-1', there is an edge from node 'i' to node 'i+1' of weight 'wi', and there is an edge from node 'n' to node '1' of weight 'wn'. Thus, the 'n' nodes form a directed cycle.
You have to process 'm' queries of the following four types. In the following, 'x' denotes a node between '1' and 'n'. Also, some queries will attempt to add or delete nodes, but it's guaranteed that the original 'n' nodes will never be deleted.
. 1 x w : Let the farthest node from 'x' be 'y'. Add an edge of weight 'w' from 'y' to a new node.
. 2 x w : Add an edge of weight 'w' from 'x' to a new node.
. 3 x : Let the farthest node from 'x' be 'y'. Delete node 'y'.
. 4 x : Let the farthest node from 'x' be 'y'. Print the distance from 'x' to 'y'.
The distance from 'x' to 'y' is defined as the shortest total weight of any path from 'x' to 'y'. The farthest node from 'x' is the node 'y' with the largest distance from 'x'.
Note: If multiple nodes are farthest from 'x', choose the one that was added to the graph most recently.
Complete the function cyclicalQueries which takes in an integer array 'w' denoting the weights of the initial edges and an integer 'm' and returns a list of answers to queries of type '4'. You have to take the query information from standard input, as described in the input format section.
Input Format:-
The first line contains a single integer 'n'.
The next line contains 'n' space-separated integers 'w1','w2',...,'wn'.
The next line contains a single integer 'm' denoting the number of queries. 'm' lines follow, where the 'ith' line denotes the 'ith' query, each in the format described above.
Constraints
- 1 <= n,w <= pow(10,5)
- 1 <= w,wi <= pow(10,9)
- 1 <= x <= n
Output Format-:
For each query of type '4', print the answer in a single line.
Sample Input 0
5
1 1 1 1 1
4
1 1 5
4 2
3 2
4 2
Sample Output 0
8
4
Explanation 0
Query 1: A new node '6' is added from node '5', with an edge weight of '5'.
Query 2: Distance from node '2' to node '6' is printed.
Query 3: Node '6' is deleted.
Query 4: Distance from node '2' to node '5' is printed.
// Complete the cyclicalQueries function below.
vector<long> cyclicalQueries(vector<long> w, int m) {
// Return the list of answers to all queries of type 4. Take the query information from standard input.
}
What have you tried so far? What are you having problems with?
Can you show us your code so that we can tell where you can change/improve things?
Can you show us your code so that we can tell where you can change/improve things?
Topic archived. No new replies allowed.