There's always a problem to fall asleep after a late night (early morning) match, also drinking coffee during competition doesn't exactly help with that. So, here comes a rough write-up of div1 problems.

250 — MissingLCM

As one can verify easily using prime factorization theorem, the LCM of a set of numbers is , where α_p is the maximal power of p which divides some element of the set. Let us find largest p^t ≤ n for every prime p ≤ n; there should be a number in [n + 1;m] that divides p^t as well. Thus, ; there is a case when the new number divides some greater power of p, but we're fine with that. Find the greatest lower constraint for all p ≤ n. Use the Eratosphene's sieve to find all the primes. An O(n) solution is possible.

450 — ColorfulLineGraphs

Consider vertices from left to right. How many ways there are to place a new vertex along with an outcoming edge (if any)? There are k ways to place the vertex without an edge; if we choose the incoming vertex for the new edge, this excludes one color among possible options. Thus, if x vertices were already placed, there are exactly k + x(k - 1) ways to place a new vertex, possibly with an edge. The answer is simply the product k·(k + (k - 1))·(k + 2(k - 1))·.... It suffices to notices that M is rather small, and the product elements are looped modulo M, thus it is easy to find out how many times an element contributes to the product. Take care not to overflow int64. An solution is possible.

1000 — BridgeBuilding

Connecting two vertices with a zero-weight edge is effectively the same as merging the vertices into one; we will further go with this interpretation.

Call the parts of the graph between the merged vertices the havens (or whatever); a haven can be a loop or a pair of paths joined together. A loop haven can be represented by a pair of numbers (l, r) — the numbers of merged points in the original enumeration. Denote L_l, r (R_l, r) the largest distance from a vertex of (l, r)-haven to the merged vertex l (r), S_l, r the largest distance between any two vertices of (l, r)-haven, and D_l, r the distance between l and r (after merging each of them). All these numbers can be computed in O(n³) for all pairs (l, r) (use two pointers to compute S_l, r).

Suppose we have chosen pairs of vertices to merge; which pair of vertices can be farthest apart now? The farthest pair of vertices (u, v) can lie in the same haven, or in different havens. In the first case all pairs of vertices will be considered explicitly; in the second case the distance is equal to L + D₁ + ... + D_k + R, where L is the distance from u to the closest merged vertex, D₁, ..., D_k are distances between consecutive merged vertices inside a single haven, and R is the distance from the last merged vertex to v.

Binary search the diameter x. Compute dp_i, j with the following meaning: suppose we merged j pairs of vertices with last pair to merge having index i, we also took care that in the processed part no pair of vertices is at distance larger than x; than dp_i, j is the largest value of L + D₁ + ... + D_k such that the last merged vertex of D_k is the merged vertex i. Initialize dp_i, 1 with the two-paths havens, after that consider all possible options for the next vertex i; consider pairs of points in the current haven using S_l, r and all the rest using the DP value. Finally, to find the answer use such dp_i, k that the last two-paths haven does not have its vertices too far apart, and also dp_i, k + tail_i ≤ x, where tail_i is the largest distance from i to any of the ends. That makes for an solution, also probably a highly optimized O(n⁴) might pass.