If w + m ≤ d or w > d, we print "good luck". Otherwise, we print "see you next semester".
Complexity: O(1).
We can always build a palindrome if we have at most one letter with odd frequency. Since both strings are palindromes, all letters have even frequencies, except he middle letter when the length of the string is odd. So the answer is NO only when both strings are of odd length and the middle letters are different.
Complexity: O(|s1| + |s2|) for reading, and O(1) to check.
The number of trees is equal to the number of components in the graph. Initially, the number of components is n. Adding an edge will always decrease the number of components by 1 as the constructed graph doesn't have cycles.
We add an edge at node i if there's a value greater than valuei to its left. So we can solve the problem by reading values and keeping the maximum value updated. We add an edge when currentValue < maxValue and decrease the answer.
Complexity: O(n).
If we have multiple trees in the forest, it is clear that the value at the root of the second tree must be greater than all values before it, otherwise it will have a parent.
Also, removing the root of a tree produces zero or more trees, the root of each of these trees must have a value greater than all values before it other than the removed root.
We can build the array as follows:
Let the sizes of the trees be s1, s2, ....
Pick the first tree, assign the value s1 to the root, and give each child v of the root a consecutive range of values of size equal to the subtree at v. Then recursively, a child will be assigned to the maximum value in the given range, and the remaining range will be diveded over its children.
So the first tree is built using values [1, s1], the second tree using values [s1 + 1, s1 + s2], and so on.
Complexity: O(n).
To increase the number of trees, some nodes must become roots. Roots don't have parents, so the values of these roots must be greater than all values to their left.
Can we make node i a root by removing at most one element before it? If vi is greater than all values before it, we don't need to remove any element as i is already a root. Otherwise, we can make i a root if and only if it has only one value greater than it before i. Removing that value will leave i without a parent.
So we need the maximum value and the second maximum value before an element to decide if we can make it a root or not. And in case we can, we also need the indices of these maximums to know which element should be removed.
We can count for each index j the value fj, the number of indices that need j to be removed to become a root. We also decrease fj by one if j is a root, as we will lose one root by removing j.
For each starting element of a subarray i, we increment the end of the subarray j while updating the array f. As values in f are initially 0 or -1, then only increase, it is easy to keep the maximum value in f while increasing some elements.
Complexity: O(n2).
We can simulate the process recursively or using two vectors and swapping them. The first vector will represent the strengths of the teams in the current round, and the second vector will represent the winners of the current round.
Complexity: O(n).
Let k be the height of the tree, that is, 2k = n.
The winning team of the tournament will face k teams and beat them all, therefore contributing to the answer by k × s1st.
The second-place team will also face k teams, winning k - 1 times and losing the last one. This will contribute to the answer by (k - 1) × s2nd - s2nd for a total of (k - 2) × s2nd.
Through our previous observation of how much each team's individual strength contributes to the final answer, it is clear now that the first-place team should be assigned to the team with the maximum strength, and the second-place team to the team with the second maximum strength.
The next two teams in 3rd and 4th place each will win k - 2 times and lose once. 5th to 8th place will win k - 3 times and lose once, and so on. We should keep assigning places in decreasing order of strength for these teams.
Complexity: O(nlogn), as we need to sort the strengths.
Note that in a cylinder, the degree of each node is 3. If we choose one of the vertical edges, mark one end in blue and the other in red, then do a multi-source BFS marking each adjacent node with the color if its parent, we will get one cycle colored in blue and the other colored in red! Check the following animated GIF:
Since we don't know if an edge is vertical or not, we can try all of the three edges of a node, if one of them produced two cycles of size 
, and those two cycles are connected using vertical edges, then we found a solution. Note that sometimes you need to reverse one of the cycles to align the vertical edges.
Complexity: O(n).
The main idea is to build a weighted tree that contains only the nodes mentioned in the operations and/or the queries, plus few other nodes that can be the result of the LCA of some pairs.
We will keep a sorted list of the IDs that will be needed in the operations and the queries.
Each time we activate a generator, we know the number of nodes and the range of IDs that will be generated, if we number the required nodes of each generator in DFS order and sort them, then during our LCA operations we may need those nodes or the LCA of some consecutive nodes. So we add all these nodes to a weighted tree, where the weight of an edge is the number of edges between the two nodes. To find the weight of an edge, we can initially build a sparse table for each generator and store the depths of the nodes. We need the sparse tables for finding the LCAs too.
Finally, we build a sparse table for the weighted tree to answer the queries.
The total number of nodes in the weighted tree won't exceed 2 * (k + q). Multiplied by 2 because we add the LCA of consecutive nodes in DFS order.
Complexity: O(TlogT + NlogN), where T = 2 * (k + q) and N is the total number of nodes in all generators.
Drawing a side of a square that already has 3 drawn sides will get us one point and allow us to draw another edge.
Count for each square the number of missing sides, put all squares with 1 missing side in a queue and process them one by one by filling the missing side, increasing the answer by 1, and decreasing the number of missing sides of the adjacent square by 1. If the adjacent square now has one missing side, add it to the queue.
Be careful with your implementation. It is possible for an edge to complete two squares at the same moment. If the other square is already in the queue, you should not process it or increase the answer by 1.
Complexity: O(R × C).
Whats wrong with test 12 in problem I. Tree Generators ??
I think you are building the actual tree, which may contain up to 1010 nodes. So you are getting Runtime error because the number of nodes exceeds 106.
I think that this phrase says that the maximum number of nodes is 105 or not ?? Total number of characters over all generators will not exceed 2 × $10^5$.
That's the total number of nodes in the generators. But you can activate the same generator multiple times.
Test #12 has one generator of length 2 × 105, and we activate this generator around 105 times.
Ah it's ok thank you :D
What is test 148 in problem H???
Answer is
NO.Some consecutive nodes in your cycles are not connected.
Such a stupid mistake, I can't believe it i got WA on test 148 :(
very strong tests, and very interesting problems, thanks lot enjoyed doing it :D