ABC 131 Solutions

A: Trivial.  Store the number using a string rather than an int to check digits more easily.

B:  Iterate over all possible numbers to remove and remove the one with least absolute value.

C:  First, write a function to get the number of numbers divisible by some X in a range.  To do so, find the smallest and greatest multiples of X in a range and then the rest is trivial.  After that, we do complementary counting/PIE, so our answer is B-A+1 - f(C) - f(D) + f(lcm(C, D)).  Essentially equivalent to https://www.codechef.com/FFC12019/problems/SHADOW.

D: Process the tasks in descending order of deadline.  Maintain the total time required for tasks encountered so far, and if this time is greater than the current deadline, we can't complete the encountered tasks in time, so the answer is no.  After each deadline, subtract the difference between the two consecutive deadlines from our total time (to account for us having time to complete some of the tasks).  (Essentially, this is equivalent to greedily completing tasks in increasing order of deadline.)  Very standard problem, most people here have probably seen it before.

E: The only nontrivial/relatively original problem in this set.  The answer is -1 only if K > (N-1) choose 2.  We will give a construction for the remaining K below.  To prove that higher K are impossible, note that any two vertices connected by an edge will have distance 1, so we can't use pairs connected by edges.  Since the graph is connected, we must have at least N-1 edges, so we can have at most N choose 2 - (N-1) = (N-1) choose 2 pairs.

If K = 0, output a complete graph.  Otherwise, suppose that C choose 2 <= K < (C+1) choose 2.  Call C vertices "outside vertices" and the remaining vertices "inside vertices".  Connect all of the inside vertices to all other vertices (in other words, add edges between all pairs of vertices except those that are both outside).  We can see that this gives C choose 2 pairs with distance 2, since the set of pairs with distance 2 is exactly the set of pairs of outside vertices.  If K > C choose 2, remove one of the inside vertices (if there is only one inside vertex, C = N-1, which would imply K > (N-1) choose 2, and we already established that we can ignore those cases, so there will still be at least one inside vertex afterwards).  Then, connect it to N - K + C choose 2 - 1 other vertices, including at least one inside vertex.  Obviously, our vertex will have distance 0 to itself and distance 1 to all vertices it is connected to, but it has distance 2 to all other vertices, so this adds N - 1 - (N - K + C choose 2 - 1) = K - C choose 2 valid pairs, completing the construction.

F: Create a graph connecting points with the same x or y coordinate.  We claim that the answer is the result when N is subtracted from the sum over each connected component in this graph of the product of the numbers of distinct X- and Y-coordinates represented in the component.

Proving that connected components are independent is pretty simple.  Then, the number of points created from the starting points in each connected component is the product of the numbers of distinct X-coordinates and Y-coordinates in the component.  We can prove that these points can all be created by induction.

Note that we cannot construct the entire graph, since it could have O(N^2) edges.  However, since we just need to run a BFS to construct connected components, this doesn't turn out to be a huge obstacle--we just store lists of points at each X or Y coordinate and use those lists to deal with transitions rather than building an adjacency list.