Download and listen to the problem statement here. It is an MP3 audio file that is 3 minutes and 16 seconds long.
The game is available for playing!
Download the following files:
Then, run the game by entering java -jar Pipes.jar in the command line/terminal. Read README.pdf for additional info.
The first line of input contains $$$t$$$, the number of test cases.
The first line of each test case contains two space-separated integers $$$r$$$ and $$$c$$$, the number of rows and the number of columns in the grid.
Each of the next $$$r$$$ lines consist of a string of $$$c$$$ characters, representing the grid. Each character is either:
- a lowercase or uppercase letter,
- '|' which represents a vertical pipe, or
- '-' which represents a horizontal pipe.
For each test case, output one line containing the answer:
- If it is not possible to connect the pairs of letters through a sequence of clicks, output F.
- If it is possible, output the minimum number of clicks needed to connect all pairs of letters.
For all subtasks
$$$1 \le t \le 10$$$
$$$1 \le r, c \le 500$$$
There is exactly zero or two of each letter.
There is at least one letter in the grid.
Subtask 1 (20 points):
$$$1 \le r, c \le 50$$$
The grid contains exactly one pair of equal letters.
Subtask 2 (25 points):
The grid contains exactly one pair of equal letters.
Subtask 3 (30 points):
$$$1 \le r, c \le 50$$$
Subtask 4 (25 points):
No additional constraints.
2 3 6 -|-|-| |g|-g- -|-|-| 2 2 I| |I
1 F
3 4 5 A|-A| -|B|a |---a ||B-| 3 8 |--|---| -A||B|AB |||----| 3 4 |--| BCCB ||--
2 F F
4 3 10 A--------A x--X--x--X E--------E 2 3 lol |o| 1 4 AbbA 5 8 -||-bW-W a||a--|| Z|Zxbw|w z-zx-|-| r|-||-|r
F F F 9
The first sample I/O is valid for all subtasks, while the second and third sample I/O are only valid for the third and fourth subtasks.
The following illustrates the first test case in the second sample I/O:
The minimum number of moves is $$$2$$$, as illustrated by the following:
The following images illustrate the rest of the test cases in the second sample I/O:
It is impossible to connect the letters in both cases, so the output is F for both.
In an alternate universe, a virus carried primarily by raccoons has spread worldwide. To develop a vaccine, scientists are studying its RNA makeup.
In this universe, RNA (Racoon Nucleic Acid) is constructed rather differently. An $$$m$$$-length RNA strand can be represented by an array of $$$m$$$ nonnegative integers $$$A_i$$$. A substrand of a RNA strand is any nonempty contiguous subarray of this RNA strand. Two substrands are said to be compatible if the sum of their elements are equal. The infection index of a RNA strand is the maximum size of a set containing only its substrands, such that no two elements in the set are compatible.
To help in the research of the virus, the Pandemic Research Committee (PRC) has teamed up with the National Overseer Institute on Pandemic Havocs (NOI PH). Together, they discovered that the virus is an $$$n$$$-length RNA strand with infection index $$$k$$$. They also discovered that all elements making up the virus strand never exceeded $$$10^9$$$. However, after these discoveries, they are running low on virus samples to research with.
As a member of the final selection pool of interns working in the NOI PH, you realized this was the perfect opportunity to prove your worth! You decide to try and reconstruct the virus with what is known to make more samples. If you succeed, you may even be invited to intern in the International Overseer of Infections (IOI)! Do your best!
Note that the information obtained on the virus may have also been miscalculated, and a RNA strand with its characteristics may be inconstructible. If this is the case, you must also say so.
The first line of input contains $$$t$$$, the number of test cases. Then $$$t$$$ lines follow, each containing two space separated integers $$$n$$$ and $$$k$$$.
For each given $$$n$$$ and $$$k$$$, output a single line containing
- "POSSIBLE" (without the quotes) if there exists a length-$$$n$$$ RNA strand with infection index $$$k$$$ where every element $$$A_i$$$ is a nonnegative integer between $$$0$$$ and $$$10^9$$$ (inclusive), and
- "IMPOSSIBLE" (without the quotes) if it does not exist.
In addition, if you outputted POSSIBLE, print a second line containing $$$n$$$ space-separated integers $$$A_1, A_2, \ldots, A_n$$$ denoting the elements of the length-$$$n$$$ RNA strand.
If there are several answers, output any.
For all subtasks
$$$1 \le t \le 10000$$$
$$$1 \le n \le 1000$$$
$$$1 \le k \le 10^6$$$
The sum of $$$n^2$$$ across all test cases in a file is $$$\le 10^7$$$
Subtask 1 (16 points): $$$n \lt 30$$$
Subtask 2 (17 points): $$$n \le 50$$$
Subtask 3 (15 points): $$$n \le 100$$$
Subtask 4 (14 points): $$$n \le 200$$$
Subtask 5 (15 points): $$$n \le 400$$$
Subtask 6 (9 points): $$$n \le 750$$$
Subtask 7 (14 points): No additional constraints.
2 1 2 3 4
IMPOSSIBLE POSSIBLE 2 1 2
Sample case $$$1$$$: We have $$$n = 1$$$. It is impossible to create a $$$1$$$-length RNA strand with infection index $$$k=2$$$, so we output IMPOSSIBLE.
Sample case $$$2$$$: We have $$$n = 3$$$. One $$$3$$$-length RNA strand that has infection index $$$k=4$$$ is 2 1 2. An example set of four substrands in this strand are $$$[1]$$$, $$$[2]$$$, $$$[1, 2]$$$, and $$$[2, 1, 2]$$$. Note that $$$[2, 1]$$$ and $$$[1, 2]$$$ are compatible because their element sums are the same, and hence cannot both be in this set. $$$[2, 2]$$$ is not a substrand because it is not contiguous. Other solutions exist such as 1 1 2, and you may output any.
After the completion of his manga Tights in The Wind, mangaka Kakushi Gotou took a part time job as a JUMP! comics warehouse forklifter.
The warehouse is a parallelogram with row length $$$r$$$ and column length $$$c$$$. The storage slots of the warehouse are mini hexagons denoted by coordinates $$$(i,j)$$$, where $$$i$$$ is its row number and $$$j$$$ is its column number. The slot at coordinate $$$(i,j)$$$ has $$$A_{(i,j)}$$$ JUMP! comics already stacked on it.
We define the instability of the warehouse stacks to be the largest difference in height between any two adjacent storage slots in the warehouse. We say two stacks are adjacent if their hexagonal slots share a side. More formally, the slot at coordinate $$$(i,j)$$$ is adjacent to the slots at coordinates $$$(i,j-1)$$$, $$$(i,j+1)$$$, $$$(i-1,j)$$$, $$$(i-1,j+1)$$$, $$$(i+1,j-1)$$$, and $$$(i+1,j)$$$ (if they exist). The arrows in the above grid visually depict adjacent nodes.
Kakushi's job is to minimize this instability in order to prevent a potential book avalanche. To do so, he can bring in up to $$$k$$$ JUMP! comics, which he can pile up on any stack he wishes. To avoid garnering hatred from his forklifter senpais, Kakushi does not want to move comics initially/already stacked in the warehouse.
What is the minimum instability of the warehouse if Kakushi brings in the optimal number of JUMP! comics and places them on the stacks optimally?
Note: The warehouse grid is NOT a rectangle, it is a slanted parallelogram. Look at the sample input/output explanation or the above warehouse grid example for clarity.
The first line of input contains $$$t$$$, the number of test cases.
Each test case begins with three integers $$$r$$$, $$$c$$$, and $$$k$$$, the number of rows of the warehouse, the number of columns of the warehouse, and the maximum number of comics Kakushi can bring in, respectively.
$$$r$$$ lines then follow, each containing $$$c$$$ integers. The $$$j$$$th integer in the $$$i$$$th line denotes the number of comics at coordinate $$$(i,j)$$$, i.e. $$$A_{(i,j)}$$$.
Output one integer, the minimum instability obtainable by placing up to $$$k$$$ JUMP! comics in the warehouse stacks.
For all subtasks
$$$1 \le A_{(i,j)} \le 10^{12}$$$
$$$0 \le k \le 10^{18}$$$
$$$1 \le r, c, rc \le 10^5$$$
The sum of the $$$rc$$$'s in a single file is $$$\le 4\cdot 10^5$$$
$$$1 \le t \le 10$$$
$$$rc \gt 1$$$
Subtask 1 (5 points):
$$$k = 0$$$
Subtask 2 (10 points):
$$$r, c, rc, k \le 200$$$
Subtask 3 (15 points):
$$$r, c, rc \le 200$$$
Subtask 4 (15 points):
$$$r, c, rc \le 3000$$$
Subtask 5 (20 points):
$$$r = 1$$$ or $$$c = 1$$$
Subtask 6 (20 points):
$$$rc \le 30000$$$
The sum of the $$$rc$$$'s in a single file is $$$\le 60000$$$
Subtask 7 (15 points):
No additional constraints.
1 3 5 12 15 13 9 13 9 11 5 11 13 12 10 13 8 16 16
4
Note: The sample case is not valid for the first and fifth subtasks. It is valid for the other subtasks.
The warehouse has $$$r=3$$$ rows and $$$c=5$$$ columns. Kakushi can bring in up to $$$k=12$$$ JUMP! comics. The warehouse initially looks like the following:
Kakushi can choose to bring in $$$11$$$ comics to the warehouse and place them as follows:
This way, the maximum difference between any two adjacent cells in the grid is $$$4$$$, and exactly $$$11$$$ comics are used.
Since the citizens of the country were not fussing about worrying how not to get arrested during quarantine, or hosting birthday mañanitas for their beloved police chief, the Philippines was able to finally rightfully claim the Spratly Islands as part of their territory, and even establish a successful system of ferries connecting the islands together, with tours! Do you remember how fulfilling it was to meticulously and lovingly craft optimal solutions to these problems, after you were put in charge of the project?
Of course, ever since you handed over leadership of the ferry project to another administration, the new management proceeded to thoughtlessly add more ferry routes and ruin the system you developed. But hey, you don't care about that, right? It doesn't matter that all your hard work was ruined by a new team that doesn't care about the project nearly as much as you did. Nope!
To recap, there are $$$n$$$ islands labeled $$$1$$$ to $$$n$$$, and $$$m$$$ ferry services that allow travel between pairs of islands. The $$$i$$$th ferry service connects islands $$$u_i$$$ and $$$v_i$$$, and due to the event-that-shall-not-be-named, citizens are only permitted to use this ferry if they are at least $$$d_i$$$ seconds old (because everyone knows their age down to the second, obviously). A ferry always connects two different islands, but the same pair of islands may have multiple ferry services between them.
Even though the ferry services are up and running again, people are generally discouraged from leaving their houses and returning to their home province (again, due to the event-that-shall-not-be-named). Despite this, some people still insist on leaving their islands anyway! You are aware of $$$k$$$ different rebellious souls, as well as each of their respective romantic partners (there are $$$k$$$ romantic partners in total). You also know the ages of the rebels—the $$$i$$$th rebel is $$$H_i$$$ seconds old.
How do we prevent them from visiting their romantic partners? Your master plan is simple!
You will build $$$2k$$$ houses on the islands, and relocate each of the rebels or romantic partners to these houses (one to each house), such that it is impossible for each rebel to ever reach the island of their partner by using the ferry system. The romantic partners can be assumed to stay in their assigned island and will never attempt to move. It is okay for multiple rebels or multiple partners to live on the same island, and it is even okay for a rebel to live on the same island as the partner of a different rebel, so long as it is impossible for them to reach their own partner.
How many ways can you choose where to build each of the $$$2k$$$ houses such that this condition is fulfilled? Two ways are different if one of the rebels or one of the partners has their home on a different island between the two ways. Since this can be quite large, output your answer modulo $$$10^9+7$$$.
The first line of input contains three space-separated integers, $$$n$$$, $$$m$$$, and $$$k$$$, respectively.
This is followed by $$$m$$$ lines, each containing three space-separated integers $$$u_i$$$, $$$v_i$$$, and $$$d_i$$$, meaning that there exists a ferry service connecting islands $$$u_i$$$ and $$$v_i$$$ that you have to be $$$d_i$$$ seconds old in order to use.
Finally, this is followed by a single line containing $$$k$$$ space-separated integers, where the $$$i$$$th of these integers is $$$H_i$$$.
Output a single line containing the answer modulo $$$10^9+7$$$.
For all subtasks
$$$2 \leq n \leq 10^6$$$
$$$1 \leq m, k \leq 2\cdot 10^5$$$
$$$1 \leq u_i, v_i \leq n$$$
$$$u_i \neq v_i$$$
$$$1 \leq d_i, H_i \leq 2\cdot10^9$$$
Subtask 1 (10 points):
$$$n, m, k \leq 20$$$
Subtask 2 (20 points):
$$$n, m, k \leq 200$$$
Subtask 3 (10 points):
$$$k = 1$$$
$$$n \leq 7641$$$
Subtask 4 (15 points):
$$$k = 1$$$
Subtask 5 (5 points):
$$$d_i$$$ is the same across all ferry services.
$$$n \leq 7641$$$
Subtask 6 (10 points):
$$$d_i$$$ is the same across all ferry services.
Subtask 7 (30 points):
No further constraints.
4 3 2 1 2 567600000 2 3 662300000 3 4 567600000 536100000 630700000
96
3 4 2 1 2 599200000 2 3 599200000 3 1 599200000 1 3 410000000 504600000 1009200000
0
7641 9 9 1 1521 6 1521 1896 9 1896 1916 12 1916 1942 15 1942 1945 18 1945 1965 21 1965 1986 24 1986 2016 27 2016 2020 30 12 1 2 1 14 12 5 14 9
110345126
Hey, it's your friend Crazy Rich Sean! You haven't seen him since the last time you visited Singapore. It turns out he's even crazier and even richer than before. People think that the sign of being rich is being able to afford private jets with caviar and Iberico ham and solid gold toilet seats. The true craziest and richest of society can afford to buy ideas—democracy, truth, and most importantly, numbers.
Crazy Rich Sean bought a shiny new integer sequence. Don't even bother looking for it in the OEIS, since Crazy Rich Sean's team of lawyers has copyrighted, patented, and trademarked this sequence for his exclusive use.
Define the sequence $$$R$$$ as the unique nondecreasing sequence of positive integers $$$R(1), R(2), R(3), \dots$$$ such that for every $$$i \geq 1$$$, $$$i$$$ appears in the sequence exactly $$$R(i) + R(i+1)$$$ times. It starts as: $$$$$$\begin{array}{r|rrrrrrrrrrrrrrrrrrrr} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & \dots \\ \hline R(i) & 1 & 1 & 2 & 2 & 2 & 3 & 3 & 3 & 3 & 4 & 4 & 4 & 4 & 5 & 5 & 5 & 5 & 5 & 6 & \dots \end{array}$$$$$$
Crazy Rich Sean wants to test out this new integer sequence by playing a game with his employees. Each of his employees has a unique ID number which is some positive integer, and he has an employee for every positive integer. For this game, he announces that all employees whose ID number is between $$$a$$$ and $$$b$$$ (inclusive) must participate. The participating employees must line up in one long queue. An employee with ID number $$$x$$$ is considered safe if (and only if) at least one of the following is true:
- This employee is the first person in the queue.
- If $$$y$$$ is the ID number of the employee directly in front of them in the queue, then $$$\frac{R(y)}{R(x)}$$$ is an integer strictly greater than $$$1$$$.
All employees that are not safe will end up fired. That's awful! Why would Sean do this? Because he's crazy, and rich, and he'll get away with it too, thanks to that aforementioned team of lawyers.
Due to your friendship, Crazy Rich Sean allows one concession—you are allowed to decide the order in which the employees should line up. Among all possible queueing orders, what is the minimum number of employees that will end up fired?
The first line of input contains $$$t$$$, the number of test cases. The following $$$t$$$ lines describe the test cases.
Each test case consists of a single line containing two space-separated integers $$$a$$$ and $$$b$$$.
For each test case, output a single integer denoting the answer for that test case.
For all subtasks
$$$1 \le t \le 4\cdot 10^5$$$
$$$1 \le a \le b \le 2\cdot 10^{18}$$$
Subtask 1 (7 points): $$$b \le 10$$$, $$$t \le 30$$$
Subtask 2 (7 points): $$$b \le 20$$$, $$$t \le 30$$$
Subtask 3 (6 points): $$$b \le 30$$$
Subtask 4 (7 points): $$$b \le 100$$$
Subtask 5 (8 points): $$$b \le 3000$$$, $$$t \le 500$$$
Subtask 6 (20 points): $$$b \le 2\cdot 10^5$$$, $$$t \le 500$$$
Subtask 7 (5 points): $$$b \le 10^6$$$
Subtask 8 (5 points): $$$b \le 2^{32}$$$, $$$t \le 500$$$
Subtask 9 (5 points): $$$b \le 2^{32}$$$
Subtask 10 (5 points): $$$b \le 10^{12}$$$, $$$t \le 500$$$
Subtask 11 (5 points): $$$b \le 10^{12}$$$
Subtask 12 (5 points): $$$b \le 10^{15}$$$, $$$t \le 500$$$
Subtask 13 (5 points): $$$b \le 10^{15}$$$
Subtask 14 (5 points): $$$t \le 500$$$
Subtask 15 (5 points): No additional constraints.
3 1 10 2 5 4 6
6 2 2
Here's one possible queueing order of employees $$$1$$$ to $$$10$$$ (from back to front): $$$$$$7, 4, 10, 1, 5, 2, 9, 3, 6, 8$$$$$$
With this queueing order, you can verify that $$$6$$$ employees will end up getting fired. The only safe employees are employees $$$1$$$, $$$2$$$, $$$4$$$ and $$$8$$$.
It can also be shown that any other queueing order will have $$$6$$$ or more employees end up getting fired. Therefore, the answer for the first sample case is $$$6$$$.