Kars is tired and resentful of the narrow mindset of his village since they are content with staying where they are and are not trying to become the perfect life form. Being a top-notch inventor, Kars wishes to enhance his body and become the perfect life form. Unfortunately, $$$n$$$ of the villagers have become suspicious of his ideas. The $$$i$$$-th villager has a suspicion of $$$a_i$$$ on him. Individually each villager is scared of Kars, so they form into groups to be more powerful.
The power of the group of villagers from $$$l$$$ to $$$r$$$ be defined as $$$f(l,r)$$$ where
$$$$$$f(l,r) = |a_l - a_{l+1}| + |a_{l + 1} - a_{l + 2}| + \ldots + |a_{r-1} - a_r|.$$$$$$
Here $$$|x-y|$$$ is the absolute value of $$$x-y$$$. A group with only one villager has a power of $$$0$$$.
Kars wants to break the villagers into exactly $$$k$$$ contiguous subgroups so that the sum of their power is minimized. Formally, he must find $$$k - 1$$$ positive integers $$$1 \le r_1 \lt r_2 \lt \ldots \lt r_{k - 1} \lt n$$$ such that $$$f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$$$ is minimised. Help Kars in finding the minimum value of $$$f(1, r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$$$.
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 100)$$$ — the number of test cases. The description of test cases follows.
The first line of each test case contains two integers $$$n,k$$$ $$$(1 \leq k \leq n \leq 100)$$$ — the number of villagers and the number of groups they must be split into.
The second line of each test case contains $$$n$$$ integers $$$a_1,a_2, \ldots, a_n$$$ $$$(1 \leq a_i \leq 500)$$$ — the suspicion of each of the villagers.
For each test case, output a single integer — the minimum possible value of sum of power of all the groups i. e. the minimum possible value of $$$f(1,r_1) + f(r_1 + 1, r_2) + \ldots + f(r_{k-1} + 1, n)$$$.
34 21 3 5 26 31 9 12 4 7 212 81 9 8 2 3 3 1 8 7 7 9 2
4 11 2
In the first test case, we will group the villagers with suspicion $$$(1,3,5,2)$$$ into $$$(1,3,5)$$$ and $$$(2)$$$. So, $$$f(1,3) + f(4,4) = (|1 - 3| + |3 - 5|) + 0 = 4 + 0 = 4$$$.
In the second test case, we will group the villagers with suspicion $$$(1,9,12,4,7,2)$$$ into $$$(1),(9,12),(4,7,2)$$$. So, $$$f(1,1) + f(2,3) + f(4,6) = 0 + 3 + 8 = 11$$$.
Jonathan is fighting against DIO's Vampire minions. There are $$$n$$$ of them with strengths $$$a_1, a_2, \dots, a_n$$$. $$$\def\and {{\,\texttt{&}\,}}$$$
Denote $$$(l, r)$$$ as the group consisting of the vampires with indices from $$$l$$$ to $$$r$$$. Jonathan realizes that the strength of any such group is in its weakest link, that is, the bitwise AND. More formally, the strength level of the group $$$(l, r)$$$ is defined as $$$$$$f(l,r) = a_l \and a_{l+1} \and a_{l+2} \and \ldots \and a_r.$$$$$$ Here, $$$\and$$$ denotes the bitwise AND operation.
Because Jonathan would like to defeat the vampire minions fast, he will divide the vampires into contiguous groups, such that each vampire is in exactly one group, and the sum of strengths of the groups is minimized. Among all ways to divide the vampires, he would like to find the way with the maximum number of groups.
Given the strengths of each of the $$$n$$$ vampires, find the maximum number of groups among all possible ways to divide the vampires with the smallest sum of strengths.
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^4)$$$ — the number of test cases. 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 number of vampires.
The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the individual strength of each vampire.
The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output a single integer — the maximum number of groups among all possible ways to divide the vampires with the smallest sum of strengths.
331 2 352 3 1 5 245 7 12 6
1 2 1
In the first test case, the optimal way is to take all the $$$n$$$ vampires as a group. So, $$$f(1,3) = 1 \and 2 \and 3 = 0$$$.
In the second test case, the optimal way is to make $$$2$$$ groups, $$$(2,3,1)$$$ and $$$(5,2)$$$. So, $$$f(1,3) + f(4,5) = (2 \and 3 \and 1) + (5 \and 2) = 0 + 0 = 0$$$.
DIO knows that the Stardust Crusaders have determined his location and will be coming to fight him. To foil their plans he decides to send out some Stand users to fight them. Initially, he summoned $$$n$$$ Stand users with him, the $$$i$$$-th one having a strength of $$$a_i$$$. Using his vampiric powers, he can do the following as many times as he wishes:
- Let the current number of Stand users be $$$m$$$.
- DIO chooses an index $$$i$$$ ($$$1 \le i \le m$$$).
- Then he summons a new Stand user, with index $$$m+1$$$ and strength given by: $$$$$$a_{m+1} = a_i \oplus a_{i+1} \oplus \ldots \oplus a_m,$$$$$$
where the operator $$$\oplus$$$ denotes the bitwise XOR operation.
- Now, the number of Stand users becomes $$$m+1$$$.
Unfortunately for DIO, by using Hermit Purple's divination powers, the Crusaders know that he is plotting this, and they also know the strengths of the original Stand users. Help the Crusaders find the maximum possible strength of a Stand user among all possible ways that DIO can summon.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10\,000$$$). 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 number of Stand users initially summoned.
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \lt 2^8$$$) – the strength of each Stand user.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, output a single integer, maximum strength of a Stand user among all possible ways that DIO can summon.
340 2 5 131 2 358 2 4 12 1
7 3 14
In the first test case, one of the ways to add new Stand users is as follows:
- Choose $$$i=n$$$. Now, $$$a$$$ becomes $$$[0,2,5,1,1]$$$.
- Choose $$$i=1$$$. Now, $$$a$$$ becomes $$$[0,2,5,1,1,7]$$$. $$$7$$$ is the maximum strength of a Stand user DIO can summon.
In the second test case, DIO does not need to add more Stand users because $$$3$$$ is the maximum strength of a Stand user DIO can summon.
Josuke is tired of his peaceful life in Morioh. Following in his nephew Jotaro's footsteps, he decides to study hard and become a professor of computer science. While looking up competitive programming problems online, he comes across the following one:
Let $$$s$$$ be a binary string of length $$$n$$$. An operation on $$$s$$$ is defined as choosing two distinct integers $$$i$$$ and $$$j$$$ ($$$1 \leq i \lt j \leq n$$$), and swapping the characters $$$s_i, s_j$$$.
Consider the $$$m$$$ strings $$$t_1, t_2, \ldots, t_m$$$, where $$$t_i$$$ is the substring $$$^\dagger$$$ of $$$s$$$ from $$$l_i$$$ to $$$r_i$$$. Define $$$t(s) = t_1+t_2+\ldots+t_m$$$ as the concatenation of the strings $$$t_i$$$ in that order.
There are $$$q$$$ updates to the string. In the $$$i$$$-th update $$$s_{x_i}$$$ gets flipped. That is if $$$s_{x_i}=1$$$, then $$$s_{x_i}$$$ becomes $$$0$$$ and vice versa. After each update, find the minimum number of operations one must perform on $$$s$$$ to make $$$t(s)$$$ lexicographically as large$$$^\ddagger$$$ as possible.
Note that no operation is actually performed. We are only interested in the number of operations.
Help Josuke in his dream by solving the problem for him.
$$$\dagger$$$ A string $$$a$$$ is a substring of a string $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by the deletion of several (possibly, zero or all) characters from the beginning and several (possibly, zero or all) characters from the end.
$$$\ddagger$$$ A string $$$a$$$ is lexicographically larger than a string $$$b$$$ of the same length if and only if the following holds:
- in the first position where $$$a$$$ and $$$b$$$ differ, the string $$$a$$$ has a $$$1$$$, and the string $$$b$$$ has a $$$0$$$.
The first line contains three integers $$$n$$$, $$$m$$$, $$$q$$$ ($$$1 \leq n,m,q \leq 2 \cdot 10^5$$$).
The next line contains a binary string $$$s$$$ of length $$$n$$$, consisting only of digits $$$0$$$ and $$$1$$$.
The $$$i$$$-th line of the next $$$m$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$).
The $$$i$$$-th line of the next $$$q$$$ lines contains a single integer $$$x_i$$$ ($$$1 \leq x_i \leq n$$$).
Print $$$q$$$ integers. The $$$i$$$-th integer is the minimum number of operations that need to be performed on $$$s$$$ to get the lexicographically largest possible string $$$t(s)$$$ in the $$$i$$$-th round.
2 2 4 01 1 2 1 2 1 1 2 2
0 1 0 1
8 6 10 10011010 5 6 2 3 6 8 5 7 5 8 6 8 3 5 6 2 5 2 5 8 4 1
2 3 2 2 1 2 2 2 2 2
In the first test case,
Originally, $$$t(s) = s(1,2) + s(1,2) = 0101$$$.
After the $$$1$$$-st query, $$$s$$$ becomes $$$11$$$ and consequently $$$t$$$ becomes $$$1111$$$. You don't need to perform any operation as $$$t(s)$$$ is already the lexicographically largest string possible.
After the $$$2$$$-nd query, $$$s$$$ becomes $$$01$$$ and consequently $$$t$$$ becomes $$$0101$$$. You need to perform $$$1$$$ operation by swapping $$$s_1$$$ and $$$s_2$$$. Consequently, $$$t(s)$$$ becomes $$$1010$$$ which is the lexicographically largest string you can achieve.
This is an interactive problem.
Made in Heaven is a rather curious Stand. Of course, it is (arguably) the strongest Stand in existence, but it is also an ardent puzzle enjoyer. For example, it gave Qtaro the following problem recently:
Made in Heaven has $$$n$$$ hidden integers $$$a_1, a_2, \dots, a_n$$$ ($$$3 \le n \le 5000$$$, $$$1 \le a_i \le 4$$$). Qtaro must determine all the $$$a_i$$$ by asking Made in Heaven some queries of the following form:
- In one query Qtaro is allowed to give Made in Heaven three distinct indexes $$$i$$$, $$$j$$$ and $$$k$$$ ($$$1 \leq i, j, k \leq n$$$).
- If $$$a_i, a_j, a_k$$$ form the sides of a non-degenerate triangle$$$^\dagger$$$, Made in Heaven will respond with the area of this triangle.
- Otherwise, Made in Heaven will respond with $$$0$$$.
By asking at most $$$5500$$$ such questions, Qtaro must either tell Made in Heaven all the values of the $$$a_i$$$, or report that it is not possible to uniquely determine them.
Unfortunately due to the universe reboot, Qtaro is not as smart as Jotaro. Please help Qtaro solve Made In Heaven's problem.
$$$^\dagger$$$ Three positive integers $$$a, b, c$$$ are said to form the sides of a non-degenerate triangle if and only if all of the following three inequalities hold:
- $$$a+b \gt c$$$,
- $$$b+c \gt a$$$,
- $$$c+a \gt b$$$.
The interaction begins with reading $$$n$$$ ($$$3 \le n \le 5000$$$), the number of hidden integers.
To ask a question corresponding to the triple $$$(i, j, k)$$$ ($$$1 \leq i \lt j \lt k \leq n$$$), output "? $$$i$$$ $$$j$$$ $$$k$$$" without quotes. Afterward, you should read a single integer $$$s$$$.
- If $$$s = 0$$$, then $$$a_i$$$, $$$a_j$$$, and $$$a_k$$$ are not the sides of a non-degenerate triangle.
- Otherwise, $$$s = 16 \Delta^2$$$, where $$$\Delta$$$ is the area of the triangle. The area is provided in this format for your convenience so that you need only take integer input.
If the numbers $$$a_i$$$ cannot be uniquely determined print "! $$$-1$$$" without quotes. On the other hand, if you have determined all the values of $$$a_i$$$ print "! $$$a_1$$$ $$$a_2$$$ $$$\dots$$$ $$$a_n$$$" on a single line.
The interactor is non-adaptive. The hidden array $$$a_1, a_2, \dots, a_n$$$ is fixed beforehand and is not changed during the interaction process.
After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:
- fflush(stdout) or cout.flush() in C++;
- System.out.flush() in Java;
- flush(output) in Pascal;
- stdout.flush() in Python;
- see the documentation for other languages.
Hacks
You can hack a solution with the following input format.
The first line contains a single integer $$$n$$$ ($$$3 \le n \le 5000$$$) — the number of hidden integers.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 4$$$) — the hidden array.
3 63
? 1 2 3 ! -1
6 0 0 0 63 15 135
? 1 2 3 ? 2 3 4 ? 4 5 6 ? 1 5 6 ? 3 5 6 ? 1 2 4 ! 3 2 1 4 2 2
15 3 3 3 3 3 0
? 1 2 3 ? 4 6 7 ? 8 9 10 ? 11 12 13 ? 13 14 15 ? 4 5 6 ! -1
15 3 15 0 3 3 3
? 1 2 3 ? 3 4 5 ? 4 5 6 ? 7 8 9 ? 10 11 12 ? 13 14 15 ! 1 1 1 2 2 4 1 1 1 1 1 1 1 1 1 1
10 3 48 3 48 63 0
? 1 3 5 ? 4 6 8 ? 1 5 9 ? 6 8 10 ? 4 2 6 ? 7 10 8 ! 1 3 1 2 1 2 4 2 1 2
In the first example, the interaction process happens as follows:
| Stdin | Stdout | Explanation |
| 3 | Read $$$n = 3$$$. There are $$$3$$$ hidden integers | |
| ? 1 2 3 | Ask for the area formed by $$$a_1$$$, $$$a_2$$$ and $$$a_3$$$ | |
| 63 | Received $$$16\Delta^2 = 63$$$. So the area $$$\Delta = \sqrt{\frac{63}{16}} \approx 1.984313$$$ | |
| ! -1 | Answer that there is no unique array satisfying the queries. |
From the area received, we can deduce that the numbers that forms the triangle are either ($$$4$$$, $$$4$$$, $$$1$$$) or ($$$3$$$, $$$2$$$, $$$2$$$) (in some order). As there are multiple arrays of numbers that satisfy the queries, a unique answer cannot be found.
In the second example, the interaction process happens as follows:
| Step | Stdin | Stdout | Explanation |
| 1 | 6 | Read $$$n = 6$$$. There are $$$6$$$ hidden integers | |
| 2 | ? 1 2 3 | Ask for the area formed by $$$a_1$$$, $$$a_2$$$ and $$$a_3$$$ | |
| 3 | 0 | Does not form a non-degenerate triangle | |
| 4 | ? 2 3 4 | Ask for the area formed by $$$a_2$$$, $$$a_3$$$ and $$$a_4$$$ | |
| 5 | 0 | Does not form a non-degenerate triangle | |
| 6 | ? 4 5 6 | Ask for the area formed by $$$a_4$$$, $$$a_5$$$ and $$$a_6$$$ | |
| 7 | 0 | Does not form a non-degenerate triangle | |
| 8 | ? 1 5 6 | Ask for the area formed by $$$a_1$$$, $$$a_5$$$ and $$$a_6$$$ | |
| 9 | 63 | Received $$$16\Delta^2 = 63$$$. So the area $$$\Delta = \sqrt{\frac{63}{16}} \approx 1.984313$$$ | |
| 10 | ? 3 5 6 | Ask for the area formed by $$$a_3$$$, $$$a_5$$$ and $$$a_6$$$ | |
| 11 | 15 | Received $$$16\Delta^2 = 15$$$. So the area $$$\Delta = \sqrt{\frac{15}{16}} \approx 0.968245$$$ | |
| 12 | ? 1 2 4 | Ask for the area formed by $$$a_3$$$, $$$a_5$$$ and $$$a_6$$$ | |
| 13 | 135 | Received $$$16\Delta^2 = 135$$$. So the area $$$\Delta = \sqrt{\frac{135}{16}} \approx 2.904738$$$ | |
| 14 | ! 3 2 1 4 2 2 | A unique answer is found, which is $$$a = [3, 2, 1, 4, 2, 2]$$$. |
From steps $$$10$$$ and $$$11$$$, we can deduce that the the multiset $$$\left\{a_3, a_5, a_6\right\}$$$ must be $$$\left\{2, 2, 1\right\}$$$.
From steps $$$8$$$ and $$$9$$$, the multiset $$$\left\{a_1, a_5, a_6\right\}$$$ must be either $$$\left\{4, 4, 1\right\}$$$ or $$$\left\{3, 2, 2\right\}$$$.
As $$$\left\{a_3, a_5, a_6\right\}$$$ and $$$\left\{a_1, a_5, a_6\right\}$$$ share $$$a_5$$$ and $$$a_6$$$, we conclude that $$$a_5 = a_6 = 2$$$, as well as $$$a_1 = 3$$$, $$$a_3 = 1$$$.
From steps $$$6$$$ and $$$7$$$, we know that $$$a_5 = a_6 = 2$$$, and $$$a_4$$$, $$$a_5$$$ and $$$a_6$$$ cannot form a non-degenerate triangle, hence $$$a_4 = 4$$$.
With all the known information, only $$$a_2 = 2$$$ satisfies the queries made in steps $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$12$$$ and $$$13$$$.
In the third example, one array that satisfies the queries is $$$[1, 1, 1, 1, 3, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]$$$.
While tracking Diavolo's origins, Giorno receives a secret code from Polnareff. The code can be represented as an infinite sequence of positive integers: $$$a_1, a_2, \dots $$$. Giorno immediately sees the pattern behind the code. The first $$$n$$$ numbers $$$a_1, a_2, \dots, a_n$$$ are given. For $$$i \gt n$$$ the value of $$$a_i$$$ is $$$(a_{i-n}\ |\ a_{i-n+1})$$$, where $$$|$$$ denotes the bitwise OR operator.
Pieces of information about Diavolo are hidden in $$$q$$$ questions. Each question has a positive integer $$$v$$$ associated with it and its answer is the smallest index $$$i$$$ such that $$$a_i \gt v$$$. If no such $$$i$$$ exists, the answer is $$$-1$$$. Help Giorno in answering the questions!
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10\,000$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$ , $$$1 \leq q \leq 2 \cdot 10^5$$$).
The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the parts of the code which define the pattern.
The $$$i$$$-th line of the next $$$q$$$ lines contain a single integer $$$v_i$$$ ($$$0 \leq v_i \leq 10^9$$$) — the question Giorno asks you.
The sum of $$$n$$$ and $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
Print $$$q$$$ numbers. The $$$i$$$-th number is the answer to the $$$i$$$-th question asked by Giorno.
32 32 11234 50 2 1 3012345 51 2 3 4 572604
1 3 -1 2 2 4 -1 -1 -1 3 8 1 5
In the first test case, $$$a = [2,1,3,3,\ldots]$$$.
- For the first question, $$$a_1=2$$$ is the element with the smallest index greater than $$$1$$$.
- For the second question, $$$a_3=3$$$ is the element with the smallest index greater than $$$2$$$.
- For the third question, there is no index $$$i$$$ such that $$$a_i \gt 3$$$.