You are given an integer $$$n$$$. Find all values of $$$x$$$ where $$$1 \le x \le 2^{100}$$$, such that $$$[1 \oplus x, 2 \oplus x, \dots , n \oplus x]$$$ forms a permutation of size $$$n$$$.
The first line contains a single integer $$$n$$$ ($$$1\le n \lt 2^{30}$$$).
If there are no such values of $$$x$$$, output $$$-1$$$. Otherwise, output all valid $$$x$$$.
6
7
3
-1
In the first sample, for $$$n=6$$$, only $$$x=7$$$ satisfies the condition:
$$$[1\oplus \color{orange}{7}, 2\oplus \color{orange}{7}, 3\oplus \color{orange}{7}, 4\oplus \color{orange}{7}, 5\oplus \color{orange}{7}, 6\oplus \color{orange}{7}]=[6, 5, 4, 3, 2, 1]$$$.
You are given a $$$n \times n$$$ grid. You can perform the following operation:
- Select any row or column in the grid and replace each integer in that row or column with the mean of the integers in that row or column.
Your task is to maximize the minimum value in the grid by performing the operations any number of times.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$) — the size of the grid.
Each of the following $$$n$$$ lines contains $$$n$$$ integers $$$a_{i,j}$$$ ($$$1 \leq a_{i,j} \leq 10^9$$$) — the elements of the grid.
Output the maximum possible minimum value in the grid after the operations.
Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a-b|}{\max(1,|b|)}\le 10^{-6}$$$.
2 7 8 1 2
4.5000000
In the first example, we can obtain the answer in the following way:
- Choose column $$$1$$$: $$$ \begin{pmatrix} \color{orange}7 & 8 \\ \color{orange}1 & 2 \end{pmatrix} \rightarrow \begin{pmatrix} \color{orange}4 & 8 \\ \color{orange}4 & 2 \end{pmatrix} $$$
- Choose column $$$2$$$: $$$ \begin{pmatrix} 4 & \color{orange}8 \\ 4 & \color{orange}2 \end{pmatrix} \rightarrow \begin{pmatrix} 4 & \color{orange}5 \\ 4 & \color{orange}5 \end{pmatrix} $$$
- Choose row $$$1$$$: $$$ \begin{pmatrix} \color{orange}4 & \color{orange}5 \\ 4 & 5 \end{pmatrix} \rightarrow \begin{pmatrix} \color{orange}{4.5} & \color{orange}{4.5} \\ 4 & 5 \end{pmatrix} $$$
- Choose row $$$2$$$: $$$ \begin{pmatrix} 4.5 & 4.5 \\ \color{orange}4 & \color{orange}5 \end{pmatrix} \rightarrow \begin{pmatrix} 4.5 & 4.5 \\ \color{orange}{4.5} & \color{orange}{4.5} \end{pmatrix} $$$
Now, the minimal number in the grid is $$$4.5$$$.
You are given an array $$$a$$$ of length $$$n$$$.
Your task is, for each $$$k \in \{1, \ldots, n\}$$$, to find the subsequence of length $$$k$$$ with the maximum Greatest Common Divisor.
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — the length of the array.
The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) — elements of array $$$a$$$.
Output $$$n$$$ integers — the maximum Greatest Common Divisor for each $$$k$$$.
7 3 4 9 6 8 2 3
9 4 3 3 1 1 1
Elements highlighted in orange are one of the optimal subsequences:
- $$$k=1$$$, $$$a=[3, 4, \color{orange}9, 6, 8, 2, 3]$$$.
- $$$k=2$$$, $$$a=[3, \color{orange}4, 9, 6, \color{orange}8, 2, 3]$$$.
- $$$k=3$$$, $$$a=[\color{orange}3, 4, \color{orange}9, \color{orange}6, 8, 2, 3]$$$.
- $$$k=4$$$, $$$a=[\color{orange}3, 4, \color{orange}9, \color{orange}6, 8, 2, \color{orange}3]$$$.
- $$$k=5$$$, $$$a=[3, \color{orange}4, \color{orange}9, 6, \color{orange}8, \color{orange}2, \color{orange}3]$$$.
- $$$k=6$$$, $$$a=[\color{orange}3, \color{orange}4, \color{orange}9, 6, \color{orange}8, \color{orange}2, \color{orange}3]$$$.
- $$$k=7$$$, $$$a=[\color{orange}3, \color{orange}4, \color{orange}9, \color{orange}6, \color{orange}8, \color{orange}2, \color{orange}3]$$$.
You are given a string $$$s$$$. You can perform the following operation:
- Choose a letter $$$c$$$ and find all its occurrences in $$$s$$$. Let these occurrences be $$$p_1, \dots, p_m$$$. You cyclically increase the letters at those positions by one. The cost of this operation is $$$p_m - p_1$$$.
Your task is to make all the letters equal, achieving the minimal total cost.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the string.
The second line contains $$$s_1, \dots, s_n$$$. The letters are lowercase English alphabet characters.
Output the minimal total cost.
5 azabz
3
4 abca
0
8 baknsasn
52
10 bcforobxgf
54
You can perform the following operations to achieve the optimal answer:
- $$$aza\color{orange}bz \rightarrow aza\color{orange}cz$$$, the cost is $$$0$$$.
- $$$aza\color{orange}cz \rightarrow aza\color{orange}dz$$$, the cost is $$$0$$$.
- ...
- $$$aza\color{orange}yz \rightarrow aza\color{orange}zz$$$, the cost is $$$0$$$.
- $$$a\color{orange}za\color{orange}z\color{orange}z \rightarrow a\color{orange}aa\color{orange}a\color{orange}a$$$, the cost is $$$3$$$, because the occurrences of $$$\color{orange}z$$$ are $$$\{2, 4, 5\}$$$ and the cost is $$$5 - 2$$$.
The total cost is $$$3$$$.
You are given two arrays $$$a$$$ and $$$b$$$, both of length $$$n$$$.
You are creating a new array $$$c$$$. Initially, it is empty. On step $$$i$$$, you add either $$$a_i$$$ or $$$b_i$$$ to the end of the array.
Your task is to construct array $$$c$$$ in such a way that the length of the Longest Increasing Subsequence of $$$c$$$ is maximized.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the length of the arrays.
The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — elements of array $$$a$$$.
The third line contains $$$n$$$ integers $$$b_1, \dots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — elements of array $$$b$$$.
Output the length of the Longest Increasing Subsequence in the constructed array $$$c$$$.
6 1 4 3 5 2 9 4 3 1 2 5 1
4
5 1 9 4 5 6 1 9 10 5 6
4
In the first sample, you can choose $$$c = \{a_1, b_2, a_3, a_4, b_5, a_6\}$$$.
The values of $$$c$$$ are $$$\{\color{orange}1, 3, \color{orange}3, \color{orange}5, 5, \color{orange}9\}$$$. The elements highlighted in orange form the Longest Increasing Subsequence of length $$$4$$$.
You are given two trees. Add one edge between them in a manner that minimizes the diameter of the resulting tree.
The first line contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the number of vertices in the first tree.
Then follow $$$n-1$$$ lines describing the tree; the $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$) — an edge in the tree.
The next line contains an integer $$$m$$$ ($$$2 \leq m \leq 2 \cdot 10^5$$$) — the number of vertices in the second tree.
Then follow $$$m-1$$$ lines describing the tree; the $$$j$$$-th line contains two integers $$$u_j$$$ and $$$v_j$$$ ($$$1 \leq u_j, v_j \leq m$$$, $$$u_j \neq v_j$$$) — an edge in the tree.
Output the minimum possible diameter.
5 1 2 1 3 3 4 3 5 7 1 2 1 3 3 4 3 5 3 6 7 5
5
In the sample, a new edge can be added as depicted below:
The highlighted edge is newly added. The diameter in this tree is $$$5$$$.
You are given an array $$$a_1, \dots, a_n$$$. Your task is to count the number of pairs $$$1 \leq i \lt j \leq n$$$ for which $$$\gcd(a_i + j, a_j + i) = i + j$$$.
The first contains a single integer $$$n$$$ ($$$2\le n\le 2\cdot 10^5$$$) — the length of the array $$$a$$$.
The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$1 \leq a_i \leq 2\cdot 10^5$$$) — elements of array $$$a$$$.
Output the number of pairs that satisfy the condition.
6 13 20 11 16 11 5
4
5 1 2 3 4 5
10
In the first sample, there are four pairs:
- $$$[\color{orange}{13}, \color{orange}{20}, 11, 16, 11, 5]$$$, where $$$\gcd(13+2,20+1)=1+2$$$.
- $$$[\color{orange}{13}, 20, \color{orange}{11}, 16, 11, 5]$$$, where $$$\gcd(13+3,11+1)=1+3$$$.
- $$$[\color{orange}{13}, 20, 11, 16, \color{orange}{11}, 5]$$$, where $$$\gcd(13+5,11+1)=1+5$$$.
- $$$[13, \color{orange}{20}, 11, \color{orange}{16}, 11, 5]$$$, where $$$\gcd(20+4,16+2)=2+4$$$.
In the second sample, each pair satisfies the condition.
You are given a permutation $$$a$$$ of length $$$n$$$. You can perform the following operation:
- Choose a segment $$$1\leq l\leq r\leq n$$$ and sort it. The cost of such operation is $$$a_l + \dots + a_r$$$.
Your task is to sort the permutation with minimal total cost.
The first contains a single integer $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the length of the permutation $$$a$$$.
The second line contains $$$n$$$ integers $$$a_1, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$) — elements of permutation $$$a$$$.
Output the minimal total cost.
6 3 1 2 4 6 5
17
4 1 4 3 2
9
In the first sample, you can perform the following operations:
- $$$[\color{orange}3, \color{orange}1, \color{orange}2, 4, 6, 5] \rightarrow [\color{orange}1, \color{orange}2, \color{orange}3, 4, 6, 5]$$$, the cost is $$$1+2+3=6$$$.
- $$$[1, 2, 3, 4, \color{orange}6, \color{orange}5] \rightarrow [1, 2, 3, 4, \color{orange}5, \color{orange}6]$$$, the cost is $$$5+6=11$$$.