A — Tenki
This is a fairly simple task--just iterate over all positions in the strings and count the ones where S[i] = T[i].
Runtime: $$$O(|S|)$$$. Click here for my submission.
B — Power Socket
Note that we already have one socket, so we need to fill $$$B-1$$$ more sockets. Additionally, each new outlet we add will take up one socket and add $$$A$$$ sockets, resulting in a net addition of $$$A-1$$$ sockets. We thus need to create at least $$$B-1$$$ sockets where each outlet gives us $$$A-1$$$ sockets, making our answer $$$\lceil \frac{B-1}{A-1} \rceil$$$. Since most programming languages use floor division, we can also express this as $$$\lfloor \frac{A+B-3}{A-1} \rfloor$$$.
Runtime: $$$O(1)$$$. Click here for my submission.
C — Lower
We essentially use two pointers. Maintain the starting position at zero. Then, while the next position isn't higher than the current one, we make that move. If the next position is higher than the current one, we need to reset the starting position to the current position. The answer is then the maximum number of consecutive moves we make without resetting the starting position.
You can also think of this as simulating the given process and picking the best answer, but only from starting positions that are higher than the previous position. The reason this gives us the best possible answer is that if we have a starting position lower than the position before it, we could get one extra move by starting from the previous position instead, so we should never start at a position that is not higher than its previous position.
Runtime: $$$O(N)$$$. Click here for my submission.
D — ModSum
Notice that the result when a number is taken mod $$$X$$$ can be at most $$$X-1$$$. Therefore, since we're summing results mod $$$1$$$, $$$2$$$, $$$3$$$, and so on, up to $$$N$$$, our answer can be at most $$$0 + 1 + 2 + \cdots + N-1 = \frac{N(N-1)}{2}$$$.
Now, let's prove that we can always achieve this answer. Take $$$1$$$ mod $$$2$$$, $$$2$$$ mod $$$3$$$, and so on, up to $$$N-1$$$ mod $$$N$$$. Then, take $$$N$$$ mod $$$1$$$, which adds zero to the sum. Therefore, this approach gives us an answer of $$$1 + 2 + 3 + \cdots + N-1 = \frac{N(N-1)}{2}$$$.
Runtime: $$$O(1)$$$. Click here for my submission.
E — League
Let's rephrase this as a graph problem. We essentially have $$$\dbinom{N}{2}$$$ matches we need to play, and we are given a set of criteria that each indicate that some match must be played before some other match. We can express the matches as vertices on a graph and the given requirements as directed edges. An edge from one match to another means that the first match must be played before the second.
Phrased like this, the problem seems very similar to topological sorting (given the set of requirements that one vertex must come before another). And indeed, this motivates a similar solution. Maintain the set of matches with no incoming edges. Then, while this set is non-empty, increase the day by one and delete these matches from the graph, removing their outgoing edges as well. Finally, replace the set of matches with no incoming edges by adding any matches whose last incoming edges were removed. (To avoid checking each individual match every time, we can maintain the indegrees of each match and then simply check whether a match now has indegree zero each time we remove one of its incoming edges.)
After the set is empty, we must have either processed every match or encountered a cycle. In the latter case, the answer is $$$-1$$$, as this indicates that there is no order in which to play the matches. In the former case, we can now output the number of days we computed.
Runtime: $$$O(N^2)$$$. Click here for my submission.
F — Engines
First, I'll present the (rather sketchy) solution I used in-contest. Then, I'll discuss the somewhat simpler approach that was most likely intended by the problemsetters.
My solution used a pruned complete search. The actual idea is fairly simple--the challenging part is showing that it will run in time.
First, let's split into four cases. In two of the cases, we'll be attempting to maximize the x-coordinate; in the other two we'll try to minimize it. Similarly, in two of the cases, we'll attempt to maximize the y-coordinate, and in the other two we'll try to minimize it. (The motivation for these cases is that we maximize our end result by either maximizing or minimizing the two coordinates.) The rest of the solution will be tailored to the case in which we attempt to maximize both coordinates--the other cases can be made identical by multiplying the appropriate values in the data by $$$-1$$$.
Now, let's make a key observation. If, after considering some number of the engines, we could reach two points $$$(a, b)$$$ and $$$(c, d)$$$, with $$$a <= c$$$ and $$$b <= d$$$, we shouldn't consider $$$(a, b)$$$ in the future, as no matter what moves we make later on, $$$(c, d)$$$ will always do a better job of maximizing $$$x$$$ and $$$y$$$.
Let's suppose we're adding the engines one by one. Given a set of candidate points we've reached so far, our new set of candidates is the original set plus the points in the original set when the current engine is added to them. Then, we can prune this data to delete any redundant nodes as outlined in our observation.
Finally, after we process every engine, we can iterate over all points in our candidate set and pick the one that gives us the best answer. We'll then print the best answer from all four of our cases.
We should be able to intuitively see that this is correct--each case is guaranteed to print the correct answer if that answer lies in its quadrant. However, the tricky part is bounding its time complexity. One fairly simple bound is $$$O(N^2 \, maxX)$$$, as we consider $$$N$$$ engines, and at any point our set may contain at most $$$O(N \, maxX)$$$ points because it will contain at most one point for each X-coordinate. However, in practice, we actually do much better than this, as it's rare that we'll actually have anywhere near $$$N \, maxX$$$ points. My solution had an unnecessary $$$\log N$$$ factor in the big-O expression (though this made it somewhat faster in practice--I sorted the candidate points rather than iterating over every possible position), but it passed in about 900 ms. It's possible that some particularly tough test case might cause this submission to TLE, but such a case would have to be very contrived.
Now, let's discuss a simpler and more efficient solution. The key observation is that when we order the engines by the angles their vectors make with the x-axis, the answer will include vectors in some contiguous range. A proof of this fact is at this link. Then, the solution is fairly easy to implement--we can iterate over all possible ranges and compute the answers for each of them, taking the maximum as our result. When implemented appropriately, this is an $$$O(N^2)$$$ approach. Credit for this solution goes to silxi, as he was the one who showed it to me after we both finished the contest.
As always, feel free to post questions or comments below.
