Alice has $$$n$$$ sour candies, each with some sourness described by an integer. Because she does not like the sourness of her candies to vary too much, she is going to choose $$$k$$$ sour candies and eat them. Alice wants to choose candies to eat in order to minimize the largest (absolute) difference between two candies. If Alice optimally chooses which candies to eat, what is the smallest maximum difference between any two remaining candies?
The first line will contain integers $$$n$$$ and $$$k$$$, ($$$1 \leq k \lt n \leq 1000$$$). The second line will contain $$$n$$$ integers, describing the sourness of the i-th candy.
Output the minimal largest absolute difference between any two candies left. If there is 1 candy left, the answer is 0.
6 31 4 8 9 12 16
4
4 12 9 3 1
2
6 410 8 2 6 7 10
0
In the first test case, Alice should eat candies with sourness 1, 4, and 16. Then the maximum difference is (12-8) = 4. In the second test case, Alice should eat the candy with sourness 9. Then the maximum difference is (3-1) = 2. In the third test case, Alice should eat the candies with sourness 8, 2, 6, and 7. Then the maximum difference is (10-10) = 0.
Sage started getting bored of eating the same sour strips every day, so she decided to play a game with them. Using the sour strips, she plans to use the strips to draw the perimeters of two squares on the coordinate plane. Each side of these squares will be parallel to either the $$$x$$$ or $$$y$$$ axis. However, if the perimeters ever overlap, then she won't be able to lay the strips on top of each other to make the shapes! Even if the perimeters intersect at a vertex, it is impossible. Can you check her plan to confirm it is feasible?
The first line contains three integers $$$x_1, y_1, s_1$$$ ($$$0 \leq |x_1|, |y_1| \leq 10^3, 1 \leq s_1 \leq 10^3$$$) — the coordinates of the lower-left corner of the first square and its side length, respectively.
The second line contains three integers $$$x_1, y_1, s_1$$$ ($$$0 \leq |x_2|, |y_2| \leq 10^3, 1 \leq s_2 \leq 10^3$$$) — the coordinates of the lower-left corner of the second square and its side length, respectively.
Output "YES" (without the quotes) if the squares overlap, and print "NO" otherwise. You can output the answer in any case.
1 1 22 2 2
YES
0 0 12 2 2
NO
0 0 41 1 2
NO
0 0 11 1 1
YES
Anisha loves sour candy! Her favorite sour snack are sour straws
Anisha has come into possession of $$$n$$$ sour straws, but she is actually very picky about how she eats them. In particular, each of her sour straws has an associated length: the $$$i^\text{th}$$$ of her sour straws has a length of $$$l_i$$$ inches.
Anisha can choose to eat a subset of her sour straws if each of the sour straws in the subset has a length divisible by all shorter sour straws included in the subset. More formally, if her subset of sour straws is denoted as $$$S \subseteq \{1, 2, \dots, n\}$$$, then $$$\forall\ i, j \in S,\ l_i \leq l_j \implies l_i \mid l_j$$$ must hold (where $$$a \mid b$$$ means $$$b$$$ is divisible by $$$a$$$).
Despite her pickiness, Anisha wants to eat as many sour straws as possible. As such, she wants you to compute the largest subset of her sour straws that she can eat without violating her condition mentioned above.
The input will begin with a single line containing a single integer $$$n\ (1 \leq n \leq 10^3)$$$, denoting the number of sour straws Anisha has.
The next line will contain $$$n$$$ space-separated integers $$$l_1, l_2, \dots, l_n\ (1 \leq l_i \leq 2 \cdot 10^9)$$$, denoting the lengths of each of Anisha's sour straws, in inches.
The output should consist of a single line containing a single integer, the size of the largest possible subset of sour straws that Anisha can eat at once without violating her pickiness condition.
52 7 5 4 8
3
510 10 10 10 10
5
It's Halloween, and you are on a quest to collect candies! The candies are scattered at various points in a 2D plane. You start at the origin $$$(0, 0)$$$, and you can collect the candies by traveling in a straight line. You want to maximize the number of candies you can collect in a single trip, and the condition is that all the candies you collect must lie on the same straight line passing through the origin.
Given $$$n$$$ candies, each located at distinct coordinates $$$(x_i, y_i)$$$, your task is to determine the maximum number of candies you can collect by traveling in one straight line.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — the number of candies. The next $$$n$$$ lines each contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$-10^9 \leq x_i, y_i \leq 10^9$$$) — the coordinates of the $$$i$$$-th candy. It is guaranteed that no candy is at the origin.
Output a single integer, the maximum number of candies you can collect by traveling along a single straight line passing through the origin.
52 14 26 38 410 5
5
The candy store is running a special deal today! They have lined up $$$n$$$ candies in an array and are letting the first customer take home a contiguous subarray of the candies for free! Hearing this news, Suzuka and her friend Mizyu immediately raced to the candy store to take advantage. Suzuka, being the faster of the two, reaches the candy store first, and so she gets the deal.
To Suzuka, the $$$i$$$th candy has a tastiness of $$$a_i$$$. Since Suzuka finds some candies too sour to be enjoyable, $$$a_i$$$ can be negative. Obviously, the more tasty candies the better, so Suzuka wants to take a subarray that maximizes the sum of tastiness of candies in the subarray. However, as a consolation for her loss, Suzuka promises Mizyu the subarray she picks will include at least one piece of Mizyu's favorite type of candy, which she will share with Mizyu.
Suzuka wants to know, what is the greatest sum of tastiness of a subarray containing Mizyu's favorite candy that she can take?
The first line of input contains a single integer $$$n\ (1\leq n\leq2\cdot10^5)$$$ — the number of candies in the array.
The second line contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n\ (-10^9 \leq a_i\leq 10^9)$$$ — the tastiness of each candy.
The last line contains $$$n$$$ integers $$$b_1,b_2,\dots,b_n\ (b_i\in\{0,1\})$$$ — denoting which candies are of Mizyu's favorite type, where $$$b_i=1$$$ means the $$$i$$$th candy is Mizyu's favorite, and $$$b_i=0$$$ means it is not. It is guaranteed at least one of the candies will be Mizyu's favorite type.
Output a single integer, the greatest sum of tastiness of a subarray that contains at least one piece of Mizyu's favorite candy.
4-1 2 3 -41 1 0 0
5
510 -30 10 -100 500 1 0 1 0
-10
31000000000 1000000000 10000000001 1 1
3000000000
For the first test case, Suzuka can take the second and third candies corresponding to the subarray [2, 3] to obtain a total tastiness of 2+3=5.
For the second test case, Suzuka can take the first three candies corresponding to the subarray [10, -30, 10] to obtain a total tastiness of 10+(-30)+10=-10. Note she cannot take something like a subarray of just the last candy, because that does not contain Mizyu's favorite type of candy.
Marshall Mathers, a magician (note the intellectual use of alliteration), code name "Houdini", is tasked distributing sour candy to his fans. His stock of sour candy can be modeled as a bunch of containers, $$$n$$$ of them to be precise. Container $$$i$$$ ($$$1 \leq i \leq n$$$) contains $$$a_i$$$ units of sour candy. Marshall by magic generates links from one container to another, in such a way that any container can be reached from any other container by traversing a serious of links, and this path is unique for all pairs of nodes. Further, at most one edge exists between 2 containers and no container has a link to itself (this whole setup is a tree).
He now wants to distribute the candy among his fans - he does this (magically) removing some of the links he created, splitting the tree into smaller trees, and giving each fan a tree of containers of sour candy. His supervisor Dr. Dre for reasons unknown wishes that each fan gets an even number of units of sour candy in total. Further, none of the candy should be left.
Marshall wants to know, if he removes links optimally, at most how many fans can he distribute candy to, if at all possible to satisfy the conditions set by Dr. Dre.
The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 200,000$$$), representing the number of containers.
The second line of input contains $$$n$$$ space-separated integers $$$a_1, a_2, ... a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
The next $$$N-1$$$ lines contain to integers $$$1 \leq u \leq n$$$ and $$$1 \leq v \leq n$$$ representing a link between containers $$$u$$$ and $$$v$$$.
Output a single positive integer, representing the number of fans that Marshall can distribute sour candy to. Output $$$-1$$$ if it is impossible to satisfy Dr. Dre's conditions.
41 3 2 41 22 34 2
3
41 3 2 41 33 22 4
2
41 3 3 41 23 21 4
-1
In the first example, Houdini can remove the links 2-3 and 2-4 leaving the components (1,2), (3,) and (4,), each of which can be given to a fan.
In the second example, the link 2-4 can be removed, and this is the best we can do.
In the third example, there is no way to remove links such every tree has an even number of candies.
Julia is going treat or tricking down her street. She can go between any two adjacent houses where an adjacent house is defined as one to its left, right, or across the street. The first time Julia passes by a house, she must go up to the door and knock, and she will either get a trick or a treat. If she gets a trick, it makes her sad, so she loses happiness. If she gets a treat, she will gain some happiness since she got her favorite sour candies. She starts "above" the street on the leftmost end, and she does not need to visit every house before reaching her destination. What is the happiest Julia can be when she reaches the opposite corner (right end and opposite side) of the street?
The first line will contain one integer $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$) — the number of houses on each side of the street.
The second line will contain $$$n$$$ integers $$$a_i$$$ ($$$-10^3 \leq a_i \leq 10^3$$$) indicating the amount of happiness gained or lost at each house.
The third line will contain $$$n$$$ integers $$$b_i$$$ ($$$-10^3 \leq b_i \leq 10^3$$$) indicating the amount of happiness gained or lost at each house.
Specifically Julia can move from $$$a_i$$$ to $$$a_{i - 1}$$$, $$$a_{i + 1}$$$, or $$$b_i$$$, or from $$$b_i$$$ to $$$b_{i - 1}$$$, $$$b_{i + 1}$$$, $$$a_i$$$.
Output one integer indicating the maximum happiness Julia can end with. Specifically her path must start at $$$a_1$$$ and end at $$$b_n$$$.
35 2 73 -5 4
21
45 7 -3 -102 -8 -2 5
14
Sample 1 Explanation: We start at $$$a_1$$$ and get 5 happiness.
We go over to $$$b_1$$$ and get 3 more bringing our total to 8.
We can then go back to $$$a_1$$$, and cannot get any more happiness since we've already visited. But, we can go to $$$a_2$$$ from here and get 2 happiness, bringing our total to 10.
Next, we go to $$$a_3$$$ and get 7 more bringing our total to 17.
Finally, we go over to $$$b_3$$$ and get 4 more giving us a final happiness of 21.
Alice and Bob are playing a game. They have a game board with $$$r$$$ rows and $$$c$$$ columns. The squares of the grid are either colored white or black. They start with a piece of sour candy placed in the first row and first column, corresponding to the top-left corner of the grid. They take turns, starting with Alice, and each player must either move the piece down (increasing the column number), to the right (increasing the row number), or diagonally down and right. However, they can't move the piece into a black square or off the grid. If a player cannot make a move, they lose. If both player play optimally, can you determine who wins?
The first line contains two integer $$$r, c$$$ ($$$1 \leq r, c \leq 1000$$$) — the number of rows and number of columns in the grid, respectively.
The following $$$r$$$ lines contain a string $$$s_i$$$ of length $$$c$$$, where $$$s_{i, j}$$$ equals 'W' or 'B' — the color of the square in the $$$i$$$th row and $$$j$$$th column, where 'W' corresponds to white and 'B' corresponds to black.
It is guaranteed that the top-left corner of the grid is white.
Print "Alice" (without the quotes) if Alice wins under optimal play, and print "Bob" otherwise.
4 5WBWBWWWWWWBWBWBBWBWB
Alice
2 2WBBB
Bob
Rachel has $$$n$$$ bags of candy containing $$$1, 2, \ldots, n$$$ pieces of candy. However, since she tripped and fell down the stairs, her candy bags have now been randomly scattered across the floor. Being the organized person she is, Rachel decides to arrange the bags of candy in a line $$$a_1, a_2, \ldots, a_n$$$, such that the $$$i$$$-th bag of candy contains $$$a_i$$$ pieces of candy in it.
Rachel wants to answer the following query for each interval $$$[l, r]$$$: if she rearranges the candies bags with $$$a_l, a_{l + 1}, \dots, a_{r - 1}, a_r$$$ candies, can she have $$$l, l + 1, \ldots, r$$$ pieces of candy in each bag respectively for that section?
The first line will contain $$$n, q$$$ ($$$1\leq n, q\leq 2\cdot 10^5$$$) — the number of bags of candy Rachel has and the number of queries respectively. Then, for the next $$$q$$$ lines, each line will contain two integers, $$$l_j, r_j$$$ ($$$1\leq l_j\leq r_j\leq n$$$), which represent the interval $$$[l, r]$$$ that Alice wants to perform the query on.
It is guaranteed that the sum of $$$n + q$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.
For each query, respond either "YES" or "NO" (case insensitive, without the quotes) on a new line.
5 31 3 2 5 41 32 51 4
YES YES NO
For each query, we check if the subsequence of candies from bag $$$l$$$ to $$$r$$$ can be rearranged to match the increasing sequence $$$[l+1, r]$$$.
- Query 1: Candies in bags 1 to 3: $$$[1, 3, 2]$$$. This can be rearranged to: $$$[1, 2, 3]$$$, which matches the sequence $$$[1, 2, 3]$$$. Result: YES
- Query 2: Candies in bags 2 to 5: $$$[3, 2, 5, 4]$$$. This can be rearranged to: $$$[2, 3, 4, 5]$$$, which matches the sequence $$$[2, 3, 4, 5]$$$. Result: YES
- Query 3: Candies in bags 1 to 4: $$$[1, 3, 2, 5]$$$. This cannot be rearranged to match the sequence $$$[1, 2, 3, 4]$$$. Result: NO
Alice is creating a candy factory! Unfortunately, in order to minimize production cost she needs to make some complicated decisions.
Each piece of candy undergoes three steps in production. First, the shape of the candy is formed. Then, sourness is added. Finally, the candy is wrapped. Alice has $$$n$$$ machines, each of which is capable of all three tasks, but can only be configured to do one of the three tasks. Further, the $$$i$$$th machine uses $$$a_i$$$ energy to form the candy, $$$b_i$$$ energy to add sourness, and $$$c_i$$$ energy to wrap it. Alice did some research and found that she needs $$$x$$$ of her machines to be configured to form the shape, $$$y$$$ machines to add sourness, and $$$z$$$ machines to wrap the candy. The total energy consumed by her factory is equal to the sum of the energy consumed by each machine. Note that a machine may be configured to do nothing, in which case it will not use any energy.
Please help Alice by finding the minimum energy required for her to build her candy factory!
The first line of input will contain $$$n$$$, $$$x$$$, $$$y$$$, and $$$z$$$. ($$$3 \leq n \leq 10^5$$$, $$$1 \leq x, y, z \leq \min(n, 100)$$$, $$$x + y + z \leq n$$$).
The next line will contain $$$n$$$ space separated integers $$$a_1, a_2, ..., a_n$$$ ($$$1 \leq a_i \leq 10^6$$$) — the energy required by the $$$i$$$th if set to form the shape of the candies.
The next line will contain $$$n$$$ space separated integers $$$b_1, b_2, ..., b_n$$$ ($$$1 \leq b_i \leq 10^6$$$) — the energy required by the $$$i$$$th if set to add sourness to the candies.
The last line will contain $$$n$$$ space separated integers $$$c_1, c_2, ..., c_n$$$ ($$$1 \leq c_i \leq 10^6$$$) — the energy required by the $$$i$$$th if set to wrap the candies.
Output a single integer, denoting the minimum energy required by a factory of Alice configures the machines optimally.
3 1 1 11 2 33 3 22 2 5
5
8 2 1 24 3 2 1 2 3 4 98 2 8 9 3 2 3 19 8 3 2 1 1 6 7
6