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.

Why it is named "final"?

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.)

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?

Currently, you can see the ranking page. The official result will be announced later.

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

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).

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_{1}], [i_{1}+ 1,i_{2}], ..., [i_{k - 1}+ 1,n]. Then, the sum isa_{n}-a_{1}+k- (a_{i1 + 1}-a_{i1}) - ... - (a_{ik - 1 + 1}-a_{ik - 1}). Thus, we just need to sort the valuesa_{i}-a_{i - 1}in decreasing order and we can greedily subtract the largestk- 1 differences froma_{n}-a_{1}+k.Problem 2.

Sort the items in increasing order of

A_{i}and letP_{i}=B_{1}+B_{2}+ ... +B_{i}. Note that sinceB_{i}is positive, we'll always choose a subsegment [l,r] of items. If we choose [l,r], the value isB_{r}-B_{l - 1}- (A_{r}-A_{l}) = (B_{r}-A_{r}) - (B_{l - 1}-A_{l}). We can iteraterfrom left to right and keep track of the prefix minimum ofB_{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) withi+j=Sfor some fixedS). The states aredp[i][j], whereiis the current row we're considering andjis 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

PfromStoT. We can easily prove that our path fromUtoVwill enter some vertex inPat most once and exit it at most once (otherwise we can walk insidePinstead of walk outsidePin the interval between first exit and second entry). Let's do Dijkstra's algorithm from bothUandV, and letd1[i],d2[i] denote the distance fromitoUandVrespectively. If our path fromUtoVnever touchPthen our distance is simplyd1[V], so we will assume it touchesP.Our problem reduces to choosing a shortest path from

StoTsuch that if we leti,jbe the vertices in the shortest path such thatd1[i] andd2[j] are minimized respectively, thend1[i] +d2[j] is minimized.We can compute

dp[i], the minimum possibled2[j] among all verticesjfor some shortest path fromStoianddp2[i] whereSis replaced withT. Now, iterate over all verticesvsuch thatvlies on some shortest path fromStoT(or equivalently distance fromStov+ distance fromvtoT= distance fromStoT), and find the minimum possible value ofd1[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 ofO(3^{L}) time and store them withO(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 inO(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 theO(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 lengthL- 7 inO(1) time.This solution works in

O(2^{7}·(3^{13}+Q)) time andO(3^{13}+Q) memory.My Solution of Problem 5:

(

N= 2^{L})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 withO(2^{A})(A : the number of '1').Similarly, we can also calc query with

O(2^{B})(B : the number of '0')By the way, we can calc query with

O(2^{C})(C : the number of '?'), obviously.Last, we choice those 3 algorithms for each query, we can archive

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

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