500A — New Year Transportation

In this problem we are given a directed graph, and asked whether a particular vertex is reachable from vertex 1. It is possible to solve this by running a depth-first search starting from vertex 1.

Since every vertex has at most one outgoing edge, it is possible to write the DFS as a simple loop. Some people used this to make very short submissions.

500B — New Year Permutation

Imagine a graph with one vertex for each entry in the permutation, and edges between pairs of swappable entries. It is easy to see that no matter how many swaps we make, no entry can end up in a location that is not in its connected component. We can also show that within any connected component, we can achieve any rearrangement of the entries that we wish.

Since we want to make the lexicographically smallest permutation, we should greedily rearrange the entries within each connected component so that they are in increasing order.

N ≤ 300, so we are not concerned with runtime. One can determine the connected components using a number of standard algorithms (Floyd-Warshall, Union Find, etc.).

500C — New Year Book Reading

Consider an arbitrary day d, on which we must read book b. Let d' be the last day before d on which book b was read (if there is no previous day, let d' =  - ∞). Observe that, on day d, we cannot avoid lifting all of the books read on any day between d' and d. If we add up all the weights of these required liftings, we will have a lower bound on the answer.

This lower bound can be computed with two loops, in O(M²) time. We must be sure not to add a book's weight multiple times, if it was read multiple times in the interval (d', d).

If we initially arrange the books in order of the first day on which they are read, we will achieve the described lower bound. So, we have our answer.

500D — New Year Santa Network

By linearity of expectation, E(d(c₁, c₂) + d(c₁, c₃) + d(c₂, c₃)) = E(d(c₁, c₂)) + E(d(c₁, c₃)) + E(d(c₂, c₃)). By symmetry, those three values are all equal. So, we need only compute E(d(c₁, c₂)). We can multiply it by 3 to find the answer.

Let us imagine that a random selection (c1, c2, c3) is made. We'll define a function f(j), for each edge j, so that f(j) = w_j if j is part of the shortest path from c₁ to c₂, and f(j) = 0 otherwise. Observe that . Again by linearity, we have .

We can write E(f(j)) = w_j·P(j), where P(j) is the probability that edge j is included in the path from c₁ to c₂. If we compute P(j) for all j, we can then compute in O(N). Also, we can handle updates in O(1); if w_j changes to w'_j, we subtract w_j·P(j) from the answer, and add w'_j·P(j).

So, let's figure out P(j) for each j. Any edge j, if removed from the tree, separates the graph into two separate connected components a and b. Edge j will be included in the shortest path from c₁ to c₂ if and only if one of them is in a, and the other is in b. So, we want the number of ways to select (c₁, c₂, c₃) such that c₁ and c₂ are on opposite sides of edge j, divided by the total number of ways to select (c₁, c₂, c₃). Let's have |a| and |b| denote the number of vertices in a and b, respectively. Then .

To figure out |a| and |b| for each j, we can root the tree arbitrarily and compute the depth and subtree size for each vertex in O(N) time. Then for an edge j, if v_j is the deeper vertex incident to j, we know one component has size equal to the subtree size of v_j. For the other component, we use the fact that |b| = N - |a|.

500E — New Year Domino

When domino i is knocked over, it covers the interval [p_i, p_i + l_i]. If we see a query (x_j, y_j), it is equivalent to the question "If we knock over all dominoes with index , how much of the interval [p_xj, p_yj] won't be covered?" We can modify that question a little more, to say that we knock over all dominoes with index i ≥ x_j, without changing its answer.

Now, consider knocking over the dominoes from right to left. As soon as we knock over domino i, we will immediately process all of the queries with x_j = i, and record their answers. What we need is a data structure that supports two operations: "cover range [p_i, p_i + l_i]" (when we knock over a domino) and "compute how much of the range [p_xj, p_yj] is not covered" (when we wish to answer a query). This can be done using coordinate compression and a segment tree.

It's worth noting there are a lot of other ways to solve this problem. The other tutorial uses a completely different approach. Also, the approach described here may be implemented using different data structures. For example, here is my implementation using BBSTs and a Binary Indexed Tree.

500F — New Year Shopping

We will use the standard dynamic programming approach for 0/1 knapsack. To summarize what it does for us, imagine we are given an ordered list of items (c_i, h_i). Let F(k, b) be the maximum happiness we can buy, if we consider only the first k items in the list, and have a budget of b. If K is the size of the list, and B is the maximum possible budget, we can compute F(k, b) for all possible k and b in O(KB) time.

Let us sort all of the items by their display time. Suppose that we focus on the queries (a_j, b_j) with , for some particular t. Let A be a list of the items with display time in (t - P, t], and let B be a list of the items with display time in (t, t + P). Let both lists be sorted in order of display time.

Every query with will have available to it some suffix of A, along with some prefix of B. We'll do a knapsack DP on the elements of A, in reverse order, and another on the elements of B, in normal order. Finally, to answer any query (a_j, b_j) with , we can consider all possible ways to split the budget b_j between the items in A and the items in B, in linear time. For each possible way to split the budget, we need simply look up one value from each DP table to know the maximum possible happiness.

If we perform the process above on t = 1, 1 + P, 1 + 2P, 1 + 3P, ... until t exceeds the maximum possible day D, we'll be able to answer all of the queries. Let's think about the runtime of this solution. For each t, the described process takes O(KB) time, where K is the number of items whose display time is in (t - P, t + P). Each object can only appear in up to two of these intervals. So, the overall runtime for all of the knapsack DP's we perform is O(nB). Computing the final answer takes O(B) per query, or O(qB) overall.

500G — New Year Running

Don't know how to solve this yet. Maybe someone who is not gray can provide the solution. :)