I recently wrote the CCC Senior Division. I just wanted to share my analysis for each problem.
First let us consider the number of matched characters in string one and string two. If there are characters in string two that cannot be matched with characters in string one, it cannot be an anagram. We don't have to consider the number of wildcards because we can just match it with the unmatched characters in string one. Therefore, just keep a count of the characters in string one subtracted by the characters in string two. If there are more characters of one individual letter in string two than string one, it cannot be an anagram.
For both problems, sort the speeds from Dmojistan and Pegland in increasing order. If you want the minimum total speed, always pair the fastest from Dmojistan with the fastest from Pegland, the second fastest from Dmojistan with the second fastest from Pegland, and so on. If you want the maximum total speed, always pair the slowest from Dmojistan with the fastest from Pegland, the second slowest from Dmojistan with the second fastest from Pegland, and so on. It can be mathematically proven that this will always yield the maximum/minimum total speed.
Let us observe that any subset of vertices induces a subtree on the original tree and that we have to visit every vertex in the induced subtree to visit all the Pho restaurants. Next, let us consider an easier problem where we have to return to our starting position. The total distance travelled will be the number of edges in the subtree multiplied by two. Finally because we don't have to return to our original position, we want to subtract the longest distance in the tree. Thus our final answer will be the number of edges in the subtree multiplied by two subtracted by the longest path distance in the subtree.
If we loop through all possible values of where and take the max of the rice ball sums where , we can obtain our answer.
In order to compute , we have to consider a couple of cases:
For the last case, looping through and uses two for loops bringing the total time complexity to , but you can reduce that to using maps or the two pointer method by making the observation that each prefix/suffix is monotonically increasing.
Let us make a couple of observations first:
It has a property of addictivity meaning that if two initial states are combined by computing the
exclusive or of each of their states, then their subsequence configurations will be combined in the
same way. For example, the second generation of
01010 can be computed by the XOR of the second
000...0001000...000yields the Sierpinski's Triangle
Using these three observations, we can compute the row of any generation in time. By decomposing into a set of powers of two, we can obtain a time complexity of .