It is Earth Kingdom tradition to track the year with some piles of raised earth. To mark the new year, earthbenders come together to raise the ground $$$1$$$ unit, representing the new year.
Unfortunately, they can only raise the dirt from its initial height of $$$0$$$ to a maximum height of $$$3$$$ (since they lack proper training). As a solution, when a pile needs to be raised to a height of $$$4$$$, instead they gently lower the pile back to a height of $$$0$$$ and raise the area to the right by $$$1$$$ unit of height.
There are currently $$$N$$$ piles, representing the current year. Given the state of the dirt piles, determine what the piles would look like in $$$K$$$ years.
Two space-separated numbers, $$$1 \leq N \leq 1000$$$ and $$$1 \leq K \leq 10^4$$$.
The next $$$N$$$ numbers represent the current pile heights from left to right, where the last pile is guaranteed to have non-zero height.
The piles after $$$K$$$ years, from left to right, where the last pile has non-zero height.
3 6 3 2 2
1 0 3
1 21 2
3 1 1
For National Rock Day, you've decided to paint the rock that you were gifted. This is a peculiar rock that is divided into $$$n$$$ sections, numbered $$$1,...,n$$$. Every second for the next $$$x$$$ seconds, your friend will give you two numbers. The first number will represent the section that you should start painting at and then the second number will represent the section that you should stop painting at (both inclusive). Every coat of paint will have a thickness of 1. Can you find the section with the largest thickness at any point in the rock after all layers of paint have been applied?
The first line contains one number $$$n$$$ ($$$1 \leq n \leq 10^5$$$), representing the number of sections the rock is divided into. The second line contains one number $$$x$$$ ($$$1 \leq x \leq 100$$$), representing the number of times your friend will give you starting and stopping numbers.
The next $$$x$$$ lines will each contain two integers $$$i, j$$$ ($$$1 \leq i \leq j \leq n$$$) representing the starting and stopping sections to paint.
Output the region of the rock that has the greatest thickness (has the most coats of paint). If there are multiple, return the lowest section number.
5 1 2 4
2
10 3 3 5 4 8 5 9
5
It's raining rocks! Hallelujah!
It's raining rocks, every type of rock!
Pyroclastic, metamorphic, lustrous, and igneous!
Coarse and silty and sedimentary and porous!
Specifically, it's raining rocks in $$$N$$$ very specific locations along a line, where the $$$l_i$$$ is the $$$i$$$-th location. Before the weather event, you want to set up a system to collect these rocks to avoid catastrophic landslides. You plan to lay out some baskets where the rocks will fall, to keep them contained.
A basket of width $$$w$$$ can capture rocks from $$$w$$$ consecutive locations. You have commissioned $$$K$$$ baskets with the same width, but you still need to figure out how wide the baskets should be.
Given the locations of rock-rain, $$$l_i$$$ and the number of commissioned baskets, determine the minimal width the baskets should be to capture every falling rock.
The first line contains two integers, $$$1 \leq N \leq 10^5$$$ and $$$1 \leq K \leq 10^5$$$.
The second line contains $$$N$$$ integers, $$$1 \leq l_i \leq 10^9$$$
Output a single number, the minimal basket width needed to collect all the rocks.
4 2 6 1 4 5
3
There are $$$n$$$ cities in BIT Land, where the $$$i$$$th city has value $$$a_i$$$. Between every pair of cities, there is a road paved with rocks. The cost to travel from city $$$i$$$ to city $$$j$$$ over the rocky road is $$$a_i \& a_j$$$, where $$$\&$$$ is the bitwise AND operator.
Some of these distances are large, so you discovered an alternative route. Each city $$$i$$$ has a corresponding city in the mirror universe TIB Land. The value of each city in TIB Land, $$$b_i$$$, is the value you get when flipping the lowest $$$32$$$ bits of $$$a_i$$$. Between each pair of cities is a road paved with avocados. The cost to travel from city $$$i$$$ to city $$$j$$$ over the avocado-y road is $$$b_i \& b_j$$$. There is a portal between city $$$i$$$ in BIT Land and city $$$i$$$ in TIB Land, so there is no cost traveling between the two universes.
You want to make a delivery of rocks and avocados starting at city $$$1$$$ and ending at city $$$n$$$, both in BIT Land. You want to minimize the total cost of your path, which is computed by summing the cost of each edge you travel on. What is the minimum cost that you would have over any path?
The first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 2000$$$) — the number of cities.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 2^{32} - 2$$$) – the value of each city in BIT Land.
Print a single integer — the shortest distance from city $$$1$$$ in BIT Land to city $$$n$$$ in BIT Land.
3 1 2 1
0
2 4294967294 4294967292
1
Everyone loves collecting rocks! That is, everyone except you.
You are stuck in a big cave, with your trusty magnetic backpack. The cave consists of $$$n$$$ caverns connected by $$$m$$$ tunnels. You start at cavern $$$1$$$ and the exit as at cavern $$$n$$$. Each tunnel has $$$a$$$ magnetic rocks that will automatically stick to your backpack once you enter the tunnel. However, each tunnel also has its own magnetic field, and will take away $$$b$$$ rocks once you leave (or all of your rocks, if you have less than $$$b$$$ rocks).
You hate collecting rocks, so you must figure out how to leave with the least number of rocks, if you even can escape this cave.
The first line contains two integers, $$$n$$$ ($$$1 \leq n \leq 300$$$) and $$$m$$$ ($$$1 \leq m \leq n(n-1)$$$).
Then, $$$m$$$ lines follow, each containing four integers: $$$x$$$, $$$y$$$ ($$$1 \leq x, y \leq n$$$) and $$$a$$$, $$$b$$$ ($$$0 \leq a, b \leq 10$$$). This denotes a one-way tunnel from cavern $$$x$$$ to cavern $$$y$$$, where you gain $$$a$$$ rocks upon entering and lose $$$b$$$ rocks upon leaving.
Output a single integer, the minimum number of rocks you can leave the cave with, or -1 if it is not possible to escape the cave.
4 4 1 2 10 0 2 4 2 1 4 3 0 5 3 2 3 3
1
In the example, a path that achieves this is 1 -> 2 -> 4 -> 3 -> 2 -> 4 -> 3 -> 2 -> 4 -> 3 -> 2 -> 4. In order, the number of stones you have is: 0, 10, 11, 6, 6, 7, 2, 2, 3, 0, 0, 1.
The Jackson School of Geosciences recently bought a Rocks & Fossils Kit – 200+ Piece Set Includes Geodes, Real Fossils, Rose Quartz, Jasper, Aventurine & Many More Rocks, Crystals & Gemstones! The school would like to give out the rocks to faculty. To do so, they lay out the rocks in a line. Each rock has some value $$$c_i$$$.
However, as geologists specializing in different rock types, the faculty members have very particular requirements as to what rocks they are willing to take. In particular, each geologist will only take rocks starting at some position $$$a_j$$$, and then continue taking rocks from indices $$$a_j+1, a_j+2,...$$$ until one of the following happens:
The faculty members line up to take turns choosing rocks. JSC wants to know: what's the maximum number of collections that can be satisfied, if they choose the optimal order in which the faculty members line up?
The first line contains two integers $$$1 \le N \le 10^5$$$ and $$$1 \le M \le 10^5$$$, corresponding to the number of rocks and the number of faculty members, respectively.
The next line contains $$$N$$$ integers $$$c_1,...,c_N$$$, where $$$c_i$$$ represents the value of the $$$i$$$th rock. $$$(1 \le c_i \le 10^9)$$$
The third line contains $$$M$$$ integers $$$a_1,...,a_M$$$, where the $$$j$$$th faculty member takes rocks starting at index $$$a_j$$$. $$$(1 \le a_j \le N)$$$
The fourth and final line contains $$$M$$$ integers $$$k_1,...k_M$$$, where the $$$j$$$th faculty member satisfies their rock collection if the total value of the rocks they collect is greater than or equal to $$$k_j$$$. $$$(1 \le k_j \le 10^9)$$$
Output one integer: the maximum number of collections that can be satisfied.
7 4 1 5 3 1 2 3 1 1 3 4 5 5 6 5 6
2
7 3 1 5 3 3 2 3 1 1 2 5 10 1 3
2
In the first example, one possible ordering of faculty members is [1, 3, 2, 4]:
Bernardo just made an amazing lunch for himself, featuring his favorite dish, guacamole! He used a slew of ingredients along with his trusty molcajete, but now its time for him to clean up the mess he made while cooking. He has to hurry, though, in order to make it on time to his job (as a truck driver who transports large amounts of rocks and avocados across the country).
Because he is short on time, Bernardo needs to be efficient as he cleans up, so he will only perform $$$Q$$$ actions to tidy his kitchen.
Bernardo has $$$N$$$ cabinets in his kitchen lined up in a row. Initially, they are all closed, and can contain zero or more ingredients. For each integer $$$i$$$ such that $$$1 \leq i \leq Q$$$, Bernardo will perform an action, either:
After each of the $$$Q$$$ actions, your task is to calculate the length of the longest contiguous subarray of open cabinets as well as the maximum sum of the number of ingredients found within any contiguous subarray of open cabinets.
The input will begin with a line containing two space separated integers, $$$N$$$, and $$$Q$$$ ($$$1 \leq N, Q \leq 10^5$$$).
The next line will contain $$$N$$$ space separated integers, the $$$i$$$th of which, denoted by $$$x_i$$$ ($$$1 \leq x_i \leq 10^9$$$), denoting how many ingredients are initially in the $$$i$$$th cabinet.
The next $$$Q$$$ lines will each describe one of Bernardo's action. The $$$i$$$th of these lines will begin with an integer $$$t$$$ ($$$t \in \{1, 2, 3, 4\}$$$), denoting the type of the $$$i$$$th action.
If $$$t = 1$$$, there will also appear a single integer $$$x_i$$$ ($$$1 \leq x_i \leq N$$$), denoting the cabinet to open. If $$$t = 2$$$, there will also appear two integers, $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq N$$$), denoting the cabinets to swap the ingredients of. If $$$t = 3$$$, there will also appear two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i \leq N$$$, $$$1 \leq y_i \leq 10^9$$$), denoting the cabinet to add $$$y_i$$$ ingredients to. Finally, if $$$t = 4$$$, there will also appear two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq N$$$), denoting that all ingredients from $$$x_i$$$ should move to cabinet $$$y_i$$$.
Output should consist of $$$Q$$$ lines, the $$$i$$$th of which containing two space-separated integers. The first should represent the length of the longest contiguous subarray of open cabinets after the $$$i$$$th action, and the second should represent the maximum sum of the number of ingredients found within any contiguous subarray of open cabinets.
3 3 1 2 3 1 2 2 1 3 1 3
1 2 1 2 2 3
5 5 1 1 1 1 1 1 2 1 4 1 3 1 1 1 5
1 1 1 1 3 3 4 4 5 5
Daniel RuLasso has acquired a large circular platform that he intends to place in the middle of a lake, and has a collection of $$$N$$$ equally weighted rocks (treated as points on the 2D plane) that he wishes to arrange on the platform for decoration. He figures that he can kill two birds with one stone by assigning the task to Kobra Cai students. As all the rocks are conveniently already on the platform, Daniel asks the students to move the rocks into a balanced state on the platform for a more aesthetically pleasing setup.
The platform is centered at the origin of the 2D plane and has infinite radius. An arrangement of rocks on the platform is considered balanced if it will not cause the platform to capsize once placed in water; this requires every rock at $$$(x, y)$$$ to be matched with a corresponding rock that is symmetric about the origin (possibly itself). Multiple rocks can be placed at the same location. However, moving any rock from $$$(a, b)$$$ to $$$(c, d)$$$ requires $$$\left(|a-c|^2 + |b-d|^2\right)$$$ energy units. The Kobra Cai students want to minimize the total energy units expended to achieve a balanced arrangement, and would like to know the minimum amount of energy units needed to do so.
The first line of input contains a single integer $$$N$$$ ($$$1 \leq N \leq 20$$$), representing the number of rocks on the platform. The next $$$N$$$ lines of input contain two integers $$$x, y$$$ ($$$0 \leq |x|, |y| \leq 10^4$$$) representing the current position $$$(x, y)$$$ of a rock.
Output the total amount of energy units necessary to move the $$$N$$$ rocks into a balanced arrangement. Any answer within $$$10^{-6}$$$ of the true solution will be accepted.
2 -1 1 1 1
2.0000000000
1 3 4
25.0000000000
For the first case, both rocks can be moved onto the $$$x$$$-axis.
For the second case, the sole rock just needs to be moved to the origin.