Truck-Kun is traversing the complex metropolis of Tokyo. Tokyo is represented by a graph with $$$N$$$ ($$$1 \le N \le 300$$$) nodes. There is a directed edge between every pair of nodes, each having some amount of people on it. $$$w_{i,j}$$$ ($$$-10^9 \le w_{i, j} \le 10^9$$$). denotes the amount of people on the edge going from node $$$i$$$ to node $$$j$$$ (yes, there can be negative people). Since Truck-Kun wants to be a helpful truck, he wants to pick up as many people as possible by traversing through a simple path in the graph. A simple path of length $$$K$$$ is defined as a list of distinct nodes $$$a_1, a_2, \ldots, a_K$$$. The amount of people on a simple path is defined as $$$\sum_{i=1}^{K-1} w_{a_i,a_{i+1}}$$$. Since Truck-Kun knows this problem is hard, he only wants you to estimate the maximum amount of people that he can pick up by traversing through a simple path. Your answer will be considered correct if it is at least half of the true maximum. Formally, if $$$v$$$ is the true maximum and your code outputs $$$x$$$, it will be considered correct if $$$x \ge \frac{v}{2}$$$.
The first line contains a single integer $$$N$$$ ($$$1 \le N \le 300$$$).
The next $$$N$$$ lines each contain $$$N$$$ integers. The integer on the $$$i$$$-th row and $$$j$$$-th column denotes $$$w_{i, j}$$$ ($$$-10^9 \le w_{i, j} \le 10^9$$$).
Output a single integer $$$x$$$ ($$$0 \le x \le 10^{18}$$$), denoting an estimate of the maximum amount of people that Truck-Kun can pick up by traversing through a simple path. Your answer will be considered correct if it is at least half of the true maximum. Formally, if $$$v$$$ is the true maximum and your code outputs $$$x$$$, it will be considered correct if $$$x \ge \frac{v}{2}$$$.
40 -10 -10 6-10 0 10 -10-10 -10 0 -10-10 -5 1 0
11
In the samples, an optimal simple path is $$$1$$$, $$$4$$$, $$$2$$$, $$$3$$$. This path contains $$$w_{1, 4} + w_{4, 2} + w_{2, 3} = 1 - 5 + 10 = 11$$$ people.
Lazy Bob has recently discovered how cool trucks are, so one day he decides to stand on the side of the freeway and stare at some. In one given day, he knows that he will see $$$N$$$ ($$$2 ≤ N ≤ 200,000$$$) trucks pass by him.
He notices that each truck has a defining feature: the length between the front and back wheels, given by an integer $$$a_i$$$ ($$$1 ≤ a_i ≤ 1,000,000$$$). All of the trucks he sees have different $$$a_i$$$ values.
Now, Bob wants to take two pictures, each containing a different truck, to show to his friends at school. Because longer trucks are cooler, but he wants to show his friends the variety of lengths in trucks, he assigns a pair of trucks with lengths $$$a_i$$$ and $$$a_j$$$ an arbitrary score of $$$(a_i + a_j)^{|a_i - a_j|}$$$. Please help Bob find the maximum such value for any pair of trucks $$$i ≠ j$$$. Because this value can be very large, give Bob the maximum truck-pair score (mod $$$10^9 + 7$$$). Just to clarify, Bob wants [the maximum truck-pair score] (mod $$$10^9 + 7$$$), not the maximum remainder of a truck-pair score when divided by $$$10^9 + 7$$$.
Line 1: One integer $$$N$$$ ($$$2 ≤ N ≤ 200,000$$$).
Line 2: $$$N$$$ space-separated integers: $$$a_1$$$, $$$a_2$$$, … $$$a_N$$$ ( $$$1 ≤ a_i ≤ 1,000,000$$$, all $$$a_i$$$ distinct), each describing the $$$i$$$th truck's length.
Line 1: One integer representing the remainder when the maximum truck-pair score between any pair of trucks is divided by $$$10^9 + 7$$$.
3 1 5 2
1296
Here are the scores for each pair of trucks:
$$$1$$$ & $$$2$$$: $$$(1+5)^{|1-5|} = 6^4 = 1296$$$
$$$1$$$ & $$$3$$$: $$$(1+2)^{|1-2|} = 3^1 = 3$$$
$$$2$$$ & $$$1$$$: $$$(5+1)^{|5-1|} = 6^4 = 1296$$$
$$$2$$$ & $$$3$$$: $$$(5+2)^{|5-2|} = 7^3 = 343$$$
$$$3$$$ & $$$1$$$: $$$(2+1)^{|2-1|} = 3^1 = 3$$$
$$$3$$$ & $$$2$$$: $$$(2+5)^{|2-5|} = 7^3 = 343$$$
The maximum truck-pair score is between trucks $$$1$$$ & $$$2$$$, and that value, when taken (mod $$$10^9 + 7$$$), is $$$1296$$$.
Lazy Bob lives in Bobland, a country with $$$N$$$ ($$$2 ≤ N ≤ 100,000$$$) cities, each labeled with a number from $$$0…N-1$$$. Each city $$$x$$$ has a one way road to exactly one other city: $$$2x$$$ (mod $$$N$$$).
Lazy Bob is standing at city $$$K$$$ ($$$0 ≤ K ≤ N-1$$$). A self-driving car starts at city $$$1$$$ and keeps driving on one way roads, keeping a running sum of the labels of all the cities it goes through (including city $$$1$$$). However, because this running sum can be very big, it displays the remainder when this sum is divided by $$$N+1$$$.
Bob is curious to know if he will, at some point, see every value from $$$0$$$ to $$$N$$$ on the autonomous car's display. Help Bob by printing "YES" if this is the case, and "NO" otherwise (without the quotes). Because Bob is lazy (it is part of his name, after all), he will permanently stay in city $$$K$$$.
Line 1: Two space-separated integers, $$$N$$$ and $$$K$$$ ($$$2 ≤ N ≤ 100,000$$$, $$$0 ≤ K ≤ N-1$$$).
Line 1: "YES" if Bob will at some point see every value from $$$0$$$ to $$$N$$$ on the self-driving car's display, and "NO" otherwise (without the quotation marks)
3 1
YES
Here are the first 8 value-city states that the car will reach, with the value displayed (mod $$$N+1$$$), as it is on the car:
1: value: 1 city: 1
2: value: 3 city: 2
3: value: 0 city: 1
4: value: 2 city: 2
5: value: 3 city: 1
6: value: 1 city: 2
7: value: 2 city: 1
8: value: 0 city: 2
Bob is at city 1, and he will see value 0 at step 3, value 1 at step 1, value 2 at step 7, and value 3 at step 5. These are all of the possible values, (mod $$$N+1$$$), so the answer is "YES".
It's common knowledge that Corviknight fly air taxis in Galar. However, since they are always on edge due to the presence of Tinkaton, they think about interesting number theory properties to occupy their minds.
One day, Rowlet proposed a simple and fun game to the Corviknight population. It is known that Galar has $$$N$$$ cities, and each has a unique population $$$a_i$$$. Rowlet wants to find the number of ordered triples of cities $$$(i, j, k)$$$ such that the greatest common divisor of the populations of the first two cities is equal to the least common multiple of the populations of the second two cities.
The first line of input contains a number $$$T$$$ $$$(1 \leq T \leq 5*10^4)$$$, denoting the number of test cases.
Each test case contains on its first line $$$N$$$ $$$(1 \leq N \leq 2*10^5)$$$, the number of cities in Galar. The second line contains $$$N$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq 2*10^5)$$$. All values are pairwise distinct.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$2*10^5$$$.
A single number, the number of triples.
431 2 441 6 2 361 3 4 8 6 2451 7 2 5 3
1 2 8 0
In the first test case, the only valid triple is $$$(3, 2, 1)$$$, since $$$gcd(a_3, a_2) = lcm(a_2, a_1)$$$.
In the second test case, the valid triples are $$$(2, 3, 1)$$$ and $$$(2, 4, 1)$$$.
In the last test case, it can be shown that there are no valid triples.
Chad the chauffeur driver has $$$N$$$ trips scheduled for today. For each trip, we know that it starts at time $$$s_i$$$ and ends at time $$$e_i$$$. If a trip overlaps with another, the later trip is delayed and starts at the end of the earlier trip. A trip's start time can be the same as a previous trip's end time. Chad can also cancel at most $$$K$$$ trips.
To stop Chad from overworking himself, help him find the earliest time he can finish his trips.
Line 1: Two integers, $$$N$$$ and $$$K$$$ ($$$1 ≤ N ≤ 4000$$$, $$$1 ≤ K \lt N$$$).
Lines 2…$$$N$$$+1: Two integers, $$$s_i$$$ and $$$e_i$$$, representing the $$$i$$$th trip's starting time and ending time ($$$1 ≤ s_i \lt e_i ≤ 10^9$$$).
Line 1: One integer representing the earliest time Chad can finish his trips.
3 11 65 75 8
8
By canceling the last trip, Chad has to work only from $$$t$$$=1 to $$$t$$$=8.
Recently, Sparkle has been interested in vehicles, so she has set up a number line and placed $$$N$$$ ($$$1 \le N \le 5000$$$) trucks with equal mass on it. The $$$i$$$-th truck is initially located at position $$$x_i$$$ ($$$1 \le x_i \le 10^9$$$) with velocity $$$v_i$$$ ($$$-10^9 \le v_i \le 10^9$$$). Since this is all a dream, when two trucks collide, they will not explode, but rather undergo a perfectly elastic collision, ie. if two trucks collide, their velocities will be swapped. Sparkle is now curious about the number of times the trucks will collide, and she wants you to find this number or tell her that there will be infinite collisions. Note that if $$$k$$$ trucks collide at the same time, then this will be counted as $$$\frac{k(k - 1)}{2}$$$ collisions.
The first line contains a single integer $$$N$$$ ($$$1 \le N \le 5000$$$).
Each of the next $$$N$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le 10^9$$$, $$$-10^9 \le v_i \le 10^9$$$). It is guaranteed that all $$$x_i$$$ are distinct.
Output a single integer denoting the total number of collisions or $$$-1$$$ if there will be infinite collisions.
21 12 -1
1
The two trucks will move towards each other and collide once before going into opposite directions and never colliding again.
Ruien is traveling to Asia from Canada. During the 14-hour long flight, he gets so bored he tries to steal his friend Alex's passwords.
All of Alex's passwords are encoded in a square matrix. However, to avoid remembering an entire matrix of numbers, Alex decides to remember only two sequences, so that he can compute the matrix by finding the product of these sequences. To puzzle any potential hacker even more, Alex never uses his square matrix directly, but instead uses the $$$K$$$th power of it.
Help Ruien compute this $$$K$$$th power. Specifically, for two sequences $$$a_1,...,a_N$$$ and $$$b_1,...,b_N$$$, let the $$$N$$$ by $$$N$$$ square matrix $$$A$$$ satisfy $$$A_{(i,j)}=a_i*b_j$$$. Let $$$B$$$=$$$A^K$$$.
Find the sum of the elements of $$$B$$$.
Output your answer modulo $$$998244353$$$.
Line 1: Two integers, $$$N$$$ and $$$K$$$ ($$$1 ≤ N ≤ 10^5$$$, $$$0 ≤ K \lt 998244353$$$).
Line 2: Sequence $$$A$$$, the $$$i$$$th number being $$$a_i$$$ ($$$|a_i|≤ 10^9$$$).
Line 3: Sequence $$$B$$$, the $$$i$$$th number being $$$b_i$$$ ($$$|a_i|≤ 10^9$$$).
Line 1: One integer, representing the sum of the elements of $$$B$$$, modulo $$$998244353$$$.
3 31 2 34 5 6
92160
$$$A$$$ is the matrix:
4 5 6
8 10 12
12 15 18
Two thousand years ago, someone took the first step towards defeating the Dark Lord. Now, Yuria and friends are continuing that journey. However, before they can defeat the Dark Lord, they must first defeat their crippling boredom, since as it turns out, riding on a wagon for months on end is not the most fun experience. Thus, Yuria has devised a game that she and her party can play while on the road. Yuria creates an array of $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) $$$1$$$'s and $$$0$$$'s, represented by the array $$$a_1, a_2, \ldots, a_N$$$ ($$$0 \le a_i \le 1$$$). Then, she will perform $$$Q$$$ ($$$1 \le Q \le 2 \cdot 10^5$$$) queries on the array:
- "1 l r" — Flip the values of all values in the subarray $$$a_l, a_{l + 1}, \ldots, a_r$$$. Formally, set $$$a_i = (a_i + 1)\%2$$$ for all $$$l \le i \le r$$$.
- "2 l r" — Play a game using the values in the subarray $$$a_l, a_{l + 1}, \ldots, a_r$$$, where players take turns selecting a maximal subarray containing either all $$$1$$$'s or all $$$0$$$'s and remove it. The player who cannot make a move loses. Note that any subarray a player chooses must be maximal, meaning that it cannot be contained by a larger subarray containing all $$$1$$$'s or all $$$0$$$'s. Since Yuria is not very responsible at cleaning up after herself, after playing the game, all of the values in the subarray will be reset to $$$0$$$, ie. $$$a_i = 0$$$ for all $$$l \le i \le r$$$. Please tell Yuria if she will win as the player who makes the first move.
The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$1 \le N, Q \le 2 \cdot 10^5$$$).
The second line contains $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$ ($$$0 \le a_i \le 1$$$).
The next $$$Q$$$ lines each contain three integers $$$t$$$, $$$l$$$, and $$$r$$$ ($$$1 \le t \le 2$$$, $$$1 \le l \le r \le N$$$).
For each query of type $$$t = 2$$$, output "YES" if the player who makes the first move will win, "NO" if the player who makes the second move will win, and "DRAW" if the game will end in a tie.
9 71001110102 7 92 6 72 3 91 6 72 4 81 4 42 6 7
YES NO YES YES YES
The first query uses the subarray $$$010$$$, and it can be shown that Yuria will win as the first player.
After the first query, the subarray is reset to $$$0$$$, so the array will become $$$100111000$$$.
After the third query, the array values are $$$100000000$$$.
The fourth query flips the interval $$$[6, 7]$$$, so the array will become $$$100001100$$$.
In last year's GPL, Rowlet was playing around with an AI Duck. It was not the smartest duck then, but since then its intelligence has increased sharply! Rowlet will need to find a proper name for it, but for now, it is called Iron Bundle.
Unfortunately, Iron Bundle is extremely fast, so Rowlet has dispatched Psyduck to find it. Psyduck knows it is at one of the $$$N$$$ metro stations in Medali City (to save costs, there are $$$N - 1$$$ sections of track between two stations) but doesn't know which one. As a result, Psyduck will randomly begin searching at one of the $$$N$$$ stations. Rowlet wants to know what the sum of the shortest paths between all possible starting points of Psyduck and Iron Bundle are.
Rowlet has enlisted the help of the local Archaludon to disable exactly one section of track. Archaludon can also sense Iron Bundle (being a Steel type helps), and will tell Rowlet which side of the disabled track Iron Bundle is on. Then, Rowlet can ensure that Psyduck can always reach Iron Bundle. Notice that this drastically cuts down the number of starting pairs for Psyduck and Iron Bundle.
The first line consists of the number $$$T$$$ ($$$1 \leq T \leq 5*10^4$$$), the number of testcases.
Each test case contains on its first line $$$N$$$ ($$$2 \leq N \leq 2*10^5$$$), the number of stations in Medali City.
The next $$$N - 1$$$ lines contain two integers $$$a_i$$$, $$$b_i$$$ $$$(1 \leq a_i, b_i \leq N, a_i \neq b_i)$$$, representing a section of track.
It is guaranteed that the sum of $$$N$$$ across all test cases does not exceed $$$2*10^5$$$.
For each testcase, output a single line containing the minimum sum of lengths.
341 21 33 451 21 32 42 551 22 32 42 5
2 5 9
In the first test case, it is optimal to remove the track between $$$1$$$ and $$$3$$$. Then we are left with two groups of interconnected stations $$$(1-2)$$$ and $$$(3-4)$$$, which each have path length sum 1.
One day, Lazy Bob was sitting on his chair on the side of the freeway, as he usually does, just staring into empty space (and watching for trucks of course). When all of a sudden, a genie showed up out of nowhere in a sick Lambo. The genie was named Genie Pre-Trained Transformer, or GPT for short, but most people call him Generous George.
Unfortunately, George was not as generous as his name implied, because instead of granting Bob three wishes, he gave Bob a puzzle. However, if Bob managed to solve this puzzle, he would receive an infinite amount of money (which Bob loves, because he wants his own collection of Lamborghinis). The puzzle is defined as follows:
• You are given a number containing $$$N$$$ digits ($$$1 ≤ N ≤ 200,000$$$). All of the digits are either $$$1$$$ or $$$2$$$.
• You are also given $$$K$$$ ($$$0 ≤ K ≤ 10^9$$$) coins which you can use to perform operations on the number.
• The first operation allows you to replace any digit with a $$$1$$$ for cost $$$c_1$$$ and with a $$$2$$$ for cost $$$c_2$$$.
• The second operation allows you to swap any two digits at indices $$$i$$$ and $$$j$$$ for cost $$$|i - j|$$$.
• Using only the coins that you have, minimize the number with these two operations.
Lazy Bob took one good look at this puzzle and decided that he could not bother to solve it. However, the prospect of having infinite Lambos (and maybe even his own trucks) does entice him. The genie also said something about having multiple guesses for the minimum, but each guess will cause Bob to lose $1 out of his infinite amount (unfortunately, Bob does not understand the concept of infinity, so he does not realize he could just keep guessing until he gets the right answer).
Therefore, Bob tasks you with solving this puzzle for him, and only gives you one try: he cannot afford to lose a single dollar. Help him find the minimum possible value the number can have.
Line 1: Four space-separated integers $$$N, K, c_1, c_2$$$ ($$$1 ≤ N ≤ 200,000$$$, $$$0 ≤ K, c_1, c_2 ≤ 10^9$$$). Line 2: One integer with $$$N$$$ digits (all of which are either $$$1$$$ or $$$2$$$) representing the number that Generous George gave to Lazy Bob.
Line 1: An $$$N$$$ digit number (all of which are either $$$1$$$ or $$$2$$$) representing the minimum possible number after some amount of operations.
2 1 2 321
12
In this example, Lazy Bob has $$$1$$$ coin, which is not enough for either of the replace operations. However, he can swap the digits at positions $$$1$$$ and $$$2$$$ with a cost of $$$|1-2|$$$ = $$$1$$$ coin, and get the minimum possible number: $$$12$$$.
On his visit to Paris, Lazy Bob encountered the Eiffel Tower. He thought to himself: "Wow, that's a tall tower." Also on his visit, he watched acrobats at a Cirque du Soleil event. Combining these two made him think of a genius idea: what if he made a pile of turning 'acrobats' as tall as the Eiffel Tower, but out of his favorite automobile, the truck?
The concept would be as follows: Lazy Bob would stack $$$N$$$ ($$$1 ≤ N ≤ 100,000$$$) trucks on top of a small metal ball, each having their backs placed on the fronts of the truck below it. However, all of the trucks would have cool magnetic sides, which allow them to stick to the truck below them, no problem.
However, it is pretty difficult for Bob to think about so many trucks concurrently, since his imagination can't really handle that much complexity; so he asks you to figure something out for him.
He wants to perform a specific operation: rotate a specific truck $$$r_q$$$ ($$$1 ≤ r_q ≤ N$$$) by $$$3366$$$ degrees clockwise around the front/ball below it (he chose this number because it is the biggest number he knows). When a truck $$$r_q$$$ is rotated, all of the trucks on top of it will remain in the same position relative to $$$r_q$$$ because their magnetic sides are super strong.
After each operation, Bob wants to find out the $$$x$$$ and $$$y$$$ coordinates of the head of the last truck, relative to the starting ball which is placed at the origin.
Because Bob's brain is quite mystical, each truck might have different integer lengths, represented by $$$l_i$$$ ($$$1 ≤ l_i ≤ 10,000$$$). Also, you can completely disregard any physics, so trucks can pass through other trucks and their heights and the starting ball can be treated as infinitely small (Bob does not yet know any physics). Also, the trucks can go underground into negative y-coordinates.
At the beginning, the trucks are stacked upward, so the original coordinates of the head of the last truck are ($$$0, sum(l_i)$$$). Help Bob find these coordinates after every one of the $$$Q$$$ ($$$1 ≤ Q ≤ 100,000$$$) rotation operations.
Line 1: Two space-separated integers, $$$N$$$ and $$$Q$$$ ($$$1 ≤ N, Q ≤ 100,000$$$).
Line 2: $$$N$$$ space-separated integers $$$l_1,l_2,...,l_N$$$ ($$$1 ≤ l_i ≤ 10,000$$$).
Line 3: $$$Q$$$ space-separated integers $$$r_1,r_2,...,r_q$$$ ($$$1 ≤ r_q ≤ N$$$).
Line 1…$$$Q$$$: Two space separated floating point numbers (to 3 decimal places, truncated) representing the $$$(x, y)$$$ coordinates after every one of the $$$Q$$$ queries.
2 11 12
0.809 0.412
After one rotation of the second truck, it can be shown that the final coordinates will be $$$(0.809, 0.412)$$$.
The Interastral Peace Corporation (IPC) owns a permutation $$$a_1, a_2, \ldots, a_N$$$ of length $$$N$$$ ($$$2 \le N \le 5 \cdot 10^5$$$).
Infamous hacker Silver Wolf has performed $$$Q$$$ ($$$1 \le Q \le 5 \cdot 10^5$$$) operations to mess up the permutation:
- "l r" — Rotate the interval $$$[l, r]$$$, ie. set $$$a_i = a_{i + 1}$$$ and $$$a_r = a_l$$$.
After these operations, the IPC will have to restore their permutation to its sorted form after reaching performing some swaps on it. However, they are not completely sure of the rotation that Silver Wolf will perform these operations in. Thus, they need you to find the sum of the minimum number of swaps the IPC will need to restore their permutation over all rotations of operations. Formally, let $$$o_0, o_1, \ldots, o_{Q - 1}$$$ be the operations. Silver Wolf may choose any non-negative integer $$$x$$$ and set $$$o_i = o_{(i + x)\%Q}$$$. Let $$$f(x)$$$ be the minimum number of swaps the IPC needs to restore their permutation for a given $$$x$$$ that Silver Wolf chooses. You need to find $$$\sum_{x=0}^{Q - 1} f(x)$$$.
The first line contains two integers $$$N$$$ and $$$Q$$$ ($$$2 \le N \le 5 \cdot 10^5$$$, $$$1 \le Q \le 5 \cdot 10^5$$$).
The next $$$Q$$$ lines contain two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \lt r \le N$$$). The $$$i$$$-th line denotes that Silver Wolf will perform an operation rotating the interval $$$[l, r]$$$.
Output a single integer, $$$\sum_{x=0}^{Q - 1} f(x)$$$.
5 21 42 5
8
For $$$x = 0$$$, the IPC's final permutation will be $$$[2, 4, 1, 5, 3]$$$. This can be sorted by swapping the indices $$$(1, 3)$$$, $$$(2, 3)$$$, $$$(3, 5)$$$, and $$$(4, 5)$$$ in that order.
For $$$x = 1$$$, the IPC's final permutation will be $$$[3, 4, 5, 1, 2]$$$. This can be sorted by swapping the indices $$$(1, 4)$$$, $$$(2, 5)$$$, $$$(3, 4)$$$, and $$$(4, 5)$$$ in that order.