In the SEPT16 challenge, there was the question JTREE, which was solvable with a DFS traversal and a segment tree, which is a top down approach to solve it.
I was having difficulty solving the problem at the start as it I didn’t read the that the edges were “directed”.
So the extension question is the same with a small change, What if the edges are undirected? How can one solve such a question? Will it be like DP on trees?
An example of why it becomes difficult:
Consider a test case like this
5 4
2 1
3 2
4 3
5 3
2 1 10
3 2 10
4 3 1
5 2 1
The problem arises in the case of node 5, if it were directed, the node had a unique traversal. 5->2->1 (cost of 11). But in case of an undirected graph, the optimal travelling would be 5->4->1(cost of 2). How can one solve this question?
Another intersting extension-What if the tickets had negative cost?
I’m sure the problem setter must have thought of this too, but just out of curiosity, how should we approch such a problem.
The given test case does not form a tree, it fails to have N-1 edges, your example have 5 vertex and 5 edges making it cyclic, and tree are acyclic.
Even if the graph had undirected edges, definition of tree implies that there is only one path between the root and any other node(actually between any two pair of nodes).
see this link for mare clarification --> Tree
I’m sorry, but there are only 4 edges(2-1, 3-2, 4-3, 5-3). The first line 5 4 is for the number of nodes and number of tickets. I followed the format of the question.
Solution will be different for Undirected case, cause, it might be possible. I can give you a test case for the same if you want.
And yes, I also think the problem can be solved using HLD.
@ashwanigautam there can be case when we want to change normal visiting path i.e from node x to root so that we can pick some ticket with very big K and small w , which will prove to be beneficial . @sahilarora.535 i dont think that this can be solved with HLD or may be i just couldnt think of it (provide me some hints if you have thought about it ) . @pandusonu similar thing happened with me as well and after wasting hours i read the given test case and bam “GTA : wasted”
Hi guys, I also spent some times thinking about it… I finally though it is probably at least NP-complete.
But if someone comes up with a cool solution using heavy-light, post it here please !! I’m not very familiar with this structure (I know how it works in theory though).
@ashwanigautam Consider a complete binary tree of level 5 and let there be two leaf nodes with same parent. Let left child have a ticket with k = 2 and w = 100000. Let the right child have a ticket with k = 5 and w = 1. Also, let all other nodes have ticket with same values. If we go by directed one, minimum cost for left child would be 100000 + 100000 + 100000. In undirected, the person in left child can go to the right child using original ticket, and then to root in 100001. Hope it’s clear.
@arunnsit I am not sure, I just started the theory. If we traverse the tree breadth first rather than depth first as we did in the problem, and then find node with minimum value in the k nodes, maybe we can do it.
I knew I wasn’t the only one who thought of the problem like this! During the contest, I too was solving the obviously much more difficult task, and failed to come up with an algorithm that runs sufficiently fast.
The fastest runtime I came up with was O(K*N + N^2). This approach is easy: start with an edgeless graph, and for every ticket, run a BFS/DFS through the (original) tree and place directed edges from every node that you can reach with that ticket to that ticket’s starting node. After this it’s enough to run a Dijkstra to get the minimal distance from the root to every other node. Because there can be up to N^2 edges, the complexity is O(N^2).
Another useful observation for solving the problem better is that if you’re at node x and you just used an edge of ticket t to relax a node y, it’s useless to use anymore edges of ticket t, because they all lead to node y, and x is already the node with the least distance from root that is connected with y by an edge of ticket t. (Because of the order Dijkstra’s traverses the graph)
This means that each ticket will only actually need to be processed once, and then we can remove it from the set of unprocessed tickets. If you run a Dijkstra with a set, and manage to come up with a structure that supports the following operations:
Query for any ticket in the structure that can reach our node x, or say that it doesn’t exist
Remove ticket t from the structure
You can have a solution that runs in O(N log N + K * s), where s = operations per structure operation. Ideally s should be O(log N), but O(log^2 N) is okay too. Naively, this can be implemented in O(N) easily.
If you want, I can describe the pseudocode in more detail: I’m pretty sure it’s not wrong. But I don’t know how to code a data structure like this, or if it even exists. I had already tried writing the tree in the shape of an array, in many different ways, in order to maybe figure out how to build a segment tree on this aray, but failed. I’ve tried using centroid decomposition, but failed for the same reason I failed using HLD: a ticket can cover up to O(N) chains / centroid sectors, it doesn’t make sense to use these algorithms at all. I couldn’t think of a working BST either. Any help on the matter would be appreciated.