635A - Orchestra

We can iterate over each possible rectangle and count the number of violists enclosed. This can be optimized with rectangular prefix sums, though the simple brute force is sufficient for this problem.

Runtime: O(n⁶)

634A - Island Puzzle

Notice that, as we move the empty pedestal around the circle, we cyclically permute the statues (and the empty pedestal can be anywhere). Thus, we can reach one state from another if and only if, after removing the empty pedestal, they are cyclic shifts of each other. The starting and ending configurations are permutations, so we can check this in linear time.

Runtime: O(n)

627A - XOR Equation

For any two integers a and b, we have , where is the xor and a&b is the bitwise AND. This is because is non-carrying binary addition. Thus, we can find a&b = (s - x) / 2 (if this is not an integer, there are no solutions).

Now, for each bit, we have 4 cases: , and . If , then a_i = b_i, so we have one possibility: a_i = b_i = a_i&b_i. If , then we must have a_i&b_i = 0 (otherwise we print 0), and we have two choices: a_i = 1 and b_i = 0 or vice versa. Thus, we can return 2ⁿ, where n is the number of one-bits in x. (Remember to subtract 2 for the cases a = 0 or b = 0 if necessary.)

Runtime:

627B - Factory Repairs

Using two binary-indexed trees, we can maintain the prefix and suffix sums of the amounts we can produce with maximum production rates of B and A, respectively. Then we can just query the binary-indexed trees to find the maximum possible production given the start and end of the repairs.

Runtime: .

627C - Package Delivery

We solve this with a greedy algorithm: for each gas station, we fill our tank to min(n, d) liters of gasoline, where d is the distance to the next gas station with cheaper (or equal) gas. This is optimal, as, if we can make it to a station with cheaper gas without buying expensive gas, we should (and fill up our tank at the cheaper station). Otherwise, all stations within range n are more expensive, so we should buy as much gas as possible right now.

Alternatively, if we say that we always “use” the gasoline we buy in the order we buy it, then the gasoline used in the ith unit must have been purchased within the last n units. Then we can greedily use the cheapest gas within the last n miles. We can maintain this in a queue with range-min-query, which gives us linear runtime (after sorting).

Runtime:

627D - Preorder Test

We binary search on the answer, so we need to answer queries of the following form: is the a depth-first search traversal such that the first k vertices all have value at least v? We can answer this with a greedy tree-DP: for each subtree, we compute whether or not all its vertices have value at least v, and if not, the longest possible prefix with all values at least v. Then, our transition function can be greedy: the maximum possible prefix with all values at least v is the sum of the sizes of all child subtrees which are all at least v plus the largest prefix of all child subtrees.

Runtime:

627E - Orchestra

We can think of a rectangle in the grid as a pair of an (xlo, xhi) interval and a (ylo, yhi) interval. Suppose we fix the x-interval and want to determine the number of corresponding y intervals which create rectangles containing at least k violists. Given a sorted list of the y-coordinates of all violists in the range, this is simple: m violists split the y-coordinates into m + 1 (possibly empty) intervals that span all the columns, and the number of total intervals that work is simply the number of pairs of points that are at least k intervals apart.

As we sweep over the xhi coordinate and maintain the list of violists, we want to insert each violist into a sorted list and look at its k nearest neighbors to determine the change in number of intervals. Inserting violists into a sorted list, however, is difficult to do in constant time. Instead, we sweep in reverse. Start with xhi = r and a linked list containing all the desired violists; decrementing xhi is now a simple process of removing the necessary elements from a linked list and examining their neighbors as we do so.

Runtime: O(r²k + rnk)

627F - Island Puzzle

First, if we never move the empty pedestal through any cycle, then moving the empty pedestal to and from any given position cannot change the location of the statues, as performing a move in the opposite direction as the previous undoes the previous move.

Thus, in our graph with one cycle, we can only do the following two operations: move the empty pedestal from one location to another (without loss of generality, only using the original tree), and cyclically permute the elements along the one cycle (except the element closest to the root).

Now, to check satisfiability, we can greedily first move the empty pedestal from its start position to its end position -- since this procedure can be undone, it will never change the satisfiability of the rearrangement. Then, we only have to check that all changed elements lie on a possible cycle. This uniquely determines the edge to be added.

To compute the minimum number of moves, we compute the minimum moves to move the empty pedestal from the start to the cycle, the minimum moves to permute the cycle as desired, and the minimum moves from the cycle to the end point.

Runtime: O(n)