Recent turmoil has left the people of the Earth Kingdom more disconnected than ever. The people lack contact with the outside world and are starting to go hungry. No worries, Avatar Korma is here to save the day!
Korma has analyzed the area and realized that the $$$N$$$ villages (numbered $$$1...N$$$) of the Earth Kingdom are left with only $$$M$$$ roads (which are traversable in both directions). Furthermore, the road infrastructure of the kingdom has been so damaged that every pair of villages has either one or no paths between each other. In addition, they don't have any food!
Faced with this issue, Korma has a plan. Korma will airlift food shipments to some of these villages and with the magic of friendship, she knows that the villagers are incredibly generous and will share food with other villages, if they're able to transport it.
Given the existing roads, Help Korma determine the minimal number of food shipments she will need to feed all the villages.
The first line contains two integers, $$$1 \leq N \leq 10^5$$$ and $$$0 \leq M \leq 10^5$$$.
The next M lines contain a pair of integers $$$A$$$ and $$$B$$$, where $$$1 \leq A, B \leq N$$$ and $$$A \neq B$$$, denoting an existing road connecting villages $$$A$$$ and $$$B$$$.
A single integer denoting the minimal number of food shipments needed to feed all villagers.
5 3 4 2 2 1 5 3
2
The provided roads are bidirectional and unique.
A renowned airbender Tang invents a technique he calls the "Air Moped", where he spins up a perfect sphere and can ride on it. The bigger the sphere, the easier it is to ride on it and the faster it can go.
A student of his is geometrically inclined and wants to know how many lattice points (i.e. how many points $$$(x, y, z)$$$ where $$$x$$$, $$$y$$$ and $$$z$$$ are integers) are on the surface of some air moped that is created. Can you help him?
One integer $$$1 \leq R \leq 7500$$$, the radius of the air moped.
One integer $$$N$$$ denoting the number of integer coordinate points on the surface of the air moped.
1
6
2
6
Cabbage Corp recently bought two airship routes that were being flown with the exact same set of stations. Wanting to cut costs, Cabbage Corp decides that the two routes can be replaced by one route that service some subset of the stations in the same order that appears in both routes. Still wanting some customer satisfaction, however, they still want to maximize the number of stops kept in this new route. Can you help them find the maximum length of the route they can keep?
First line contains $$$1 \leq N \leq 5 \cdot 10^5$$$, the number of stations serviced. The next two lines each contain $$$N$$$ integers $$$0 \leq a_i \lt N$$$, $$$a_i \neq a_j \forall i \neq j$$$ representing the order of stations serviced by each.
Print one integer that corresponds to the length of the longest route common to both routes.
5 0 1 2 3 4 4 1 2 3 0
3
5 4 1 0 3 2 2 0 4 3 1
2
Mei and Kylie are bored at the circus, and decided they wanted to play with fire while Azuko was gone. There are $$$n$$$ flames currently in a line, and each flame has a size $$$s_i$$$. Mei and Kylie want to combine all the flames into 1, but since they aren't fire-benders, it costs a certain amount of energy to merge flames. Given two flames next to each other in line $$$s_i$$$ and $$$s_j$$$, it costs $$$s_i + s_j$$$ to merge the two flames, and then it is replaced with a flame that is $$$s_i + s_j$$$ in size at the same place in line.
Given $$$n$$$ flames and their sizes, determine the minimum cost to merge all the flames!
The first line will contain $$$n$$$ $$$(1 \le n \le 200)$$$, the total number of flames.
The next line will each contain $$$n$$$ integers $$$s_i$$$ $$$(1 \le s_i \le 10^5)$$$, the size of the $$$i^{th}$$$ flame.
A single integer detailing the minimum cost to merge all the flames together into one big flame.
3 1 4 5
15
2 10 9
19
After journeying far and wide, Tang has finally made it to the legendary Fire Temple where he must speak with an ancient Avatar and learn the fate of the world. There's just one problem—the massive door into the inner sanctuary is sealed shut! Fortunately, it appears that there's a puzzle embedded in the door which, when solved, may trigger the unlocking mechanism.
There are six number dials embedded into the door, grouped into three pairs of digits, all separated by colons. The symbol of an hourglass engraved on a nearby wall indicates that the numbers refer to units of time—specifically, hours, minutes, and seconds, in the format $$$\texttt{hh:mm:ss}$$$.
Tang believes that if he sets the dials to show the time of a significant celestial event, then that will solve the puzzle and open the temple door. He has $$$N$$$ guesses about when that celestial event could be and wants to try them all. However, Tang notices that $$$D$$$ unique digits are missing from the dials, making it impossible to precisely set the dials to some of his guesses. Not to fear though, surely the ancient Fire Sages would have designed the door to accept the closest time setting possible that can be displayed on the dials.
Help Tang enter the inner sanctuary of the Fire Temple! For each time guess $$$g_i$$$ that Tang wants to try on the door, output the closest possible time that he will be able to display, given that some digits are missing from the dials.
The first line of input contains an integer $$$D$$$ ($$$1 \leq D \leq 9$$$) denoting the number of digits absent from the puzzle dials. The next line contains $$$D$$$ space-separated integers, sorted in increasing order, which are the digits not available on the six dials.
Then the third line of input contains an integer $$$N$$$ ($$$1 \leq N \leq 10^4$$$) denoting the number of time guesses Tang wants to make. $$$N$$$ lines follow, each containing a guess index $$$i$$$ followed by one of Tang's time guesses $$$g_i$$$ in the six-digit format $$$\texttt{hh:mm:ss}$$$.
For each of Tang's guesses in order, output one line containing the guess index $$$i$$$ followed by the closest possible time setting to $$$g_i$$$ that Tang will be able to input on the door, printed in the same format $$$\texttt{hh:mm:ss}$$$. In the case of a tie between closest settings, output the smaller time quantity.
Note, the values for hours, minutes, or seconds in Tang's guesses will lie in the range from $$$0$$$ to $$$59$$$, and similarly, no hours, minutes, or seconds value greater than $$$59$$$ may be set by Tang on the dials (the digits available on the individual dials prevent this).
2 8 9 4 0 38:15:51 1 32:06:35 2 23:31:47 3 04:05:47
0 37:57:57 1 32:06:35 2 23:31:47 3 04:05:47
Cabbage Dan hears that Avatar Tang will be far away in the Fire Empire land for the day and realizes that it is finally safe for him to set out his cabbage stall for sales. Due to his long period of inactivity, lots of folks are lined up to get one of his world-famous cabbages. As $$$n + m$$$ people gather around the stall, he realizes that $$$n$$$ of them each brought exactly one copper coin, and the remaining $$$m$$$ of them brought exactly one silver coin and no other currency. In the Earth Empire, two copper coins are equivalent to one silver coin and Dan charges a single copper coin for a single cabbage. All his customers are extremely frugal so they will only buy a single cabbage even though they might be able to buy more.
Dan starts the day with $$$k$$$ copper coins but he has no idea what order the $$$n + m$$$ customers will actually come to pay (in fact the customers will come in random order with all orderings being equally likely). Dan doesn't want to run into the embarrassing situation where a customer pays him in a silver coin but he doesn't have a copper coin to give back in change. Thus, he asks you to compute the probability that he can help all his customers and give appropriate change to everyone over the course of the day.
The first and only line of input will contain $$$3$$$ space-separated integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$0 \leq n, m \leq 10^{5}$$$ and $$$0 \leq k \leq 20$$$) where $$$n$$$ is the number of people paying with a copper coin, $$$m$$$ is the number of people paying with a silver coin, and $$$k$$$ is the number of copper coins Cabbage Dan begins the day with.
The probability that Cabbage Dan is able to service all customers and give change to everyone that needs it, answers will be accepted if they are within $$$10^{-6}$$$ of the correct answer.
4 2 1
0.9333333333
5 3 1
0.8571428571
0 2 2
1
Rake Mully has arrived on a new planet to collect a secret resource named hardtogetium. Hardtogetium is freely available on a location called the world tree, and Rake plans to traverse parts of the world tree and collect as much of this resource as he can.
Specifically, the world tree consists of $$$n$$$ hardtogetium mines, where the $$$i$$$th mine contains $$$w_i$$$ tons of hardtogetium. Furthermore, given any two mines, it is guaranteed that there exists a unique path between those two mines that Rake can travel along.
Rake has limited capacity, so he's decided to mine hardtogetium in the following way. Rake will randomly select two distinct vertices, $$$u, v$$$, and will collect all the hardtogetium from the mine with the maximum amount of hardtogetium on the path from $$$u$$$ to $$$v$$$, and he must consume hardtogetium equal to the amount in mine with the minimum hardtogetium on the path to power his mining apparatus. Specifically, given $$$u$$$ and $$$v$$$, he will collect $$$\max_x w_x - min_x w_x$$$ for all $$$x$$$ on the path from $$$u$$$ to $$$v$$$.
Given that he is equally likely to pick any possible $$$u, v$$$, what is the expected number of tons of hardtogetium that Rake will collect. This number can be expressed as a non-reducible fraction $$$\frac{p}{q}$$$, so output $$$pq^{-1} \pmod {10^9 + 7}$$$.
The first line consists of a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ giving the number of mines. The next line consists of $$$n$$$ integers where the $$$i$$$th integer $$$w_i$$$ gives the number of tons of hardtogetium on mine $$$i$$$. The next $$$n - 1$$$ lines consist of two integers $$$u_i, v_i$$$ $$$(1 \leq u_i, v_i \leq n)$$$, which indicates that there is an edge that Rake can travel across between $$$u_i$$$ and $$$v_i$$$.
Output the expected number of tons of hardtogetium that Rake will collect. This number can be expressed as a non-reducible fraction $$$\frac{p}{q}$$$, so output $$$pq^{-1} \pmod {10^9 + 7}$$$.
3 4 5 6 1 2 1 3
666666673
5 5 2 1 4 6 1 2 1 3 2 4 3 5
4
For the first input, Rake can expect to collect $$$\frac{6 - 4 + 6 - 4 + 5 - 4}{3}$$$ tons, which gives us $$$\frac{5}{3}$$$.
You are an elite metalbending soldier personally selected by Cuvira to aid her in piloting the "secret weapon" that will crush the enemies of the Earth Empire. Although you are a proficient bender, Cuvira would like to do the honors of moving the mech herself, and has instead delegated you to quickly calculating the necessary adjustments to keep the mech running smoothly.
The state of the contraption can be represented as a single array of $$$N$$$ integers, which is initially filled with zeroes. Cuvira will periodically shout out commands to update the array based on her planned movements and requests for information about the array after the updates that have occurred thus far. A command to update the array will consist of two integers $$$1 \leq x \leq y \leq N$$$, and you will add $$$(a-x+1)(a-x+2)$$$ to the $$$a$$$-th element of the array for every $$$a$$$ between $$$x$$$ and $$$y$$$, inclusive. A request for information about the array will also consist of two integers $$$1 \leq x \leq y \leq N$$$, but you will instead reply with the sum of array elements indexed from $$$x$$$ to $$$y$$$, inclusive, modulo $$$10^9+7$$$.
As Cuvira diverted her entire investment into the main artillery built into the mech, she neglected to provide an onboard computer/HUD for you to keep track of the computations. Lucky for you, there is a programmable calculator in your pocket that you can use to efficiently respond to Cuvira's queries.
The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \leq N, Q \leq 10^5$$$) that represent the length of the mech array and the number of commands/requests Cuvira shouts out to you, respectively. The next $$$Q$$$ lines each contain three space separated integers $$$t$$$, $$$x$$$, and $$$y$$$ ($$$1 \leq t \leq 2$$$ and $$$1 \leq x \leq y \leq N$$$). For a command as described above, $$$t = 1$$$, and otherwise $$$t = 2$$$ to denote a request. The meaning of integers $$$x$$$ and $$$y$$$ in each case are described above.
Print out a single integer for each request Cuvira makes on its own line, and in the order in which they are given to you.
8 4 1 1 8 2 7 8 1 4 6 2 5 6
128 90