You are on the hunt for some tasty dino eggs! There are $$$n$$$ dinosaur nests belonging to $$$m$$$ unique species lined up in a row. Each nest belongs to a species $$$s_i$$$ and has an egg with weight $$$w_i$$$. Your bag can hold no more than $$$k$$$ eggs. In order to preserve species $$$\textit{diversity}$$$, you will not take eggs from the same species more than $$$x$$$ times. In order to prevent a species from becoming $$$\textit{invasive}$$$, you must take at least 1 egg from each species. Find the maximum total weight of eggs you can steal!
The first line of input will contain four integers $$$n$$$ $$$m$$$ $$$k$$$ $$$x$$$, defined below:
- $$$n$$$ $$$(1 \leq n \leq 10^5)$$$: the number of nests
- $$$m$$$ $$$(1 \leq m \leq n)$$$: the number of unique species
- $$$k$$$ $$$(m \leq k \leq n)$$$: the capacity of your bag
- $$$x$$$ $$$(1 \leq x \leq n)$$$: the maximum number of eggs from a single species you can collect
The second line of input will consist of $$$n$$$ integers, where the $$$i$$$-th integer is $$$s_i$$$ $$$(1 \leq s_i \leq m)$$$, denoting the species of the $$$i$$$-th nest.
The third line of input will consist of $$$n$$$ integers, where the $$$i$$$-th integer is $$$w_i$$$ $$$(1 \leq w_i \leq 10^5)$$$, denoting the weight of the $$$i$$$-th nest's egg.
Output a single integer, the maximum total weight of eggs you can collect.
5 2 5 2 1 1 2 2 2 1 2 3 4 5
12
8 3 4 2 1 2 3 1 2 3 1 2 9 1 2 8 3 4 7 5
26
In the first test case, you want to take both of the eggs of species type 1, and the eggs weighted 5 and 4 from species type 2. This sums up to 12. Note that you do not have to fill your bag's capacity.
In the second test case, you should take the eggs with weights 9, 8, 5, and 4.
While blasting for coal, Boomberg happened upon a tablet filled with mysterious markings that looked like dinosaur tracks. Luckily, you recognize that this text is written in an ancient dinosaur language known as Dinossian, so you pull out a translation from your pocket that you have kept for this very moment.
Translation from Dinossian to English. It is now your job to translate the message on the tablet into English.
Your text written in Dinossian will consist of $$$2$$$ lines, each containing $$$2n$$$ characters, which will be one of '.', '<', 'V', '>', or '^', which will represent empty spaces, left prints, down prints, right prints, and up prints, respectively. When translated into English, the text can contain letters or digits.
Each letter written in Dino will take up a 2x2 grid, so every letter in Dinossian will be written from left to right, side by side, without spaces.
A 'single' character like B would look like:
| $$$\gt$$$ | $$$.$$$ |
| $$$.$$$ | $$$.$$$ |
A 'vertical' character like M would look like:
| $$$\vee$$$ | $$$.$$$ |
| $$$\wedge$$$ | $$$.$$$ |
And a 'horizontal' character like 6 would look like:
| $$$\lt$$$ | $$$\vee$$$ |
| $$$.$$$ | $$$.$$$ |
The first line of input will contain $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of characters to translate.
The next 2 lines each contain $$$2n$$$ characters, each of which will be one of '.', '<', 'V', '>', or '^' — representing the markings in Dinossian.
It is guaranteed that the input translates to a valid set of characters.
Output $$$n$$$ characters in a single line, the text translated from Dinossian into English. Print your result in all uppercase.
9<V^<V.V.<.<.V.^.>.....^.>.>.>.>.^.^.
65MILLION
The first letter in Dinossian is the leftmost 2x2 grid:
| $$$\lt$$$ | $$$\vee$$$ |
| $$$.$$$ | $$$.$$$ |
which corresponds to a 6.
The second letter in Dinossian is the 2nd 2x2 grid from the left:
| $$$\wedge$$$ | $$$\lt$$$ |
| $$$.$$$ | $$$.$$$ |
which corresponds to a 5.
A similar process for every one of the 9 characters. The final translated text should read '65MILLION'.
Cole, who is trying to make the most of his last year of elementary school, has an array $$$a$$$ of $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ plates of chicken stars arranged in a straight line in his backyard.
Unfortunately for Cole, Barney the Dinosaur has just arrived—and he's furious that Cole chose chicken stars over dinosaur nuggets. In a fit of rage, Barney decides to stomp on a contiguous sequence of plates.
Formally, Barney will choose one subarray of length $$$k$$$ $$$(1 \leq k \leq n)$$$ and stomp on it, destroying all of the chicken stars in this subarray.
Cole, acting quickly, can save the chicken stars from one plate before Barney stomps. That is, he can choose one index $$$i$$$ and set $$$a_i = 0$$$ before Barney makes his move.
Barney wants to maximize the number of chicken stars he stomps on while Cole wants to minimize it. Assuming both perform their actions optimally, how many chicken stars will Barney stomp on?
The first line contains integers $$$n, k$$$ $$$(1 \leq k \leq n \leq 10^5)$$$ where $$$n$$$ the size of $$$a$$$ (number of plates of chicken stars) and $$$k$$$ is the length of the subarray that Barney will stomp on.
The second line contains $$$n$$$ integers, $$$[a_1, a_2, ... a_n]$$$ $$$(1 \leq a_i \leq 10^9$$$), the elements in $$$a$$$.
Output one number, the number of chicken stars Barney will stomp on.
5 33 5 7 4 7
11
4 41 10 4 8
13
In the first test case, one set of actions that results in the provided answer is:
Cole saves plate $$$i = 3$$$, setting $$$a_3 = 0$$$ Barney stomps on subarray $$$[3...5]$$$ $$$0 + 4 + 7 = 11$$$
In the second test case, one set of actions that results in the provided answer is:
Cole saves plate $$$i = 2$$$, setting $$$a_2 = 0$$$ Barney stomps on subarray $$$[1...4]$$$ (this is his only option) $$$1 + 0 + 4 + 8 = 11$$$
Scientists believe that the mitochondria in eukaryotic cells actually came from early cells engulfing mitochondria through a process known as endosymbiosis. Now, people refer to this theory as Symbiogenesis.
As a scientist working in the Karyotype Analysis and Replication Project (KARP for short), you are simulating how this may happen.
You have a rectangular box with sides parallel to the $$$x$$$ and $$$y$$$ axes, with its bottom-left corner at $$$(0,0)$$$ and its upper-right corner at $$$(w,h)$$$. A cell starts in the bottom-left corner and moves at a constant velocity with an initial vector of $$$(x_1,y_1)$$$ (the $$$x$$$ velocity is $$$x_1$$$ units/second, and the $$$y$$$ velocity is $$$y_1$$$ units/second). A mitochondrion starts in the top-right corner and moves at a constant velocity with an initial vector of $$$(-x_2,-y_2)$$$. Whenever a cell or mitochondrion hits a wall, it will bounce off the wall perfectly, without changing its speed.
You are given $$$n$$$ versions of this setup. For each setup, how many seconds will it take for the cell and mitochondrion to meet for the first time? If they will never meet, print out $$$-1$$$ instead.
The first line of input contains $$$n$$$ ($$$1\le n\le 2\cdot 10^5$$$) — the number of setups.
The $$$i^\text{th}$$$ line of the next $$$n$$$ lines contains $$$w_i$$$, $$$h_i$$$, $$$x_{i_1}$$$, $$$y_{i_1}$$$, $$$x_{i_2}$$$, $$$y_{i_2}$$$ ($$$1\le w_i,h_i\le 10^9, 0\le x_{i_1},y_{i_1},x_{i_2},y_{i_2}\le 10^9$$$) — the width, height, velocity of the cell $$$(x_{i_1}, y_{i_1})$$$, and the velocity of the mitochondrion $$$(-x_{i_2}, -y_{i_2})$$$ for the $$$i^\text{th}$$$ setup. It is guaranteed that $$$x_{i_1}$$$ and $$$y_{i_1}$$$ are not both $$$0$$$. It is also guaranteed that $$$x_{i_2}$$$ and $$$y_{i_2}$$$ are not both $$$0$$$.
Output $$$n$$$ numbers, the $$$i^\text{th}$$$ of which represents the minimum number of seconds it will take for the cell and mitochondrion to meet for setup $$$i$$$. Your answer will be considered correct if it is within $$$10^{-6}$$$ of relative or absolute error. If the cell and mitochondrion never meet, output $$$-1$$$ instead.
22 2 1 3 1 32 2 1 1 1 3
1.0000000000 1.0000000000
Archie, the rising star of the renowned Archer family of archaeologists, is conducting his first major excavation. He had all the pieces required for an Archaeopteryx fossil, but before he could assemble the skeleton, his dog took one of the bones, disrupting Archie's carefully planned layout.
The original layout for the skeleton was in the form of $$$n$$$ lines, where the $$$i^{\text{th}}$$$ line contained the indexes of the bones that were adjacent to bone $$$i$$$. Adjacency was undirected, so if the $$$i^{\text{th}}$$$ line contained $$$j$$$, then the $$$j^{\text{th}}$$$ line contained $$$i$$$. Every bone in the original layout was adjacent to at least one other bone. However, one of the bones was taken, removing its corresponding line, so there are now $$$n-1$$$ lines, and all lines after the line representing the stolen bone are shifted down by one.
Please help Archie determine the index of the earliest bone that could have been stolen and its adjacent bones.
The first line of input contains $$$n$$$ ($$$2 \le n \le 2 \cdot 10^3$$$), the number of lines in the original layout.
The next $$$n-1$$$ lines start with an integer $$$m$$$ ($$$1 \le m \lt n$$$), followed by $$$m$$$ distinct integers $$$b_i$$$ ($$$1 \le b_i \le n$$$), the adjacent bones to bone $$$x$$$ ($$$b_i \ne x$$$), where $$$x$$$ was the index of the line in the original layout.
The output should be one line containing the earliest possible index of the stolen bone, followed by its adjacent bones in ascending order.
32 2 32 1 2
2 1 3
In this case, the only possible index of the stolen bone is bone $$$2$$$, and it was previously adjacent to bones $$$1$$$ and $$$3$$$.
With the rise of mammoths and mastodons, the animals are trying to learn from the lessons of their ancestors. They have decided the best way to store all their food is in a humongous warehouse, where people regularly come and go. Jeff Bezoic is now trying to figure out how to keep up with all of this traffic!
The warehouse is conveniently split up into 26 sectors labeled from 'A' to 'Z'. Mr. Bezoic has also come up with a way to categorize all the traffic into two categories of people:
- Inventory: An animal will simply come in to make note of the amount of stock in a sector, and then go on with their day.
- Delivery: An animal will come in and modify a sector (either increasing or decreasing the food in it), and then leave.
Jeff was originally given a list of all the traffic that would be occurring the next day. Every entry in the log contains the ID of the person, their category (Inventory or Delivery), and what sector of the warehouse they're going to. Complications have arose in the warehouse, however, such that a person cannot enter the warehouse more than once a day. That is, once a worker enters, they must do all of their inventory and delivery before leaving. Jeff is fine with reorganizing the log to let these workers know ahead of time, but there are certain requirements he needs to make sure of:
- If the original log has Worker 'A' doing inventory before Worker 'B' does delivery in the same warehouse sector, 'A' must come before 'B' in the new log, so that 'A' isn't affected by modifications that should come later.
- If the original log has Worker 'A' doing delivery before Worker 'B' does inventory in the same warehouse sector, 'A' must also come before 'B' so that 'B' records the right inventory.
Note that once a new order is decided, a worker will come in and do all their tasks in the same order as they would have in the original larger log.
With so many potential workers, Jeff naturally wants to automate this as much as possible. However, he wants the order to be as lexicographically smallest$$$^\dagger$$$ possible. Can you help him out?
$$$^\dagger$$$ Note that all orderings will be a permutation of the numbers from $$$1$$$ to $$$n$$$, so I will define it here along that definition. If permutation $$$a$$$ is lexicographically smaller than permutation $$$b$$$, $$$a[i] \lt b[i]$$$ in the first position where $$$a[i] \ne b[i]$$$.
The first line of input will contain two integers $$$n$$$ and $$$m$$$ ($$$3 \le n \le 10^5$$$, $$$n \le m \le 2n$$$), the number of unique workers and the number of entries in the original log respectively.
The next $$$m$$$ lines will be in the form $$$x$$$ $$$c$$$ $$$d$$$. $$$x$$$ will be the ID of the worker ($$$1 \le x \le n$$$), $$$c$$$ is the warehouse sector being visited (an uppercase letter from 'A' to 'Z'), and $$$d$$$ is either 'I' (inventory) or 'D' (delivery).
It is guaranteed all $$$n$$$ IDs will appear in the list of $$$m$$$ logs.
Output a space-separated list of $$$n$$$ integers, which represents the lexicographic smallest ordering that satisfies all of the original log's orderings. If no such ordering exists, simply output $$$-1$$$.
3 51 A I2 B I3 B I2 B D2 A D
1 3 2
3 61 A I2 B I3 B I2 B D2 A D3 B I
-1
In the first test case, the 3rd and 4th logs force $$$3$$$ before $$$2$$$, while the 1st and 5th force $$$1$$$ before $$$2$$$. The two possible orderings are $$$[1, 3, 2]$$$ and $$$[3, 1, 2]$$$.
In the second test case, the 3rd and 4th logs force $$$3$$$ before $$$2$$$. However, the 4th and 6th logs force $$$2$$$ before $$$3$$$. This cycle causes a contradiction, so there is no ordering that keeps the warehouse running smoothly.
Researchers at Meta have been working on a self-supervised learning model for images called DINO. However, not all researchers seem to be equally working on the model. In particular, Johnny, one of the researchers, has been getting easily distracted at the team meetings.
For example, during the presentation this morning, a slide with a neural network containing a fully-connected layer appeared, and Johnny decided to start counting the number of unique intersection points that exist between the edges in the layer. However, Johnny realizes that doing this manually will take forever, and now he wants you to help him count the intersection points for him!
A fully-connected linear layer can be represented as a set of $$$n$$$ input nodes and $$$m$$$ output nodes with straight-line edges connecting every pair of input and output nodes. The input nodes are equally spaced on a vertical line, and the output nodes are equally spaced on another vertical line.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n, m \le 1000$$$) – the number of input nodes and the number of output nodes of the fully-connected linear layer, respectively.
Output a single integer, the number of unique intersection points between the edges in the fully-connected linear layer. Nodes do not count as intersection points of edges.
4 3
14
In the example test case, there are $$$4$$$ input nodes and $$$3$$$ output nodes. From the diagram above, observe that there are $$$14$$$ unique intersection points by manual inspection.
Randy is playing his favorite game: Dino Run.
Dino run is situated on a circular map with positions $$$1$$$ to $$$n$$$. At any given time, a position could be empty or filled with a cactus. The Dino moves right at a constant pace of $$$1$$$ position per timestep; when the Dino is at position $$$N$$$, it arrives at position $$$1$$$ at the next timestep. The game is over when the Dino touches a cactii.
Initially, all the positions are empty, and every timestep, a cactus grows at an empty position. If a cactii grows in a position in the same timestep that the Dino is on that position, the game is over.
Randy controls this Dino, and has one action he can make: jump. In a single jump, the Dino leaps into the air and floats for up to the next $$$k$$$ timesteps. In other words, the Dino can jump over at most $$$k$$$ consecutive cactii. Note that while the Dino is in the air, it still moves forward at the constant rate of one position per timestep.
Since Randy is a pro gamer, his jumps are precisely powered and timed. However, given the growth of the cactii, at some point, it is inevitable that the game will be over. To help Randy calculated his trajectories, he gives you $$$q$$$ queries.
For each query, he gives you a starting point $$$l$$$ and an ending point $$$r$$$. He wants to find the last possible timestep his Dino can start on the ground (not floating) at position $$$l$$$ and successfully end on the ground (not floating) at position $$$r$$$ without losing.
Please help Randy so he can set the new high score.
The first line contains $$$n, k, q$$$. $$$1 \leq k \lt n \leq 10^6, 1 \leq q \leq 10^5$$$.
The second line contains $$$n$$$ integers, $$$c_1, c_2, c_3, ... c_n$$$, where $$$c_i$$$ is the location where a cactus is added at the $$$i$$$th timestep. $$$1 \leq c_i \leq n$$$. Note that the second line represents the order that the cactii are added, not the timestep in which each position gets filled.
The next $$$q$$$ lines contain two integers each $$$l, r$$$, which represent the range for each query. $$$1 \leq l,r \leq n$$$. Note that it is not guaranteed that $$$l \lt r$$$. If $$$r \lt l$$$, it means that we are considering the trajectory on the map going from position $$$r, r+1, ..., n, 1, 2, ..., l-1, l$$$.
Output $$$q$$$ integers, one for each query, representing the first time when it is impossible for a dino to go from $$$l$$$ to $$$r$$$. Output $$$-1$$$ for a query if it is just generally impossible.
10 2 2 7 9 1 3 2 6 4 10 5 8 10 5 7 7
2 -1
4 0 10 4 3 2 1 1 4 1 3 1 2 1 1 2 4 2 3 2 2 3 4 3 3 4 4
-1 -1 1 3 -1 -1 2 -1 1 -1
For the first query in the first sample, the section we are interested in the trajectory of positions $$$10, 1, 2, 3, 4, 5$$$.
If Randy starts at $$$10$$$ at timestep $$$2$$$, Randy performs a small jump, causing us to be in the air at timestep $$$3$$$ and touch down at timestep $$$4$$$ at position $$$2$$$. Then, at timestep $$$4$$$, Randy immediately jumps again causing us to be in the air for timestep $$$5$$$ and timestep $$$6$$$, landing at position $$$5$$$ safely at timestep $$$7$$$.
If instead Randy starts at timestep $$$3$$$ notice that he would land at position $$$2$$$ at timestep $$$5$$$, but there would already be a cactus there, causing him to lose.
Therefore, timestep $$$2$$$ is the latest timestep that Randy can complete this segment.
For the second query in the first sample, this is impossible since a cactus spawns at position $$$7$$$ at timestep $$$1$$$, and the Dino needs to start and end on the ground. So, the Dino can never spawn, causing this to be impossible.