Hey,
Here are the hints for week 8 of the DSA learning series:
Hint 1
While the friendship is not transitive, if i is friends with j and j is friends with k, i and k must also go through the same escape route.
Hint 2
Create a graph where the nodes are the people, create edges between all pairs of friends
The number of unique escape routes = the number of connected components in the graph. You can find this using BFS or Union Find.
Hint 3
The number of possible captains in each component = the size of the component
Hint 4
The total possible combinations of captains = the product of sizes of all components
Hint 1
Consider the N \cdot M grid to be a graph with each cell acting as a node
Hint 2
Create edges between adjacent cells with same strength value
Hint 3
Each state is a connected component of nodes in our graph. Find connected components using BFS or DSU.
Hint 4
The maximum number of banks (let’s call it x) is the maximum size of any component
Hint 5
The minimum strength of such a state = the minimum strength (per node) of any component with size = x
Hint 1
Note that if you can transform a to b and b to c, you can transform a to c.
Hint 2
Create a directed graph where the nodes are the letters and the edges are the mappings.
Hint 3
Create a map of type pair<char, char> to bool, where mp[{x, y}] stores whether it is possible to convert x to y.
Hint 4
If node y is reachable from node x, say mp[{x, y}] = true. You can do this by running a BFS from all nodes. Note: mp[{x, x}] is also true.
Hint 5
If the lengths of S and T are unequal then it’s obviously impossible to convert S to T
Hint 6
Else, for any i (0 \leq i < |S|), if mp[{S_i, T_i}] = false then output NO. Else, if this condition is true for all i, output YES.
Hint 1
Create a graph where the nodes are the digits
Hint 2
Your first instinct would be to create edges between S_i and S_{i-1}, S_i and S_{i+1}, and S_i and all j (1 \leq j \leq N, j \neq i) where S_i = S_j. However, on closer analysis, you will notice that this results in a maximum of N^2 edges, which can’t pass for N = 10^5.
Hint 3
Let’s only create edges with S_i and S_{i + 1}, and S_i and S_{i-1}. Therefore, we only have {2 \cdot N} - 2 edges.
Hint 4
Now, to find the shortest path to S_N, let’s run a BFS from S_1.
Hint 5
In order to facilitate the 3^{rd} type of jump (between digits with same value), notice an observation - optimally, you will make this type of jump at most once for each digit.
Hint 6
Therefore, for each digit x, make this jump only the very first time you reach a digit with value x.
The time complexity of this will be O(N) combined for all types of digits.
Hint 1
Note that the levels of the tree alternate between red and black. Initially all even levels are black (0, 2, 4, …), and all odd levels are red (1, 3, 5, … )
Hint 2
We have a binary tree, therefore the depth of the tree is Log_{2}N where N = 10^9 in this problem. Therefore, the depth is around 30 at most.
Hint 3
To find the level of any node x, find \lfloor Log_{2}x \rfloor
Hint 4
To find the parent of any node x at level y, find 2^{y - 1} + \frac{x - 2^y}{2}
Hint 5
For each pair of nodes a, b, in order to find the frequency of colours in their path, keep lifting the nodes to their LCA.
Hint 6
Start by lifting the node with lower height until both nodes have equal height.
Hint 7
Then, lift both nodes simultaneously until they are at the same position.
Hint 8
Keep adding the colour on each level while lifting the nodes. Each position that the nodes visit while lifting is a node in the path between them.
Hint 1
This problem is a trivial application of Union Find. Initially, the parent of dish i is i.
Hint 2
For each component, you need to additionally store the highest value of a dish in that component.
Hint 3
Whenever you receive a query of the first type, perform a union operation between the parent of dish x and dish y.
Hint 4
In a union operation, set the parent of the new component as the parent who owns a dish with higher value. The highest value of a dish in the component will remain the same.
Hint 5
For the second type of query simply perform a find operation and print the parent.
Hint 1
Since the graph is a tree, there is a unique path between all pairs of nodes. Therefore, we needn’t worry about “shortest path”.
Hint 2
The inverse operation of XOR is XOR itself.
Hint 3
For each node x, store the XOR of the path from 1 to x. Let’s call this val_x
Hint 4
To handle queries of form x, y, you need to first find the LCA of x and y. You can do this by precomputing a DFS array and creating a sparse table/segment tree on it. Alternatively, you can use binary lifting.
Hint 5
The answer for any pair of nodes x, y = val_x \oplus val_y \oplus lca where \oplus represents the XOR operation.
Hint 1
Run a BFS or use union find to store the connected components in the forest
Hint 2
For each connected component, find the root of the tree (the smallest element if it’s type even, or the largest element if it’s type odd). Do this in O(N) total.
Hint 3
Run a DFS from the root of each component and find the sum of levels for the component. Add it to the strength of team even or team odd depending on the size of the component. Do this in O(N+M) total.
Hint 4
Print the strength.
Hint 1
In order to check for co-primality, simply check in O(Log_2N) if the GCD of two numbers are 1.
Create edges between all pairs of elements which are co-prime.
Hint 2
If the graph is already connected, output 0.
Hint 3
Observation: all prime numbers p are co-prime with all numbers x unless p is a factor of x. Since all numbers have to be between 2 and 50, let’s select a prime number with minimum number of multiples. 47 is the largest prime number and only has 1 multiple (47) in the range (2, 50).
Hint 4
Therefore, we can make the graph connected by replacing any number with 47. The only case where the graph won’t be connected necessarily is when another 47 exists in the array.
Hint 5
To tackle this case, instead of adding 47, we add another prime number with similar properties - 43. Note that all 47_s will connect to 43_s, and all other numbers will connect to both 47 and 43.
Therefore, the answer is either 0 or 1 each time.
Hint 1
Consider DP_x to be the maximum components you can create in the subtree of x after removing x from the tree
Hint 2
Note that, in order to remove x from the tree, you have to remove at least one of its children. Let’s preemptively remove the child j with the max dp_j and set dp_x = dp_j. What more can we add to this?
Hint 3
Note that once we remove any child of x, all of $x$’s subtrees will be divided into separate components. Therefore, over all children j (excluding the one we added in step 2), add max( dp_j, 1) to the answer.
Hint 4
Our final answer is max(1, dp_1).
Hint 1
The key observation lies in the fact that we can always fill the matrix with only 0 and 1.
Hint 2
There are 4 types of contradictions that can occur.
Hint 3
The first 2 types of contradictions are simple - B[a, b] \neq B[b, a], and B[a, a] \neq 0.
Hint 4
To find the 3^{rd} and 4^{th} type of contradiction, first note this: if B[a, b] = 0, then A_a = A_b. Therefore, we can group these elements into classes. Let us perform union find for this.
Hint 5
A contradiction occurs where an edge with weight 1 occurs between elements in the same class.
Hint 6
The 4^{th} type of contradiction is the most complicated. After grouping the elements into classes, create a graph with the nodes as the classes and all edges with weight 1 (these are guaranteed to occur between different classes).
Hint 7
If any cycle with odd length exists in the graph (i.e, the graph is not bipartite), there is a contradiction. Else, the matrix can be filled.