UJGOI Contest#408

UJGOI Contest (Editorial)

Author:

Pavlo Tsitsei

Task preparation:

Pavlo Tsitsei, Oleksandr Tymkovych

Editorial:

Pavlo Tsitsei

Claim:

If we have two identical queries, we can work with it as with one query. This is because of operation bitwise xor. We have that a\oplus a=0 and a\oplus b\oplus a=b. So, if we choose two identical operations, it is equal to choosing none of them. In the next blocks, we will assume that all queries are unique.

Block : n\le 5:

Since is up to 5, we can have up to 10 queries, so we can just try all subsets of queries if they are correct.

Block : q\le 20:

We can try all subsets of queries. In order not to traverse the array, we can make an array where a_i=b_1\oplus b_2\oplus\dots\oplus b_i, and in this array, a query from to is equivalent to changing just b_l and b_{r+1}. So, we can count the number of ones in the array and when we change b_i, if it is 1, we decrease this value by one and change b_i, otherwise we increase the value and change element b_i. In order for the subset to be an answer, we need that after all queries we have zero ones.

Block : q\le 40:

Let's assume that is the index of the first element in the array. Let r_1, r_2, ..., r_m be all queries of type l, r_i in ascending order. Then, we use queries l, r_1 and delete all others and add r_1+1, r_i for all where i>1. In this way, if we choose query r_1+1, r_i, it is the same as choosing l, r_i. So, we can just do this many times until we get an array full of zeros.

Block : n\le 64:

Let's change our initial array to array as in the first block. Note that it can be represented as the binary representation of some number , and queries will be just xor of two powers of 2 (2^{r+1}\oplus 2^l). Then, we need to make the number equal to 0. We can try to do this greedily. Let's sort the array of queries in descending order. Then, we will make a new array sequentially. We push the biggest element of the array of queries to the end of this array. For each next element (let it be ), we traverse the array changing to min(x, x\oplus c_i) where is the -th element of the new array. If is not zero, we push it to the back of the array. To get the answer, we try to change in a way we changed , and we need to make it 0.

Block : All \ell_i are different:

We can use a greedy algorithm to solve this. Let's start from the first occurrence of element 1 in the array. Obviously, we need to make it zero, and there can be only one query starting in this position (we need to take the one that starts here. Intuitively, it is because if we change the array to array b we change only 2 elements, first and last). So we do this algorithm while we have queries or while we have some 1 in the array.

Block : a_i = 1 for all :

If we make an array as in the second block, it looks like , and each query will change two elements, which we can express as changing the index where element is. So, we can express it as a graph where we start at vertex and each edge changes your position (where edge is a query). And you need to get to vertex n+1, which can be done using .

Block : n, ~q~\le ~1000:

We will make an array as in the second block. Now, let's make a graph where the vertex set is the vertices of the array and the edge set is queries. Note that some number of queries can form a path and if we use all queries in the path, then only the elements that will change are the first and last. So, to solve the task, we can fix one element, which is , and find a path to any other element which is . Then, take all queries, i.e. path. If there is no other element equal to , there is no way to make an array equal to zero.

Block : without additional constraints:

We can optimize the solution for block 7 by making MST on the graph and making LCA on it. In this way, we can find a path between two vertices in .

Also, we can try to do it differently. We will construct a graph as in block and change b_{l_i} to b_{l_i}\oplus 1. Now, if we direct an edge from l_i to r_{i}+1, we need to change b_{r_{i}+1} to the opposite and take an edge to the answer. If we direct an edge in a different direction, we change b_{l_i} to the opposite and don't take the query. Now, we need to direct all edges in a way that some vertices have odd and others even in-degree (depending on the value of b_i). To do this, we need to find the DFS tree of it and edges not from the DFS tree directly in any direction. Then, we can greedily direct all edges in the tree, starting from the leaves. Then, just check if all vertices have the desired in-degree. The solution works in .