Yes

Accordingly to this paper of IOI reactive tasks are "Reactive tasks: Solutions comprise a single source file of a computer program that is compiled together with an “opponent” library provided by the organizers, and interacts with it according to the specification given in the task description. Such solutions are not allowed to read anything from the standard input, or write anything to the standard output."

AKA interactive tasks.

20 minutes left to the beginning of the first day, good luck guys

It's here.

How to do passport faster than O(n^2)

What I heard in the editorial at onsite contest hall is that, speeds up $$$O(N^2)$$$ DP with a technique called "relaxed convolution", and achieves the time complexity of $$$O(N^{1.59})$$$ or $$$O(N \log^2 N)$$$.

May I ask how to do the O(n^2) dp? I have no idea how to approach this task...

Sort the edges and then find a point in time when the sum of edges on the path is at most y. Binary search + persistent/2d data structure works.

Mo I guess?

$$$O((n+m+q)\log(n))$$$ with persistent trees I guess.

You can solve in $$$O((m + q)\log(m) + n\log(n))$$$ using persistent segment trees. Normally it's $$$log(C_{max})$$$ but you can make it $$$log(m)$$$ by compressing values. The idea is to use persistent segment trees to find the sum and count of elements $$$\leq x$$$ from a node to root. You can do this by keeping a persistent segment tree on root and for every node creating another segment tree by updating its parent's segment tree persistently. Then, you can find those values for a path with $$$f(a) + f(b) - 2 * f(lca(a, b))$$$. When you can find that, you can binary search for the max price you'll take. This way, one query is $$$O(log^2(m)$$$. However, you can use binary search on segment tree trick. You walk on the segment tree as usual but instead of 1, you keep track of 3 pointers.

I see an "Until analysis ends:" timer on the contest page of day 1. I guess that means upsolving is available.

I think there will be an editorial here (not posted yet, maybe after contest). As the editorial of JOISC2022 is posted here.

Hi. Will upsolving be open after all 4 days of contests, or we can upsolve somewhere right now?

Hi. Is upsolving still open?

Is this just using the fact that in a zigzag the big segment in an optimal solution has <= log(L) size? And putting that in a segment tree? Maybe there's some way to optimize the merge function in the segment tree. But it seems hard, and then you will save one log factor at most.

could you elaborate more ?

With this complexity you can barely solve one query within TL, let alone 50000 of them (but that's also the best I came up with). However Radewoosh told me that we can prove that some kind of greedy works.

(First key, but easy fact is that all small chunks are single elements, which I assume onwards). Let us assume we are solving a query for the entire sequence. Let $$$g(k)$$$ be the lowest index of a k-th small chunk in any viable solution. Let $$$f(i)$$$ be the highest $$$j<i$$$ such that both $$$j$$$ and $$$i$$$ can be consecutive small chunks. It is obvious that $$$f(g(k+1)) \ge g(k)$$$. But the key observation is that $$$g(k+1)$$$ can actually be set as the lowest $$$i$$$ such that $$$f(i) \ge g(k)$$$. There is a technical exchange argument involving $$$g(k), f(i)$$$ and $$$i$$$ that goes along the way "if $$$g(k)$$$ and $$$i$$$ cannot be put as consecutive small chunks then you can replace $$$g(k)$$$ with $$$f(i)$$$ and put $$$i$$$ into your greedy optimal sequence", which works because of some inequalities. You need to take some care about what is happening around the borders, but that is less interesting I guess.

There is still a lot of work to be done, but I guess that was the stopping point for the majority of people

Mine is $$$O(n\log(A) + q(\log^2(A)+\sqrt{n}))$$$, where $$$A = 10^9$$$, but I guess we can get rid of $$$\sqrt{n}$$$ part (but it was the easiest one to implement).

Case analysis a little bit and then you end up with M pairs of bitmasks of size N $$$(A_j, B_j)$$$. They say that if you choose $$$i \in A_j, j \in B_j$$$, the answer for pair (i,j) increases by 1. Then, you need to do subset dp over the sets of $$$B$$$ to achieve the biggest answer given that i is contained in some mask of As. Some care is needed for i=j case.

Group edges by depth mod 3 and always mark the biggest group and flipping known edges upward the root.

Let us group vertices by their depth modulo 3 and take the biggest group. With one query you can get at least one edge outgoing from each of these (which will be disjoint). And recurse on all connected components in parallel. That gives $$$\log_{1.5}(n)$$$ queries

There is one additional caveat. Ideally when recursing we would like to forget that edges whose directions we already know about exist. That can't really be done, but you can orient them all towards the root and never query a root of a remaining connected component

In fact, a lot of solution can pass this problem. Here's the standard solution(in my point of view):

Before one operation, if on this table a product is put, then we say the table is occupied.

As you can see, if the table is occupied, then after a operation, at least one of its edges('s direction) can be confirmed. In order to work out in 30 operations, we want to occupy as many tables as possible in every single query, but occupied tables also influence each other.

Also, confirmed edges can be annoyed. If we know the direction between (a,b). Next time when occupy table a, use the reverse operation to make sure $$$a\leftarrow b$$$. What's more, a and b can't be occupied at the same operation.

Based on the trival thought above, we can figure out the method to solve a chain in three queries. It's the time to promote this method.

• Root the tree with node 0, and get every node's depth, mantain three set, the first set cantains all nodes which depth mod 3 = 0, the second cantains all nodes which depth mod 3 = 1 etc.
• Choose the largest set, occupy all the nodes in it in this operation.
• If every edge of one node is confirmed, delete it from the set. Repeat step 2.

The correctness of this method is simple, if two nodes are in the same set, they won't influence each other. Every time, no less than $$$\frac 1 3$$$ of the undirected edges can be comfirmed, so at most $$$\log_{\frac 3 2}n=29$$$ operations are need.

I solved Conveyor in a different way, without even using the knowledge of where the product ended up, it only looks at if some product remained stationary (and all edges where thus pointing inwards for this vertex).

It is easy to see that we can confirm the direction of a leaf edge in 1 query, by just putting a product on the leaf, and checking in the end result if the product stayed in place or not. In fact this same trick works for all leafs at the same time.

After we know the direction of some edge of a leaf, we can just as well ignore this edge from now on, by pointing it in the right direction.

So if there are a lot of leaves in our forest in the current step we are done.

Otherwise it must be the case that there are a lot of degree 2 vertices. Let's query those degree 2 vertices by placing product on each degree 2 vertex (actually not on two adjacent degree 2 vertices).

With 3 queries we can query all combinations of edge directions of its two edges. (not 4, because 1 query can be saved because we know what its answer will be). This takes slightly too many queries, but during the degree 2 process we can also still use our leaf removing strategy in parallel, and this gives AC.

It seems there are many interesting solutions to Conveyor. Here is my solution:

This can directly be used for the full solution. Take all nodes with degree $$$\leq 2$$$ and group them into connected components. These components will be lines and can be solved in parallel all together using two queries using the method for the previous subtask. Then "remove" all these nodes and all their edges by orienting the edges towards the remaining graph. And repeat.

It is not hard to show that the number of nodes with degree $$$\leq 2$$$ is always strictly greater than half of the total number of nodes. This gives at most $$$2 \log_2 n$$$ queries. Although that can be greater than $$$30$$$, this is a high upper bound and it can be shown this solution will never need more than $$$30$$$ queries.

You can do subset dp, if you only iterate over subsets it's $$$3^M$$$, if you only change 1 bit, it's $$$M2^M$$$

D&C on $$$1...M$$$, if you have a time interval $$$(l,r)$$$, calculate the answer for all queries containing the middle $$$m$$$. First, build a virtual tree on $$$C_l, ... C_r$$$, then run dfs from $$$C_m$$$ on the virtual tree, you get a triple $$$(x,y,w)$$$ for each edge meaning, increase the answer of all queries with $$$l\leq x \lor y \leq r$$$ by $$$w$$$, (notice $$$x<m, y>m$$$), this can be done with a fenwick tree. This gives $$$\mathcal{O}(n\log^2{n})$$$ complexity.

I had a solution using MO in $$$O(n\sqrt{q}logn)$$$ but I couldn't make it fit in the TL :(

How did you achieve O(1) transitions? https://mirror.codeforces.com/blog/entry/114003?#comment-1015100 You should have definitely passed subtask 4

How to solve the last subtask of problem guard?

I passed the first subtask by considering the islands with $$$S_i=2$$$, and realized there should be one more guard between adjacent $$$S_i=2$$$ islands. Not clever enough to come up with the idea of the second subtask though.

I did each of the first four subtasks one by one, although the idea for the third and fourth subtasks came clear almost immediately after I solved the second subtask.

I didn't solve $$$N \le 16$$$ in contest, but I assume it was some kind of brute force?

My solution was $$$O(n + q (\log R + \log n)$$$ and it is a relatively simple implementation, how would a solution be $$$O(n \log n \log R)$$$?

My idea was to compute right[i] and left[i], the last node you will reach before turning back if you are currently at node i and going right or left respectively.

To do this, notice for each candidate turning point x[i], you can calculate the interval your starting node must be in to turn at that point (actually it's one before your starting node): WLOG say you're going right, then the distance to the next point at x[i] is x[i+1]-x[i]. So to turn, the node before your starting node must be to the right of x[i] - (x[i+1] - x[i]) = 2 * x[i] - x[i+1]. Similarly, the formula going left is 2 * x[i+1] - x[i].

Then iterate in the reverse direction of each of the arrays (iterate leftward on right array and vice versa), and keep a stack of pair<turning node, boundary of interval>, popping from the stack when the current point is not in the interval.

Then using this you can compute distance in $$$O(\log R)$$$ per query as you change directions at most $$$O(\log R)$$$ times, as in Swistakk's solution (each two changes of directions we are at least doubling the covered distance). For each direction change the next node is nxt = right[pos + 1] or nxt = left[pos — 1].

Interesting idea, during the contest I thought that you could try answering queries offline by using a priority queue and DSU. It looks like you only need to store the logarithm for the covering interval, and maintain $$$X[i]-X[i-1]\leq 2^k$$$ in DSU. This gets us $$$\mathcal{O}(N\alpha{(N)} + Q\log{R})$$$

I passed with $$$O(n S \log(n) / w)$$$, where $$$w$$$ is the wordsize, because of bitsets. Maybe other people can comment what they did. This fitted in ~0.2s. I reduced the problem to some knapsack style DP with some extra constraints, and noticed that a bunch of states were not reachable giving $$$O(n S \log(n))$$$ states. My states were just true or false so I optimized the transitions with bitsets.

https://cms.ioi-jp.org Here during the analysis you can upsolve.

In order to know we need to sacrifice Tutis to zh0ukangyang

From the E869120's review:

First, let's consider embedding the information of $$$(X, Y)$$$ in the $$$8$$$ squares of the diagonal. The method of embedding can be constructed by simulated annealing.
In this case, if $$$X = Y$$$, $$$42$$$ squares remain, and if $$$X ≠ Y$$$, $$$43$$$ squares remain, so we can achieve $$$N = 42$$$.

Next, in the case of $$$X = Y$$$, we will embed not only $$$(X, Y)$$$ on the diagonal but also the information of the last character of the string. Then, we need to embed $$$256$$$ types into $$$8$$$ characters, but the method of embedding can be discovered in a realistic time by speeding up the simulated annealing.

They're available on oj.uz if you want to upsolve or sth