In the North of the modern-day Kowloon Island, there lies the memorial park of the historic Kowloon Walled City. Once a military fort and enclave of the Qing Dynasty, it became lawless in 1899 after diplomatic conflicts between the Qing and the British government. Its lawless status has persisted throughout most of the 20th century, until its demolishment in 1994. Over the years, the Kowloon Walled City become one of the most densely populated place in the world.
Kowloon Walled City (© City of Darkness Revisited) 
Hand-drawn Map (© Kowloon Walled City Kaifong Welfare Promotion Association) Now, imagine you are given the map of the bygone Kowloon Walled City. The map can be considered as a connected, undirected graph with $$$N$$$ locations and $$$M$$$ pathways. There might exist multiple pathways between the same two locations.
Initially, you start in location $$$1$$$. Each step, if there are pathways remaining for the location you are in, you can choose any one of them and move to the other side of the pathway. Then, you cross out that pathway on the map. If at any moment, there are no more pathways on the map attached to the location you are in, you are stuck.
Your target is to construct moves that lead to you being stuck at some location other than location $$$1$$$. Report if no such sequence of moves exists.
The first line contains two integers: $$$N, M$$$ ($$$2 \leq N \leq 10^5, N - 1 \leq M \leq 2 \times 10^5$$$), the number of locations and the number of pathways, respectively. The $$$i^\text{th}$$$ line among the next $$$M$$$ lines contains two integers: $$$U_i, V_i$$$ ($$$1 \leq U_i \neq V_i \leq N$$$), meaning that there is an undirected pathway between location $$$U_i$$$ and location $$$V_i$$$.
If such a walk exists, then on the first line, output $$$K$$$ ($$$2 \leq K \leq M + 1$$$), the length of the walk. Then, on the next line, output $$$K$$$ integers: $$$S_1, S_2, \dots, S_K$$$, where $$$S_1 = 1$$$, there is a pathway between $$$S_i$$$ and $$$S_{i+1}$$$ for $$$1 \leq i \leq K - 1$$$, and you are stuck at $$$S_K$$$ afterwards.
Otherwise, if no such walk exists, output -1 on the first and only line.
If there exists multiple walks that make you stuck at locations other than location $$$1$$$, you may output any of them.
4 41 22 33 44 1
-1
6 81 22 33 45 46 52 54 51 6
8 1 6 5 4 3 2 5 4
Sample 1:
You will always go back to location 1 no matter how you walk.
Sample 2:
The walk 1 6 5 4 3 2 5 is not accepted. Although you do not go back to location 1, you haven't got stuck yet.
In the heart of bustling Hong Kong, a unique cultural experience awaits: the thrill of playing Ping Pong Pinball machines outside vibrant stationery shops. These shops, brimming with colorful pens, stacks of notebooks, and artistic supplies, often feature these captivating machines as a draw for young and old alike.
A Ping Pong Pinball machine. At a Ping Pong Pinball machine, players can play a game with a $1 coin, potentially winning attractive prizes. In each game, the player pings 5 table tennis balls one by one, each independently and uniformly falling into one of the 5 vertical slots. At the end of the game, the player will be awarded the basic prize if four balls land in a single row (either horizontally or vertically), or the grand prize if all five balls land in a single row (either horizontally or vertically).
You are now observing Alice playing the game outside a stationery shop. After Alice pinged the first 3 balls, you noted down the current distribution of balls across the five vertical slots. You are now wondering whether it is still possible for Alice to win the basic prize and/or the grand prize by (luckily) pinging the 2 remaining balls.
The input consists of 5 integers $$$C_1, C_2, C_3, C_4, C_5$$$ ($$$0 \leq C_i \leq 3$$$). Here, $$$C_i$$$ denotes the number of balls in the $$$i$$$-th vertical slot.
It is guaranteed that Alice has pinged exactly 3 balls, i.e., $$$C_1 + C_2 + C_3 + C_4 + C_5 = 3$$$.
If it is possible for Alice to win the grand prize in the current game, output op.
Otherwise, if it is possible for Alice to win the basic prize in the current game, output add oil.
If it is not possible for Alice to win any prizes in the current game, output gg.
1 2 0 0 0
add oil
1 0 1 0 1
op
Sample 1:
It is possible to win the basic prize by pinging the remaining balls into slot 2, forming a vertical line, or slots 3 and 4 respectively, forming a horizontal line. However, it is impossible to win the grand prize regardless of how the remaining balls are pinged.
 | $$$\Rightarrow$$$ |  |  |
Sample 2:
It is possible to win the grand prize by pinging the remaining balls into slots 2 and 4 respectively, forming a horizontal line.
 | $$$\Rightarrow$$$ |  |
The Chinese (Lunar) New Year festivities are in full swing along the West Kowloon Waterfront Promenade. During the Lantern Festival, the day marking the end of the Lunar New Year, a popular activity at night is known as "caai dang mai" (猜燈謎), i.e. "guessing lantern riddles", where children go out at night carrying paper lanterns and solve riddles on the lanterns, often related to guessing meanings of phrases. These riddles, written on slips of paper and attached to the lanterns, offer a fun challenge for young and old alike.
Lantern riddles (© Epoch Group Limited) This year, a particularly interesting lantern riddle has captured everyone's attention. Instead of traditional riddles displayed on one lantern, there is a row of $$$N$$$ consecutive lanterns labelled 1, 2, ..., $$$N$$$, where the $$$i$$$-th lantern ($$$1 \leq i \leq N$$$) displays a string of lowercase characters $$$S_i$$$. It is guaranteed that all $$$S_i$$$ are distinct. The challenge is to find combinations of lanterns that satisfy a special string triangle inequality.
We say that three strings $$$X$$$, $$$Y$$$, $$$Z$$$ satisfy the string triangle inequality if and only if for every permutation $$$[X', Y', Z']$$$ of $$$[X, Y, Z]$$$, the following condition is satisfied: $$$X' + Y' \gt Z'$$$. In other words, all of the following must be satisfied:
- $$$X + Y \gt Z$$$
- $$$X + Z \gt Y$$$
- $$$Y + X \gt Z$$$
- $$$Y + Z \gt X$$$
- $$$Z + X \gt Y$$$
- $$$Z + Y \gt X$$$
Here, + denotes the string concatenation operator, while > denotes the "lexicographically larger than" comparison operator (the same way + and > operate on strings in C++).
The lantern riddle is: count the number of tuples $$$(i, j, k)$$$ where $$$1 \leq i \lt j \lt k \leq N$$$ and the strings $$$S_i, S_j, S_k$$$ satisfy the string triangle inequality.
The first line contains one integer $$$N$$$ ($$$3 \leq N \leq 2 \times 10^5$$$), representing the number of lanterns.
The next $$$N$$$ lines each contain a sequence of lowercase characters $$$S_i$$$ ($$$3 \leq \sum |S_i| \leq 10^6$$$), representing the strings on the lanterns.
It is guaranteed that all $$$S_i$$$ are distinct.
Output a single integer, the number of tuples satisfying the requirement.
5aaaaaaaaaaaaaaaaaaaa
7
3abc
0
Sample 1:
All strings contain the character a only. Hence, the problem is equivalent to finding the number of tuples of integers $$$(a,b,c)$$$ such that $$$2 \le a \lt b \lt c \le 6$$$ and the usual triangle inequality for integers is satisfied. The valid tuples are $$$(2, 3, 4), (2, 4, 5), (2, 5, 6), (3, 4, 5), (3, 4, 6), (3, 5, 6), (4, 5, 6)$$$.
Sample 2:
a + b = ab < c. Therefore there are no valid tuples.
"What's the Time, Mr. Fox?" (狐狸先生幾多點) is a popular children's game in Hong Kong. In this chase/tag-styled game, $$$N$$$ players cautiously approach the tagger, Mr. Fox, before desperately trying to avoid being caught.
Today, you are participating in a "What's the Time, Mr. Fox?" game with $$$N$$$ friends. You will be playing as Mr. Fox, while your friends will be the $$$N$$$ players trying to avoid being caught by you. The game is played on a track of length $$$L$$$, where point 0 is the origin, and point $$$L$$$ is the destination. All $$$N$$$ players are initially positioned at point 0, while you are initially positioned at point $$$L$$$. The $$$i$$$-th player ($$$1 \leq i \leq N$$$) has a pace of $$$A_i$$$.
It is guaranteed that $$$1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq L$$$, and $$$A_{i+1} - A_i \geq A_{i+2} - A_{i+1}$$$ for $$$1 \leq i \leq N - 2$$$.
The players' goal is to reach the destination or avoid being caught by you, while your goal is to catch as many players as possible.
The game proceeds as follows:
- First Stage: You select a positive real number $$$U$$$, and each player $$$i$$$ walks a distance of $$$A_i \times U$$$.
- If a player $$$i$$$ walks a distance $$$A_i \times U \geq L$$$, they have reached or exceeded the destination and are safe (i.e., they will not be caught by you).
- Second Stage: You shout "Catch!" and start running from point $$$L$$$ back to point 0 to catch the players. For each player $$$i$$$ who did not reach the destination (i.e., $$$A_i \times U \lt L$$$), they start running from point $$$A_i \times U$$$ back to point 0. Specifically,
- Player $$$i$$$ starts running back to point 0 at a speed of $$$P$$$ units per second.
- You start running from point $$$L$$$ to point 0 at a speed of $$$W$$$ units per second, where $$$P \lt W$$$.
- If player $$$i$$$ reaches point 0 on or before the time you reach point 0, player $$$i$$$ is safe.
If a player has not walked a distance of at least $$$L$$$ in the first stage, and reached point 0 strictly after the time you reached point 0 in the second stage, that player is considered caught by you. (In other words, any player that is not safe is caught by you.)
Given $$$Q$$$ scenarios, where in the $$$i$$$-th scenario, you are provided with the integers $$$P$$$ and $$$W$$$, the players' running speed and your running speed in the second stage respectively, determine, with the optimal choice of the real number $$$U$$$ (such $$$U$$$ may not be unique), what is the maximum number of players that you can possibly catch.
The first line contains three integers $$$N$$$, $$$L$$$, and $$$Q$$$ ($$$1 \leq N, Q \leq 2 \times 10^5$$$, $$$1 \leq L \leq 10^9$$$), representing the number of players (not counting you), the length of the track, and the number of scenarios respectively.
The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$, representing the pace of the players. You are reminded that $$$1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq L$$$ and $$$A_{i+1} - A_i \geq A_{i+2} - A_{i+1}$$$ for $$$1 \leq i \leq N - 2$$$.
The next $$$Q$$$ lines each contain two integers $$$P$$$ and $$$W$$$ ($$$1 \leq P \lt W \leq 10^9$$$), representing the parameters for a scenario.
For each scenario, output one integer, the maximum number of players that you can possibly catch.
4 70 11 2 3 442 69
2
Sample 1:
By choosing 22 as $$$U$$$, we can catch player 2 and 3.
Every night, the light show "A Symphony of Lights" takes place across the Victoria Harbour. Lights of various colours and types on the skyscrapers are turned on in synchronization with orchestral music. In this problem, you are required to solve a challenge related to the light show!
A Symphony of Lights (© Calvin Sit) Let's say there are $$$N$$$ skyscrapers located on one side of the Victoria Harbour. We index the skyscrapers by $$$1, 2, \dots, N$$$ as viewed from left to right.
For simplicity, suppose the process of "A Symphony of Lights" is as follows:
- At time $$$1$$$, the lights on one skyscraper are turned on.
- Then, at each time $$$i$$$ where $$$2 \leq i \leq N$$$, lights on one more skyscraper are turned on. For the sake of harmony, that skyscraper must be adjacent to some skyscrapers already with lights on.
- Once the lights of a skyscraper are turned on, they remain on until the end of the light show.
- After time $$$N$$$, lights on all the skyscrapers are on.
Your friend told you that at time $$$X$$$, the lights of skyscraper $$$Y$$$ were turned on. Can you find a sequence of turning on the lights of the skyscrapers that matches this information, or report that this is impossible?
Note that if there exist multiple sequences of turning on the lights that are consistent with the given information, you may output any of them.
The first and only line contains three integers: $$$N, X, Y$$$ ($$$1 \leq N \leq 2 \times 10^5$$$, $$$1 \leq X, Y \leq N$$$), the number of skyscrapers, the time of the information, and the index of the skyscraper of the information, respectively.
If it is possible that the target skyscraper appears on at time $$$X$$$, output Yes on the first line. Then, on the second line, output $$$N$$$ integers, the indices of the skyscrapers whose lights are turned on, in chronological order.
Otherwise, output No on the first and only line.
5 2 4
Yes 3 4 2 1 5
5 5 4
No
Sample 1:
Note that the order 5 4 3 2 1 is also accepted.
Hong Kong's outlying islands are a collection of over 250 islands scattered across its surrounding waters, each offering unique charm and attractions. While some, like Lantau Island, are well-known and bustling with activity, others remain tranquil and largely untouched, perfect for those seeking nature, hiking, or a glimpse into traditional village life. These islands are connected by ferry services, making them popular day-trip destinations for both locals and tourists. Their diverse landscapes, from sandy beaches to lush mountains, provide a striking contrast to Hong Kong's urban core.
Different views of Lamma Island, Yung Shue Wan and Sok Kwu Wan side (© The HK HUB) Imagine Hong Kong has $$$N$$$ outlying islands, and two different tour itineraries — Tour A and Tour B — have been planned. Each itinerary lists the islands in a unique order, represented by two permutations $$$A$$$ and $$$B$$$ of the numbers $$$1$$$ through $$$N$$$.
In each operation, you can select a subarray in both tours, say from the $$$l$$$-th to $$$r$$$-th islands that will be visited (with $$$1 \leq l \leq r \leq N$$$), and reorganize the visiting order for that subarray in both tours by sorting it in increasing order. Your challenge is to adjust the itineraries so that Tour A ends up visiting the islands in perfect ascending order, while Tour B does not. Determine whether this is possible, and if so, construct a sequence of operations that achieves the goal using the minimum number of operations.
More formally, you are given $$$2$$$ permutations $$$A$$$ and $$$B$$$ with length $$$N$$$. In each operation, you can pick $$$2$$$ integers $$$1 \leq l \leq r \leq N$$$ and sort the subarrays $$$A[l..r]$$$ and $$$B[l..r]$$$ (inclusive) simultaneously. Determine whether you can successfully sort $$$A$$$ but not $$$B$$$, and if so, provide a construction using the minimum number of operations.
Each test contains multiple test cases. The first line contains a single integer $$$T$$$ ($$$1 \leq T \leq 1000$$$) — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer $$$N$$$ ($$$3 \leq N \leq 1000$$$) — the length of the permutations.
The second line of each test case contains $$$N$$$ integers $$$A_1, A_2, \dots, A_N$$$ ($$$1 \leq A_i \leq N$$$) — the permutation $$$A$$$. It is guaranteed that $$$A$$$ forms a permutation.
The third line of each test case contains $$$N$$$ integers $$$B_1, B_2, \dots, B_N$$$ ($$$1 \leq B_i \leq N$$$) — the permutation $$$B$$$. It is guaranteed that $$$B$$$ forms a permutation.
It is guaranteed that the sum of the values of $$$N$$$ across all test cases does not exceed $$$5000$$$.
For each test case, print -1 if it is impossible to sort $$$A$$$ but not $$$B$$$.
Otherwise, on the first line, print $$$q$$$ ($$$q \geq 0$$$), the minimum number of operations to do so. Then, for the next $$$q$$$ lines, print $$$l$$$ and $$$r$$$, the ranges for the operation. If there are multiple answers, print any.
541 2 3 44 3 2 141 3 2 41 2 4 344 2 1 31 3 4 243 4 1 21 3 2 431 2 31 2 3
0 1 2 3 2 1 3 3 4 -1 -1
In the first set of input data, $$$a$$$ is already sorted but $$$b$$$ isn't. Hence the answer is $$$0$$$.
In the second set of input data, after the operations, $$$a = $$$ 1 2 3 4 and $$$b = $$$ 1 2 4 3. Since $$$a$$$ is not sorted initially, $$$1$$$ is the minimum number of operations to sort $$$a$$$ and not $$$b$$$.
In the third set of input data, after the operations, $$$a = $$$ 1 2 3 4 and $$$b = $$$ 1 4 2 3. It can be proven that $$$2$$$ is the minimum number of operations required.
In the fourth and fifth set of input data, it can be proven that it is impossible to sort $$$a$$$ and not $$$b$$$. Hence the answer is $$$-1$$$.
In Hong Kong, the Chinese (Lunar) New Year is widely celebrated, a time of vibrant traditions and joyous reunions. One of the most cherished customs is the giving of red packets, or "lai see" (利是), filled with money, symbolizing prosperity for the year ahead.
Red Packets (© e-print HK) Ah Ma, the beloved matriarch of the family, takes this tradition very seriously. This year, she has a total of $$$N$$$ one-dollar coins, to distribute among $$$M$$$ red packets for her numerous grandchildren, nieces, and nephews.
However, Ah Ma is a firm believer in numerology and the auspicious power of certain digits.
In particular, the digits 2, 6, and 8 are considered especially lucky, bringing fortune and happiness:
- 2: Symbolizes harmony and balance, as "good things come in pairs" (好事成雙).
- 6: Represents smooth progress and success, as its pronunciation in Chinese is similar to the word for "flow" (流), meaning everything going smoothly.
- 8: Highly lucky because its pronunciation is similar to the word for "wealth" or "prosperity" (發).
On the other hand, the digits 1, 3, 4, 5, 7, and 9 are seen as unlucky, associated with misfortune:
- 4: Considered unlucky because its pronunciation is similar to the word for "death" (死).
- 1, 3, 5, 7, 9: Giving out red packets that end with odd digits only happens in funerals, so these digits are commonly associated with misfortune.
The digit 0 is neutral; considered neither lucky nor unlucky.
Therefore, Ah Ma insists that no red packet should contain an amount ending in an unlucky digit (1, 3, 4, 5, 7, or 9) (e.g. 4, 14, 23, 1, 59). While adhering strictly to this rule, she wants to maximize the number of red packets containing an amount ending in a lucky digit (2, 6, or 8) (e.g. 22, 48, 1345796, 444444442). Each red packet must also contain a positive amount, as an empty red packet is considered a bad omen.
With the Lunar New Year approaching in just over a week, Ah Ma needs your help. Given the total amount of one-dollar coins $$$N$$$ and the number of red packets $$$M$$$, can you determine if it's possible to distribute all the one-dollar coins, not a single coin less, according to her rules? And if so, what's the maximum number of red packets containing an amount ending in a lucky digit?
The first and only line of input consists of two integers $$$N$$$ and $$$M$$$:
For all cases:
- $$$N \geq 2M$$$
- $$$N$$$ is even
- $$$2 \leq N \leq 2 \times 10^9$$$
- $$$1 \leq M \leq 10^9$$$
If it is not possible to distribute the money such that no red packet contains an amount ending in an unlucky digit, output -1.
Otherwise, output the maximum number of red packets that can contain an amount ending in a lucky digit while adhering to the above rule.
8 4
4
24 5
5
Sample 1: Ah Ma should place 2 one-dollar coins into each red packet. All of them are lucky packets.
Sample 2: Ah Ma should place 2, 6, 8, 6 and 2 one-dollar coins into the red packets respectively. All of them are lucky packets.
On the streets of Hong Kong, double-decker buses are everywhere, serving passengers like you and me at every moment! If you observe them closely, you'll notice that these double-deckers differ in appearance, length, engine sound, and more. This is because they are in different models, and you have been challenged to hop on every model available in the district!
There are $$$N$$$ bus stops, numbered from $$$1$$$ through $$$N$$$. Connecting these bus stops, there are $$$M$$$ bus routes, numbered from $$$1$$$ through $$$M$$$. The $$$i$$$-th route has $$$C_i$$$ unique stops in a specific order and runs bidirectionally. Travelling between two adjacent stops on any route always takes exactly 1 minute. Because buses run very frequently, you can assume that every minute, there is at least one bus at each stop for each direction of every route.
The bus company owns $$$K$$$ distinct double-decker models, numbered from $$$1$$$ through $$$K$$$. The $$$i$$$-th route is assigned to a specific model $$$D_i$$$, and the route is served by that model only.
You start at stop 1 with at most $$$T$$$ minutes. Your goal is to:
- Ride on each of the $$$K$$$ models at least once (i.e., spend at least 1 minute travelling on a route served by that model).
- Return to stop 1 in no more than $$$T$$$ minutes.
Switching from one bus to another at any stop requires no time, and you can always board a bus immediately without waiting. Are you able to complete the challenge?
The first line contains four integers: $$$N$$$, $$$M$$$, $$$K$$$, and $$$T$$$ ($$$2 \leq N, T \leq 100$$$, $$$1 \leq M \leq 20$$$, $$$1 \leq K \leq 10$$$).
The next $$$M$$$ lines each describe a bus route. For the $$$i$$$-th line:
- The line begins with two integers $$$C_i$$$ and $$$D_i$$$: $$$C_i$$$ is the number of stops on this route ($$$2 \leq C_i \leq 20$$$), and $$$D_i$$$ is the model number for this route ($$$1 \leq D_i \leq K$$$).
- This is followed by $$$C_i$$$ integers: $$$S_{i1}, S_{i2}, \ldots, S_{iC_i}$$$, where $$$S_{ij}$$$ is the $$$j$$$-th stop of route $$$i$$$ ($$$1 \leq S_{ij} \leq N$$$).
It is guaranteed that you can travel to every stop from stop 1 and that every model is assigned to at least one route.
If it is possible to hop on all different double-deckers models and be backed at stop 1 on or before $$$T$$$, output a single line Yes, otherwise a single line No.
4 2 2 33 1 1 2 33 2 1 2 4
Yes
3 2 2 32 1 1 22 2 3 1
No
Sample 1:
A valid plan is as follows:
- Travel from stop 1 to stop 2 via route 1, with model 1.
- Then, travel from stop 2 back to stop 1 via route 2, with model 2.
You have used both models (1 and 2) and returned to stop 1 in 2 minutes, which does not exceed $$$T=3$$$. Because buses are always available, you do not have to wait for the next bus at any stop.