Maria is a big fan of all things sweet, especially maple syrup. Luckily, she's managed to find a large grove of maple trees and wants to collect as much syrup as she can! The grove consists of $$$n$$$ trees and $$$n - 1$$$ paved roads that Maria can travel on. The grove is connected, so Maria can reach any tree from any start tree by traveling along these paved roads. Each tree has an associated syrup value, $$$s_i$$$, which gives how much syrup Maria can potentially extract from the tree.
Unfortunately, Maria doesn't want to risk getting lost in the grove and straying too far away from her starting position. Given that Maria can start from any tree in the grove and collect syrup from all trees that are directly connected to her starting tree with a single road, find out the maximum amount of syrup that Maria can collect!
The first line is a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, which gives the number of trees in the maple grove. The next line consists of $$$n$$$ integers $$$s_i$$$ $$$(1 \leq s_i \leq 1000)$$$, where the $$$i$$$th value gives the syrup values for the $$$i$$$th tree. The next $$$n - 1$$$ lines consist of two integers $$$u_i, v_i$$$ $$$1 \leq u_i, v_i \leq n$$$, which gives two trees that are connected by a paved road.
Output a single integer giving the maximum amount of syrup that Maria can collect.
4 1 2 3 4 1 2 2 3 3 4
9
If Maria starts at tree $$$3$$$, she can collect $$$2 + 3 + 4 = 9$$$ syrup overall.
The Once-ler is back with his lucrative Thneed business!
There are $$$N$$$ truffula trees in a row, and the Once-ler visits them in order, starting at the first truffula tree. He starts with a Super-Axe-Hacker with durability $$$d$$$.
Each truffula tree has toughness $$$t_i$$$, and the Once-ler can choose to chop down a truffula tree if and only if the durability of his Super-Axe-Hacker is greater than or equal to the current tree's toughness ($$$d \ge t_i$$$). Every time the Once-ler chops down a tree, the durability of his Super-Axe-Hacker decreases by one.
However, this time, the Once-ler wants to avoid chopping down trees unsustainably and angering the Lorax. Therefore, the Once-ler refuses to chop down more than one tree in a row.
However, he still needs to make a profit. Each truffula tree he cuts down can make one Thneed. To reach his quota, he needs to make $$$k$$$ Thneeds.
What is the minimum starting durability $$$d_{min}$$$ of the Once-ler's Super-Axe-Hacker that guarantees at least $$$k$$$ Thneeds will be made?
The first line contains two integers $$$N$$$ and $$$k$$$ where $$$N$$$ is the number of truffula trees, and $$$k$$$ is the number of Thneeds the Once-ler needs to make. ($$$1 \le N \le 10^5, 1 \le k \le N$$$)
The next line contains $$$N$$$ integers $$$t_1...t_n$$$ where $$$t_i$$$ is the toughness of the $$$i$$$th truffula tree. ($$$1 \le t_i \le 10^9$$$)
Output $$$d_{min}$$$, the minimum starting durability that guarantees at least $$$k$$$ Thneeds will be made. If it is not possible to make $$$k$$$ Thneeds while satisfying all the requirements, output $$$-1$$$.
6 2 4 9 2 1 2 10
3
6 5 8 8 8 8 8 8
-1
In the first example, the Once-ler starts with durability $$$d=3$$$, and chops down the 3rd and 5th trees to create 2 Thneeds.
In the second example, the Once-ler cannot make 5 Thneeds without angering the Lorax.
Alfred, an avid botanist and lumberjack, while traveling across the state of California, has come across an absolutely humongous giant sequoia tree. Being the botanist that he is, Alfred would like to examine this fascinating giant sequoia tree in great depth. More specifically, he would like to observe its branches.
Each of the $$$n$$$ branches of the giant sequoia tree has a specific length associated with it, and certain branches are longer than others. Because of this, Alfred was inspired to solve a certain problem, though his skills in computing are quite limited, and he has come to you for help!
Alfred would like to figure out the longest strictly-increasing consecutive sub-array (a sub-array such that $$$a_{i+1} \gt a_i$$$ for each $$$i$$$ except the last in the sub-array) of the giant sequoia tree branches. However, he is torn between his love for botany and his duties as a lumberjack. He can either choose to leave the tree alone and compute the answer directly, or he can chop off a consecutive sub-array of size exactly $$$k$$$ from the giant sequoia tree before running his computations. More formally, Alfred can choose some index $$$i$$$ such that $$$i + k - 1 \leq n$$$ and then remove the branches at indices $$$i, i + 1, i + 2, \dots, i + k - 1$$$. Since he doesn't have all that much energy after hiking all day, he can only perform this action a maximum of one time.
Given his choices, can you help Alfred find the longest strictly-increasing consecutive sub-array within the giant sequoia tree after at most one chop of size $$$k$$$?
The first line of input will contain a two space-separated integers $$$n$$$ ($$$1 \leq n \leq 10^5$$$) and $$$k$$$ ($$$0 \leq k \leq n$$$), the number of branches of the giant sequoia tree and the number of possible branch removals, respectively.
The second line of input will contain $$$n$$$ space separated integers $$$a_i$$$ ($$$1 \leq a_i \leq 10^9$$$ for $$$1 \leq i \leq n$$$). The $$$i$$$-th integer on the second line represents the length of the $$$i$$$-th branch of the giant sequoia tree starting at the lowest branch.
The output should consist of a single integer $$$x$$$, where $$$x$$$ represents the longest strictly-increasing sub-array of branches after either $$$0$$$ or $$$k$$$ consecutive branch removals.
3 2 1 2 3
3
6 2 1 2 4 3 5 6
4
Alfred can choose to remove either $$$0$$$ or $$$k$$$ consecutive branches from the giant sequoia tree. Actions which are strictly disallowed are removing $$$x$$$ branches where $$$x \not\in \{0, k\}$$$ and/or removing a set of branches which are non-contiguous.
Cacti are basically desert trees, and they deserve some love too.
After staring at a bunch of cacti, you've realized that, indeed, cacti are quite beautiful! In fact, as you looked at them more, you realize that some "perfect cacti" look geometric:
Not only are cacti geometric, but they're also recursive (like trees)! However, so far you've only been able to cultivate perfect $$$k$$$-cacti of height 1 – that is, cacti that resemble perfect polygons with $$$k$$$ sides.
Suddenly, you remember something from class: just like trees, cacti can be graphs too! In fact, we can treat the perfect cactus graph as an unweighted, undirected graph between vertices (of the polygon). You begin to wonder: given a perfect cacti graph, how long does it take to get from one node to another? Or, even better – can you find these values, even as edges are broken and restored?
The first line begins with three integers, $$$k$$$ $$$(3 \leq k \leq 10^{18})$$$, $$$h$$$ $$$(h=1)$$$ and $$$q$$$ $$$(1 \leq q \leq 10^5)$$$. $$$k$$$ and $$$h$$$ describe the cactus graph (which is a $$$k$$$-cactus of height $$$h$$$).
It is guaranteed that the number of nodes in the perfect cactus graph does not exceed $$$10^{18}$$$.
Then, $$$q$$$ lines follow, each containing three integers: $$$a, i, j$$$. The type of query is determined by $$$a$$$:
- $$$a=1$$$: Find the minimum number of edges needed to get from vertex $$$i$$$ to vertex $$$j$$$.
- $$$a=2$$$: Remove the edge from vertex $$$i$$$ to vertex $$$j$$$. It is guaranteed that this edge exists in the perfect cactus graph.
- $$$a=3$$$: Restore the edge from vertex $$$i$$$ to vertex $$$j$$$. It is guaranteed that this edge used to exist in the perfect cactus graph, but is currently not in the graph.
Since the graph is not directly given to you, the vertices are labelled $$$0 \ldots k-1$$$, starting at the root, and going clockwise.
For each query where $$$a=1$$$, print out the minimum number of edges needed to get from vertex $$$i$$$ to vertex $$$j$$$. If no path exists, output -1.
10 1 7 1 0 8 2 0 9 1 0 8 2 0 1 1 0 8 3 0 9 1 0 8
2 8 -1 2
In an effort to "go green", a city is investigating planting a forest of sling-trees to replace its current network of highways and stroads.
Under the new transit plan, each of the city's $$$1 \leq N \leq 10^5$$$ neighborhoods would get a single sling-tree. To navigate the network, the citizens would climb into a tree, then repeatedly sling themselves to another tree.
However, not every tree can reach every other tree. Each sling-tree $$$i$$$ has a power $$$p_i$$$ and resistance $$$r_i$$$, where $$$1 \leq p_i, r_i \leq 10^6$$$. To sling from tree $$$i$$$ to tree $$$j$$$, the power of tree $$$i$$$ must not exceed the resistance of tree $$$j$$$. In other words, this requires that $$$p_i \leq r_j$$$.
Numerous groups have raised concerns about this system, specifically worrying about experiencing in-air collisions and getting back home. To reassure the public, the city has made two stipulations for the network.
1) To minimize in-air collisions, each tree will only accept launches from one other tree
2) Citizens will never get stuck in the system (they will be able to return to their starting tree).
Given the $$$N$$$ planned sling-trees and their power and resistances, determine whether the city can keep its promises.
The first line is a single integer, $$$N$$$, giving the number of neighborhoods. The next $$$N$$$ lines consist of two integers each, $$$p_i$$$ and $$$r_i$$$, for the $$$i$$$-th tree.
A single line, "YES" or "NO", whether we can navigate from each sling-tree back to itself.
3 5 2 9 10 1 6
YES
3 5 4 8 6 5 10
NO
Baobab trees, native to regions of Africa and Australia, are some of the stoutest trees in the world, meaning they bear immensely thick trunks of up to 35 feet in diameter! The trunk of a baobab must be thick enough for it to store plenty of water inside during the rainy season so that the tree can survive through harsh, dry seasons on the African savanna.
Kofi wants to plant several varieties of baobab trees on a $$$h\times w$$$ rectangular plot of land. His primary concern is whether all of the $$$T$$$ trees he wants to plant will be able to fit together within the plot upon reaching maturity. For the $$$i^{th}$$$ seed he wants to plant, Kofi has estimated the trunk and root area that the tree is expected to grow to, in terms of a square bounding box with side length $$$t_i$$$. Help Kofi determine where to plant his baobab seeds so that all of the trees will fit!
The first line of input contains two space-separated integers $$$h$$$ and $$$w$$$ $$$(1 \leq h, w \leq 6)$$$, the height and and width of Kofi's plot of land.
The next line of input contains a single integer $$$T$$$ $$$(1 \leq T \leq 26)$$$, the number of trees Kofi wishes to plant.
The last line of input contains $$$T$$$ space-separated integers $$$t_i$$$ ($$$1 \leq t_i \leq \min(h, w)$$$), each denoting the side length of the mature bounding box for the $$$i^{th}$$$ baobab that Kofi wishes to plant.
If it is not possible for Kofi to plant all of his baobabs together in the plot, print IMPOSSIBLE.
Otherwise, output a $$$h\times w$$$ grid representing a valid layout in which Kofi could plant all of his desired trees. Mark the cells of each mature tree bounding box with a unique upper-case letter corresponding to that tree, and mark cells containing no bounding box with a '.'. Note, you may print any $$$h\times w$$$ grid representing a valid configuration of the trees, so long as $$$h$$$ is the number of rows and $$$w$$$ the number of columns in the plot.
6 6 10 2 1 1 2 1 2 1 2 1 3
J J J I I E J J J I I D J J J H H C G G B H H A G G F F . . . . F F . .
6 5 4 4 2 2 2
IMPOSSIBLE
Ada is in charge of grooming the $$$n$$$ apple trees lined up at the front row of the orchard in order to win the most beautiful orchard award.
Sydney, the judge of the contest and once a competitive programmer, has a very particular scheme to calculate the beauty of the row. The leftmost tree in the row has index $$$0$$$, the tree immediately to its right has index $$$1$$$, and so on and so forth until the $$$n$$$th tree which has index $$$n - 1$$$. If the $$$i$$$th tree has $$$a_i$$$ apples then the beauty $$$b$$$ of the row is determined by:
$$$$$$ b = \Sigma_{i = 0}^{n - 1} \left(i \oplus a_{i}\right) $$$$$$
However, Sydney is extra quirky so she will immediately disqualify any row of apple trees that either has two trees with the same number of apples on them or if a tree has more than $$$n - 1$$$ apples (a tree is allowed to have $$$0$$$ apples). Ada figures out that the assignment of the number of apples to the $$$n$$$ trees must be a permutation of the integers from $$$0$$$ to $$$n - 1$$$ (inclusive).
Ada is stressed because there are far too many possible permutations to calculate by hand and she really wants to win this contest. To make sure there is no chance of Ada losing, help her by calculating the maximum beauty score possible for the row of $$$n$$$ trees and the assignments of the number of apples for each tree that allows for that score.
Note: The $$$c \oplus d$$$ operation refers to the bitwise exclusive or operation where the $$$i$$$th bit of the result is a $$$1$$$ if $$$c$$$ and $$$d$$$ do not have the same $$$i$$$th bit (and $$$0$$$ otherwise). You can calculate this with the ^ operation in languages like Java, C++, and Python.
The first and only line of input contains a single positive integer $$$n$$$ ($$$2 \leq n \leq 10^{6}$$$) representing the number of trees in the row of the orchard.
In the first line, output the maximum possible beauty of the row.
In the second line, output any space-separated permutation $$$p$$$ of the numbers from $$$0$$$ to $$$n - 1$$$ (inclusive) such that if the $$$i$$$th tree in the row was left with $$$p_i$$$ apples, the overall beauty of the row would be equal to the number you printed in the first line.
5
20 0 2 1 4 3
In the first test case, the beauty of the row would be equal to $$$0 \oplus 0 + 1 \oplus 2 + 2 \oplus 1 + 3 \oplus 4 + 4 \oplus 3 = 20$$$ which is the same as the first number printed (trying all other permutations, we see we can't do better than $$$20$$$).
Groot, Rocket Raccoon's personal muscle in the Guardians of the Galaxy, is a special variant of the ceiba tree. Scientists at Stark Enterprises are curious as to how the resilient Flora colossus survived with its genetic material completely preserved throughout "The Blip". The sentient ceiba tree is more than happy to provide a piece of bark for the lab technicians to analyze; however, the genetic material of ceiba trees is circular in nature, which makes it difficult to compare samples due to rotational possibilities. Petra, the head of lab tech, decided to store data on samples based on a rather odd convention (due to boredom from integer hashing).
Each ceiba tree sample can be represented as a string $$$G$$$ of $$$N$$$ lowercase alphabetical characters. The representation of the sample that will be deterministically stored for a given string is based on the integer $$$1 \leq i \lt N$$$ that creates the lexicographically maximal concatenation of the reversed first $$$i$$$ characters of $$$G$$$ and the reversed last $$$N-i$$$ characters of $$$G$$$. Although Petra came up with this idea, she actually has no idea how to efficiently compute the stored representation for large amounts of samples. You, the new intern, are tasked with writing a program to help the senior lab member with her deliverables.
The first and only line of input will contain a single string $$$G$$$ as described above. It will be at most $$$10^6$$$ characters long.
Output a single line with the stored representation of $$$G$$$.
groot
rgtoo
bzyaa
zbaay
There are two parts for this problem. This is Part 2, which extends on the problem given in Part 1. Please read Part 1 first for the problem details.
Cacti are basically desert trees, and they deserve some love too.
After staring at a bunch of cacti, you've realized that, indeed, cacti are quite beautiful! In fact, as you looked at them more, you realize that some "perfect cacti" look geometric:
After studying cacti for a bit longer, you've finally been able to come up with this construction for a perfect $$$k$$$-cactus of height $$$h$$$:
- Start with a regular polygon with $$$k$$$ edges, and designate a root vertex.
- If this is cactus has a height $$$h \gt 1$$$, then each non-root vertex of this polygon grows a $$$k$$$-cactus of height $$$h-1$$$, where the sub-cacti are rooted at the point they grew from.
Based on this definition, the cactus shown above is a $$$3$$$-cactus of height 3.
With this more general definition of $$$k$$$-cacti of height $$$h$$$, can you solve the same set of queries?
The first line begins with three integers, $$$k$$$ $$$(3 \leq k \leq 10^{18})$$$, $$$h$$$ $$$(1 \leq h \leq 10^{18})$$$ and $$$q$$$ $$$(1 \leq q \leq 10^5)$$$. $$$k$$$ and $$$h$$$ describe the cactus graph (which is a $$$k$$$-cactus of height $$$h$$$).
It is guaranteed that the number of nodes in the perfect cactus graph does not exceed $$$10^{18}$$$.
Then, $$$q$$$ lines follow, each containing three integers: $$$a, i, j$$$. The type of query is determined by $$$a$$$:
- $$$a=1$$$: Find the minimum number of edges needed to get from vertex $$$i$$$ to vertex $$$j$$$.
- $$$a=2$$$: Remove the edge from vertex $$$i$$$ to vertex $$$j$$$. It is guaranteed that this edge exists in the perfect cactus graph.
- $$$a=3$$$: Restore the edge from vertex $$$i$$$ to vertex $$$j$$$. It is guaranteed that this edge used to exist in the perfect cactus graph, but is currently not in the graph.
Since the graph is not directly given to you, the vertices are indexed in the following way. For each polygon, number the vertices $$$0 \ldots k-1$$$, starting at the root and moving in clockwise order. Each index $$$i$$$, when parsed as a base $$$k$$$ number, can be interpreted as a path, where each digit corresponds to a vertex in the polygon to move to. See the notes below for details.
Also, note that the numbering convention given in Part 1 is the $$$h=1$$$ case of the above numbering.
For each query where $$$a=1$$$, print out the minimum number of edges needed to get from vertex $$$i$$$ to vertex $$$j$$$. If no path exists, output -1.
10 1 7 1 0 8 2 0 9 1 0 8 2 0 1 1 0 8 3 0 9 1 0 8
2 8 -1 2
3 3 11 1 13 22 2 1 2 2 3 13 1 13 22 2 0 1 1 13 22 1 13 17 3 0 1 1 13 22 2 0 2 1 13 22
5 7 -1 4 7 -1
The perfect cactus in the problem description is numbered as follows. The red numbers are the vertex labels in the polygon, the blue numbers are the index of each vertex, written in base 3.
For example, the vertex labelled $$$17 = 122_3$$$ corresponds to starting at the root, moving to vertex 1 in the polygon, then moving to vertex 2 in the next polygon, and then finally moving to vertex 2 in the final polygon.