A — Next Alphabet

The easiest way to deal with this problem is probably to convert the given character to an integer, add one, and convert it back. If you absolutely can't do that, a somewhat more annoying implementation would involve iterating through the alphabet, waiting until you find the given letter, using a boolean variable to store that the letter has been found, and printing the letter on the next iteration of the loop. (However, iterating over the alphabet is itself nasty unless you have conversion from letters to integers, so this approach is rather pointless unless your language just doesn't support the first method, though in that case you should probably switch languages anyway.)

Runtime: $$$O(1)$$$. Click here for my submission.

B — Achieve the Goal

In total, we need to earn $$$NM$$$ points. We subtract the points earned so far and determine whether this is a valid score for the final test. There are two special cases to deal with. First, if we need more than $$$K$$$ points, the answer is $$$-1$$$ because we cannot achieve the goal. Second, if we need a negative number of points, we should print $$$0$$$, since we must earn a nonnegative score. Otherwise, we can print $$$NM$$$ minus the sum of the input values.

Runtime: $$$O(N)$$$. Click here for my submission.

C — Welcome to AtCoder

This problem can be solved via direct simulation. Maintain two arrays: the number of incorrect submissions and whether we've seen an accepted solution, with both arrays containing entries for each problem. Then, when we see an incorrect submission for a problem, we can increment the first array. When we see a correct submission, we check whether this is the first correct submission we've seen so far and, if so, add the count of incorrect submissions for this problem to our answer.

Runtime: $$$O(N)$$$. Click here for my submission.

D — Maze Master

Note that using BFS, we can compute the distance from one point to all other points in $$$O(HW)$$$. Thus, by performing BFSes rooted from all $$$HW$$$ points, we can compute all pairwise distances in this graph in $$$O(H^2W^2)$$$. From here, we can iterate over each of these distances and compute the largest among them, which is our answer.

Runtime: $$$O(H^2W^2)$$$. Click here for my submission.

E — Max-Min Sums

We will separately count the number of times each element appears as the minimum and the maximum in a set of $$$K$$$ integers. Then, if $$$A_i$$$ appears $$$L_i$$$ times as the largest element in the set and $$$S_i$$$ times as the smallest element in the set, we add $$$(L_i - S_i) A_i$$$ to our answer.

First, sort the array and zero-index it (so that, for example, $$$A_0$$$ is the smallest element). Note that the number of sets in which $$$A_i$$$ is the largest value is the number of ways to choose $$$K-1$$$ smaller integers, or $$$\dbinom{i}{K-1}$$$. Meanwhile, the number of sets in which $$$A_i$$$ is the smallest value is the number of ways to choose $$$K-1$$$ larger integers, or $$$\dbinom{N-i-1}{K-1}$$$. We can thus compute $$$L_i$$$ and $$$S_i$$$ for each value in $$$O(1)$$$ each, with $$$O(N \log MOD)$$$ precomputation. (If you aren't familiar with how to efficiently compute the choose function, I strongly recommend looking into this--the basic idea is to precompute all relevant factorials and their modular inverses, which we can then use to compute the value of the choose function.) Now, we can use these values to compute our final answer.

Runtime: $$$O(N \log MOD)$$$. Click here for my submission.

F — Enclose All

Using the Google Algorithm, we can find code for this problem on the internet in $$$O(1)$$$ real time. From here, we can apply the copy-and-paste lemma to enter this code into our editor. Afterwards, we can read in our input and feed it to our copied algorithm, printing out the result. If you implemented the Google Algorithm effectively, your code should have $$$O(N)$$$ runtime, which will easily pass in time. This is the approach I implemented during the contest.

Of course, I'm (mostly--I actually did do this during the contest) joking, and I'll now describe the solution I assume was intended. The basic idea is that there are two cases to deal with. First, two points form a diameter of the circle, or second, at least three points are on the circle.

We will now prove that in any other case, we can shrink the circle to create a better answer. First, if only one point is on the circle, we can shrink the circle by dilating it with respect to that one point until another point is on the border, shrinking it without excluding any points. Second, if two points are on the circle, we can move the center towards these points while keeping them on the border, until the two points are on the diameter or another point is on the border, to shrink the circle without excluding any points. The reason this shrinks the circle is that the distance between the two points is constant, but the distance from the center of the circle to the line is decreasing, so by the Pythagorean Theorem we can see that the distance from the center to each of the two points, which is the radius, decreases. In all other cases, we have that either two points are on the diameter or three points are on the circle, as desired.

Thus, we can make a list of possible circles by computing the circles with the segments connecting each pair of points as diameters and the circumcircles of all triples of points. The circumcenter can be computed with some algebra by noting that it is the intersection of the perpendicular bisectors or through a closed form in terms of the given coordinates. Given the circumcenter, we can compute the circumradius by finding its distance to one of our three points. Now, we can consider each of these circles in turn and determine whether they contain all points. Among all the circles that do contain all of the points, we print the smallest radius.

Runtime: $$$O(N^4)$$$ if implemented from scratch, or $$$O(N)$$$ if copied from the internet. Click here for my submission. All credit goes to nayuki.io!

A bit of a soapbox: though this was an ABC, I think this problem was far too standard to appear on a modern programming competition, especially as problem F. Finding the solution on Google took me less than five minutes during the round, and given the simplicity of the problem statement, at least one of the round's authors/testers ought to have realized that the solution might exist on the internet already. Then, they should have done some basic research and, upon realizing how easy it would be to copy/paste the solution, scrapped this problem and written a new F.

Yes, writing original, challenging problems is very challenging, but this would have been a very easy issue to avoid. And, yes, the intended solution was not absurdly complex, but this problem still substantially advantages those who use Google and copy/paste code (including yours truly, oops), and even the intended solution is a lot easier to write if you Google the circumcenter formula. I'm not especially bothered by this as a one-time issue, but I do hope that this doesn't create a norm of allowing standard problems to appear as ABC E or F. (In contrast, for example, I'm mostly fine with problem D, even though it was also very standard, because at that level the focus probably should be on educating newcomers over encouraging competition.) I don't intend this as a personal attack on the authors, though, and I thank them for the contest and for the other five problems, which made for a very solid (if somewhat easier than usual) ABC.