Hello,
I just finished the Cisco Placement Test for batch 2026(India). It was 40 MCQ + 2 CP problems. Both of the CP problems were tree based, but I wasn't able to solve either of them. Definitely not going to get selected. But would like to discuss the problems and possible solutions.
First Problem: Given a tree with n vertices (Some of the vertices contains coin) and a binary string of length n denoting which vertex contains coins. You can collect a coin if the number of edges from your current vertex to the coin vertex is <= 2. You can start with any vertex, but after collecting all the coins you need to end at vertex you started at. what's the minimum path length you need to collect all the coins n <= 1e5 (length of the path is number of edges in the path).
Second Problem: Given a tree with n vertices. a start_vertex and an end_vertex, with a list of vertex, starting from the start_vertex you need to visit all the vertex in the list of vertex (in any order) and finish at the end_vertex. Find the minimum path that does this.
For the first problem I was really clueless how to solve it maybe there's some DP approach, For the second problem it's possible to solve it with multiple dfs but It felt to complicated to code in the given time.
Is there any elegant or easier way to solve these problems. Any discussion will be helpful.
Same here... I tried to do second one but I was messing up when we have traversed one task point and best case is from some other one which comes after that...
For the first one I think you just need to remove all the leaf in tree which doesn't have coins, then answer will be 2* number of edges.
Second one standard dijkstra algorithm.
This is just a rough idea yes still we need to handle other cases
How do you ensure all the all the vertex in the list are visited?
Another way i think was to first get the simple path from S to E, and then then use dfs backtracking to count the time spent at each vertex on the path, and answer should be their sum. For path s-a-b-e find tasks connected through s, then same for a, then for b, finally for e. as once we move on to a, coming back to visit task through s is costly.
Nice, that's a good solution. I got what you meant
How do you ensure every vertex in the given list is visited?
we would be covering the entire tree, so every task is visited. mark the simple path visited, then for each vertex in it starting from s, start a dfs, which gives us the time to visit all tasks in that component, then move one to the next vertex. the dfs logic is trivial, if you find a task return 2, if you dont return -1. if found every subsequent backtrack would add 2 to the time for this branch.
- wrong thread
For the second one I think , if we can visit each node more than once we can creat a mst(consider weight 1) Then answer will be 2*edges in mst — dist(stsrt ,end) Because we will retrace each edge twice.. except the ones on path from start to end. Hope that makes sense!
Well the graph is just a tree so mst = original graph. Just find the deepest node in each subtree and that node will contribute 2*depth.
Yep, that definitely makes sense. Thank you!
wdym that we can create a mst?isnt tree already a mst?
For the first one I kept on removing the leaf nodes, given they had no coin(just another variation of topological Sort). It was mentioned that if the distance between nodes was less than 2, we could still collect coin from either of them. So, I removed the leaf nodes again for two iterations(This time without checking if there is a coin at the leaf or not). Counted the number of edges in the leftover tree and returned (number of edges)*2, as i had to return at the same vertex after traversing the tree. Tried to solve the second via same logic, but I couldn't figure out how to find the minimum path.
Nice solution, I got what you meant.
2nd is very much similar to 1st , we will remove all the unwanted nodes and the ans is 2*edges — distence between st and end. There will be only one path from st to end (as it is a tree) and that is the distance between st and end.
i think the minimum path for the second will then just be 2* edges — dist(start-end) look at Jain's comment
I found the exact question as first on leet code Search — leet code 2603
yes same question hai would you mind telling what is the expected rating of this question on cf?
1500 maybe
I think second problem is from codefoces around 1800 rated
which one?
I need to search, i solve 2-3 months ago exact same question
https://www.geeksforgeeks.org/dsa/minimum-time-required-to-visit-all-the-special-nodes-of-a-tree/
here is similar question of second problem from codeforces F. Vlad and Unfinished Business
First Problem : Your text to link here...
For the second problem this might work=>We make the start node root of tree and for each node store the count of nodes in it's subtree that are in task array, also store for a node if the end node is in it's subtree now after doing this we start second DFS from the start node and look at its children nodes now if the child node has count 0 then we won't do dfs for it else if a node has count> 0 but also has end node inside that subtree then we will ignore it for now and check if there is any other child with subtree count>0 and explore that first, we will also keep a global count variable and will do count-- if any node from the task is visited, now as soon as we get count=0 and current node=end node we will return the ans(no.of edges traversed in complete traversal).
this is what I tried and failed for 10TC passed for 4 TC
https://codeforces.me/contest/1675/submission/325917054 mine got accepted, maybe u missed some edge cases like a subtree with count=0 but has end node in it
Those mcq's deserve upsolving of their own too.
The second problem can be taken as a variation of this problem from a recent cf round 2071C - Бесплатный сыр
If anyone is curious such problems involving 2*number of edges in a minimal subtree are also knows as steiner subtree problems !
In the second problem. I believe we can do the following :
Root the tree at the start node. Find in times for all the nodes. Sort the given list of nodes along with the end node with respect to their in times. Now, we need to visit all the nodes and return at the end node. We can see that it is always better for us to visit nodes in sequence of the new sorted list either from the start or the end of this list. So, we may either start from the first node of this sorted list, keep moving until we come across end node. We jump at the last node of this list and follow the list in reverse to ultimately finish at the end node. Or we may do the same process starting from the last node of the sorted list, jump at the first node and finish at the end node.
Edit : This may work for problems with multiple queries but a much easier solution exists for $$$q = 1$$$.