Let $$$T = (V, E)$$$ be a tree with $$$n$$$ vertices and $$$n-1$$$ edges. Each edge of the tree can be assigned a colour from $$$\{0, 1, \dots, K-1\}$$$.
A simple path in a tree is called a $$$K$$$-rainbow path if all edges along the path of length $$$K$$$ have distinct colours. An edge is said to be $$$K$$$-rainbow-valid if it lies on at least one $$$K$$$-rainbow path. A tree is called a $$$K$$$-tree if every edge in the tree is $$$K$$$-rainbow-valid.
Your task is to assign colours to the edges of a given tree to form a K-tree with the largest possible $$$K$$$. For each edge $$$e$$$, you must report its assigned colour $$$c(e) \in \{0, 1, \dots, K-1\}$$$ and the endpoints of a K-rainbow path that contains $$$e$$$.
All indices are zero-based. If multiple valid colourings or paths exist, any may be output.
The first line contains a single integer $$$ n $$$ $$$(2 \leq n \leq 10^5)$$$. In the next $$$n - 1$$$ lines you are given the edges of the tree. In each of these lines you are given $$$u$$$ and $$$v$$$ $$$(0 \leq u, v \leq n - 1)$$$ describing an edge between nodes $$$u$$$ and $$$v$$$.
Your output must consist of $$$n$$$ lines.
In the first line print the maximum possible $$$K$$$.
In the next $$$n - 1$$$ lines, each line should contain three integers: $$$c$$$, $$$u$$$ and $$$v$$$, where $$$0 \leq c \leq K - 1$$$ and $$$0 \leq u, v \leq n - 1$$$. These integers specify the colour $$$c$$$ of an edge and the path between $$$u$$$ and $$$v$$$. This path includes the edge $$$e$$$ and is a K-rainbow. The order of $$$u$$$ and $$$v$$$ does not matter.
Edges must be printed in the order they were given in the input.
30 12 1
2 1 2 0 0 0 2
60 42 35 02 12 0
3 2 3 4 0 4 3 2 3 5 0 4 1 1 3 4
162 32 44 55 01 56 74 68 73 94 107 118 1210 1314 1215 9
7 6 8 15 5 8 15 5 14 0 6 14 0 6 14 1 3 3 14 4 8 15 2 3 14 0 8 15 5 14 13 2 15 11 1 3 14 6 14 13 0 3 14 1 8 15
This is the second sample test. We have a tree with 6 nodes. Colours are written on the edges. Maximum possible K is 3 and for every edge $$$e$$$ there exists a path that includes $$$e$$$ and is a 3-rainbow.
Edge $$$e_1 = \{0, 4\}$$$ has colour 2, the path between 3 and 4 includes $$$e_1$$$ and is a 3-rainbow.
Edge $$$e_2 = \{2, 3\}$$$ has colour 0, the path between 4 and 3 includes $$$e_2$$$ and is a 3-rainbow.
Edge $$$e_3 = \{5, 0\}$$$ has colour 2, the path between 3 and 5 includes $$$e_3$$$ and is a 3-rainbow.
Edge $$$e_4 = \{2, 1\}$$$ has colour 0, the path between 4 and 1 includes $$$e_4$$$ and is a 3-rainbow.
Edge $$$e_5 = \{2, 0\}$$$ has colour 1, the path between 3 and 4 includes $$$e_5$$$ and is a 3-rainbow.
Every morning at 9 AM sharp, your manager posts a Slack message: "Good morning team! We're restructuring again to align with our strategic vision!!"
Here at MegaCorp Inc, we don't have departments; we have $$$m$$$ dynamic Synergy Hubs numbered $$$1$$$ to $$$m$$$. You are starting your journey today in Hub $$$1$$$, which, as you recall, brought down production twice in the last month.
To navigate this fluid ecosystem, we transition using one of our $$$k$$$ Key Strategic Methodologies (e.g., Agile Transformation, Lean Optimisation, Synergistic Disruption). In other words, there are several forms you can file to exit/enter hubs, which can be categorized into $$$k$$$ methodologies. Who comes up with this stuff?
Management maintains meticulous transparency. Each Hub $$$i \in \{1, \dots, m\}$$$ has its own unique set of forms for each Methodology $$$j \in \{1, \dots, k\}$$$, which for some Hub $$$i$$$ can be split as follows.
There are $$$c_{i,j}$$$ unique Departure Forms of type $$$j$$$ (like Agile Exit Protocol A-1).
Similarly, there are $$$c_{i,j}$$$ unique Onboarding Forms of type $$$j$$$ for that Hub.
Management assures us that the number of ways to leave a Hub using a methodology is always the same as the number of ways to join it using that same methodology. It's about Process Symmetry.
Every day, you must execute a "Strategic Realignment." This consists of two steps:
The Methodology type you use to leave a Hub CANNOT be the same as the Methodology type you use to join your new Hub.
As your manager explained: "If you exit with Synergy, you must enter with Lean. We can't have you leaving and joining via Agile! Think of the paradigm shifts!"
Your Task
Your manager, holding his morning coffee, now turns to you. "For our Future-State Planning meeting, I need a simple number."
How many distinct sequences of forms could you possibly file over exactly $$$d$$$ days?
You look at the clock. It's 9:05 AM. It's going to be a long week.
The first line contains three integers $$$1 \leq m \leq 10^4$$$, $$$1 \leq k \leq 40$$$ and $$$1 \leq d \leq 10^6$$$ — the number of hubs, the number of methodologies, and the number of days.
The $$$i$$$-th line of the next $$$m$$$ lines contains $$$k$$$ integers $$$c_{i,1}, c_{i,2}, \dots, c_{i,k}$$$ ($$$0 \leq c_{i,j} \leq 10^9$$$), where $$$c_{i,j}$$$ is the number of forms to enter/exit hub $$$i$$$ with methodology $$$j$$$.
It is guaranteed that for every Hub, there are the same number of Departure and Onboarding Forms.
You always start in Hub 1.
Print a single integer — the total number of distinct sequences of daily exit and entry forms possible after $$$d$$$ days, modulo $$$10^9 + 7$$$.
2 3 11 0 22 1 2
13
2 2 22 20 3
148
Long ago, in a quiet tower filled with bubbling cauldrons and dusty spellbooks, there lived a rather absent-minded magician. One evening, he decided to brew a Potion of Power. The potion starts with a magical potency of $$$1$$$ — modest, but full of potential.
The magician owns two ancient runes, called Rune $$$A$$$ and Rune $$$B$$$, each capable of multiplying the potion's current magical power by a fixed (nonnegative) integral factor. He does, however, have a terrible memory. He can't recall the exact values of these multipliers — only that:
Despite this risk, the magician is quite fond of experimenting. He decides to apply every possible sequence of $$$n$$$ runes, each either $$$A$$$ or $$$B$$$, to the initial potion to see what kinds of magical strengths he can obtain.
As he is tinkering with the runes, he realizes that he will have way too much potion. He is only planning to take a single sip — exactly one unit of magical power! Now he will need to store the remaining power from all experiments in his flasks.
By some strange coincidence of fate, as often happens in magic, each of his (infinitely many) flasks can hold exactly $$$n + 1$$$ units of magical power.
The magician is an orderly man; he refuses to leave any flask partially filled. So now he wonders:
Will it be possible to divide all of the leftover magical power (after taking his sip) into flasks such that no flask is partially filled, regardless of what the power multiplier of rune $$$A$$$ is?
The first line contains the number $$$t$$$ of test cases ($$$1 \leq t \leq 10^3$$$).
Each of the following $$$t$$$ lines contains a single integer $$$n$$$, the number of rune applications ($$$0 \leq n \leq 10^{8}$$$).
For every test case, output a single line containing "yes" if all of the remaining magical power can be bottled according to the magician's specifications for any value that the power multiplier of rune $$$A$$$ can take, and "no" otherwise.
225
yesno
Nicolas is creating a new playlist with songs from different genres. He has $$$n$$$ different genres, and each genre has $$$c_i$$$ different songs. Each song is in exactly one genre. He wants to add $$$m$$$ songs to the playlist, and they should be chosen from the different genres as evenly as possible so the playlist has a smooth sound.
Formally, given $$$n$$$ genres with $$$c_i$$$ songs each, he wants to choose $$$m$$$ songs without replacement as evenly as possible. What's the minimum difference between the number of songs from the most taken genre and the number of songs from the least taken genre?
Assuming $$$k_i$$$ is the amount of songs he picks from genre $$$i$$$, he wants to minimize:
$$$$$$\max k_i - \min k_i$$$$$$
subject to $$$0 \leq k_i \leq c_i$$$ and $$$\sum k_i = m$$$.
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$), the number of test cases.
The first line of each test case contains two integers $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), the number of genres, and $$$m$$$ ($$$1 \leq m \leq \sum c_i$$$), the number of songs he wants to pick for the playlist.
The second line of each test case contains $$$n$$$ integers $$$c_1,\dots,c_n$$$ ($$$1 \leq c_i \leq 10^9$$$), the number of songs in the $$$i$$$'th genre.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
Print one integer per test case, the minimum difference of the count of songs between the most and the least taken genre.
24 51 1 3 34 83 4 2 5
10
In the first test case, Nicolas can pick $$$1$$$ song each from the first two genres, $$$2$$$ songs from the third genre and $$$1$$$ song from the last genre. This will lead to a difference of $$$2 - 1 = 1$$$.
In the second test case, Nicolas can pick $$$2$$$ songs from each genre so there is a maximum difference of $$$0$$$.
A small kingdom consists of one road. Every house on the street is numbered sequentially from $$$A$$$ to $$$B$$$ $$$(A, A + 1, \dots, B - 1, B)$$$. The key number of a house is the largest odd divisor of the house number.
The king is throwing a party and wants to invite a select number of VIP guests. Only guests living in houses with a key number of $$$1$$$ are allowed to attend the party.
To estimate how much food and how many drinks he needs to buy, the king wants to know how many VIP guests there are.
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^5$$$), the number of test cases.
The first line of each test case contains two integers $$$A$$$ $$$(1 \leq A \leq 10^{18})$$$, the first house number, and $$$B$$$ $$$(A \leq B \leq 10^{18})$$$, the last house number.
For each test case, print the number of invited VIP guests; that is, the number of houses where the key number is 1.
31 530 351 1000000
3120
You have a grid of $$$N \times M$$$ square cells, with height $$$N$$$ units and width $$$M$$$ units. The outer border of the grid is a wall. There are 2 holes in the wall: to access the entrance (top left) cell and the exit (bottom right) cell.
The internal part of the grid consists of $$$L=2\cdot N \cdot M-(N+M)$$$ internal segments of unit length. You have $$$K$$$ walls of unit length, and you must place each of those walls at one of the internal segments (you can't place two or more walls at the same segment).
For example, the picture below shows a grid with $$$N=3$$$ and $$$M=5$$$. There are $$$L=22$$$ internal segments and there are $$$K=6$$$ walls placed.
You place walls randomly. That is, you take a wall, pick one of the free internal segments with equal probability, and place the wall there. You repeat this procedure until you have placed all $$$K$$$ walls. Let's call the result a random maze with $$$K$$$ walls.
After this, you check if the maze is solvable. The maze is solvable if there is a path from the top left cell to the bottom right cell. Formally, the maze is solvable if there exists a sequence of cells, such that the first cell in the sequence is the top left cell, the last cell in the sequence is the bottom right cell, and for every two cells adjacent in the sequence, they are adjacent by side in the grid, and there is no wall placed between them.
For every integer $$$K \in [0, L]$$$, compute the probability that a random maze with $$$K$$$ walls is solvable.
Two numbers $$$N,M$$$ — size of the grid. $$$1 \le N \le 7$$$. $$$ 1 \le M \le 100$$$. $$$N \cdot M \le 100$$$.
Print $$$L+1$$$ integers $$$p'_0, p'_1, \dots p'_L$$$ on a single line. $$$p'_K$$$ is the probability that a random maze with $$$K$$$ walls is solvable, modulo $$$10^9+7$$$.
Formally, it can be shown that the probability for a given $$$K$$$ can be expressed as an irreducible fraction $$$p_K=\frac{a_K}{b_K}$$$, where $$$a_K$$$ and $$$b_K$$$ are integers and $$$b_K \not \equiv 0 ~(\text{mod} ~ 10^9+7)$$$. For every $$$K \in [0, L]$$$, output the integer $$$p'_K = a_K \cdot b_K^{-1} ~(\text{mod} ~ 10^9+7)$$$. In other words, output such an integer $$$p'_K$$$ that $$$0 \le p'_K \lt 10^9+7$$$ and $$$p'_K \cdot b_k \equiv a_k ~(\text{mod} ~ 10^9+7)$$$.
2 2
1 1 333333336 0 0
1 4
1 0 0 0
3 2
1 1 809523816 542857147 885714292 0 0 0
In the first test:
In the second test $$$N=1$$$, so if there is at least one wall placed, it always blocks the path from start to end, so the probability of the maze being solvable is 0 for all $$$K \ge 1$$$.
Define $$$d(a,b)$$$ — distance between two strings $$$a$$$ and $$$b$$$ as the number of single-character insertions and deletions needed to transform one string to another.
You are given a list of $$$n$$$ pairwise distinct strings $$$s_1, \dots, s_n$$$ consisting of only lowercase Latin letters. For every string, find the nearest string to it from the same list. That is, for every $$$i$$$, find such $$$j$$$ that $$$j \ne i$$$ and $$$d(s_i, s_j)$$$ is the smallest possible. If there are multiple strings with the same distance, pick the lexicographically smallest one.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.
The first line of each test case contains an integer $$$n$$$ ($$$ 2 \le n \le 2 \cdot 10^4$$$) — the number of strings.
Then $$$n$$$ lines follow, containing strings $$$s_1, \dots, s_n$$$ consisting of only lowercase Latin letters, $$$1 \le |s_i| \le 8$$$. It is guaranteed that the strings are pairwise distinct.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^4$$$.
For each test case, print two lines of $$$n$$$ integers, separated by spaces.
On the first line, print numbers $$$a_1, \dots, a_n$$$, where $$$a_i$$$ is the index of the nearest string to $$$s_i$$$ ($$$1 \le a_i \le n, a_i \ne i$$$).
On the second line, print the corresponding smallest distances: $$$d(s_1, s_{a_1}), \dots d(s_n, s_{a_n})$$$.
32abcabd6abcdeabcdabcfebcdebcfeaaaaa4codeforccodeforcespolygon
2 12 22 1 5 1 3 21 1 1 1 1 72 1 2 24 4 6 9
Note that the definition of distance in this problem is different from the standard "edit distance" definition, as it doesn't allow replacements.
You have a transparent band of length N units and width M units. It's split into $$$N \times M$$$ unit squares.
You take two sides of the band (the ones with length M units), rotate one of them by 180 degrees, and connect them, getting a Möbius band of length N and width M. Then you paint each square on the band in one of $$$K$$$ colors.
Two painted Möbius bands of the same size are considered to have the same coloring if you can move one of them in such a way that it becomes indistinguishable from the other one. Otherwise, they have different colorings.
Find the number of colorings of the given Möbius band in K colors, modulo $$$10^9+7$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1\le t \le 100$$$). The description of the test cases follows.
Each test case contains 3 integers $$$N,M,K$$$ on a single line. $$$1 \le N \le 10^9$$$. $$$1 \le M,K \le 10^{18}$$$.
For every test case, output a single integer on a separate line — the number of colorings, modulo $$$10^9+7$$$.
62 2 23 5 21 3 23 1 240 6 3100 200 1
63100649079603431
The picture below shows 4 instances of the same coloring for $$$N=40, M=6, K=2$$$.
In Mancala solitaire, you are given stones in a line of holes, with hole 0 being special and containing no stones to start with.
In each turn, you choose a number $$$k$$$ such that there are exactly $$$k$$$ stones in hole $$$k$$$. Then you remove the stones from hole $$$k$$$ and put one stone each into the holes $$$k - 1, k - 2, \dots, 1, 0$$$:
The goal is to get all stones in hole 0 after some number of turns. (For example, you can do this in the above example by picking $$$k_1=3, k_2=1, k_3=2$$$, and finally $$$k_4=1$$$.)
You want to show this game to your friend and create a starting position that makes it possible for him to successfully complete the game (getting all stones in hole 0). Give such a starting position for $$$N$$$ stones. It is guaranteed that this is always possible.
The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$), the number of test cases.
The first line of each test case contains an integer $$$N$$$ $$$(1 \leq N \leq 10^{9})$$$, the number of stones you want to place in total.
It is guaranteed that the sum of all $$$N$$$ will not exceed $$$10^9$$$.
For each test case: Print one integer $$$m$$$, the number of the last hole which contains at least one stone. In the next line, print $$$m$$$ integers, the number of stones in the $$$i$$$'th hole. You can ignore hole 0.
31415
1130 1 361 2 0 2 4 6
You are given a tree $$$T$$$, and an undirected simple graph $$$G$$$. Both $$$T$$$ and $$$G$$$ have vertices numbered $$$1, 2, \dots, N$$$.
A pair of vertices $$$(u, v)$$$ is called good if the unique path between $$$u$$$ and $$$v$$$ in the tree $$$T$$$ is also a path in $$$G$$$.
Count the number of ordered good pairs $$$(u, v)$$$.
Note that $$$(u, u)$$$ is considered good for all $$$u$$$ (the path of length $$$0$$$).
The first line contains two integers $$$N$$$ and $$$M$$$ $$$(3 \le N, M \le 2 \cdot 10^5)$$$ — the number of vertices and edges in $$$G$$$.
The next $$$N - 1$$$ lines describe the tree $$$T$$$. Each line contains two integers $$$a_i, b_i$$$ $$$(1 \le a_i, b_i \le N)$$$ — an edge of $$$T$$$.
The next $$$M$$$ lines describe the graph $$$G$$$. Each line contains two integers $$$x_i, y_i$$$ $$$(1 \le x_i, y_i \le N)$$$ — an edge of $$$G$$$.
Print a single integer — the number of ordered good pairs $$$(u, v)$$$.
4 31 22 33 41 33 22 4
6
In the example, the good pairs are $$$ (1,1), (2,2), (3,3), (4,4), (2,3), (3,2) $$$. For example, the pair $$$ (1,4) $$$ is not a good pair because the path from 1 to 4 in $$$ T $$$ is $$$ 1-2-3-4 $$$, whereas in $$$ G $$$ it is $$$ 1-3-2-4 $$$, so the paths are different.
You are an intern at a hyperscale AI data center that manages a linear array of $$$n$$$ GPUs. The $$$i$$$-th GPU currently runs a compute load of $$$a_i$$$.
The data center hosts workloads for $$$m$$$ different companies. Each company $$$j$$$ uses a contiguous range of GPUs from index $$$L_j$$$ to $$$R_j$$$. Different companies may share some GPUs if their computations are colocated for efficiency, so these ranges can overlap.
Before a major demonstration, the management team sets strict balance requirements. For each company $$$j$$$, the total effective compute load across its range must lie between $$$A_j$$$ and $$$B_j$$$ inclusive.
You are allowed to adjust the load of each GPU by applying an integer change $$$\Delta_i$$$. Each adjustment can either increase or decrease the load, but all must stay within a non-negative common safety limit $$$k$$$, meaning every GPU's load can change by at most $$$k$$$ units. The smaller the limit, the better the system stability, so you aim to meet all company requirements using the smallest possible $$$k$$$.
Additionally, for hardware stability, each GPU must remain above the minimal safe operating load after adjustment: $$$a_i + \Delta_i \ge 1$$$ for all $$$i$$$.
Find the minimum integer $$$k$$$ such that there exist integer adjustments $$$\Delta_1, \Delta_2, \ldots, \Delta_n$$$ satisfying, for every company $$$j$$$,
$$$$$$ A_j \le (a_{L_j} + \Delta_{L_j}) + (a_{L_j+1} + \Delta_{L_j+1}) + \dots + (a_{R_j} + \Delta_{R_j}) \le B_j. $$$$$$
If this is impossible for any $$$k$$$, output -1.
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 1 \cdot 10^3)$$$ — the number of GPUs and the number of companies.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ $$$(1 \le a_i \le 10^9)$$$ — the current compute loads of the GPUs.
Each of the following $$$m$$$ lines describes one company and contains four integers $$$L_j$$$, $$$R_j$$$, $$$A_j$$$, and $$$B_j$$$ $$$(1 \le L_j \le R_j \le n,\; 1 \le A_j \le B_j \le 10^{12})$$$, meaning the $$$j$$$-th company uses all GPUs from index $$$L_j$$$ to $$$R_j$$$ and its total load must lie between $$$A_j$$$ and $$$B_j$$$ inclusive.
Print a single integer: the minimal possible $$$k$$$ such that there exist integer adjustments meeting all company conditions, the per-GPU safety floor $$$a_i + \Delta_i \ge 1$$$, and $$$|\Delta_i| \le k$$$ for all GPUs. If no such $$$k$$$ exists, print $$$-1$$$.
5 32 8 5 7 41 3 15 202 5 16 204 4 6 6
2
For the sample test, $$$k = 0$$$ or $$$k = 1$$$ are not feasible. For $$$k = 2$$$, possible final compute load distributions include $$$[4, 7, 4, 6, 3]$$$ or $$$[3, 8, 4, 6, 2]$$$.