William and Mary are trying to complete their HW. The last HW question asks to find the absolute difference between the maximum odd number and minimum even number in a list of numbers. Help William and Mary solve their last problem!
The first and only line will contain $$$n$$$ integers $$$(1 \leq n \leq 10^5)$$$. All integers are at most $$$10^5$$$.
Output the absolute difference between the maximum odd number and minimum even number. If there is no even number or no odd number, print "None".
1 2 3 4 5 6 7
5
1 1 1 1 1 1 1
None
William is cat-sitting a cat cafe, and he needs to feed the cats their favorite food, Kitty Pebbles. However, in order to prevent a cat tantrum, he needs to feed each cat the same number of Kitty Pebbles.
William pours some number of Kitty Pebbles into each cat's food bowl. Then, he needs to remove Kitty Pebbles from some of the bowls such that an equal number of Kitty Pebbles are in each bowl. The removed Kitty Pebbles get thrown out, because the cats refuse to eat anything that has been in another cat's bowl. What's the minimum number of Kitty Pebbles that get thrown out?
The first line contains a single integer $$$N$$$ ($$$1 \le N \le 10^5$$$), denoting the number of cats.
The next line contains $$$N$$$ integers $$$a_1,...,a_N$$$ ($$$1 \le a_i \le 10^4$$$), where $$$a_i$$$ represents the number of Kitty Pebbles William pours into the $$$i$$$th bowl.
Output a single integer, the minimum number of Kitty Pebbles that can get thrown out.
4 8 3 5 2
10
William is employed at a local factory in his dream job: middle management.
Taking the assembly line to heart, the factory contains $$$N$$$ workers, who reside on a line. Each individual $$$i$$$ has a productivity $$$p_i$$$ and works $$$h_i$$$ hours. Their individual output is given by the product of these two values.
As he is the most senior middle manager, William gets the first pick of his team. William is expected to manage a team of $$$K$$$ people and his bonus is the total output of his managed workers, in dollars. Of course, the team must be contiguous to ensure sufficient team bonding.
Please help William determine the optimal team and more importantly, tell him what he truly cares about, his bonus.
The first line contains two integers: $$$N$$$ and $$$K$$$ where $$$1 \leq K \leq N \leq 10^5$$$.
The next $$$N$$$ lines each contain two integers, $$$1 \leq p_i \leq 100$$$ and $$$1 \leq h_i \leq 100$$$.
A single integer, William's optimal bonus.
4 2 2 3 1 3 3 2 4 1
10
William has baked a cornmeal pudding pone! They have invited all their friends over to share the dessert. However, they need your help to divide it evenly among all friends.
William wants all of their friends to have an equal number of slices. However, they don't know how many friends will actually show up. Friends show up in groups (where the total number of groups is $$$N$$$), and William cuts the pone in the following manner:
- The $$$i$$$th group of friends shows up, which consists of $$$a_i$$$ people.
- If the pone is currently cut into $$$s$$$ slices, William cuts the pone into $$$k \cdot s$$$ equal slices for some integer $$$k$$$, such that each person present ($$$a_1 + ... + a_i$$$ people total) can eat an equal number of slices. (But they don't eat it yet!)
The pone starts off unsliced. William wants to know – after everyone (all $$$N$$$ friend groups) show up, what's the minimum number of slices the cake will be cut into that satisfies the given technique?
See the notes for a more detailed example.
The first line contains an integer $$$N$$$ ($$$1 \le N \le 10$$$), the number of friend groups.
The next line contains $$$N$$$ integers $$$a_1,...,a_N$$$ ($$$1 \le a_i \le 10$$$), representing the number of friends in each friend group.
Output a single integer, the minimum number of slices the cake will be cut into.
3 2 3 10
30
The example proceeds in the following manner:
- The first group of friends shows up, consisting of 2 people. The pone is initially unsliced, so William slices it into two halves, such that each friend gets a half.
- The second group of friends shows up, consisting of 3 people, so there are now 5 total people. William slices each half into 5 pieces, so there are 10 slices total and each friend gets 2 slices.
- The third group of friends shows up, consisting of 10 people, so there are now 15 total people. Each of the 10 slices can now be sliced into thirds, so there are 30 slices total and each friend gets 2 slices.
It can be shown that this is the least number of slices possible that satisfies the requirements.
William is playing a game with a robot. In this game, there is an array of $$$n$$$ integers in a line, numbered $$$1, \ldots n$$$. $$$n$$$ is even.
William and the robot take turns selecting integers from the array, starting with William. William can take an integer from anywhere in the array as long as it has not already been taken by any player. The robot always takes the leftmost, untaken integer (i.e. the one with the lowest index). The game ends once all integers have been taken. William's score is the sum of his chosen integers.
Help William get the maximum score possible.
The first line contains $$$n$$$ ($$$1 \leq n \leq 10^5$$$), the number of integers in the array.
The second line contains $$$n$$$ integers $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), where $$$a_i$$$ denotes the $$$i$$$th integer of the array.
Output the maximum score William can achieve.
4 6 1 1 4
10
10 1 3 4 9 5 2 5 5 3 6
30
William likes to play card games. In this particular game, William is dealt a row of $$$N$$$ playing cards. Each of the cards has a positive integer point value, where the $$$i$$$-th card in the row has a point value of $$$p_i$$$.
The object of the card game is to minimize the maximum point value among all of the cards that William has. To do so, William is allowed to perform operations. For any $$$1 \leq i \lt N$$$, William may halve $$$p_i$$$ and double $$$p_{i-1}$$$ so long as $$$p_i$$$ is an even number. William may perform as many operations as he desires.
If William performs operations optimally, can you figure out the minimum maximum point value that he can achieve?
The input will begin with a line containing a single integer $$$N\ (1 \leq N \leq 10^5)$$$. The next line will contain $$$N$$$ space-separated integers $$$p_0, \dots, p_{N-1}\ (1 \leq p_i \leq 10^9)$$$, the initial point values of the $$$N$$$ playing cards that William is dealt.
The output should consist of a single integer representing the minimum maximum point value among all of the cards William is dealt assuming that he performs optimal operations.
5 1 25 36 80 12
25
William is overseeing a system of spaceports in the galaxy of Glarble. Because space trips are expensive, spaceports generally try to have as few unnecessary flights as possible. In particular, the (two-way) flights can be represented by a tree, such that each planet in Glarble can be reached by each other planet in Glarble through some sequence of flights, but this sequence is unique (there is only one path from one planet to another).
Because different planets have different resources, each planet has an associated cost of visiting the planet. The cost of a trip from planet $$$u$$$ to planet $$$v$$$ ($$$u \neq v$$$), then, is the sum of the costs of all planets visited on the distinct path from $$$u$$$ to $$$v$$$. The total cost of the spaceport system is the sum of the costs of all distinct trips, where two trips are the same if they have the same starting planet and the same ending planet. Trips and flights begin and end on different planets.
William has the technological ability to upgrade spaceports; when he upgrades a spaceport, its cost decreases by one, unless the cost is already 0 in which case nothing happens. He can upgrade spaceports $$$K$$$ times (not necessarily distinct spaceports). He then wants to know: if he does this optimally, what's the minimum total cost of his new spaceport system?
The first line contains two integers $$$N$$$, $$$K$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le K \le 10^9$$$), corresponding to the number of planets, and the number of upgrades William can perform, respectively.
The second line contains $$$N$$$ integers $$$c_1,...,c_N$$$ ($$$1 \le c_i \le 10^3$$$), where $$$c_i$$$ denotes the cost of visiting planet $$$i$$$.
The next $$$N-1$$$ lines contain two integers each, $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N, u \neq v$$$), denoting that there is a two-way flight between planet $$$u$$$ and planet $$$v$$$.
Output a single integer, the minimum total cost of his new spaceport system if he upgrades spaceports optimally.
3 2 3 2 1 1 3 2 3
16
In the first example, we have 6 total trips, and the total cost of the spaceport system is 26. William can then upgrade spaceport 3 once and spaceport 1 once, and the new cost for the spaceport system is 16. It can be shown this is the least possible cost.
William and will.i.am are the host and judge, respectively, of a rap battle tournament! The $$$N$$$ contestants will perform on one of two different tracks selected by will.i.am. For each contestant, we know their "rap skill level" on each track. When two players battle on a specific track, the player with higher rap skill level on that track always wins. No two players have the same rap skill level on the same track.
The tournament consists of $$$N-1$$$ battles, and the tournament will proceed as follows:
- Randomly select two players still in the tournament.
- Choose a track out of the two available ones for the players to battle on.
- The player that wins the individual fight will continue on in the tournament, and the loser will be eliminated.
- Go back to step 1 and repeat until a single player remains.
William would like to quantitatively measure how "interesting" the tournament structure is relative to other ideas he has, which is directly proportional to the number of possible winners of the tournament. Can you help William find the number of contestants that have a shot at winning it all?
The first line of each test case contains a single integer $$$N$$$ ($$$2 \leq N \leq 10^6$$$), representing the number of tournament contestants. The second line of each test case contains $$$N$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq n$$$, $$$a_i \neq a_j$$$ for $$$i \neq j$$$), where $$$a_i$$$ is the rap skill level of the $$$i$$$-th contestant on the first track. The third line of each test case contains $$$N$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$1 \leq b_i \leq n$$$, $$$b_i \neq b_j$$$ for $$$i \neq j$$$), where $$$b_i$$$ is the rap skill level of the $$$i$$$-th contestant on the second track.
Output a single integer representing the number of unique tournament winners out of the $$$N$$$ contestants.
4 1 2 3 4 1 2 3 4
1
4 1 2 3 4 4 3 1 2
4
Today is William's 26th birthday! As such, his friends have gifted him an array of length $$$N$$$. Since he is turning 26, the array will consist of only the 26 letters of the English alphabet ($$$\{\text{a}, \text{b}, \dots, \text{z}\}$$$). However, William's friends are super picky – they want the array to be perfect before they present it to William. Each of William's $$$Q$$$ friends have a chance to either make a change to the array by changing the letter at a certain index to a different English letter, or to inspect a contiguous subarray of the array and check how many palindromes the letters within the subarray can create. A palindrome is a string which is read the same forwards and backwards.
For example, if the array initially looks like $$$\{\text{q}, \text{q}, \text{r}, \text{a}, \text{r}\}$$$, and William has 2 friends, then William's first friend may choose to change the letter $$$\text{q}$$$ at index 1 to the letter $$$\text{a}$$$, resulting in the array becoming $$$\{\text{q}, \text{a}, \text{r}, \text{a}, \text{r}\}$$$, and his second friend might inspect the contiguous subarray starting at index 1 and ending at index 4 ($$$\{\text{a}, \text{r}, \text{a}, \text{r}\}$$$). The second friend will then realize that there exist 2 possible palindromes using exactly these letters ($$$\text{arra, raar}$$$). Note: when executing an inspection, the friend must use all of the letters in the range to construct palindromes.
Since William has many friends and each friend would like to perform one of these two types of queries (and because the array they are working with is very large), they need help doing all of the necessary computations. Please help them out!
The first line of input will contain two space-separated integers, $$$N\ (1 \leq N \leq 2 \cdot 10^5)$$$ and $$$Q\ (1 \leq Q \leq 2 \cdot 10^5)$$$, denoting the length of the array and the number of friends William has, respectively. The next line will consist of a single string of length $$$N$$$ consisting of lowercase English letters representing the initial state of the array. The next $$$Q$$$ lines will each begin with either a $$$1$$$ or a $$$2$$$. A $$$1$$$ represents a query of the first type, and will be followed by an integer $$$i\ (0 \leq i \lt N)$$$ and a lowercase English letter. This means that a friend would like to replace the letter currently at index $$$i$$$ with the given letter. A $$$2$$$ represents a query of the second type, and will be followed by two integers, $$$l\ (0 \leq l \lt N)$$$ and $$$r\ (l \leq r \lt N)$$$ denoting the start and end (inclusive) of a contiguous subarray that the current friend would like to inspect.
For each query of the second type, print a single line containing the number of palindromes which can be created using the letters found within the contiguous subarray that the friend would like to inspect. Since the answer to each query can be quite large, output each number modulo $$$10^9 + 7$$$. It is guaranteed that there will be at least one query of the second type.
5 5 bbbaa 2 0 4 1 1 b 2 2 4 1 2 c 2 1 2
2 1 0