Milica has a string $$$s$$$ of length $$$n$$$, consisting only of characters A and B. She wants to modify $$$s$$$ so it contains exactly $$$k$$$ instances of B. In one operation, she can do the following:
- Select an integer $$$i$$$ ($$$1 \leq i \leq n$$$) and a character $$$c$$$ ($$$c$$$ is equal to either A or B).
- Then, replace each of the first $$$i$$$ characters of string $$$s$$$ (that is, characters $$$s_1, s_2, \ldots, s_i$$$) with $$$c$$$.
Milica does not want to perform too many operations in order not to waste too much time on them.
She asks you to find the minimum number of operations required to modify $$$s$$$ so it contains exactly $$$k$$$ instances of B. She also wants you to find these operations (that is, integer $$$i$$$ and character $$$c$$$ selected in each operation).
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 500$$$). The description of test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$3 \leq n \leq 100$$$, $$$0 \leq k \leq n$$$) — the length of the string $$$s$$$ and the number of characters B Milica wants to appear in $$$s$$$ in the end.
The second line of each test case contains the string $$$s$$$ of length $$$n$$$, consisting only of characters A and B.
For each test case, in the first line output a single integer $$$m$$$ — the minimum number of operations Milica should perform.
In the $$$j$$$-th of the next $$$m$$$ lines output an integer $$$i$$$ ($$$1 \le i \le n$$$) and a character $$$c$$$ ($$$c$$$ is 'A' or 'B') — the parameters of the $$$j$$$-th operation as described in the statement.
If there are multiple solutions with the minimum possible number of operations, output any of them.
5 5 2 AAABB 5 3 AABAB 5 0 BBBBB 3 0 BAA 10 3 BBBABBBBAB
0 1 1 B 1 5 A 1 2 A 1 6 A
In the first test case, there are already $$$2$$$ characters B in $$$s$$$, so Milica does not have to perform any operations.
In the second test case, the only way to achieve $$$3$$$ characters B in $$$s$$$ in one operation is to replace the first character of $$$s$$$ by B on the first operation: AABAB $$$\rightarrow$$$ BABAB.
In the third test case, the only way to achieve $$$0$$$ characters B in $$$s$$$ in one operation is to replace the first $$$5$$$ characters of $$$s$$$ by A on the first operation: BBBBB $$$\rightarrow$$$ AAAAA.
In the fourth test case, one of the ways to achieve $$$0$$$ characters B in $$$s$$$ in one operation is to replace the first $$$2$$$ characters of $$$s$$$ by A on the first operation: BAA $$$\rightarrow$$$ AAA. Note that "1 A" and "3 A" are also correct one-operation solutions.
Milena has received an array of integers $$$a_1, a_2, \ldots, a_n$$$ of length $$$n$$$ from a secret admirer. She thinks that making it non-decreasing should help her identify the secret admirer.
She can use the following operation to make this array non-decreasing:
- Select an element $$$a_i$$$ of array $$$a$$$ and an integer $$$x$$$ such that $$$1 \le x \lt a_i$$$. Then, replace $$$a_i$$$ by two elements $$$x$$$ and $$$a_i - x$$$ in array $$$a$$$. New elements ($$$x$$$ and $$$a_i - x$$$) are placed in the array $$$a$$$ in this order instead of $$$a_i$$$.
More formally, let $$$a_1, a_2, \ldots, a_i, \ldots, a_k$$$ be an array $$$a$$$ before the operation. After the operation, it becomes equal to $$$a_1, a_2, \ldots, a_{i-1}, x, a_i - x, a_{i+1}, \ldots, a_k$$$. Note that the length of $$$a$$$ increases by $$$1$$$ on each operation.
Milena can perform this operation multiple times (possibly zero). She wants you to determine the minimum number of times she should perform this operation to make array $$$a$$$ non-decreasing.
An array $$$x_1, x_2, \ldots, x_k$$$ of length $$$k$$$ is called non-decreasing if $$$x_i \le x_{i+1}$$$ for all $$$1 \le i \lt k$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10\,000$$$). The description of test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$) — the length of the array $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\leq a_i\leq 10^9$$$) – the array $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each test case, output one integer — the minimum number of operations required to make the array non-decreasing.
It can be shown that it is always possible to make the array $$$a$$$ non-decreasing in the finite number of operations.
431 3 241 2 3 433 2 171 4 4 3 5 7 6
1 0 3 9
In the first test case, Milena can replace the second element of array $$$a$$$ by integers $$$1$$$ and $$$2$$$, so the array would become $$$[\, 1, \, \underline{1}, \, \underline{2}, \, 2 \,]$$$. Only $$$1$$$ operation is required.
In the second test case, the array $$$a$$$ is already non-decreasing, so the answer is $$$0$$$.
In the third test case, Milena can make array $$$a$$$ non-decreasing in $$$3$$$ operations as follows.
- Select $$$i=1$$$ and $$$x=2$$$ and replace $$$a_1$$$ by $$$2$$$ and $$$1$$$. The array $$$a$$$ becomes equal to $$$[\, \underline{2}, \, \underline{1}, \, 2, \, 1 \, ]$$$.
- Select $$$i=3$$$ and $$$x=1$$$ and replace $$$a_3$$$ by $$$1$$$ and $$$1$$$. The array $$$a$$$ becomes equal to $$$[\, 2, \, 1, \, \underline{1}, \, \underline{1}, \, 1 \,]$$$.
- Select $$$i=1$$$ and $$$x=1$$$ and replace $$$a_1$$$ by $$$2$$$ and $$$1$$$. The array $$$a$$$ becomes equal to $$$[\, \underline{1}, \, \underline{1}, \, 1, \, 1, \, 1, \, 1 \,]$$$.
It can be shown that it is impossible to make it non-decreasing in $$$2$$$ or less operations, so the answer is $$$3$$$.
Elena has a grid formed by $$$n$$$ horizontal lines and $$$m$$$ vertical lines. The horizontal lines are numbered by integers from $$$1$$$ to $$$n$$$ from top to bottom. The vertical lines are numbered by integers from $$$1$$$ to $$$m$$$ from left to right. For each $$$x$$$ and $$$y$$$ ($$$1 \leq x \leq n$$$, $$$1 \leq y \leq m$$$), the notation $$$(x, y)$$$ denotes the point at the intersection of the $$$x$$$-th horizontal line and $$$y$$$-th vertical line.
Two points $$$(x_1,y_1)$$$ and $$$(x_2,y_2)$$$ are adjacent if and only if $$$|x_1-x_2| + |y_1-y_2| = 1$$$.
The grid formed by $$$n=4$$$ horizontal lines and $$$m=5$$$ vertical lines. Elena calls a sequence of points $$$p_1, p_2, \ldots, p_g$$$ of length $$$g$$$ a walk if and only if all the following conditions hold:
- The first point $$$p_1$$$ in this sequence is $$$(1, 1)$$$.
- The last point $$$p_g$$$ in this sequence is $$$(n, m)$$$.
- For each $$$1 \le i \lt g$$$, the points $$$p_i$$$ and $$$p_{i+1}$$$ are adjacent.
Note that the walk may contain the same point more than once. In particular, it may contain point $$$(1, 1)$$$ or $$$(n, m)$$$ multiple times.
There are $$$n(m-1)+(n-1)m$$$ segments connecting the adjacent points in Elena's grid. Elena wants to color each of these segments in blue or red color so that there exists a walk $$$p_1, p_2, \ldots, p_{k+1}$$$ of length $$$k+1$$$ such that
- out of $$$k$$$ segments connecting two consecutive points in this walk, no two consecutive segments have the same color (in other words, for each $$$1 \le i \lt k$$$, the color of the segment between points $$$p_i$$$ and $$$p_{i+1}$$$ differs from the color of the segment between points $$$p_{i+1}$$$ and $$$p_{i+2}$$$).
Please find any such coloring or report that there is no such coloring.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 32$$$). The description of test cases follows.
The only line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$3 \leq n,m \leq 16$$$, $$$1 \leq k \leq 10^9$$$) — the dimensions of the grid and the number of segments in the walk Elena is looking for.
For each test case, output "NO" if it is not possible to color each of the $$$n(m-1)+(n-1)m$$$ segments in blue or red color, so that there exists a walk of length $$$k+1$$$ satisfying the condition from the statement.
Otherwise, output in the first line "YES", and then provide the required coloring.
In each of the first $$$n$$$ lines of coloring description, output $$$m-1$$$ space-separated characters. The $$$j$$$-th character in the $$$i$$$-th of these $$$n$$$ lines should denote the color of the segment between points $$$(i,j)$$$ and $$$(i,j+1)$$$. Here, use 'B' to denote the blue color and 'R' to denote the red color.
In each of the next $$$n-1$$$ lines of coloring description, output $$$m$$$ space-separated characters. The $$$j$$$-th character in the $$$i$$$-th of these $$$n-1$$$ lines should denote the color of the segment between points $$$(i,j)$$$ and $$$(i+1,j)$$$. Similarly, use 'B' to denote the blue color and 'R' to denote the red color.
You can output each letter in the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses, and both 'R' and 'r' are valid notation of red.
54 5 113 3 23 4 10000000003 3 125884 4 8
YES R R B B R R R R B B B R R R B B R B B R B R B B B B B B R R R NO NO YES R B B B B R B B R R B B YES B B R R B R B R R R R B B R R B B B B B B R R R
In the first test case, one of the correct answers is shown in the picture below. The color-alternating walk of length $$$12$$$ is highlighted.
In the second and the third test cases, it can be shown that there is no coloring satisfying the condition from the statement.
Kirill has two integer arrays $$$a_1,a_2,\ldots,a_n$$$ and $$$b_1,b_2,\ldots,b_n$$$ of length $$$n$$$. He defines the absolute beauty of the array $$$b$$$ as $$$$$$\sum_{i=1}^{n} |a_i - b_i|.$$$$$$ Here, $$$|x|$$$ denotes the absolute value of $$$x$$$.
Kirill can perform the following operation at most once:
- select two indices $$$i$$$ and $$$j$$$ ($$$1 \leq i \lt j \leq n$$$) and swap the values of $$$b_i$$$ and $$$b_j$$$.
Help him find the maximum possible absolute beauty of the array $$$b$$$ after performing at most one swap.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10\,000$$$). The description of test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$) — the length of the arrays $$$a$$$ and $$$b$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1\leq a_i\leq 10^9$$$) — the array $$$a$$$.
The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1\leq b_i\leq 10^9$$$) — the array $$$b$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each test case, output one integer — the maximum possible absolute beauty of the array $$$b$$$ after no more than one swap.
631 3 53 3 321 21 221 22 141 2 3 45 6 7 8101 8 2 5 3 5 3 1 1 32 9 2 4 8 2 3 5 3 1347326 6958 3586533587 35863 59474
4 2 2 16 31 419045
In the first test case, each of the possible swaps does not change the array $$$b$$$.
In the second test case, the absolute beauty of the array $$$b$$$ without performing the swap is $$$|1-1| + |2-2| = 0$$$. After swapping the first and the second element in the array $$$b$$$, the absolute beauty becomes $$$|1-2| + |2-1| = 2$$$. These are all the possible outcomes, hence the answer is $$$2$$$.
In the third test case, it is optimal for Kirill to not perform the swap. Similarly to the previous test case, the answer is $$$2$$$.
In the fourth test case, no matter what Kirill does, the absolute beauty of $$$b$$$ remains equal to $$$16$$$.
Sofia has a string $$$s$$$ of length $$$n$$$, consisting only of lowercase English letters. She can perform operations of the following types with this string.
- Select an index $$$1 \le i \le |s|$$$ and remove the character $$$s_i$$$ from the string.
- Select a pair of indices $$$(l, r)$$$ ($$$1 \le l \le r \le |s|$$$) and sort the substring $$$s_{l} s_{l+1} \ldots s_r$$$ in alphabetical order.
Sofia wants to obtain the string $$$t$$$ of length $$$m$$$ after performing zero or more operations on string $$$s$$$ as described above. Please determine whether it is possible or not.
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 10\,000$$$) — the number of test cases.
The first line of each test case contains two integers $$$n$$$, $$$m$$$ ($$$1\leq m \leq n \leq 2\cdot 10^5$$$) — the lengths of string $$$s$$$ and $$$t$$$, respectively.
The second line of each test case contains the string $$$s$$$ of length $$$n$$$, consisting only of lowercase English letters.
The third line of each test case contains the string $$$t$$$ of length $$$m$$$, consisting only of lowercase English letters.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each test case, output "YES" if Sofia can obtain the string $$$t$$$ from $$$s$$$ using the operations above. Otherwise, output "NO".
You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
85 5sofiaafios3 2cbabc5 1sofiae15 7anavolimilovanaaamanan26 4abcdefghijklmnopqrstuvwxyznope26 4zyxwvutsrqponmlkjihgfedcbanope7 3apricotcat3 3cbaacb
YES YES NO YES NO YES NO YES
In the first test case, Sofia can perform the following operation:
- operation of the second type with $$$l=1$$$ and $$$r=5$$$: string $$$s$$$ becomes $$$\mathtt{afios}$$$ after it.
In the second test case, Sofia can perform the following operations:
- operation of the second type with $$$l=1$$$ and $$$r=2$$$: string $$$s$$$ becomes $$$\mathtt{bca}$$$ after it;
- operation of the first type with $$$i=3$$$: string $$$s$$$ becomes $$$\mathtt{bc}$$$ after it.
In the third test case, it can be shown that it is impossible to obtain $$$t$$$ from $$$s$$$ using the provided operations.
Following a world tour, Vova got himself trapped inside an $$$n \times m$$$ matrix. Rows of this matrix are numbered by integers from $$$1$$$ to $$$n$$$ from top to bottom, and the columns are numbered by integers from $$$1$$$ to $$$m$$$ from left to right. The cell $$$(i, j)$$$ is the cell on the intersection of row $$$i$$$ and column $$$j$$$ for $$$1 \leq i \leq n$$$ and $$$1 \leq j \leq m$$$.
Some cells of this matrix are blocked by obstacles, while all other cells are empty. Vova occupies one of the empty cells. It is guaranteed that cells $$$(1, 1)$$$, $$$(1, m)$$$, $$$(n, 1)$$$, $$$(n, m)$$$ (that is, corners of the matrix) are blocked.
Vova can move from one empty cell to another empty cell if they share a side. Vova can escape the matrix from any empty cell on the boundary of the matrix; these cells are called exits.
Vova defines the type of the matrix based on the number of exits he can use to escape the matrix:
- The $$$1$$$-st type: matrices with no exits he can use to escape.
- The $$$2$$$-nd type: matrices with exactly one exit he can use to escape.
- The $$$3$$$-rd type: matrices with multiple (two or more) exits he can use to escape.
Before Vova starts moving, Misha can create more obstacles to block more cells. However, he cannot change the type of the matrix. What is the maximum number of cells Misha can block, so that the type of the matrix remains the same? Misha cannot block the cell Vova is currently standing on.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10\,000$$$). The description of test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$3 \leq n,m \leq 1000$$$) — the dimensions of the matrix.
The next $$$n$$$ lines contain the description of the matrix: the $$$i$$$-th ($$$1 \le i \le n$$$) of them contains a string of length $$$m$$$, consisting of characters '.', '#', and 'V'. The $$$j$$$-th character of the $$$i$$$-th line describes the cell $$$(i, j)$$$ of the matrix. The dot '.' denotes an empty cell, the sharp '#' denotes a blocked cell, and the letter 'V' denotes an empty cell where Vova initially is.
It is guaranteed that the corners of the matrix are blocked (the first and the last characters of the first and the last lines of the matrix description are '#'). It is guaranteed that the letter 'V' appears in the matrix description exactly once.
It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$1\,000\,000$$$.
For each test case, output a single integer — the maximum number of cells Misha may block.
84 4#..#..V.....#..#3 6#.#####....#####V#3 3####V####6 5#.####...####.##V..##.#####..#7 5######.V.##.#.##.#.##.#.##...##.#.#3 7#.....#.#####.#...V.#5 8####.####..V#..##...#..##...##.####.####5 5#...###.####V####.###...#
9 0 0 3 4 10 12 5
In the first test case, the matrix is of the $$$3$$$-rd type. Misha can create obstacles in all empty cells except the cells $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$. There are $$$9$$$ such cells, and adding such obstacles does not change the type of the matrix.
In the second test case, the matrix is of the $$$3$$$-rd type. Blocking any cell changes the matrix type to the $$$2$$$-nd: one of the two exits will become unavailable for Vova. Thus, the answer is $$$0$$$.
In the third test case, the matrix is of the $$$1$$$-st type. No free cell exists (besides Vova's), so Misha cannot block any cell.
In the fourth test case, the matrix is of the $$$2$$$-nd type. Misha can create $$$3$$$ obstacles in cells $$$(5, 2)$$$, $$$(6, 3)$$$, $$$(6, 4)$$$ without changing the type of the matrix.
In the fifth test case, the matrix is of the $$$3$$$-rd type. Misha can create $$$4$$$ obstacles in cells $$$(2, 2)$$$, $$$(3, 2)$$$, $$$(4, 2)$$$, $$$(5, 2)$$$ or $$$4$$$ obstacles in cells $$$(2, 4)$$$, $$$(3, 4)$$$, $$$(4, 4)$$$, $$$(5, 4)$$$ without changing the type of the matrix.