My ultra-short problemset which can be read in 60s.

Правка en15, от wuhudsm, 2023-08-29 13:09:30

Hi guys,here I'd like to share some of my problems(will continue to be updated, depending on your feedback). All the problems are created by myself.

They contain my aesthetic of problems: the neater,the better. Interest and educational significance are also important.

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.
Constraint
Difficulty
Point

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).
Constraint
Difficulty
Point

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.

Constraint
Difficulty
Point

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.

Constraint
Difficulty
Point1
Point2
Point3

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.

Constraint
Difficulty
Point

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

Constraint
Difficulty
Point

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.

Constraint
Difficulty
Point1
Point2

There are also some problems that I think have educational significance.

8.Maximum Sum

You're given an array $$$a$$$ of size $$$n$$$.

You can do the following operation any number of times:

  • Choose any two adjacent element $$$a_i,a_{i+1}$$$;

  • Note $$$g=gcd(a_i,a_{i+1}),l=lcm(a_i,a_{i+1})$$$,set $$$a_i:=g$$$ and $$$a_{i+1}:=l$$$.

Find the maximum value of $$$\Sigma^{n}_{i=1}a_{i}$$$ you can get(mod $$$10^9+7$$$).

Constraint
Difficulty
Point

9.Collinear Points

$$$n$$$ points are given on the coordinate system such that the coordinates of the $$$i^{th}$$$ point are $$$(x_i,y_i)$$$ and $$$x_i \lt x_{i+1}$$$ for all $$$(1\le i \lt n)$$$.

Maintain two types of queries:

  • Type $$$1$$$: You are given $$$5$$$ integers in the form: 1 l r k b. For all $$$l \le i \le r$$$, change the coordinates of the $$$i^{th}$$$ point to $$$(x_i, k\cdot x_i+b)$$$.

  • Type $$$2$$$: You are given $$$3$$$ integers in the form: 2 l r. Find whether the $$$l^{th}, (l+1)^{th},\ldots ,r^{th}$$$ points are collinear (lie on the same straight line).

Constraint
Difficulty
Point1
Point2

10.Revolving Sushi

There are $$$n$$$ circular positions on the table in the sushi restaurant.

Initially, there are $$$x_i$$$ pieces of sushi in the plate at position $$$i$$$.Every second,the plate at position $$$i$$$ will be put into $$$a_i$$$ pieces of sushi.Then:

  • The plate at position $$$1$$$ will move to position $$$2$$$;
  • The plate at position $$$2$$$ will move to position $$$3$$$;
  • ...
  • The plate at position $$$n$$$ will move to position $$$1$$$.

If for each position,the number of sushi is a multiple of $$$k$$$,customers will be happy.

Find the minimum waiting time to make customers happy.If there's no solution,output $$$−1$$$ instead.

Constraint
Difficulty
Point1
Point2

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en20 Английский wuhudsm 2023-08-31 14:33:11 47 Tiny change: 'Hi guys,he' -> '(Last updated time:2023/8/31,14 problems)\n\nHi guys,he'
en19 Английский wuhudsm 2023-08-31 13:45:56 3399
en18 Английский wuhudsm 2023-08-30 11:26:05 4 Tiny change: 'y(0 \le y \le 2^{30})$ ' -> 'y(0 \le y < 2^{30})$ '
en17 Английский wuhudsm 2023-08-29 13:11:56 1 (published)
en16 Английский wuhudsm 2023-08-29 13:09:50 4 Tiny change: 'eedback). All the pr' -> 'eedback). \n\nAll the pr'
en15 Английский wuhudsm 2023-08-29 13:09:30 701
en14 Английский wuhudsm 2023-08-29 12:59:15 480
en13 Английский wuhudsm 2023-08-27 22:58:49 16 Tiny change: 'e array.\nFind the' -> 'e array.\n\nFind the'
en12 Английский wuhudsm 2023-08-27 22:11:08 4
en11 Английский wuhudsm 2023-08-27 21:59:36 1186
en10 Английский wuhudsm 2023-08-27 21:50:33 944
en9 Английский wuhudsm 2023-08-27 21:46:07 898
en8 Английский wuhudsm 2023-08-27 21:30:22 293
en7 Английский wuhudsm 2023-08-27 21:26:51 924
en6 Английский wuhudsm 2023-08-27 21:17:21 3630
en5 Английский wuhudsm 2023-08-27 20:27:51 827
en4 Английский wuhudsm 2023-08-27 20:04:10 101
en3 Английский wuhudsm 2023-08-27 20:00:44 379 Tiny change: 'asing.\n\n$1 \le x <' -> 'asing.\n\n- $1 \le x <'
en2 Английский wuhudsm 2023-08-27 19:41:13 54
en1 Английский wuhudsm 2023-08-27 19:39:52 508 Initial revision (saved to drafts)