You have an array of $$$n$$$ integers, and you want to find how many unique elements it has. An element is unique if it only appears once in the array.
For example, the array $$$[5, 7, 8, 5, 4, 4, 3]$$$ contains 3 unique elements: $$$7$$$, $$$8$$$, and $$$3$$$. $$$5$$$ is not a unique element, since it occurs twice in the array.
The first line of input contains a single positive integer $$$n$$$ $$$(1 \lt = n \lt = 200000)$$$: the length of the array.
The next line contains $$$n$$$ space-separated integers: the array. The array elements will be between $$$1$$$ and $$$10^9$$$, inclusive.
Output a single positive integer: the number of unique elements in the array.
Full problem: 5 points
9 1 2 3 4 2 5 1 6 7
5
8 1 3 3 2 3 1 2 1
0
7 6 5 7 3 4 1 2
7
You have an array $$$a$$$ consisting of $$$n$$$ positive integers, and an integer $$$k$$$.
You call a subarray an egocentric subarray if the difference between the maximum and minimum elements of the subarray is equal to $$$k$$$.
Recall that a subarray is a contiguous segment of elements of the original array, in order.
For example, if $$$a = [5, 4, 1, 2, 3, 6]$$$ and $$$k = 3$$$, then $$$[4, 1]$$$, $$$[4, 1, 2, 3]$$$, and $$$[3, 6]$$$ are egocentric subarrays, while $$$[5, 4, 1, 2]$$$, $$$[4, 1, 2, 3, 6]$$$, and $$$[5]$$$ are not.
Your task is to find the number of egocentric subarrays in the array.
The first line of input contains two space-separated integers $$$n$$$ $$$(1 \lt = n \lt = 100)$$$ and $$$k$$$ $$$(1 \lt = k \lt = 10^9)$$$: the length of the array, and the number to find if the difference is equal to, respectively.
The next line consists of $$$n$$$ space-separated integers: the array elements $$$(1 \lt = a_i \lt = 10^9)$$$.
Output the number of egocentric subarrays of the array.
Full problem: 7 points
5 3 5 4 1 2 3
3
11 7 1 3 7 6 4 2 11 18 12 9 1
2
In the first example, $$$[4, 1]$$$, $$$[4, 1, 2]$$$, and $$$[4, 1, 2, 3]$$$ are egocentric subarrays.
In the second example, $$$[11, 18]$$$ and $$$[11, 18, 12]$$$ are egocentric subarrays.
You have a string of length $$$n$$$. Unfortunately, some of its letters are infectious. More specifically, any "a" characters in the string have the potential to spread to any adjacent characters. At any point in time, an "a" character in the string can "infect" any of its adjacent characters, and make them an "a" character as well.
However, "b" characters are immune to the "a" characters' infection, and thus can't be changed into "a" characters.
For example, if we have the string "cabaccabdd", the second character of the string could infect the first character, turning it into another "a", but it couldn't infect the third character of the string, since it's a "b".
Your task is to determine the maximum number of $$$a$$$ characters that could exist in the string after an unlimited amount of infections.
For example, in the string "cabaccabdd" could become "aabaaaabdd" in an unlimited number of infections, which has 6 "a" characters.
The first line of input contains a single positive integer $$$n$$$ $$$(1 \lt = n \lt = 200000)$$$: the length of the string.
The next line of input contains the string.
Output the maximum number of $$$a$$$ characters that could exist in the string after an unlimited amount of infections.
Full problem: 10 points
15 bbbacxdbxyabxab
9
5 bbbbb
0
5 aabcc
2
You're the owner of a large park that contains $$$n$$$ water fountains. $$$q$$$ people are going to visit the park, and each of them is going to drink water from the first $$$q_i$$$ water fountains. In other words, each of the $$$q$$$ people is going to drink from all of the fountains from $$$1$$$ to $$$q_i$$$, inclusive (using 1-based indexing).
Unfortunately, some of the water fountains are going to break soon. The $$$i$$$th water fountain will break after at least $$$a_i$$$ people use it.
Each person will always use the fountains from $$$1$$$ to $$$q_i$$$, regardless of whether or not these fountains are broken or not.
Given this information, your task is to figure out how many of the water fountains will be broken after the $$$q$$$ people use them.
The first line of input contains two space-separated integers $$$n$$$ and $$$q$$$ $$$(1 \lt = n, q \lt = 100000)$$$: the number of fountains, and the number of people that are going to drink from the fountains, respectively.
The next line of input contains $$$n$$$ space-separated integers: the array $$$a$$$ $$$(1 \lt = a_i \lt = 200000)$$$, representing how many people need to drink from each fountain before it will break.
The next $$$q$$$ lines each contain a single positive integer $$$q_i$$$ $$$(1 \lt = q_i \lt = n)$$$: the number of water fountains that each person will drink at (from $$$1$$$ to $$$q_i$$$, inclusive).
Output a single positive integer $$$k$$$: how many water fountains will break after all $$$q$$$ people use them.
Subtask 1 (4 points): $$$1 \lt = n, q \lt = 1000$$$
Subtask 2 (13 points): no additional constraints
5 5 3 2 6 1 2 3 2 3 4 5
3
8 7 3 2 3 1 4 3 2 3 1 1 1 2 4 5 2
3
You want to buy a TV, and you're looking into your options. You're going to base this decision on the daily TV schedule for $$$n$$$ channels. The schedule lists the first $$$m$$$ minutes in the day. Each of the $$$n$$$ channels has interesting content for some of the minutes during the day, and uninteresting content for all of the other times during the day.
The TVs offered all have a certain amount of channels that they are able to record content from at one time, which is what you're using to try to decide which TV to buy.
You have a value called your TV score which starts at 0, and increases as you record content.
Each of the $$$n$$$ channels has a certain enjoyment value, which is a positive integer. For each minute that you record a TV channel, if the channel has interesting content, your TV score will increase by the channel's enjoyment value, and if the channel has uninteresting content, it won't change.
In each minute of the day, you can choose to record as many channels as your TV allows. You can freely switch between recording different channels between each minute, but not during minutes.
Your task is to find the minimum number of channels that your TV needs to be able to record at once, in order to attain a TV score of at least $$$k$$$.
The first line of input contains three space-separated integers $$$n$$$ $$$(1 \lt = n \lt = 1000)$$$, $$$m$$$ $$$(1 \lt = m \lt = 1000)$$$, and $$$k$$$ $$$(1 \lt = k \lt = 10^{18})$$$: the number of TV channels, the number of minutes that the schedule covers, and your goal value for the TV score, respectively.
The next line contains $$$n$$$ space-separated integers: the enjoyment value for each TV channel. Each enjoyment value will be between $$$1$$$ and $$$10^9$$$, inclusive.
The next $$$n$$$ lines each consist of a $$$m$$$-character string of ones and zeros, with each 1 character representing interesting content at the corresponding minute, and each 0 character representing uninteresting content.
Output a single positive integer $$$c$$$: the minimum number of channels that your TV needs to be able to record during a single minute, in order to be able to attain a TV score of at least $$$k$$$.
If it is impossible to attain a TV score of at least $$$k$$$ across all channels, output $$$-1$$$.
Full problem: 24 points
4 15 133 5 9 3 11 000111011000000 111111010001111 101100011011000 000110000001000
2
3 5 729 11 13 14 11000 01000 00111
-1
In the first example, if you buy a TV that can record only 1 channel at once, you can attain a TV score of 113, which is not enough. If you buy a TV that can record 2 channels at once, you can get a TV score of 159, so this is the answer.
In the second example, even if you buy a TV that can record all three channels, you only get a TV score of 77, which is not enough.
There are $$$n$$$ birds on a number line, with the $$$i$$$th bird being located at $$$a_i$$$. You have $$$m$$$ cameras, and the $$$i$$$th camera is located at $$$b_i$$$.
Your goal is to capture as many birds as possible with the $$$m$$$ cameras. To accomplish this, you can move all of the cameras as many units to the left or right as you want. However, you have to move all of the cameras at once. In other words, if you move one camera on the number line, you have to move all of the other cameras by the same amount and in the same direction.
Your task is to figure out the maximum possible number of birds that can be located at the same position as a camera, by moving the cameras as described above.
The first line of input contains two space-separated integers $$$n$$$ and $$$m$$$ $$$(1 \lt = n, m \lt = 1000)$$$: the number of birds, and the number of cameras.
The next line of input consists of $$$n$$$ space-separated integers $$$a_i$$$: the position of each bird. $$$(1 \lt = a_i \lt = 10^9)$$$, all $$$a_i$$$ are distinct, and $$$a$$$ is sorted in increasing order.
The next line of input consists of $$$m$$$ space-separated integers $$$b_i$$$: the position of each camera. $$$(1 \lt = b_i \lt = 10^9)$$$, all $$$b_i$$$ are distinct, and $$$b$$$ is sorted in increasing order.
Output the maximum possible number of birds that can be located at the same position as at least one camera, at any single point in time.
Subtask 1 (8 points): $$$1 \lt = n, m, a_i \lt = 100$$$
Subtask 2 (18 points): no additional constraints
5 5 1 3 7 8 10 5 9 11 13 18
3
3 4 1 3 5 2 7 13 18
1
In the first example, you can move the cameras to the left by 10, capturing the birds at positions 1, 3, and 8.
In the second example, you can only capture one bird, regardless of how much you move the cameras by.
You have an array $$$a$$$ consisting of $$$n$$$ positive integers. Based on this array, you're trying to calculate the product of $$$a_i^i$$$ for all values of $$$i$$$ from $$$1$$$ to $$$n$$$. For example, this value for the array $$$a = [5, 3, 4, 7, 2]$$$ is equal to $$$5^1 * 3^2 * 4^3 * 7^4 * 2^5 = 221276160$$$. We'll call this the cumulative product value.
You're goal is for this value to have the minimum number of trailing zeros in its binary representation. For example, 16 has four trailing zeros in its binary representation, while 34 only has one trailing zero.
To accomplish this, you're going to perform a certain number of swaps of adjacent elements in this array. Your task is to calculate the minimum number of swaps needed in order to obtain the minimum possible amount of trailing zeros in the binary representation of the cumulative product value, across all permutations of the array.
The first line of input contains a single positive integer $$$n$$$ $$$(1 \lt = n \lt = 10^5)$$$: the length of the array.
The next line contains $$$n$$$ space-separated integers: the array $$$(1 \lt = a_i \lt = 10^9)$$$.
Output a single positive integer: the minimum number of swaps between adjacent elements in the array, in order to minimize the cumulative product value.
Full problem: 38 points
4 3 16 2 4
4
In the example, the array $$$b = [16, 4, 2, 3]$$$ has the minimum number of trailing zeros in its cumulative product value, across all permutations of $$$a$$$.
You have an $$$n$$$ by $$$n$$$ 2D grid of integers ranging from $$$-100$$$ to $$$100$$$. You define a donut as a ring of numbers in the 2D grid, with a width of one. For example, this is an example of a donut (highlighted in green):
Note that a donut must include a "hole", i.e. a $$$2$$$x$$$2$$$ square is not considered a donut. Note also that a donut does not have to be in a square shape.
The value of a donut is defined as the sum of the numbers that it contains. For example, the donut pictured above has a value of 27. Given an $$$n$$$ by $$$n$$$ 2D grid, your task is to find the donut with the maximum value.
The first line of input contains a single positive integer $$$n$$$ ($$$n \lt = 400$$$): the width and height of the grid.
The next $$$n$$$ lines each contain $$$n$$$ space-separated integers, representing the elements of the grid. Each element will range from $$$-100$$$ to $$$100$$$, inclusive
Output the value of the maximum donut in the 2D grid.
Subtask 1 (13 points): $$$n \lt = 80$$$
Subtask 2 (34 points): no further constraints
5 1 3 -5 6 4 2 5 -8 4 0 0 8 9 3 3 -1 5 -7 2 6 -3 4 0 1 -1
39
5 13 15 -2 -3 -5 14 18 -5 -8 -10 -2 -2 1 -1 2 4 -1 0 5 -6 -2 -1 1 -1 0
37
3 -1 -2 -3 -4 -5 -6 -7 -8 -9
-40
You work at an airport, and you just received the baggage for a recently arrived flight, consisting of $$$k$$$ bags. You are in charge of placing these bags on the conveyor belt in the airport, which can be represented as a single, non self-intersecting ring.
Due to the COVID-19 pandemic, however, you want to place everyone's bags far apart on the conveyor belt.
Your task is to find the maximum distance $$$d$$$, such that it's possible to place all of the bags on the conveyor belt, and all of the bags that are next to each other on the conveyor belt will be at least $$$d$$$ units apart at all times during the conveyor belt's rotation. Assume that all parts of the conveyor belt move at the same speed.
Two bags are considered to be "next to each other" on the conveyor belt if you could travel from one bag to the other either clockwise or counter-clockwise on the conveyor belt, without encountering any other bags.
Note that in this problem, distance is measured in "Manhattan Distance", i.e. the Manhattan Distance between two points $$$(x_1, y_1)$$$ and $$$(x_2, y_2)$$$ is calculated as $$$\lvert x_2 - x_1\rvert + \lvert y_2 - y_1\rvert$$$.
The first line of input contains two space-separated positive integers $$$n$$$ $$$(1 \lt = n \lt = 200)$$$ and $$$k$$$ $$$(2 \lt = k \lt = 400)$$$: the length and width of the room that the baggage claim conveyor belt is in, and the number of bags on the upcoming flight, respectively.
The next $$$n$$$ lines contain $$$n$$$ characters each, representing the layout of the room. An "x" character represents part of the conveyor belt, while a "." character represents empty space.
The conveyor belt will be at most 400 characters long, i.e. there will be at most 400 "x" characters in the grid. The conveyor belt will also always be at least $$$k$$$ characters long.
The conveyor belt is guaranteed to be a single non-self-intersecting ring. Additionally, every conveyor belt space (every "x" character) will be directly adjacent (not diagonally) to exactly two other conveyor belt spaces.
Output a single positive integer $$$d$$$: the maximum distance, such that it's possible to place all of the bags on the conveyor belt at least $$$d$$$ units apart (in manhattan distance) at all times during the rotation of the conveyor belt.
Subtask 1 (15 points): there will be at most 15 $$$x$$$ characters in the input
Subtask 2 (61 points): no additional constraints
7 3 ....... ..xxxx. ..x..x. .xx..x. .x...x. .xxxxx. .......
3
10 2 .......... .xxxxxxxx. .x......x. xx......x. x.......x. x..xxxx.x. x.xx..x.x. xxx...xxx. .......... ..........
5
11 2 xxxxxxxxxx. x........x. xxxxxxxx.x. .......x.x. xxxxxxxx.x. x........x. xxxxxxxx.x. .......x.x. xxxxxxxx.x. x........x. xxxxxxxxxx.
7