You're given a sequence $$$a$$$ containing $$$n$$$ positive integers.
In one operation, you can split an element into two adjacent positive elements. The other parts of the sequence remain unchanged.
For example: $$$a=[3,2,1]$$$, if you split $$$a_1=3$$$ into $$$1$$$ and $$$2$$$, you'll get $$$a=[1,2,2,1]$$$.
Find the minimum nunber of operations to turn $$$a$$$ into a palindrome sequence. It can be proven that you can always do it.
A palindrome sequence is a sequence that reads the same backwards as forwards.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.
The first line of each test case contains an integer $$$n$$$ ($$$2\le n \le 3 \cdot 10^{5}$$$).
The second line contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1 \le a_i \le 10^9$$$).
The sum of $$$n$$$ over all test cases will not exceed $$$3 \cdot 10^{5}$$$.
For each test case, output a single integer — the minimum number of operations to turn $$$a$$$ into a palindrome sequence.
433 2 121 166 5 4 3 2 188 7 7 1 9 4 2 2
1 0 3 5
In the first test case, we use the following scheme: $$$[\underline{3},2,1]\xrightarrow{}[1,2,2,1]$$$.
In the second test case, we don't need to do anything.
In the third test case, we use the following scheme:$$$[\underline{6},5,4,3,2,1]\xrightarrow{}[1,\underline{5},5,4,3,2,1] \xrightarrow{}[1,2,3,\underline{5},4,3,2,1] \xrightarrow{}[1,2,3,4,1,4,3,2,1]$$$.
There is a bus and $$$n$$$ passengers sitting in it, the bus is stuck in snow and they need to push it out.
Each passenger has mass $$$m_i$$$ and force $$$f_i$$$. The mass of an empty bus is equal to $$$w$$$.
Some passengers should leave the bus and start pushing it, while the rest will remain inside. The bus will be able to be moved only if the total force of the pushers is greater or equal to the total mass of the bus with remaining passengers.
Since it is pretty cold outside, it is necessary to minimize the number of people who need to get out and push the bus.
Output the minimal number of pushers needed to get the bus out of snow. If it is impossible, output $$$-1$$$.
The first line of the input 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 two integers $$$n$$$ and $$$w$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$1 \le w \le 10^9$$$).
The second line contains $$$n$$$ integers $$$m_1, m_2, m_3, \dots, m_n$$$ ($$$1 \le m_i \le 10^9$$$).
The third line contains $$$n$$$ integers $$$f_1, f_2, f_3, \dots, f_n$$$ ($$$1 \le f_i \le 10^9$$$).
The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output a single integer — the minimal number of pushers needed to get the bus out of snow. If it is impossible, output $$$-1$$$.
43 41 1 16 6 63 41 1 13 3 31 1000100106 107 5 1 4 2 83 1 2 7 5 9
1 2 -1 3
You are given $$$20$$$ decimal strings (a decimal string is a string consisting of characters 0 to 9) each of length $$$k$$$ ($$$k$$$ is a multiple of $$$10$$$).
You have to generate a decimal string of length $$$19k/10$$$ such that at least $$$2$$$ of the given strings are present as subsequences (not necessary contiguous) of the generated string and print it.
If it is impossible to find such a string, print -1.
In the first line of input, there is an integer $$$k$$$ $$$( 1 \le k \le 10^5, k=0 \mod 10)$$$ indicating the length of each decimal string.
Then there will be $$$20$$$ lines, each line contains a decimal string of length $$$k$$$.
If it's not possible to generate such string print -1. Otherwise print the generated string.
1077000166732682666656912557360365043179498140497834429027900951735109518685927577100429078840342474499343949853013049652234838927938172454939472014008517880325170749973594312612530251566485529045810227
6508143179490497834
In the first test case, you'll find the $$$4$$$th string 6508143179490497834 and $$$5$$$th string 6508143179490497834 in the output.
Rudraksh is a school kid. But he is sleepy boy. He often gets late for his school. Also, he is famous among his friends for his knowledge and love towards prime numbers.
One day he woke up and saw that he was extremely late for his school, so he started mapping his school and home on the city's map. He marked his home to be at $$$(0,0)$$$ and school to be at $$$(x,y)$$$ where $$$x$$$ and $$$y$$$ both are positive integers. He will reach his school by making some intermediate stops in the path.
Now as he loves primes too much he will choose the path in such a way that for each two adjacent stops the Manhattan distance between them is a prime number. More formally, he can start from $$$(a,b)$$$ and stop at $$$(c,d)$$$ if and only if $$$|a-c|+|b-d|$$$ is a prime number. He wants to reach the school by making the minimum number of stops in his path. Find the minimum number of stops Rudraksh needs to take to reach school. Also find the stops he will take in his path.
Note that Rudraksh should not step out of his city boundaries i.e. at any time his x-coordinate should be between $$$0$$$ and $$$x$$$ (inclusive), and y-coordinate should be between $$$0$$$ and $$$y$$$ (inclusive).
The first line of the input contains an integer $$$t$$$ $$$(1 \leq t \leq 10^5)$$$ — the number of test cases.
For each test case, you will be provided with two positive integers $$$x$$$ $$$(1 \leq x \leq 10^7)$$$ and $$$y$$$ $$$(1 \leq y \leq 10^7)$$$ — the coordinates of the school mapped by Rudraksh.
It is guaranteed that sum of $$$(x+y)$$$ over all testcases will be less than or equal to $$$10^7$$$.
For each test case:
First print the integer $$$n$$$, which is the minimum number of stops Rudraksh took to reach school.
Now print $$$n$$$ lines each containing two non-negative integers $$$x_i$$$ $$$(0 \leq x_i \leq x)$$$ and $$$y_i$$$ $$$(0 \leq y_i \leq y)$$$ — the coordinates of the $$$i_{th}$$$ stop made by Rudraksh.
For each $$$i$$$ $$$(1 \le i \lt n)$$$, $$$|x_{i+1}-x_i| + |y_{i+1}-y_i|$$$ should be a prime number. Also, $$$x_1+y_1$$$ should be a prime number (as starting from origin).
The last stop should be his school coordinates. You don't need to print $$$(0,0)$$$.
If there are multiple answers, print any of them.
31 12 105 5
1 1 1 2 0 5 2 10 2 3 0 5 5
Given an array $$$a$$$ which is a permutation of length $$$n$$$ and a positive integer $$$k$$$ $$$(k \le 10)$$$.
For each index $$$i$$$ of the array, find the length of the longest continuous subarray (length of the subarray should be atleast $$$k$$$) containing that index, such that $$$a_i$$$ is greater than or equal to $$$k^{th}$$$ maximum element in the subarray. In other words, $$$a_i$$$ should come at $$$x^{th}$$$ position $$$(x\le k)$$$ when that subarray is sorted in descending order.
The first line contains an integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ - the number of test cases.
The descriptions of the test cases follow.
The first line of each test case contains two integers $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$ and $$$k$$$ $$$(1 \le k \le \min(n,10) )$$$ - the size of the array and the value of $$$k$$$.
The second line contains $$$n$$$ space-separated positive integers $$$a_1, a_2, a_3, ..., a_n$$$ $$$(1 \le a_i \le n)$$$ - the elements of $$$a$$$.
The sum of $$$n$$$ over all test cases will not exceed $$$2 \cdot 10^5$$$.
For every test case, print $$$n$$$ space-separated positive integers where $$$i^{th}$$$ number represents the length of the longest subarray for the $$$i^{th}$$$ index of the array as described in the statement.
52 21 24 42 1 4 34 41 2 4 33 23 1 27 41 5 3 4 7 6 2
2 2 4 4 4 4 4 4 4 4 3 2 3 4 7 5 7 7 7 4
Permutation of length $$$n$$$ means permutation of first $$$n$$$ natural numbers $$$(1, 2, 3, .... , n-1, n)$$$.
Initially there is a value $$$y=0$$$, and an array $$$A$$$ of $$$N$$$ integers. You have to pick $$$K$$$ non-empty subsequences (not necessarily contiguous). Score of each subsequence is its $$$\rm{mex}$$$ (mex of a sequence is the minimum non-negative integer that doesn't exist in the sequence).
Pick any $$$K$$$ different non-empty subsequences and arrange their scores in any order, then add the scores with odd indices to $$$y$$$ and subtract the scores with even indices from $$$y$$$. More formally, let $$$S$$$ be the sequence of ordered scores, then $$$y=S_1-S_2+S_3-\dots-(-1)^K S_K$$$.
Find the minimum possible value of $$$y$$$.
Two subsequences are different if there is at least one index that doesn't exist in exactly one of the subsequences. (So there are $$$2^N-1$$$ non-empty subsequences.)
The first line of input contains an integer $$$T$$$ ($$$1 \le T \le 100000$$$) — number of test cases
Each test case contains 2 lines:
First line contains two integers $$$N$$$ ($$$1 \le N \le 100000$$$) and $$$K$$$($$$1 \le K \le \min(10^9,2^N - 1)$$$) — size of the array and number of subsequences you have to pick.
Second line contains $$$N$$$ integers of the array $$$A$$$. For each $$$i$$$, $$$0 \le A_i \le 10^9$$$.
It is guaranteed that the sum of $$$N$$$ over all test cases doesn't exceed $$$100000$$$.
For every test case, you have to output a single integer — the minimum possible value of $$$y$$$ you can obtain.
36 40 0 2 3 1 48 71 2 3 0 1 2 4 63 11 5 2
-10 -15 0
You are given a string $$$s$$$ of length $$$n$$$. You are performing the following operations $$$k$$$ times:
- choose a character $$$s_i$$$ ($$$1 \le i \le n$$$) and move it to the front of the string.
- choose a character $$$s_i$$$ ($$$1 \le i \le n$$$) and move it to the back of the string.
- choose a character $$$s_i$$$ ($$$1 \le i \le n$$$) and move it to the front of the string.
- and so on, depending on the parity of the number of the operation.
Find the lexicographically smallest string you can obtain.
The first line of the input 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 two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).
The second line contains the string $$$s$$$, consisting of $$$n$$$ lowercase English letters.
The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, output the lexicographically smallest string you can obtain.
47 3abacaba9 2theforces5 4edcba7 3pavlekn
aaaacbb cheforest abcde aeplknv
In the first test case, we can do the following operations:
- $$$abac\color{red}{a}ba$$$ $$$\rightarrow$$$ $$$\color{red}{a}abacba$$$
- $$$aa\color{red}{b}acba$$$ $$$\rightarrow$$$ $$$aaacba\color{red}{b}$$$
- $$$aaacb\color{red}{a}b$$$ $$$\rightarrow$$$ $$$\color{red}{a}aaacbb$$$
In the second test case, we can do the following operations:
- $$$thefor\color{red}{c}es$$$ $$$\rightarrow$$$ $$$\color{red}{c}thefores$$$
- $$$c\color{red}{t}hefores$$$ $$$\rightarrow$$$ $$$chefores\color{red}{t}$$$