Jesse has $$$n$$$ red pandas. Each of them is assigned an integer ID number. It is possible that multiple red pandas have the same ID number.
He asks them to form a single-file line sorted by ID number, but due to copious confusion, they line up in a random order! Unsure of what to do, Jesse consults his friend Jerry for help, who claims to have a perfect idea: the Cereal Sorter, a device he recently invented!
First, the Cereal Sorter will create a new empty line. Then, while there are still red pandas in the first line, it does the following:
- First, it scans through the first line in $$$k$$$ seconds, where $$$k$$$ is the number of red pandas in the first line.
- Let $$$m$$$ be the minimum ID of a red panda in the first line. The Sorter instantly removes all red pandas with ID $$$m$$$ from the first line and teleports them to the end of the second line.
See the notes for a better understanding of this process.
Jesse is convinced that this process may take a long time, as it seems quite complex. Please help him out by determining how many seconds the sorting operation will take!
The first line contains $$$n$$$, the number of red pandas ($$$1 \le n \le 10^6$$$).
The second line of input contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, the IDs of the red pandas ($$$1 \le a_i \le 10^6$$$).
Output the answer on a single line.
4 3 2 2 1
8
5 1 8 8 8 1000000
10
In the first test, the process goes like this:
- Initially, the first line is $$$[3, 2, 2, 1]$$$ and the second line is $$$[]$$$.
- The Sorter scans through the first line in $$$4$$$ seconds. The minimum ID in the first line is $$$1$$$, so it moves the red panda with ID $$$1$$$ to the second line. The first line is now $$$[3, 2, 2]$$$, and the second line is now $$$[1]$$$.
- The Sorter scans through the first line in $$$3$$$ seconds. The minimum ID in the first line is $$$2$$$, so it moves the red pandas with ID $$$2$$$ to the second line. The first line is now $$$[3]$$$, and the second line is now $$$[1, 2, 2]$$$.
- The Sorter scans through the first line in $$$1$$$ second. The minimum ID in the first line is $$$3$$$, so it moves the red panda with ID $$$3$$$ to the second line. The first line is now $$$[]$$$, and the second line is now $$$[1, 2, 2, 3]$$$.
In total, this takes $$$4+3+1=8$$$ seconds.
Problem Credits: Aryansh Shrivastava
Jesse has stolen a treasured cereal box from his principal, and needs to avoid getting caught!
Jesse's school can be modeled by a rectangle on a 2-D coordinate plane, with its lower left corner at $$$(0,0)$$$ and top right corner at $$$(H, K)$$$.
Jesse will use his escape-scanner 3000 to find a place to escape. It must be placed on integer coordinates, and will scan every point within a radius $$$R$$$.
However, Jesse's principal has hired $$$n$$$ hall monitors to catch him, standing at distinct integer coordinates in the school. If the scanner scans a point containing one of the monitors, scans on the border, or scans outside the school, it fails (and Jesse gets caught)!
What is the biggest radius $$$R$$$ he can achieve so that his escape-scanner does not fail?
Your answer is considered correct if its absolute or relative error does not exceed $$$10^{-6}$$$.
Formally, let your answer be $$$a$$$, and the jury's answer be $$$b$$$. Your answer is accepted if and only if $$$\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$$$.
The first line contains $$$H$$$, $$$K$$$, and $$$n$$$ ($$$1 \le H, K, n \le 200$$$).
The next $$$n$$$ lines, contain two integers each, $$$x_i$$$ and $$$y_i$$$ $$$(0 \le x_i \le H, 0 \le y_i \le K)$$$, signifying the location of a hall monitor.
It is guaranteed that all $$$(x_i, y_i)$$$ are distinct.
Print the maximum value of $$$R$$$ that will allow Jesse to use his escape-scanner 3000.
10 10 5 1 4 2 3 9 9 4 6 5 5
2.8284271
The maximal radius of scanning can be achieved when Jesse places his scanner on the point $$$(7, 3)$$$.
Problem Credits: Chongtian Ma
Envy plays a game where he repeatedly rolls a standard six-sided die $$$n$$$ times in a row. On each roll he writes down the number he rolls.
When he is done, he multiplies all these numbers together to get $$$k$$$.
Unfortunately, Envy ate way too much cereal after he played the game, and took a long nap.
Now, he has forgotten what numbers he rolled!
Given $$$n$$$ and $$$k$$$, find the maximum possible sum of the numbers he rolled.
You are given $$$t$$$ independent test cases ($$$1 \leq t \leq 10$$$).
The first line of input will contain a single integer $$$t$$$.
For each test case, you are given two space separated integers, $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 5000$$$), ($$$1 \leq k \leq 10^6$$$)
For every test, print the maximum possible sum of all the numbers Envy rolled.
If there is no possible sequence of die rolls that satisfies $$$n$$$ and $$$k$$$, output -1.
5 6 84 5 12 6 64 5 100 6 33
-1 11 15 16 -1
For the first test case, no possible answer exists. For the second test case, one possible sequence of dice rolls to make the maximum sum is as follows: $$$1 \rightarrow 1 \rightarrow 2 \rightarrow 1 \rightarrow 6 \rightarrow 1$$$.
There are a total of $$$5$$$ numbers, which satisfies $$$n$$$, and a product of $$$12$$$, which satisfies $$$k$$$. It can be proved that $$$1 + 1 + 2 + 1 + 6 + 1 = 11$$$ is the maximal sum.
The Global Cereal Festival (GCF) is happening at CerealLand!
GCF will have $$$n$$$ ($$$1 \leq n \leq 18$$$) attendees, labeled $$$1 \dots n$$$.
In order to engage the crowd, one of the organizers of GCF, Jesse, decides to get them to perform the permutation dance.
In this dance, the attendees stand from left to right, and then permute themselves in every possible manner, from the smallest lexicographic position to the largest lexicographic position.
A permutation $$$a$$$ of length $$$n$$$ is lexicographically smaller than a string $$$b$$$ of length $$$n$$$ if and only if the following holds:
- In the first position where $$$a$$$ and $$$b$$$ differ, $$$a$$$ has a number that is less than the corresponding letter in $$$b$$$.
For example, if $$$n = 3$$$, the attendees would permute themselves in this order:
$$$[1, 2, 3] \rightarrow [1, 3, 2] \rightarrow [2, 1, 3] \rightarrow [2, 3, 1] \rightarrow [3, 1, 2] \rightarrow[3, 2, 1]$$$.
Jesse is interested in knowing the sum of the distances attendee $$$1$$$ moves between successive permutations.
For example, when $$$n = 3$$$, the first attendee moves from position $$$1$$$ in the $$$1$$$st permutation to position $$$2$$$ in the $$$3r$$$d permutation, to position $$$3$$$ in the $$$4$$$th permutation, to position $$$2$$$ in the $$$5$$$th permutation, to position $$$3$$$ in the $$$6$$$th permutation. In total, he moves a distance of $$$1 + 1 + 1 + 1 = 4$$$.
A single integer $$$n$$$.
Output how many times the first members moves in a permutation dance of length $$$n$$$,
3
4
The sample case output is explained in the statement above.
it is important how far attendee $$$1$$$ moves, so $$$[1, 3, 2] \rightarrow [3, 2, 1]$$$ means a distance of $$$2$$$.
Problem Credits: Mythreya Dharani, Ariel Shehter.
Eric has joined his district science fair with his engineering project The Palindromic Cereal Bridge. Envy is envious of Eric's unique project, so he decides to ruin it while Eric goes to talk with the CerealCodes team.
A project can be described by an array $$$a_1, a_2, \ldots, a_k$$$ of length $$$k$$$ consisting of positive integers. We call a project jeopardized if it is not palindromic — that is, there is some $$$1 \le i \le k$$$ such that $$$a_i \neq a_{k - i + 1}$$$.
Envy likes the integers $$$l$$$ and $$$r$$$, and wants to know how many jeopardized projects there are satisfying the following: $$$$$$l \le \sum\limits_{i = 1}^{k}a_i \le r$$$$$$
Since the answer may be very large, output it modulo $$$1\,000\,000\,007$$$.
Please help him figure this out!
The input consists of multiple tests. The first line contains $$$t$$$, the number of test cases ($$$1 \le t \le 2 \cdot 10^5$$$).
The only line of each test case contains $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le 10^5$$$).
For each test case, print the answer, modulo $$$1\,000\,000\,007$$$.
4 2 3 1 1 4 4 123 456
2 0 4 318860857
In the first test, there are $$$2$$$ jeopardized arrays:
- $$$[1, 2]$$$
- $$$[2, 1]$$$
In the second test, there are no jeopardized arrays.
In the third test, there are $$$4$$$ jeopardized arrays:
- $$$[1, 1, 2]$$$
- $$$[2, 1, 1]$$$
- $$$[3, 1]$$$
- $$$[1, 3]$$$
Problem Credits: Jesse Choe and Eric Hsu
The CerealCodes gift shop contains a row of $$$n$$$ boxes of cereal. The $$$i$$$-th box contains $$$c_i$$$ pieces of cereal.
Unfortunately, one group of competitors has thought up a scheme to buy all of the cereal!
The group consists of $$$k$$$ members. They will divide the row of cereal into $$$k$$$ non-empty contiguous subsegments, and the $$$i$$$-th member will buy all the cereal boxes in the $$$i$$$-th subsegment.
Say that the $$$i$$$-th subsegment consists of all cereal boxes from $$$l_i$$$ to $$$r_i$$$. Then the smugness of the $$$i$$$-th competitor is $$$s_i = c_{l_i} | c_{l_i + 1} | \ldots | c_{r_i - 1} | c_{r_i}$$$.
The overall sadistic satisfaction the members feel (at the humiliation of CerealCodes) is equal to $$$s_1 \& s_2 \& \ldots \& s_{k-1} \& s_k$$$.
What is the maximum possible satisfaction that the group could feel as a result of this scheme?
Here, $$$|$$$ and $$$\&$$$ denote the bitwise OR and bitwise AND operations respectively.
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).
The next line contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le 10^9$$$).
Output the maximum satisfaction the group can feel.
6 2 10 4 3 1 8 7
15
Here is one plan that maximizes the humiliation:
- Member $$$1$$$ buys the subsegment $$$[1, 3]$$$, and has smugness $$$10 | 4 | 3 = 15$$$.
- Member $$$2$$$ buys the subsegment $$$[4, 6]$$$, and has smugness $$$1 | 8 | 7 = 15$$$.
The total satisfaction is equal to $$$15 \& 15 = 15$$$.
Problem Credits: Agastya Goel
Ariel is on a vacation where he must visit $$$n$$$ locations famous for their cereal, numbered $$$1 \dots n$$$.
He will visit all the locations in some order, where the $$$i$$$th location he visits is $$$a_i$$$.
Therefore, his order of visiting locations forms a permutation of length $$$n$$$. Note that a permutation of length $$$n$$$ is a sequence containing every number from $$$1 \dots n$$$ exactly once.
Ariel thinks an amazing permutation is one where there are no indices $$$(i, j, k)$$$ where ($$$1 \le i \lt j \lt k \leq n$$$) such that $$$j - i = k - j$$$ and $$$a_j - a_i = a_k - a_j$$$.
Find a permutation of $$$1 \dots n$$$ that satisfies this (the $$$i$$$th number is the $$$i$$$th location Ariel visits).
A single integer $$$n$$$ ($$$1 \leq n \leq 1000$$$).
A single line containing a space separated permutation of $$$1 \dots n$$$ such that Ariel has an amazing vacation.
Any output satisfying the above constraints will be accepted.
4
1 2 4 3
10
10 1 7 8 2 4 9 5 6 3
If we take the first sample case output, no three indices validate the above condition.
For example, if $$$(i, j, k)$$$ = $$$(1, 2, 4)$$$, $$$2 - 1 \neq 4 - 2$$$.
Another example would be $$$(i, j, k)$$$ = $$$(1, 2, 3)$$$. Although, $$$j - i = k - j$$$ since $$$2 - 1 = 3 - 2$$$, $$$a_j - a_i \neq a_k - a_j$$$ since $$$4 - 2 \neq 2 - 1$$$.
Problem Credits: Ariel Shehter
Envy and Batrick have stolen some of Ary's prized cereal!
Unfortunately, Ary has an obstacle for your escape: a $$$n$$$ x $$$m$$$ grid, where each cell is either a balloon or a bomb.
Envy and Batrick walk across the grid one row at a time holding a barbed wire between them (that can pop balloons and also activate bombs).
First, Envy and Batrick starts at position $$$i$$$ and $$$j$$$ $$$(1 \le i, j \le m)$$$ and approach the first row of the grid, popping all balloons in the range $$$[min(i, j), max(i, j)]$$$ within that first row. Note that Envy can be on the left or on the right of Batrick.
Then, they repeat the following process until exiting the grid out the bottom row: Envy or Batrick (at most one of them) may change their horizontal position (move to some $$$1 \le k \le M$$$) before approaching the next row of the grid and again popping all balloons and activating bombs in the inclusive range between them.
What is the maximum number of balloons Bessie and Elsie can pop without activating any bombs?
The first line contains $$$2$$$ integers, $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 10^3)$$$
Next $$$n$$$ lines contain $$$m$$$ characters describing the board (where '#' is a bomb and '.' is a balloon).
Output one integer, the maximum number of balloons that they can pop in the grid without activating any bombs, or -1 if they are guaranteed to turn on at least one bomb.
3 5 ..... ...#. #....
11
5 5 ..... .##.# ####. .#### .....
-1
5 5 ..... ...#. ..... ..... .....
23
For the first sample, Envy and Batrick can start at horizontal positions $$$i = 1$$$ and $$$j = 5$$$, popping $$$5$$$ balloons in the first row of the grid.
Then, Batrick can move to position $$$j = 2$$$, so that they pop $$$2$$$ balloons in the second row of the grid.
Finally, Envy can move to position $$$i = 5$$$, so that Envy and Batrick pop $$$4$$$ balloons in the last row of the grid, for a total of $$$5 + 2 + 4 = 11$$$ balloons popped.
It can be shown that this is the maximum amount of balloons they can pop.
Problem Credits: Ariel Shehter
Thomas and his army of red pandas are on a plane, attempting to smuggle a load of stolen cereal.
There are $$$n$$$ red pandas standing in a line on the plane, numbered $$$1, 2, \ldots, n$$$, and $$$n$$$ cereal boxes, also numbered $$$1, 2, \ldots, n$$$. The $$$i$$$-th red panda is currently standing in front of the $$$i$$$-th box.
The $$$i$$$-th red panda has a strength $$$a_i$$$. The $$$j$$$-th box has a weight $$$w_j$$$.
You want to push all the boxes off the plane. To accomplish this, you are allowed to perform the following operation.
- Choose some $$$1 \le l \le r \le n$$$, such that all the following hold:
- For all $$$l \le i \le r$$$, there is exactly one box at position $$$i$$$.
- Either there is no box at position $$$l - 1$$$, or $$$l = 1$$$.
- The sum of weights $$$w_l + w_{l + 1} + \ldots + w_{r-1} + w_r$$$ does not exceed $$$a_r$$$.
- The $$$r$$$-th red panda will push all boxes in the range $$$[l, r]$$$ to the left. In other words, for all $$$l \le i \le r$$$, the box at position $$$i$$$ will be moved to position $$$i-1$$$.
If a box is pushed from seat $$$1$$$, it will be pushed off the plane.
Help Thomas determine the minimum number of operations needed to push all boxes off the plane, or that it is impossible.
The input consists of multiple tests. The first line contains $$$t$$$, the number of tests ($$$1 \le t \le 1000$$$).
The first line of each test contains $$$n$$$ ($$$1 \le n \le 6000$$$).
The second line contains $$$n$$$ integers $$$w_1, w_2, \ldots, w_n$$$, the weights of the cereal boxes ($$$1 \le w_i \le 10^9$$$).
The third line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$, the strengths of the red pandas ($$$1 \le a_i \le 10^9$$$).
It is guaranteed that the sum of $$$n$$$ over all tests does not exceed $$$6000$$$.
If it is impossible to push all boxes off, print -1.
Otherwise, print the minimum number of operations needed to push all boxes off the plane.
243 1 3 23 4 2 553 1 1 3 23 4 4 2 5
7 11
In the first sub-case, all boxes can be pushed off of the plane in 7 commands.
One way is as follows:
First, the $$$2$$$nd red panda pushes the range of boxes $$$[1,2]$$$.
Then, the $$$4$$$th red panda will push the range $$$[3,4]$$$.
The $$$2$$$nd red panda can then push the range $$$[1,2]$$$ again.
The $$$1$$$st red panda can push box $$$3$$$ off of the plane.
Then, the $$$3$$$rd, $$$2$$$nd, and $$$1$$$st red panda push box $$$4$$$ in that order.
Problem Credits: Ariel Shehter
Envy has a cereal surplus so instead of eating his cereal, he decides he will play with them for a little bit.
Envy has $$$k$$$ distinct cereal pieces arranged on an $$$n$$$-by-$$$n$$$ grid. Each cell contains at most one piece of cereal.
In one move, Envy can shift the grid in four different ways: up, left, down and right. In a shift, all cereal pieces are moved as far as possible in the direction that they are shifted until they hit the edge of the grid or another piece of cereal.
We say a grid configuration is immobile if shifting the grid leftwards or downwards does not change its configuration.
Envy would like to know how many different immobile grid configurations he can reach by making moves some finite number of times.
Two grid configurations are considered different if any two of the same cells have different cereal pieces, or one is empty and the other contains cereal.
Because the answer can be very large, print it modulo $$$1\,000\,000\,007$$$.
The first line of input contains $$$n$$$, the size of the grid $$$(1 \le n \le 1000)$$$.
The next $$$n$$$ lines of input contain $$$n$$$ characters each, where each character is either a ., meaning an empty cell, or a #, meaning it contains a cereal piece (which is distinct from all other pieces). This represents the starting grid that will be played with.
It is guaranteed that the starting grid is immobile.
Print the answer modulo $$$1\,000\,000\,007$$$.
2 #. ##
3
5 #.... #.... ##... ####. #####
21
In the first test, there are three possible immobile grid states (the initial state is counted) that Envy can reach from the sample case. The cereal are numbered in the visual below to differentiate one grid state from another.
Problem Credits: Mythreya Dharani
Timothy has just conquered a cereal planet using his large brain! He immediately decided to terraform it to repurpose it with his spoon for further world domination. However, as the planet is often rains milk, Timothy would like to find out his effect on the planet.
More specifically, the planet is described as an array of $$$n$$$ heights $$$h_1$$$, $$$h_2$$$, $$$\dots$$$ $$$h_n$$$ $$$(0 \le h_i \le n)$$$.
When it rains $$$x$$$ meters of milk, all indices $$$i$$$ such that $$$h_i \lt x$$$ are "filled with milk".
A lake is defined a continuous series of indices $$$i...j$$$ $$$(1 \le i \le j \le n)$$$ such that all indices $$$k$$$ satisfying $$$i \le k \le j$$$ are filled with milk, and indices $$$i-1$$$ and $$$j+1$$$ are not filled with milk. (Note: indices $$$0$$$ and $$$n+1$$$ are not filled with milk).
Timothy will ask $$$q$$$ queries of $$$2$$$ types. The $$$j$$$-th query begins with an integer $$$t_j$$$, guaranteed to be either $$$1$$$ or $$$2$$$.
If $$$t_j=1$$$, the query will be of the form: $$$1$$$ $$$i$$$ $$$v$$$.
For this query, you should set $$$h_i$$$ to $$$v$$$.
If $$$t_j=2$$$, the query will be of the form: $$$2$$$ $$$x$$$.
For each query of $$$t_j=2$$$, output the number of distinct lakes if it were to rain $$$x$$$ meters.
The first line contains one integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^5)$$$.
The second line contains $$$n$$$ integers describing $$$h_1$$$, $$$h_2$$$, $$$\dots$$$ $$$h_n$$$.
The third line contains one integer $$$q$$$ $$$(1 \le q \le 2 \cdot 10^5)$$$.
The next $$$q$$$ lines describe $$$q$$$ queries of either $$$1$$$ $$$i$$$ $$$v$$$ or $$$2$$$ $$$x$$$.
For queries of type $$$1$$$, it is guaranteed that $$$1 \le i \le n$$$ and $$$1 \le v \le n$$$.
For queries of type $$$2$$$, it is guaranteed that $$$1 \le x \le n$$$.
For each query of the second type, output the number of distinct lakes.
5 5 4 2 1 3 4 2 2 2 3 1 2 1 2 2
1 1 2
Initially, $$$h = [5, 4, 2, 1, 3]$$$.
When it rains $$$2$$$ meters of milk, index $$$4$$$ is filled with milk, resulting in $$$1$$$ lake, consisting of index $$$4$$$.
When it rains $$$3$$$ meters of milk, indices $$$3$$$ and $$$4$$$ are filled with milk, resulting in $$$1$$$ lake consisting of indices $$$[3, 4]$$$.
Then, $$$h_2$$$ is set to $$$1$$$, resulting in $$$h = [5, 1, 2, 1, 3]$$$.
When it rains $$$2$$$ meters of milk, now indices $$$2$$$ and $$$4$$$ are filled with milk, resulting in $$$2$$$ lakes respectively.
Problem Credits: Eric Hsu
The advance of space exploration led to the discovery that not only do ancient aliens on Mars exist, they used to eat cereal too!
Mythreya, an aspiring paleontologist, has gone to Mars to excavate all the alien fossils and artifacts. Mythreya and the CerealCodes team need to quickly extract the $$$k$$$ fossils from the excavation site, which can be described as an $$$n \times n$$$ grid. Each individual cell has coordinates $$$(x,y)$$$, $$$(1 \le x,y \le n)$$$ where $$$x$$$ means that the cell is in the $$$x$$$-th row and $$$y$$$ means that the cell is in the $$$y$$$-th column.
They must bring all $$$k$$$ fossils to the base, located at cell $$$(1,1)$$$. Also, because they are on Mars, they will be traversing the rocky planet using their Rover for Terrestrial Exploration (RTE), which runs on fuel.
The grid itself contains only three different kinds of characters:
'.' signifying an empty space. It takes $$$0$$$ fuel to traverse this cell. The base will always be an empty space.
'+' signifying a rocky path. It takes $$$1$$$ fuel to traverse this cell.
'#' signifying a giant boulder. It is not possible to traverse this cell. Fossils will not be located on boulders.
The rover can move to any neighboring cell so long as it is not a boulder or outside of the grid. The fossils themselves are incredibly heavy; the $$$i$$$-th fossil weighs $$$w_i$$$ kilograms.
As such, the CerealCodes team has crafted a giant, super high-tech wheelbarrow to carry the bones around for them.
The wheelbarrow can carry at most $$$m$$$ kilograms at a time. The fossils must remain intact, so they can't be taken apart into smaller pieces.
However, because it is a high-tech wheelbarrow, new fossils can be placed into it instantaneously. After the wheelbarrow is brought to the base, all the fossils in it can instantaneously be removed as well(multiple trips to the base may be required to deposit fossils since the wheelbarrow may not be sturdy enough to carry them all at once).
Help Mythreya and the CerealCodes team figure out the minimum amount of fuel it will take to bring all fossils to the the base, if they are all currently located at the base!
The first line of input contains four integers, $$$n$$$, $$$k$$$, and $$$m$$$ $$$(2 \le n \le 500, 1 \le k \le 12, 1 \le m \le 10^9)$$$.
The next $$$n$$$ lines represent the excavation site. Each line will have $$$n$$$ characters.
Finally, the next $$$k$$$ lines contain information on the fossils themselves. The $$$i$$$-th of these $$$k$$$ lines will consist of three numbers, $$$x_i$$$, $$$y_i$$$, and $$$w_i$$$ $$$(1 \le x_i,y_i \le n, 1 \le w_i \le m)$$$. It is guaranteed that all fossils will be reachable from the base.
Output the answer as an integer on a single line.
10 4 7 ....##+.+. ###.+.+++. ###....+.. ++....#### ....###### .+..###### .+....++++ #...++.### ###+++###. ####.+#### 7 1 2 3 9 5 10 5 6 1 10 1
6
In the sample case, it is optimal to first place fossils $$$2$$$ and $$$4$$$ into the high-tech wheelbarrow and bring them to the base. Then, one can bring the other two fossils to the base in any order. Mythreya and the CerealCodes team will have to traverse rocky cells at least $$$6$$$ times, so the answer is $$$6$$$. It can be shown that there is no better answer.
Problem Credits: Patrick Deng and Eric Hsu
Allen has bought some coveted alphabet cereal!
He has $$$n^2$$$ ($$$1 \leq{n^2} \leq{10^6}$$$) total pieces of cereal.
Curiously, the cereal pieces are only in the shape of the letters w, and u. Specifically, he has $$$m$$$ ($$$1 \leq{m} \leq{n^2}$$$) pieces marked w and $$$n^2 - m$$$ pieces marked u.
Of course, he wants to play around with them, and decides to place these cereal pieces into an $$$n$$$ by $$$n$$$ grid of cells. Each piece of cereal must go onto exactly one cell such that the entire grid is filled.
Allen notices that the grid contains some unusual phrases. He is most interested in forming his favorite phrase, uwu. He wants to know the optimal configuration of cereal pieces he can have such that the maximum number of uwu's can be seen on the grid (only horizontally or vertically).
Please help him figure this out!
For each test case, there will be one line of input containing two space separated integers $$$n$$$ and $$$m$$$.
Please output any grid configuration of $$$n^2$$$ cells if exactly $$$m$$$ of them have to be w, and the rest have to be u, such that there are the maximum possible number of uwu's in the grid.
Any grid configuration that satisfies the constraints and has the maximum uwu's will be considered correct.
Note that an uwu is in the grid if there are three consecutive characters (either horizontally or vertical) that spell out uwu.
3 5
uwu www uwu
3 2
uwu uwu uuu
In the first sample, there are 4 total uwu's in the grid: one on row 1, one on row 3, on on column 1, and one on column 3.
It can be proved that there can be a maximum of 4 uwu's in the grid given the constraints.
Problem Credits: Eric Hsu and Larry Xing
At the Supermarket, there are $$$2n$$$ brands of cereal arranged in a row.
There are $$$n$$$ regular customers of the Supermarket. The $$$i$$$-th customer likes all brands in the range $$$[l_i, r_i]$$$.
Two customers will compete with each other for cereal if their cereal ranges intersect, and neither range is contained in the other. Formally, customers $$$i$$$ and $$$j$$$ will compete with each other if one of the following holds:
- $$$l_i \lt l_j \lt r_i \lt r_j$$$
- $$$l_j \lt l_i \lt r_j \lt r_i$$$
The Supermarket is open on Mondays and Wednesdays. Determine if there is a way to partition the customers into Monday shoppers and Wednesday shoppers so that there is no cereal competition on any day.
The first line contains an integer $$$n$$$, the number of people ($$$1 \le n \le 10^5$$$).
The next $$$n$$$ lines contain two integers, $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \lt r_i \le 2n$$$).
It is guaranteed that each integer from $$$1$$$ to $$$2n$$$ appears exactly once in the endpoints of the segments.
If no partition satisfying the conditions above exists, output -1.
Otherwise, on the first line, output two integers, $$$x$$$ and $$$y$$$ — the number of Monday shoppers and Wednesday shoppers respectively.
On the second line, output $$$x$$$ integers, the indices of the Monday shoppers.
On the third line, output $$$y$$$ integers, the indices of the Wednesday shoppers.
Each integer from $$$1$$$ to $$$n$$$ should appear exactly once.
5 7 10 5 8 3 9 1 6 2 4
3 2 1 4 5 2 3
7 13 14 7 10 3 12 4 8 2 6 5 9 1 11
-1
In the first test, shoppers $$$1$$$, $$$4$$$, and $$$5$$$ are assigned to Monday. This is valid because:
- Shopper $$$1$$$ does not compete with shopper $$$4$$$ because their ranges do not intersect.
- Shopper $$$1$$$ does not compete with shopper $$$5$$$ because their ranges do not intersect.
- Shopper $$$5$$$ does not compete with shopper $$$4$$$ because shopper $$$5$$$'s range is completely contained in shopper $$$4$$$'s range.
Similarly, shoppers $$$2$$$ and $$$3$$$ are assigned to Wednesday, which is valid because:
- Shopper $$$2$$$ does not compete with shopper $$$3$$$ because shopper $$$2$$$'s range is completely contained in shopper $$$3$$$'s range.
Problem Credits: Thomas Liu
After climbing the tallest mountains in Agastya's kingdom, Larry decides to go on a relaxing hike.
There are given $$$n$$$ cereal mountains arranged in a line, numbered $$$1 \dots n$$$ $$$(2 \leq n \leq 10^5)$$$. The cereal mountains are described as $$$2$$$ arrays $$$h_1, h_2, \dots, h_n$$$ and $$$v_1, v_2, \dots, v_n$$$; the heights of the mountains and the greatness of the view. Mountain $$$i$$$ has a height of $$$h_i$$$, and a view with greatness $$$v_i$$$ $$$(0 \leq h_i, v_i \leq 10^9)$$$.
Larry wants to hike a subarray of mountains. The difficulty of a hike $$$d(l, r)$$$ is defined as the difference between the highest and lowest mountain in the range $$$[l, r]$$$, more specifically: $$$d(l, r) = \max(h_{l}, h_{l+1}, \dots, h{r}) - \min(h_{l}, h_{l+1}, \dots, h{r})$$$.
The enjoyment of a hike $$$f(l, r)$$$ is defined as the sum of the greatness of the views of the mountains in the range $$$[l, r]$$$ divided by the difficulty of the range, more specifically: $$$f(l, r) = \frac{\sum_{n=l}^{r} v_{n}}{d(l, r)}$$$
Since Larry like challenges, he wants to hike a subarray with a difficulty greater than $$$0$$$.
Find the maximum enjoyment Larry can achieve in a hike with a difficulty greater than $$$0$$$.
It is guaranteed that there is at least one hike that fits the constraints.
The first line contains one integer $$$n$$$.
The next line contains $$$n$$$ space separated integers $$$v_1, v_2, \dots, v_n$$$.
The next line contains $$$n$$$ space separated integers $$$h_1, h_2, \dots, h_n$$$.
Print one real number, the maximum enjoyment of a hike with a difficulty greater than one. Your answer is considered correct if the relative or absolute error is less than or equal to $$$10^{-6}$$$.
More specifically, if your answer is $$$a$$$ and the expected answer is $$$b$$$, your answer will be accepted if $$$\frac{|a-b|}{\max(1, |b|)} \leq 10^{-6}$$$.
5 0 4 5 5 4 6 5 0 8 9
9.00000000000000000000
10 6 6 9 9 9 1 1 4 0 1 22 40 18 1 9 35 39 7 19 30
2.25000000000000000000
In the first sample case, the largest enjoyment of a hike we can get is with the hike ($$$4$$$, $$$5$$$).
The total enjoyment we will get is $$$(5 + 4)/(9 - 8) = 9$$$.
In the second sample case, we should take the hike ($$$1$$$, $$$3$$$).
Problem Credits: Agastya Goel, Eric Hsu
Agastya, the king of the Cereal Kingdom, loves to use his god powers to create cereal mountains.
More specifically, Agastya's Cereal Kingdom is described as and array length $$$n$$$ of heights $$$h_1, h_2, \dots h_n$$$.
When Agastya casts a spell at position $$$i$$$ with power $$$p$$$ and range $$$r$$$, for all indices $$$1 \leq j \leq n$$$ such that $$$|j - i| \le r$$$, $$$h_j$$$ increases by $$$p \cdot (r - |j-i|)$$$.
Larry is an over achiever, so he always wants to climb up to the tallest mountains near him. Larry is at position $$$p$$$, and wants to know the height of the tallest mountain within distance $$$d$$$ from his current position.
More specifically, Larry wants to know $$$\max(h_i)$$$ such that $$$1 \leq i \leq n$$$ and $$$|i-p| \le d$$$.
Please help Larry find the tallest of the cereal mountains.
The first line contains one integer, $$$n$$$ $$$(1 \leq n \leq 2 \cdot 10^5)$$$.
The next line contains $$$n$$$ integers, describing $$$h_1, h_2, \dots h_n$$$ $$$(1 \leq h_i \leq 10^9)$$$.
The next line contains one integer, $$$q$$$ $$$(1 \leq q \leq 2 \cdot 10^5)$$$.
The $$$i$$$-th line of next $$$q$$$ lines first contains an integer $$$t_i$$$, describing the type of query.
If $$$t_i = 1$$$, then Agastya casts a spell. The query type is followed by $$$3$$$ integers $$$i$$$, $$$p$$$, and $$$r$$$, describing the position, power, and range of the spell $$$(1 \leq i, r \leq n)$$$, $$$(1 \leq p \leq 10^2)$$$.
If $$$t_i = 2$$$, then the query type is followed by two integers $$$p$$$ and $$$d$$$, describing the position of Larry, who wants to know the height of the tallest mountain within distance $$$d$$$ $$$(1 \leq p, d \leq n)$$$.
For each query of type $$$2$$$, print out one integer $$$i$$$ followed by a newline, describing the height of the tallest mountain within distance $$$d$$$ from position $$$p$$$.
5 3 4 0 3 5 4 1 4 5 5 2 5 1 1 2 3 2 2 2 2
25 25
Initially, the $$$h$$$ = $$$[3, 4, 0, 3, 5]$$$.
When Agastya casts a spell at position $$$4$$$ with power $$$5$$$ and range $$$5$$$, the increases are $$$[10, 15, 20, 25, 20]$$$ and $$$h$$$ = $$$[13, 19, 20, 28, 25]$$$.
The tallest mountain within distance $$$1$$$ of index $$$5$$$ is $$$25$$$.
Agastya then casts a spell at position $$$2$$$ with power $$$3$$$ and range $$$2$$$. The increases are $$$[3, 6, 3, 0, 0]$$$, and $$$h$$$ = $$$[16, 25, 23, 28, 25]$$$.
The tallest mountain within distance $$$2$$$ of index $$$2$$$ is $$$25$$$.
Problem Credits: Agastya Goel
Envy has found an apple tree, but unfortunately, finds out that the apples are not ripe at all. Because he has a huge sweet tooth, and is craving something sugary, he decides to turn the apples into cereal!
Although he does not know how to do this, he consults the all-knowing Larry. Larry confides in Envy that he will give him the ancient Apple Method needed to make cereal, if Envy solves the following question:
You are given a tree of $$$n$$$ ($$$1 \leq {n} \leq {5 \cdot 10^3}$$$) nodes, numbered $$$1 \dots n$$$, and $$$n-1$$$ edges.
You want to visit every node in this tree exactly once. You can start at any node, and jump from any node to any other node.
A jump is considered magical if the node that you move to is within the subtree of the node you are currently on.
You are given $$$q$$$ queries, where the $$$i$$$th query gives you two numbers $$$x_i$$$ and $$$y_i$$$.
For each query, compute the number of paths visiting every nodes in the subtree of node $$$x$$$ (including $$$x$$$) with exactly $$$y$$$ magical jumps.
Note that ($$$1 \leq x \leq n$$$) and $$$y$$$ is strictly less than the number of nodes in the subtree of $$$x$$$ ($$$y$$$ can be $$$0$$$).
Since this number can be quite large, find it modulo $$$10^9 + 7$$$.
The first line contain $$$n$$$.
The next $$$n - 1$$$ lines contains two integers $$$a$$$ and $$$b$$$, meaning that the $$$a$$$th node is connected to the $$$b$$$th node.
The next line will contain an integer $$$q (1 \leq q \leq 5000)$$$.
The next $$$q$$$ lines will contain two integers $$$x_i$$$ and $$$y_i$$$.
Note: the tree is rooted at node $$$1$$$.
For every query of the form $$$x_i$$$, $$$y_i$$$, compute the number of paths visiting every node in the subtree of $$$x$$$ exactly once such that the path contains $$$y$$$ magical jumps, modulo $$$10^9 + 7$$$.
Each answer for a distinct query should be on a newline.
4 1 2 2 3 2 4 3 2 0 2 1 2 2
2 4 0
The graph below represents the tree described in the sample input.
For the first query, the two possible paths are $$$4 \rightarrow 3 \rightarrow 2$$$ and $$$3 \rightarrow 4 \rightarrow 2$$$.
Problem Credits: Larry Xing