There are $$$n$$$ players, numbered from $$$1$$$ to $$$n$$$. They are playing "Among Us" and exactly one of them is a hidden impostor. The remaining players need to do tasks around the spaceship and catch the impostor.
Some players were already seen doing a task so they can't be an impostor. You're given a list of values $$$x_i$$$, each denoting a player who did a task. The list might contain duplicates.
Players win if they kick the impostor out of the spaceship. But can they be sure who the impostor is? Print YES if the given list uniquely determines who the impostor is, and NO otherwise.
If the list contains all $$$n$$$ players, then apparently there's a mistake and the impostor faked a task. It's impossible to catch him or her, so you need to print NO. (If the list doesn't contain all players then we don't consider the possibility of faking a task.)
The first line contains two integers $$$n$$$ $$$(2 \leq n \leq 1000)$$$ and $$$k$$$ $$$(1 \leq k \leq 1000)$$$ — the number of players and the size of the list.
The second line contains $$$k$$$ space separated integers $$$x_1, x_2, \ldots, x_k$$$ ($$$1 \leq x_i \leq n$$$) — players who did a task and thus can't be the impostor. The values $$$x_i$$$ don't need to be distinct.
Output YES if players can be certain about who the impostor is, and NO otherwise.
3 3 1 2 2
YES
4 2 3 1
NO
3 5 2 1 1 3 3
NO
2 2 2 2
YES
In the first sample test, there are three players, numbered $$$1$$$, $$$2$$$ and $$$3$$$. Players $$$1$$$ and $$$2$$$ did at least one task each. Only player $$$3$$$ can be the impostor.
In the second test, players $$$1$$$ and $$$3$$$ did a task, which leaves players $$$2$$$ and $$$4$$$ as potential impostors. Players can't be certain who the impostor is so the answer is NO.
In the third test, all players were apparently seen doing a task so players can't catch the sneaky impostor.
In the fourth test, player $$$2$$$ did many tasks and player $$$1$$$ must be the impostor.
John the farmer has two rabbits, which like to keep eating bigger and bigger carrots. He likes setting up interesting games for them. One day he has set up the following game:
There are $$$n$$$ carrots in a row, carrot $$$i$$$ has size $$$a_i$$$. The two rabbits start the game at different endpoints. Each rabbit first eats the carrot at that endpoint and then keeps moving to every next carrot as long as such a next carrot is greater than or equal to the previous carrot.
So, the first rabbit first eats the first carrot, then second, third, and so on, as long as every next carrot is not-smaller than the previous one. Similarly, the other rabbit starts from the last carrot and then moves to the second last carrot, and so on.
If rabbits meet at some position, one of them eats the carrot there and they both stop. A carrot can't be eaten twice, and a rabbit can't skip a carrot. It doesn't matter which rabbit moves first at the beginning or at any moment.
John is wondering how many carrots can the rabbits eat at most. Can you help him find the answer to his question?
The first line contains an integer $$$n$$$ $$$(2 \leq n \leq 2 \cdot 10^5)$$$ denoting the number of carrots.
The second line contains $$$n$$$ space-separated integers $$$a_i$$$ $$$(1 \leq a_i \leq 10^9)$$$ denoting the size of each carrot.
Print one integer — the maximum possible number of eaten carrots.
4 1 2 3 4
4
5 1 3 2 3 1
4
9 1 1 2 1 9 2 1 1 2
4
7 1 3 5 4 4 3 2
7
5 2 2 2 2 2
5
In the first sample, it is easy to see that the rabbits can eat all carrots. A possible way the game could go is the following: the first rabbit eats carrot $$$1$$$ (starting carrot) –> the second rabbit eats carrot $$$4$$$ (starting carrot) –> the first rabbit eats carrot $$$2$$$ ($$$2$$$ > $$$1$$$) –> the first rabbit eats carrot $$$3$$$ ($$$3$$$ > $$$2$$$). Keep in mind that the second rabbit can not eat carrot $$$3$$$ because it is smaller than the current carrot that rabbit $$$2$$$ ate.
In the third sample, the rabbits can eat at most $$$4$$$ carrots. The possible actions of the game are the following: The first rabbit eats the first carrot, then he moves to the second one because its size is equal to the current carrot. Then he eats the third carrot because it is greater than the current carrot (which is now carrot $$$2$$$). He stops here because the fourth carrot is smaller than the current one. The second rabbit can only eat the starting carrot (because the next carrot is smaller than it) and the game ends because no rabbit can eat any more carrots.
Kevin has an array $$$a$$$ consisting of $$$n$$$ integers.
His best friend, George also wants to make his own array $$$b$$$ of the same length. But, in order to not make Kevin upset, Bob wants to create the smallest possible array distance with Kevin's array. The array distance is defined as the sum of absolute differences of corresponding elements:
$$$$$$\sum_{i=1}^{n} abs(a_i - b_i)$$$$$$
Unfortunately, George's array can't contain two different elements. For example, he can create one of arrays $$$[1,1,1,1]$$$, $$$[2]$$$, $$$[3,3]$$$ but he can not make the arrays $$$[1,2]$$$ or $$$[3,3,3,3,3,4]$$$.
Help George find the minimum possible distance of the arrays.
The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 2\cdot10^5)$$$ — the length of the arrays.
The second line contains $$$n$$$ space separated integers $$$a_i$$$ $$$(0 \leq a_i \leq 10^9)$$$.
Print the minimum possible distance of the arrays, if George creates the optimal array.
5 4 5 1 2 3
6
4 4 4 4 4
0
3 1 3 9
8
In the first test case the optimal strategy is to construct array $$$[3,3,3,3,3]$$$ so the total distance will be abs($$$3-4$$$) + abs($$$3-5$$$) + abs($$$3-1$$$) + abs($$$3-2$$$) + abs($$$3-3$$$) = $$$6$$$.
In the second test case George can choose to construct $$$[4,4,4,4]$$$ so the distance will be 0.
Sanda's father has a number $$$a$$$.
One day her father wanted to obtain another number $$$s$$$ and asked Sanda for help.
But Sanda only knows one operation, she can rearrange the digits of a given number $$$a$$$ (she can't construct a number with leading zeroes).
Sanda now wants to know if she can write the desired number $$$s$$$ as the sum of the father's original number $$$a$$$ and a rearrangement of it (the rearrangement can be equal to the original number).
In other words, you have to check if there exists a number $$$b$$$ which is obtained by reordering the digits from the initial number $$$a$$$ such that $$$a + b = s$$$.
Help Sanda determine if she can be successful, print "YES" if she can do the job, else print "NO".
The first (and only) line contains positive integers $$$a$$$ and $$$s$$$ $$$(1 \leq a, s \leq 10^{15})$$$.
Print "YES" if she can do the job, else print "NO".
1000 1001
NO
123 255
YES
100 200
YES
In the first sample, it is impossible to find any permutation that fits the requirement.
In the second sample, a possible permutation of digits of the number $$$123$$$ is $$$132$$$ Adding them up together we obtain $$$255$$$ - the required sum, so there exists at least a solution
You are given a string s consisting only of lowercase Latin letters. s has length $$$n$$$.
You are also given a string t made of $$$2$$$ lowercase Latin letters.
Your task is to count the number of pairs (L, R) such that the substring starting from L and ending in R (that is, $$$s_ls_{l+1}s_{l+2}... s_r$$$) contains t.
Note that the answer may not fit in 32-bit integer data types.
The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 2\cdot10^5)$$$- the length of string $$$s$$$.
The second line contains the string s.
The third line contains the string t of length $$$2$$$.
The number of pairs (L, R) such that the substring starting from L and ending in R contains t.
4 dabc ab
4
8 hshshshs hs
25
6 yyujsa sa
5
5 fpmbe ai
0
For the first test: s $$$=$$$ "dabc" and t $$$=$$$ "ab". So, all the pairs(L, R) are: (0, 2), (1, 2), (1, 3), (0, 3) corresponding to the substrings: "dab", "ab", "abc", "dabc".
For the second test, please note that, for example, each of four substrings "hs" is counted separately towards the answer, because we count pairs $$$[L, R]$$$ rather than distinct substrings.
For the third test, there are $$$5$$$ possible pairs and they are:
Alice and Bob are playing a game on an $$$n\times n$$$ grid made of square cells. They play a game and each player wants to paint more cells in their color. Initially, all cells have no color.
In one move, Alice can choose a $$$2 \times 2$$$ empty square and paint all four cells red. None of those four cells can be colored before, and they all must be inside the grid. If there is no available $$$2 \times 2$$$ square, Alice must pass and Bob will keep making moves.
In Bob's move, he can paint one empty cell blue.
They move alternately, Alice goes first. The game stops when all cells are painted (so neither of them can make a move).
If they both play optimally, who will have more cells at the end? Print Alice if there will be strictly more red cells than blue cells; Bob for more blue cells; and Draw if there will be same number of blue and red cells.
You have $$$t$$$ test cases to answer.
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 1000)$$$, the number of test cases.
The next $$$t$$$ lines contain a single integer $$$n$$$ $$$(1\leq n \leq1000)$$$, the size of the matrix.
For each test case, print one line with the answer Alice, Bob or Draw accordingly.
3 3 1 4
Bob Bob Draw
This is a possible situation after two full turns for $$$n = 4$$$. Alice then can't make any more moves and Bob will cover all the remaining cells, resulting in a draw 8:8.
