Why it is named "final"?

Auto comment: topic has been updated by joisino (previous revision, new revision, compare).

Auto comment: topic has been updated by joisino (previous revision, new revision, compare).

Could we see official results anywhere?

How to solve E? 75 points are interesting for me, too.

Brief outline of my solutions :

Problem 1.

Note that we're essentially partioning the array a[] into k parts and take the sum of the (difference of the max and min element of each part + 1). Suppose the parts are [1, i₁], [i₁ + 1, i₂], ..., [i_k - 1 + 1, n]. Then, the sum is a_n - a₁ + k - (a_i1 + 1 - a_i1) - ... - (a_{ik - 1 + 1} - a_ik - 1). Thus, we just need to sort the values a_i - a_i - 1 in decreasing order and we can greedily subtract the largest k - 1 differences from a_n - a₁ + k.

Problem 2.

Sort the items in increasing order of A_i and let P_i = B₁ + B₂ + ... + B_i. Note that since B_i is positive, we'll always choose a subsegment [l, r] of items. If we choose [l, r], the value is B_r - B_l - 1 - (A_r - A_l) = (B_r - A_r) - (B_l - 1 - A_l). We can iterate r from left to right and keep track of the prefix minimum of B_l - 1 - A_l.

Problem 3.

For each skewer, let's consider the G square that is contained by it. Even if there were no restrictions, each G square can only be part of at most 2 skewers (one in the up direction, one in the right direction). We can check which directions are valid for each G square in O(nm) time total. A configuration of skewers is equivalent to choosing a valid direction (or no directions) in each G square.

If we choose the up direction for a G square in (i, j), then we cannot choose the right direction for the squares (i - 1, j + 1) and (i + 1, j - 1). Similarly, if the right direction is chosen for (i, j), then the up direction can't be chosen for squares (i - 1, j + 1) and (i + 1, j - 1). Conversely, these 2 conditions are sufficient, i.e. every valid assignment satisfying these 2 additional conditions corresponds to a valid skewering.

Thus, we can do a simple linear-time dp for each diagonal (consisting of squares (i, j) with i + j = S for some fixed S). The states are dp[i][j], where i is the current row we're considering and j is 0 if we did not assign any direction to the square in last row, 1 if we assigned the right direction and 2 if we assigned the up direction.

Problem 4.

Suppose we fixed a shortest path P from S to T. We can easily prove that our path from U to V will enter some vertex in P at most once and exit it at most once (otherwise we can walk inside P instead of walk outside P in the interval between first exit and second entry). Let's do Dijkstra's algorithm from both U and V, and let d1[i], d2[i] denote the distance from i to U and V respectively. If our path from U to V never touch P then our distance is simply d1[V], so we will assume it touches P.

Our problem reduces to choosing a shortest path from S to T such that if we let i, j be the vertices in the shortest path such that d1[i] and d2[j] are minimized respectively, then d1[i] + d2[j] is minimized.

We can compute dp[i], the minimum possible d2[j] among all vertices j for some shortest path from S to i and dp2[i] where S is replaced with T. Now, iterate over all vertices v such that v lies on some shortest path from S to T (or equivalently distance from S to v + distance from v to T = distance from S to T), and find the minimum possible value of d1[v] + min(dp[v], dp2[v]).

Problem 5.

Let's solve the problem for L ≤ 13 first. We will compute the answer for each of the 3^L possible queries in total of O(3^L) time and store them with O(3^L) memory. (Idea is that the answer for a string with at least one question mark is the sum of answer for a string where the last question mark is replaced by 0 and 1, and we can precompute which bits are the "children" of each bit first to make sure we do state transitions in O(1)).

To solve the full problem, we will do meet-in-the-middle. We iterate over the 128 possible values for the first 7 bits and for each iteration we iterate over all queries and find the queries such that the first 7 bits match the query pattern (it's possible to check this in O(1) with precomputation). We do the O(3^L) dp above every iteration (reusing the same array for dp to avoid MLE) and now for each query, we can solve the suffix of length L - 7 in O(1) time.

This solution works in O(2⁷·(3¹³ + Q)) time and O(3¹³ + Q) memory.

You can submit all problems here: https://oj.uz/problems/source/307

Where can I find the test data for the problems? It seems that test data is generally published on the contest information page for JOI, but I cannot find it for this contest.