Finding path having a subpath and has maximum gcd(starting node, ending node)
I got a question in a contest(which is ended weeks ago). The question as I interpreted was -:
Given an undirected acyclic graph which is connected by (N-1) edges
and N nodes. The graph is guaranteed to be connected. Given two nodes
u and v, you have to find two nodes x and y of the graph such that the
path between these two nodes overlaps the path between the given
cities u and v completely and gcd(x, y) is maximum possible.
Constraints
1 <= N <= 5 * 10^5
1 <= a,b,u,v <= N
where a,b are the two arbitrary nodes in the graph.
Example let the graph has 10 nodes (1 to 10)
Now in preceeding line I will give two integers a and b which means a and b are directly connected.
1 4
1 5
1 2
4 3
4 6
5 7
2 10
2 9
2 8
At last
u v
4 2
Ans - 4
The path from u to v is 4 -> 1 -> 2
Now, some of the paths which completely ovelaps the path from u to v are:
4 -> 1 -> 2 -> 10
3 -> 4 -> 1 -> 2 -> 9
4 -> 1 -> 2 -> 8
and so on....
Note that, selecting the path from 4 to 8 completely overlaps path u to v and also gcd(4,8) = 4 which is the maximum possible.
The graph is :
https://i.stack.imgur.com/Phkwi.png
Time Limit: 3.0 sec
My approach for solving the problem was :
Find the path from each node to every other node and store it in list of arrays.
Iterate over all lists and find whether u and v path is contained in the array.
If the path is found and calculate the gcd of starting and ending node and check for the max gcd.
However I think my approach is too brute force and code is too long and I think it has too much complexity.
Can anyone suggest any suggestion or approach to tackle this question?
java graph greatest-common-divisor undirected-graph
asked Dec 30 '18 at 14:46
Brij Raj KishoreBrij Raj Kishore
1,0201418
add a comment |
I got a question in a contest(which is ended weeks ago). The question as I interpreted was -:
Given an undirected acyclic graph which is connected by (N-1) edges
and N nodes. The graph is guaranteed to be connected. Given two nodes
u and v, you have to find two nodes x and y of the graph such that the
path between these two nodes overlaps the path between the given
cities u and v completely and gcd(x, y) is maximum possible.
Constraints
1 <= N <= 5 * 10^5
1 <= a,b,u,v <= N
where a,b are the two arbitrary nodes in the graph.
Example let the graph has 10 nodes (1 to 10)
Now in preceeding line I will give two integers a and b which means a and b are directly connected.
1 4
1 5
1 2
4 3
4 6
5 7
2 10
2 9
2 8
At last
u v
4 2
Ans - 4
The path from u to v is 4 -> 1 -> 2
Now, some of the paths which completely ovelaps the path from u to v are:
4 -> 1 -> 2 -> 10
3 -> 4 -> 1 -> 2 -> 9
4 -> 1 -> 2 -> 8
and so on....
Note that, selecting the path from 4 to 8 completely overlaps path u to v and also gcd(4,8) = 4 which is the maximum possible.
The graph is :
https://i.stack.imgur.com/Phkwi.png
Time Limit: 3.0 sec
My approach for solving the problem was :
Find the path from each node to every other node and store it in list of arrays.
Iterate over all lists and find whether u and v path is contained in the array.
If the path is found and calculate the gcd of starting and ending node and check for the max gcd.
However I think my approach is too brute force and code is too long and I think it has too much complexity.
Can anyone suggest any suggestion or approach to tackle this question?
java graph greatest-common-divisor undirected-graph
asked Dec 30 '18 at 14:46
Brij Raj KishoreBrij Raj Kishore
1,0201418
Show us your code
– Just another Java programmer
Dec 30 '18 at 14:48
pastebin.com/7YfQBVW6
– Brij Raj Kishore
Dec 30 '18 at 14:56
Its a bit long and uncommented. Sorry I have to do it in hurry at that time.
– Brij Raj Kishore
Dec 30 '18 at 14:56
add a comment |
I got a question in a contest(which is ended weeks ago). The question as I interpreted was -:
Given an undirected acyclic graph which is connected by (N-1) edges
and N nodes. The graph is guaranteed to be connected. Given two nodes
u and v, you have to find two nodes x and y of the graph such that the
path between these two nodes overlaps the path between the given
cities u and v completely and gcd(x, y) is maximum possible.
Constraints
1 <= N <= 5 * 10^5
1 <= a,b,u,v <= N
where a,b are the two arbitrary nodes in the graph.
Example let the graph has 10 nodes (1 to 10)
Now in preceeding line I will give two integers a and b which means a and b are directly connected.
1 4
1 5
1 2
4 3
4 6
5 7
2 10
2 9
2 8
At last
u v
4 2
Ans - 4
The path from u to v is 4 -> 1 -> 2
Now, some of the paths which completely ovelaps the path from u to v are:
4 -> 1 -> 2 -> 10
3 -> 4 -> 1 -> 2 -> 9
4 -> 1 -> 2 -> 8
and so on....
Note that, selecting the path from 4 to 8 completely overlaps path u to v and also gcd(4,8) = 4 which is the maximum possible.
The graph is :
https://i.stack.imgur.com/Phkwi.png
Time Limit: 3.0 sec
My approach for solving the problem was :
Find the path from each node to every other node and store it in list of arrays.
Iterate over all lists and find whether u and v path is contained in the array.
If the path is found and calculate the gcd of starting and ending node and check for the max gcd.
However I think my approach is too brute force and code is too long and I think it has too much complexity.
Can anyone suggest any suggestion or approach to tackle this question?
java graph greatest-common-divisor undirected-graph
asked Dec 30 '18 at 14:46
Brij Raj KishoreBrij Raj Kishore
1,0201418
I got a question in a contest(which is ended weeks ago). The question as I interpreted was -:
Given an undirected acyclic graph which is connected by (N-1) edges
and N nodes. The graph is guaranteed to be connected. Given two nodes
u and v, you have to find two nodes x and y of the graph such that the
path between these two nodes overlaps the path between the given
cities u and v completely and gcd(x, y) is maximum possible.
Constraints
1 <= N <= 5 * 10^5
1 <= a,b,u,v <= N
where a,b are the two arbitrary nodes in the graph.
Example let the graph has 10 nodes (1 to 10)
Now in preceeding line I will give two integers a and b which means a and b are directly connected.
1 4
1 5
1 2
4 3
4 6
5 7
2 10
2 9
2 8
At last
u v
4 2
Ans - 4
The path from u to v is 4 -> 1 -> 2
Now, some of the paths which completely ovelaps the path from u to v are:
4 -> 1 -> 2 -> 10
3 -> 4 -> 1 -> 2 -> 9
4 -> 1 -> 2 -> 8
and so on....
Note that, selecting the path from 4 to 8 completely overlaps path u to v and also gcd(4,8) = 4 which is the maximum possible.
The graph is :
https://i.stack.imgur.com/Phkwi.png
Time Limit: 3.0 sec
My approach for solving the problem was :
Find the path from each node to every other node and store it in list of arrays.
Iterate over all lists and find whether u and v path is contained in the array.
If the path is found and calculate the gcd of starting and ending node and check for the max gcd.
However I think my approach is too brute force and code is too long and I think it has too much complexity.
Can anyone suggest any suggestion or approach to tackle this question?
java graph greatest-common-divisor undirected-graph
java graph greatest-common-divisor undirected-graph
asked Dec 30 '18 at 14:46
Brij Raj KishoreBrij Raj Kishore
1,0201418
asked Dec 30 '18 at 14:46
Brij Raj KishoreBrij Raj Kishore
1,0201418
edited Dec 31 '18 at 2:33
Brij Raj Kishore
asked Dec 30 '18 at 14:46
Brij Raj KishoreBrij Raj Kishore
1,0201418
asked Dec 30 '18 at 14:46
Brij Raj KishoreBrij Raj Kishore
1,0201418
asked Dec 30 '18 at 14:46
Brij Raj KishoreBrij Raj Kishore
1,0201418
1,0201418
Show us your code
– Just another Java programmer
Dec 30 '18 at 14:48
pastebin.com/7YfQBVW6
– Brij Raj Kishore
Dec 30 '18 at 14:56
Its a bit long and uncommented. Sorry I have to do it in hurry at that time.
– Brij Raj Kishore
Dec 30 '18 at 14:56
add a comment |
Show us your code
– Just another Java programmer
Dec 30 '18 at 14:48
pastebin.com/7YfQBVW6
– Brij Raj Kishore
Dec 30 '18 at 14:56
Its a bit long and uncommented. Sorry I have to do it in hurry at that time.
– Brij Raj Kishore
Dec 30 '18 at 14:56
Show us your code
– Just another Java programmer
Dec 30 '18 at 14:48
Show us your code
– Just another Java programmer
Dec 30 '18 at 14:48
pastebin.com/7YfQBVW6
– Brij Raj Kishore
Dec 30 '18 at 14:56
pastebin.com/7YfQBVW6
– Brij Raj Kishore
Dec 30 '18 at 14:56
Its a bit long and uncommented. Sorry I have to do it in hurry at that time.
– Brij Raj Kishore
Dec 30 '18 at 14:56
Its a bit long and uncommented. Sorry I have to do it in hurry at that time.
– Brij Raj Kishore
Dec 30 '18 at 14:56
add a comment |
1 Answer
1
active
oldest
votes
Maybe you can do a dfs on the starting and ending vertex and from those vertices remove the ones already on the sub graph. Now you have all the possible vertices which can be part of the solution. Check all possible combinations from those vertices and select the pair with maximum gcd.
During the dfs make sure to add a if condition to ignore the vertex connceted to it so that on each side of the sub path you only get the vertices which are not part of the sub path
answered Dec 30 '18 at 15:14
Sanath KumarSanath Kumar
1039
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53978580%2ffinding-path-having-a-subpath-and-has-maximum-gcdstarting-node-ending-node%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
Maybe you can do a dfs on the starting and ending vertex and from those vertices remove the ones already on the sub graph. Now you have all the possible vertices which can be part of the solution. Check all possible combinations from those vertices and select the pair with maximum gcd.
During the dfs make sure to add a if condition to ignore the vertex connceted to it so that on each side of the sub path you only get the vertices which are not part of the sub path
answered Dec 30 '18 at 15:14
Sanath KumarSanath Kumar
1039
add a comment |
Maybe you can do a dfs on the starting and ending vertex and from those vertices remove the ones already on the sub graph. Now you have all the possible vertices which can be part of the solution. Check all possible combinations from those vertices and select the pair with maximum gcd.
During the dfs make sure to add a if condition to ignore the vertex connceted to it so that on each side of the sub path you only get the vertices which are not part of the sub path
answered Dec 30 '18 at 15:14
Sanath KumarSanath Kumar
1039
add a comment |
Maybe you can do a dfs on the starting and ending vertex and from those vertices remove the ones already on the sub graph. Now you have all the possible vertices which can be part of the solution. Check all possible combinations from those vertices and select the pair with maximum gcd.
During the dfs make sure to add a if condition to ignore the vertex connceted to it so that on each side of the sub path you only get the vertices which are not part of the sub path
answered Dec 30 '18 at 15:14
Sanath KumarSanath Kumar
1039
Maybe you can do a dfs on the starting and ending vertex and from those vertices remove the ones already on the sub graph. Now you have all the possible vertices which can be part of the solution. Check all possible combinations from those vertices and select the pair with maximum gcd.
During the dfs make sure to add a if condition to ignore the vertex connceted to it so that on each side of the sub path you only get the vertices which are not part of the sub path
answered Dec 30 '18 at 15:14
Sanath KumarSanath Kumar
1039
edited Dec 30 '18 at 15:24
answered Dec 30 '18 at 15:14
Sanath KumarSanath Kumar
1039
answered Dec 30 '18 at 15:14
Sanath KumarSanath Kumar
1039
answered Dec 30 '18 at 15:14
Sanath KumarSanath Kumar
1039
1039
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53978580%2ffinding-path-having-a-subpath-and-has-maximum-gcdstarting-node-ending-node%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Show us your code
– Just another Java programmer
Dec 30 '18 at 14:48
pastebin.com/7YfQBVW6
– Brij Raj Kishore
Dec 30 '18 at 14:56
Its a bit long and uncommented. Sorry I have to do it in hurry at that time.
– Brij Raj Kishore
Dec 30 '18 at 14:56