Single Round Match 846 Editorials
IHWCPenalty
We just need to carefully simulate the penalty box as described in the statement. To do that, we can simply keep track of the number of players from each team in the penalty box. For p/P we increment the corresponding count, for s/S we decrement it and for g/G we check what type of a goal it was and decrement the opponent’s count if it was a power-play goal.
IHWCTie
Often the key to an easy solution is a suitable generalization, or a suitable specialization. This problem is of the latter type. We have a lot of freedom, and there is no clear and easy way how to generate some standings in which exactly the fourth and fifth team are equal. But we aren’t forced to have just those teams at an equal score, the tie can be bigger – and that’s where we can find the easier solutions.
If N is odd, i.e., N = 2*K + 1, we can easily find a set of results such that all N teams have the same number of points. To do this, imagine the 2K+1 teams around a circle. Each team will beat the K teams that follow it in the clockwise direction, and lose to the other K.
If N is even, we can use the above solution to get N-1 tied teams, and then add one extra team. The team can either beat everyone else (in which case it ends first and everyone else is tied for second to N-th place), or it can lose to everyone else. Both options give us a valid solution that is again very easy to construct.
HockeyLeagueDraft
We can easily show that each team only has to consider two options: either they draft the player with the highest available A[x] as an attacker, or the one with the highest available D[x] as a defender. The team will pick the better of these two options.
To do the drafting in an efficient way, we can maintain two separate sets of players who haven’t been drafted yet: one ordered according to A and then id, the other ordered according to D and then id. This allows us to pick the next drafted player in O(log P) and also update both sets in O(log P), where P is the number of players. The total time complexity is thus O((P+T)*log P).
Essentially the same total time complexity can also be obtained using only arrays. We will use three: one with players sorted by A, one with players sorted by D, and one array of booleans telling us which players are still available. We will maintain a pointer into each of the first two arrays. Each time a team goes to draft, we find the rightmost available player in each array (shifting the pointer left until it hits an available player) and then we evaluate the pick and mark the picked player as unavailable. This solution needs O(P log P) for the initial sorting of arrays and then the entire draft takes O(P) time only because we only move the pointers to the left, so each of them will at most traverse its array once.
HockeyAllStars
We can use meet in the middle to get a solution that is guaranteed to be fast enough. To do this, we split the players into two groups of N/2 players each. Within each group, there are 3^(N/2) ways how to split the players: each can be placed into team A, team B, or sent away. We can iterate over all of them and generate a separate list of 3^(N/2) options for each group. For each option we will simply store two values: the total strength U of uninvited players and the (possibly negative) difference D between strengths of team B and A.
Now we need to find the best way how to pair a partial solution for the first half of the players with a partial solution for the second half.
Without loss of generality we can assume that in the optimal solution team B is at least as strong as team A, so we will only look for such solutions. This way the difference between B and A is always non-negative and we don’t need to deal with absolute values.
We will sort each list of options according to D.
We can then iterate over all options for the second half of the players in the order in which the difference between B and A increases. During this iteration, more and more options for the first half of the players become viable. We can simply keep track of the best one among them (i.e., the one with the smallest value of U - K*D) and pair that with the second half we’re currently processing.
The time complexity of this solution is O( N*3^(N/2) ).
Autocomplete
We can start by storing the given dictionary and the given goal in a trie. As we type, we move along the edges of this trie: letters move us downwards, backspace returns us to the parent node. Of course, we are also allowed to depart the trie and type useless stuff.
Autocompletion does not apply if we are outside the trie, so we just need to do it when in a trie node. Everything is small enough so we can directly use the rules in the statement to precompute the autocompletion suggestions for each node. More precisely, two sets of suggestions: one if we reached the node via backspace and one if we reached it in any other way.
As the goal corresponds to a node of the trie, any valid sequence of A actions must end on a trie. If we depart from the trie by typing a suffix that doesn’t correspond to a valid branch, we can only return back to the trie by backspacing the same number of times. Thus, at any moment in any valid solution the suffix of the current word that isn’t a part of the trie can have at most A/2 characters – otherwise we clearly won’t have enough time to backspace all of them.
Additionally, it should be obvious that the actual extra characters don’t matter, only their count does – we are eventually backspacing them away regardless of what they are.
Thus, at any moment during any valid sequence of actions we are in one of the following states:
in a trie node X, reached in a “regular” way
in a trie node X, reached via backspace
s steps away from the nearest trie node X, for some s (1 <= s <= A/2)
This gives us a total of at most N*(2+A/2) < 30,000 states in the worst case. (N <= |W| + |L| + 1 is the number of nodes in the trie.) If we include the number of actions taken so far into the state, we get about 1.5M total states.
In each state we can either type a letter, type backspace, or choose one of the provided suggestions (if any), for a total of about 30 possible actions, each leading to a new state that is one action closer to the end of the process. This gives us about 45M possible state-to-state transitions in the worst case, which is small enough. Thus, we can calculate the answer using dynamic programming: for each number of actions taken and each reachable state after that many actions we will calculate the total number of ways to get there.