Hi guys,here I'd like to share my problem set in an interesting way. All the problems are created by myself.

They contain my aesthetic of problems: the neater,the better. It should be also interesting and best to have educational significance.

You can find the editorial for all the problems in the link,so I will only write down some interesting points under the statement.

Let's go :)

1.Increasing and Decreasing

Construct an array $$$a$$$ consisting of $$$n$$$ integers which satisfies the following conditions:

• $$$a_1=x,a_n=y$$$;
• $$$a$$$ is strictly increasing;
• if we denote $$$b_i=a_{i+1}-a_{i}$$$ for $$$1 \leq i \leq n-1$$$, then $$$b$$$ is strictly decreasing.

2.(Yet Another) Increasing and Decreasing

Construct an array $$$a$$$ consisting of $$$n$$$ integers which satisfies the following conditions:

• $$$a_1=x$$$;
• $$$a_n<2^{30}$$$;
• $$$a$$$ is strictly increasing;
• if we denote $$$b_i=a_{i+1}⊕a_{i}$$$ for $$$1 \leq i \leq n-1$$$, then $$$b$$$ is strictly decreasing($$$⊕$$$ is bitwise-xor).

3.Mex Path

You are given a $$$2 \cdot n$$$ grid $$$a$$$. On the grid,there is a non-negative integer $$$a_{i,j}$$$ in row $$$i$$$ and line $$$j$$$.

You must walk from $$$(1,1)$$$ to $$$(2,n)$$$. Each cell can be accessed at most once.At each step, you can go up, down, or right(but not to the left or beyond the boundary).

Note the set of numbers on the grid you have walked through is $$$S$$$. Find the biggest $$$mex(S)$$$ you can get.

4.Divisor Chain

You are given an integer $$$x$$$. Your task is to reduce $$$x$$$ to $$$1$$$.

To do that, you can do the following operation:

• select a divisor $$$d$$$ of $$$x$$$, then reduce $$$x$$$ by $$$d$$$.

There is an additional constraint: you cannot select the same value of $$$d$$$ more than twice.

Output any scheme which reduces $$$x$$$ to $$$1$$$ with at most $$$1000$$$ operations.

5.Strange Shuffle

There is a big array $$$a$$$ of size $$$n$$$ and $$$a_i=i$$$ initially.

The following process will be repeated cyclically until there is only one element left:

• Erase $$$a_1$$$.
• Note $$$x$$$ is the amount of elements in the current $$$a$$$.Move the first $$$⌊x/2⌋$$$ elements after the last $$$x−⌊x/2⌋$$$ elements.
• Erase $$$a_1$$$.
• Reverse the whole array. Find the value of the last remaining element.

Now let's increase the difficulty a bit.Here are two interaction problems that I really enjoy.

6.Get the Segment

There’s a hidden array $$$a$$$ of size $$$n$$$. Each element of the array is either $$$1$$$ or $$$2$$$.

Interact with the judge using queries. Each query is of the form:

l r You choose two positive integers $$$l$$$ and $$$r$$$ $$$(1 \leq l \leq r \leq n)$$$.The judge will reply with $$$\Sigma^{r}_{i=l}a_i$$$.

Use at most $$$40$$$ queries to find a subarray with sum $$$k$$$(given $$$k$$$ guarante such subarray exists).

7.Xor X,Get MAX

There’s a hidden array $$$a$$$ consisting of $$$n$$$ distinct non-negative integers.

Interact with the judge using queries. Each query is of the form:

x y: Given two non-negative integers $$$x$$$ and $$$y(0 \le y \le 2^{30})$$$ as the query, the hidden array $$$a$$$ is updated by setting $$$a_{x}:=a_{x} \oplus y$$$. After that, the judge will return the maximum value of the updated array.

Make all the elements of the array equal to $$$0$$$ using at most $$$10^5$$$ operations.