joisino's blog

By joisino, history, 2 weeks ago, In English,

Hello Everyone!

The 17th Japanese Olympiad in Informatics Final Round Online Contest will be held on 11 Feb. (00:30 — 04:30 GMT).

The contest duration is 4 hours and there will be 5 problems, which is the same as the 17th JOI Final Round. Problem statements will be provided both in Japanese and English.

The registration page will be announced 30 minutes before the contest. I will update this blog post then.

You can see details in the contest information page.

UPD: The contest has postponed 30 minutes due to a technical issue. Sorry for inconvenience.

UPD2: The contest site is open. You can register now.

UPD3: The contest is over. Currently, the contest is in analysis mode. You can submit your codes through the contest site unofficially. The official result and the contest materials (input/output, official editorial, official answer code) will be distributed later.

 
 
 
 
  • Vote: I like it  
  • +64
  • Vote: I do not like it  

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why it is named "final"?

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    A preliminary round is held in December every year, which is provided only in Japanese.

    This contest is the onsite final contest of JOI.

    (Most of contestants think of the delegation selection camp in March as the true final round, though.)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Could we see official results anywhere?

»
2 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    13 days ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    Only for 75 points my solution: I generated new array with 2^14 size for all possible masks of first 6 symbols in query (totally 3^6 masks). It works fast and holds 32 MB of memory. Then for each query we have already known the array for it's 6 first symbols, and then we can naively compute the answer in O(2^14) time for query. The final complexity is fast precalc + O(2^14*Q).

»
2 weeks ago, # |
  Vote: I like it +76 Vote: I do not like it

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, i1], [i1 + 1, i2], ..., [ik - 1 + 1, n]. Then, the sum is an - a1 + k - (ai1 + 1 - ai1) - ... - (aik - 1 + 1 - aik - 1). Thus, we just need to sort the values ai - ai - 1 in decreasing order and we can greedily subtract the largest k - 1 differences from an - a1 + k.

Problem 2.

Sort the items in increasing order of Ai and let Pi = B1 + B2 + ... + Bi. Note that since Bi is positive, we'll always choose a subsegment [l, r] of items. If we choose [l, r], the value is Br - Bl - 1 - (Ar - Al) = (Br - Ar) - (Bl - 1 - Al). We can iterate r from left to right and keep track of the prefix minimum of Bl - 1 - Al.

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 3L possible queries in total of O(3L) time and store them with O(3L) 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(3L) 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(27·(313 + Q)) time and O(313 + Q) memory.

  • »
    »
    12 days ago, # ^ |
    Rev. 2   Vote: I like it +15 Vote: I do not like it

    My Solution of Problem 5:

    (N = 2L)

    If query don't contain '1', we can solve this problem O(NlogN + Q) with fast zeta transform(we can precalc for all type of query). If query contain '1'? We use inclusion-exclusion principle, and calc query with O(2A)(A : the number of '1').

    Similarly, we can also calc query with O(2B)(B : the number of '0')

    By the way, we can calc query with O(2C)(C : the number of '?'), obviously.

    Last, we choice those 3 algorithms for each query, we can archive

»
12 days ago, # |
  Vote: I like it +15 Vote: I do not like it

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

  • »
    »
    12 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Time limits and memory limits were wrong for the last three problems, now fixed.