Baker Beaver has prepared a long fruit tart. This tart is decorated with a sequence of $$$2N+1$$$ toppings: $$$N$$$ pieces of Indigo berries, $$$N$$$ pieces of Tangerine slices, and exactly one Marzipan star. Baker Beaver will be happy if the toppings are arranged in the form $$$\texttt{M} \underbrace{\texttt{ITIT}\dots\texttt{IT}}_{N\text{ times}}$$$. That is, the first topping should be $$$\texttt{M}$$$, and then $$$\texttt{I}$$$ and $$$\texttt{T}$$$ should alternate, beginning with $$$\texttt{I}$$$.
However, in the morning rush, the toppings were placed in a scrambled order, represented by a string $$$s$$$ of length $$$2N+1$$$ consisting of the characters $$$\texttt{M}$$$, $$$\texttt{I}$$$, and $$$\texttt{T}$$$. To fix the tart without ruining the crust, you may perform the following operation any number of times (possibly zero):
- Choose an index $$$i$$$ ($$$1 \le i \lt |s|$$$), split the string into two parts $$$s[1 \dots i]$$$ and $$$s[i+1 \dots |s|]$$$, and then swap the two parts to obtain the new string $$$s[i+1 \dots |s|] + s[1 \dots i]$$$.
Each test contains multiple test cases. The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$).
The second line of each test case contains a string $$$s$$$ of length $$$2N+1$$$, consisting of $$$N$$$ occurrences of $$$\texttt{I}$$$, $$$N$$$ occurrences of $$$\texttt{T}$$$, and exactly one occurrence of $$$\texttt{M}$$$.
The sum of $$$N$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print a single integer — the minimum number of operations required to make Baker Beaver happy.
If it is impossible, print $$$-1$$$ instead.
32MITIT2TITMI2MTIIT
01-1
For the first test case, the order $$$\texttt{MITIT}$$$ will already make Baker Beaver happy, so the answer is $$$0$$$.
For the second test case, you can split the string into $$$\texttt{TITIT}$$$ and $$$\texttt{MI}$$$, then swap the two parts to obtain $$$\texttt{MITITIT}$$$. Thus, the answer is $$$1$$$.
For the third test case, it can be shown that no sequence of operations can produce $$$\texttt{MITIT}$$$, so the answer is $$$-1$$$.
Busy Beaver has filled a pit with $$$N$$$ labeled oranges. The $$$i$$$-th orange is labeled $$$a_i$$$.
Busy Beaver is playing a game with these oranges. They start with a score of $$$0$$$. Then, until there is only one orange left, Busy Beaver will select two oranges $$$i$$$ and $$$j$$$, gain $$$|a_i - a_j|$$$ points, discard one of these oranges, and return the other to the pit.
Find the maximum number of points Busy Beaver can score.
Each test contains multiple test cases. The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $$$N$$$ ($$$1 \le N \le 2\cdot 10^5$$$).
The second line of each test case contains $$$N$$$ integers $$$a_1, \dots, a_N$$$ ($$$1\le a_i\le 10^9$$$).
The sum of $$$N$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print the maximum number of points Busy Beaver can score.
331 6 31451 500000000 500000000 500000000 1000000000
802499999999
For the first test case, Busy Beaver should first select oranges $$$2$$$ and $$$3$$$, obtain $$$|6-3|=3$$$ points, then discard orange $$$3$$$. Then, after selecting oranges $$$1$$$ and $$$2$$$, Busy Beaver obtains $$$|1-6|=5$$$ additional points, ending with $$$8$$$ points total. This is the maximum number of points Busy Beaver can score.
Busy Beaver and Sneaky Snake visit a carrot shop. There are $$$N$$$ carrots for sale, arranged in a row from left to right. The carrots are numbered $$$1, 2, \dots, N$$$ from left to right, and the $$$i$$$-th carrot has a flavor index $$$a_i$$$.
They want to eat carrots to maximize their total satisfaction. They take turns eating carrots, with Busy Beaver going first.
- On Busy Beaver's turn, he eats one of the two leftmost remaining carrots.
- On Sneaky Snake's turn, she eats one of the two rightmost remaining carrots.
- If only one carrot remains, the player whose turn it is must eat it.
When a player eats a carrot, they gain satisfaction equal to that carrot's flavor index. The game ends when all carrots have been eaten.
Both players play optimally to maximize their own total satisfaction. Before they start, Busy Beaver wants to know the final total satisfactions of Busy Beaver and Sneaky Snake.
Furthermore, the shop owner frequently changes the flavor index of a carrot. There are $$$Q$$$ modifications; in each modification, the flavor index of one carrot is changed. After each modification, compute the final total satisfactions of both players. Note that the modifications are applied cumulatively.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.
The first line of each test case contains two integers $$$N$$$ and $$$Q$$$ ($$$4 \le N \le 2 \cdot 10^5$$$, $$$0 \le Q \le 2 \cdot 10^5$$$).
The second line of each test case contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$, where $$$a_i$$$ is the initial flavor index of the $$$i$$$-th carrot ($$$1 \le a_i \le 10^9$$$).
Each of the next $$$Q$$$ lines contains two integers $$$x_i$$$ and $$$v_i$$$, meaning that in the $$$i$$$-th modification, the flavor index of the $$$x_i$$$-th carrot is changed to $$$v_i$$$ ($$$1 \le x_i \le N$$$, $$$1 \le v_i \le 10^9$$$).
The sum of $$$N$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.
The sum of $$$Q$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output $$$Q+1$$$ lines.
On the first line, output the final total satisfactions of Busy Beaver and Sneaky Snake respectively for the initial flavor indices.
On the next $$$Q$$$ lines, in the $$$i$$$-th line, output the final total satisfactions after applying the first $$$i$$$ modifications.
There are three subtasks for this problem.
- ($$$10$$$ points): $$$N = 4$$$.
- ($$$30$$$ points): $$$Q = 0$$$.
- ($$$60$$$ points): No additional constraints.
44 03 5 1 64 62 7 4 12 51 63 92 24 113 19 04 2 3 7 5 1 6 9 88 54 3 6 5 10 1 2 72 85 46 93 32 15
8 79 57 511 511 108 1015 138 1220 2518 2023 2023 1423 2220 2227 22
In the first test case, the initial flavor indices are $$$A = [3, 5, 1, 6]$$$. The game will proceed as follows.
- Busy Beaver can take either the first or the second carrot. He takes the second carrot and gains $$$5$$$ satisfaction.
- Sneaky Snake can take either the third or the fourth carrot. She takes the fourth carrot and gains $$$6$$$ satisfaction.
- Busy Beaver can take either the first or the third carrot. He takes the first carrot and gains $$$3$$$ satisfaction.
- Sneaky Snake can only take the third carrot. She gains $$$1$$$ satisfaction.
At the end of the game, Busy Beaver has total satisfaction $$$8$$$, and Sneaky Snake has total satisfaction $$$7$$$.
Busy Beaver has an array of $$$N$$$ integers $$$a_1,a_2,\dots,a_N$$$ with $$$1 \le a_i \lt 2^K$$$. As a coder, he loves writing numbers in binary!
Define the roundness of an array of positive integers as the total number of trailing $$$0$$$'s in the binary representations of all its elements. For example, the array $$$[2,3,6,8,10]$$$ is written in binary as $$$[1\underline{\color{red}0},11,11\underline{\color{red}0},1\underline{\color{red}0}\underline{\color{red}0}\underline{\color{red}0},101\underline{\color{red}0}]$$$, so its roundness is $$$1+0+1+3+1=6$$$.
Busy Beaver may choose an integer $$$x$$$ such that $$$0 \le x \lt 2^K$$$ and $$$x \neq a_i$$$ for all $$$i$$$, and then replace every element by $$$a_i \oplus x$$$, where $$$\oplus$$$ is bitwise XOR. For the current array, find the maximum possible roundness after this operation.
Then, $$$Q$$$ updates will follow. Each query updates $$$a_i \leftarrow v$$$ for some $$$1 \le i \le N$$$ and $$$1 \le v \lt 2^K$$$. Note that updates are persistent, meaning that each update modifies the array, and subsequent updates should be applied to the current state.
Output the maximum roundness for the initial array, and again after each update.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.
The first line of each test case contains three space-separated integers $$$N$$$, $$$Q$$$, and $$$K$$$ ($$$1 \leq N \leq 2\cdot 10^5$$$, $$$0\leq Q\leq 2\cdot 10^5$$$, $$$1\leq K\leq 60$$$).
The second line of each test case contains $$$N$$$ space-separated integers $$$a_1, \dots, a_N$$$ ($$$1\leq a_i \lt 2^K$$$) — the members of the array $$$a$$$.
The next $$$Q$$$ lines each contain two integers $$$i$$$ and $$$v$$$ ($$$1\le i \le N$$$, $$$1 \le v \lt 2^K$$$), describing an update.
The sum of $$$N$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.
The sum of $$$Q$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output $$$Q+1$$$ lines.
The first line should contain a single integer — the answer before any updates.
The $$$i$$$-th of the next $$$Q$$$ lines should contain the answer after the $$$i$$$-th update.
There are three subtasks for this problem. Let $$$\sum N$$$ denote the sum of $$$N$$$ across all test cases and let $$$\sum Q$$$ denote the sum of $$$Q$$$ across all test cases.
- ($$$20$$$ points): $$$\sum N, \sum Q\leq 1000, K\leq 25$$$. In addition, it is guaranteed that $$$K \gt 1$$$, $$$a_i \lt 2^{K-1}$$$ for all $$$i$$$, and $$$v \lt 2^{K-1}$$$ in all updates.
- ($$$30$$$ points): $$$\sum N, \sum Q\leq 1000, K\leq 25$$$.
- ($$$50$$$ points): No additional constraints.
25 0 31 1 2 3 44 4 31 3 5 72 41 43 44 4
504468
For the first test case, the optimal value of $$$x$$$ is $$$x=5$$$, which gives $$$a \oplus 5=[4,4,7,6,1]$$$. The roundness is $$$5$$$.
In the second test case, before the first update, since $$$x \neq a_i$$$ for all $$$i$$$, $$$x$$$ must be even, implying that all of $$$a \oplus x$$$ are odd, so the answer is $$$0$$$. After the first update, the array becomes $$$a=[1,4,5,7]$$$. Here, $$$x=3$$$ provides the best result with $$$a\oplus 3=[2,7,6,4]$$$, with roundness $$$4$$$.
Calico Bear is convinced that no one can surpass his high score in Snake. Busy Beaver, thinking otherwise, would like to write an algorithm to prove him wrong.
Snake is played on an infinite 2D grid. A snake is a sequence of distinct cells forming a path from a head to a tail, where each consecutive pair of cells shares an edge. The length of the snake is the number of cells it contains.
The game begins at time $$$0$$$ with a single snake of length $$$1$$$, located at $$$(0, 0)$$$, and a single apple at some other location.
Busy Beaver will make a series of $$$N$$$ inputs in $$$\{\texttt{L}, \texttt{R}, \texttt{D}, \texttt{U}\}$$$ (left, right, down, up) to control the snake. Each input updates the snake as follows. First, the head moves one cell in the specified direction. Every other cell of the snake then shifts to the cell previously occupied by the preceding cell, leaving the tail unoccupied. If the head moves onto a cell containing an apple, the apple is eaten, and the snake grows a cell where the tail was before. A new apple then spawns on a cell not occupied by the snake.
An input is only valid if, after the update, no two cells of the snake coincide. It is guaranteed that no input opposes the previous one.
Let the score of the game be $$$\sum_{t=0}^N L_t$$$, where $$$L_t$$$ is the length of the snake at time $$$t$$$ (after $$$t$$$ inputs). Given the series of $$$N$$$ inputs, find the maximum possible score over all possible apple placements such that all inputs are valid.
The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 100$$$) — the number of test cases.
The first line of each test case contains a single integer $$$N$$$ ($$$1 \leq N \leq 5\cdot 10^3$$$).
The following line contains a string $$$s$$$ of $$$N$$$ characters ($$$s_i \in \{\texttt{L}, \texttt{R}, \texttt{D}, \texttt{U}\}$$$), where $$$s_i$$$ represents the $$$i$$$-th input that Busy Beaver makes. No input opposes the previous one.
The sum of $$$N$$$ across all test cases does not exceed $$$5\cdot 10^3$$$.
For each test case, output an integer answer on a new line.
There are two subtasks for this problem.
- ($$$60$$$ points): The sum of $$$N$$$ over all test cases does not exceed $$$500$$$.
- ($$$40$$$ points): No additional constraints.
33RRR5RDLUR6DDLURU
101822
The example consists of three test cases.
In the first test case, the snake moves $$$3$$$ times. The snake is able to eat $$$3$$$ apples without colliding with itself. The score is $$$L_0+L_1+L_2+L_3=1+2+3+4=10$$$.
 |  |  |  |
In the second test case, the snake moves $$$5$$$ times. The snake cannot get longer than $$$4$$$ since it only occupies $$$4$$$ cells. The score is $$$L_0+L_1+L_2+L_3+L_4+L_5=1+2+3+4+4+4=18$$$.
In the third test case, the snake moves $$$6$$$ times. The snake cannot get longer than $$$4$$$ since it has a loop of $$$4$$$ cells. After the loop, the snake cannot grow again because the apple should be spawned at time $$$3$$$, and at that time, the final cell is occupied by the tail of the snake. The score is $$$L_0+L_1+L_2+L_3+L_4+L_5+L_6=1+2+3+4+4+4+4=22$$$.
 |  |  |  |
 |  |  |