The magical Andy loves the number $$$9$$$. Because of this, he wants every number he sees to be divisible by $$$9$$$.
Andy possesses a special magical ability: he can rearrange the digits of a number in any order he wants. Note that Andy's number cannot have leading 0's before or after rearrangement.
Andy's friend Bob gives him a number. Andy wants to determine whether it is possible to rearrange its digits so that the resulting number is divisible by $$$9$$$.
The first line contains a single integer $$$n$$$ $$$(1 \le n \le 100)$$$ — the number Bob gives him.
—
Tests in subtasks are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
Tests $$$1-20$$$ satisfy no additional constraints.
- Print a rearranged number divisible by $$$9$$$ if it is possible, or
- Print $$$-1$$$ if it is impossible.
If multiple answers exist, print any.
7
-1
81
18
Explanation for the sample cases:
In test case 1, it can be shown it is impossible to rearrange 7 to make a multiple of 9.
In test case 2, 81 can be rearranged to form 18, and 18 is divisible by 9.
—
Problem Idea: culver0412
Problem Preparation: justin_g_20
Occurrences: Novice A, Advanced A
After arriving at Mary's house, Ian gifted a ring of flowers to Mary. The ring of flowers consists of different kinds of flowers. For convenience, we assign a number to each kind of flower and denote the ring by an array of integers $$$a_1,a_2,...,a_n$$$ where $$$n$$$ is the number of flowers in the ring, such that $$$a_i=a_j$$$ if and only if the $$$i$$$-th flower is of the same kind as the $$$j$$$-th flower.
Mary calls a ring of flowers supreme if, for any two adjacent flowers, their kinds are not the same. Note that the $$$n$$$-th flower is adjacent to the first flower. In other words, there does not exist $$$i$$$ such that $$$a_i=a_{i+1}$$$ with indices taken modulo $$$n$$$. An exception to this is that a ring which consists of only $$$1$$$ flower is always regarded as supreme.
Mary wants to cut the ring of flowers which Ian had gifted her into several chains of flowers, and form a new ring of flowers with each chain by joining both of its ends. She wants all of the newly formed rings to be supreme. What is the minimum number of rings Mary needs to form to meet her requirement?
The first line consists of an integer $$$t$$$ ($$$1\le t\le 10^4$$$), the number of test cases.
The first line of each test case consists of a single integer $$$n$$$ ($$$1\le n\le 3\cdot10^5$$$), the number of flowers in the ring.
The second line of each test case consists of $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1\le a_i\le n$$$), where $$$a_i$$$ is the kind of the $$$i$$$-th flower.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3\cdot10^5$$$.
—
Tests in subtasks are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
Tests $$$1-20$$$ satisfy no additional constraints.
For each test case, output an integer, the minimum number of rings that Mary needs to form such that all rings are supreme.
51131 1 141 1 2 271 2 2 6 7 3 471 1 2 1 1 2 3
13224
Explanation for the first three cases: (Note that the number on the circle representing the $$$i$$$-th flower is $$$i$$$, and the background colour of the circle is green if $$$a_i=1$$$, and blue if $$$a_i=2$$$.)
Case 1: The ring is already supreme. So the answer is $$$1$$$.
Case 2: The optimal way is to have three rings, each with one flower in it. So the answer is $$$3$$$.
Case 3: We can cut between flower $$$1$$$ and $$$4$$$, and between flower $$$2$$$ and $$$3$$$, to attain the optimal number of two rings. The answer is $$$2$$$.
—
Problem Idea: culver0412
Problem Preparation: culver0412
Occurrences: Novice B
There is a rooted tree with $$$n$$$ vertices rooted at vertex $$$1$$$. Each vertex holds a binary value $$$v_i$$$ ($$$0$$$ or $$$1$$$). In one move, you choose a vertex $$$v$$$ and flip the value of every vertex on the path from $$$v$$$ to the root (inclusive). Find the minimum number of moves to make all vertices equal to $$$1$$$.
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$), denoting the number of nodes in the tree.
The next line contains $$$n$$$ integers $$$v_i$$$ ($$$v_i \in \{0, 1\}$$$), with the $$$i$$$-th integer denoting the value of node $$$i$$$.
The next $$$n-1$$$ lines contain $$$2$$$ integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i, b_i \le n$$$), denoting an edge connecting $$$a_i$$$ and $$$b_i$$$ in the tree.
—
Tests in subtasks are numbered from $$$1−25$$$ with samples skipped. Each test is worth $$$\frac{100}{25}=4$$$ points.
Tests $$$1-3$$$ satisfy $$$n \leq 20$$$.
Tests $$$4-10$$$ satisfy that the tree is a path. That is, there is an edge from node $$$i$$$ to node $$$i+1$$$ for all $$$1\le i\le n-1$$$.
Tests $$$11-25$$$ satisfy no additional constraints.
Output one integer, the minimum number of moves to end with all vertices equal to $$$1$$$.
41 0 0 11 21 32 4
2
—
Problem Idea: jay_jayjay
Problem Preparation: theyashb
Occurrences: Novice C
You are given $$$N$$$ pairs of integers $$$m_i,b_i$$$ representing lines in the form of $$$y = m_ix + b_i$$$.
You are also given a set of integers $$$S$$$ of size $$$M.$$$
$$$$$$ f(x) = \begin{cases} \text{the minimum of all } N \text{ lines} & x \in S \\ \text{the maximum of all } N \text{ lines} & x \notin S \end{cases} $$$$$$
Determine if $$$f(x)$$$ is convex$$$^{*}$$$.
$$$^{*}$$$ A function is convex if slopes are non-decreasing over all real $$$x$$$. In other words, a function is convex if, for any real $$$x_1 \lt x_2 \lt x_3$$$, the slope from $$$x_1$$$ to $$$x_2$$$ is $$$\le$$$ the slope from $$$x_2$$$ to $$$x_3$$$.
The first line consists of an integer $$$t$$$ ($$$1 \le t \le 100$$$), the number of test cases.
The first line of each test case consists of two integers $$$N$$$ ($$$1 \le N \le 10^5$$$) and $$$M$$$ ($$$0 \le M \le 10^5$$$), the number of lines given, and the size of set $$$S$$$, respectively.
The next $$$N$$$ lines each consist of a pair of integers $$$m_i,b_i$$$ ($$$-10^9 \le m_i,b_i \le 10^9$$$), describing a line.
The next line consists of $$$S_1,S_2,...,S_M$$$ ($$$-10^9 \le S_i \le 10^9$$$), describing the set $$$S$$$.
The sum of $$$N$$$ and the sum of $$$M$$$ over all $$$t$$$ test cases does not exceed $$$10^5$$$.
—
Tests in subtasks are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
Tests $$$1-20$$$ satisfy no additional constraints.
For each test case, output "YES" if $$$f(x)$$$ is convex; otherwise, output "NO."
43 01 2-1 44 -13 11 2-1 44 -113 21 2-1 44 -11 -22 21 21 21 -2
YESYESNOYES
Visualization for sample test:
Lines used in tests 1-3 
Lines used in test 4 —
Problem Idea: Buzzy2
Problem Preparation: Buzzy2
Occurrences: Novice D
Teamscode's problemsetters have become evil! They have trapped you in a maze of $$$N$$$ rooms with $$$E$$$ bidirectional corridors, with at most one corridor between any two distinct rooms and no corridor leading from a room back to itself. Each room is painted with one of $$$L$$$ colors, and every color appears on at least one room. The maze has a peculiar structure: any two rooms of the same color always have the exact same multiset of neighboring room colors.
You don't know where you are or what colors mark the exits. You are given $$$Q$$$ scenarios to handle. In each scenario, you are told your starting room $$$v$$$ and a set of $$$l$$$ exit colors. Find the minimum number of corridors you must traverse to reach a room painted with one of the exit colors, or $$$-1$$$ if no such room is reachable from $$$v$$$.
It is guaranteed that in each scenario, the color of room $$$v$$$ is not among the exit colors.
The first line contains three integers $$$N$$$, $$$E$$$, and $$$L$$$ ($$$2 \le N \le 2 \cdot 10^5$$$, $$$1 \le E \le 4 \cdot 10^5$$$, $$$2 \le L \le 500$$$), the number of rooms, corridors, and colors.
The next $$$E$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le N$$$, $$$u \ne v$$$), describing a corridor between rooms $$$u$$$ and $$$v$$$. No two rooms are connected by more than one corridor. The maze is not necessarily connected.
The next line contains $$$N$$$ integers $$$c_1, c_2, \ldots, c_N$$$ ($$$1 \le c_i \le L$$$), where $$$c_i$$$ is the color of room $$$i$$$.
The next line contains a single integer $$$Q$$$ ($$$1 \le Q \le 2 \cdot 10^5$$$), the number of scenarios.
Each scenario consists of two lines:
- A line with two integers $$$v$$$ and $$$l$$$ ($$$1 \le v \le N$$$, $$$1 \le l \lt L$$$), your starting room and the number of exit colors.
- A line with $$$l$$$ distinct integers $$$a_1, a_2, \ldots, a_l$$$ ($$$1 \le a_i \le L$$$), the exit colors.
It is guaranteed that the color of room $$$v$$$ does not appear among the exit colors.
It is guaranteed that the sum of all $$$l$$$ values does not exceed $$$10^7$$$.
—
Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$5$$$ points.
Tests $$$1-4$$$ satisfy $$$N,Q \le 1000$$$.
Tests $$$5-20$$$ satisfy no additional constraints.
Output $$$Q$$$ integers, one per line. The $$$i$$$-th integer is the minimum number of corridors you must traverse to reach an exit room in the $$$i$$$-th scenario, or $$$-1$$$ if no exit room is reachable.
4 3 44 14 24 31 2 3 422 23 44 11
1 1
In the first scenario, you start in room $$$2$$$ and the exits are colors $$$\{3, 4\}$$$. The closest exit is room $$$4$$$, reached via $$$2 \to 4$$$, so the answer is $$$1$$$.
In the second scenario, you start in room $$$4$$$ and the exits are color $$$1$$$. The closest exit is room $$$1$$$, reached via $$$4 \to 1$$$, so the answer is $$$1$$$.
—
Problem Idea: Bryan Zhu
Problem Preparation: jay_jayjay
Occurrences: Novice E
You are playing games with turtles! In your pocket you find two arrays of integers $$$a$$$, $$$b$$$, of lengths $$$N$$$ and $$$M$$$, satisfying $$$a_i \lt a_{i+2}$$$ and $$$b_i \lt b_{i+2}$$$.
There are two turtles, one red and one blue, which are both at the same position, but are facing opposite directions.
The red turtle, for each $$$i$$$ from 1 to $$$N$$$, will move $$$a_i$$$ steps, then turn right 90 degrees.
The blue turtle, for each $$$i$$$ from 1 to $$$M$$$, will move $$$b_i$$$ steps, then turn right 90 degrees.
Once they finish, they will stop.
Output whether their paths will intersect.
Note that a turtle stopping on the other's path would still count as an intersection.
The first line consists of an integer $$$t$$$ ($$$1 \le t \le 100$$$), the number of test cases.
The first line of each test case consists of two integers $$$N$$$ and $$$M$$$ ($$$1 \le N,M \le 10^5$$$), the number of steps the red turtle will take, and the number of steps the blue turtle will take, respectively.
The second line of each test case consists of $$$a_1,a_2,...,a_N$$$ ($$$1 \le a_i \le 10^9$$$), describing the red turtle's path.
The third line of each test case consists of $$$b_1,b_2,...,b_M$$$ ($$$1 \le b_i \le 10^9$$$), describing the blue turtle's path.
The sum of $$$N$$$ and the sum of $$$M$$$ over all $$$t$$$ test cases doesn't exceed $$$10^5$$$.
—
Tests in subtasks are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
Tests $$$1-2$$$ satisfy $$$N,M,a_i,b_i \le 100$$$.
Tests $$$3-4$$$ satisfy $$$N,M \le 1000$$$.
Tests $$$5-20$$$ satisfy no additional constraints.
For each test case, output "YES" if the paths of the turtles will intersect; otherwise, output "NO." Note that the checker is case-sensitive, so outputs such as "yEs" will not be accepted.
26 61 2 3 4 5 61 1 3 4 6 66 31 2 3 4 5 61 3 5
NOYES
Visualization for test cases 1 and 2:
Test Case 1 
Test Case 2 —
Problem Idea: alexlikemath007
Problem Preparation: Buzzy2
Occurrences: Novice F, Advanced B
You are tasked with constructing a tree with $$$n$$$ nodes. Each edge must have a non-negative integer weight.
Additionally, you are given $$$m$$$ constraints. Each constraint is described by three integers $$$u$$$, $$$v$$$, and $$$w$$$, meaning that the bitwise XOR of the weights of all edges along the unique path between nodes $$$u$$$ and $$$v$$$ must be equal to $$$w$$$.
Determine whether such a tree exists. If it does, output any valid assignment of edges and their weights.
The first line contains the number of test cases, $$$t$$$ ($$$1 \leq t \leq 10^4$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$0 \leq m \leq 4 \cdot 10^5$$$).
The next $$$m$$$ lines contain three integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$u \neq v$$$, $$$0 \leq w \lt 2^{30}$$$), representing a constraint.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.
—
Tests in subtasks are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.
Tests $$$1-20$$$ satisfy no additional constraints.
For each test case, output "YES" or "NO", depending on whether or not such a tree exists. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
If you output "YES", output $$$n - 1$$$ lines, each containing three space-separated integers $$$u$$$, $$$v$$$, and $$$w$$$ ($$$1 \leq u, v \leq n$$$, $$$0 \leq w \lt 2^{30}$$$), denoting that there is an edge between nodes $$$u$$$ and $$$v$$$ with weight $$$w$$$.
25 51 5 31 4 43 5 53 2 12 5 45 22 3 32 3 4
YES 1 3 6 3 4 2 2 4 3 4 5 7 NO
For the first test case, the sample output corresponds to the tree below:
We can show that this tree satisfies all listed constraints. For example, for the constraint $$$u = 1$$$, $$$v = 5$$$, $$$w = 3$$$, the path XOR from node $$$1$$$ to node $$$5$$$ is $$$6 \oplus 2 \oplus 7 = 3$$$, satisfying the constraint.
For the second test case, there is no possible tree because it is impossible for the path between node $$$2$$$ and node $$$3$$$ to have a path XOR of both $$$3$$$ and $$$4$$$.
—
Problem Idea: theyashb
Problem Preparation: n685
Occurrences: Novice G, Advanced C
You are given an array $$$a$$$ with size $$$n$$$ and an integer $$$k$$$; you can do the following operation:
1. Choose two indices $$$i, j$$$.
2. Choose a positive prime factor of $$$a_i$$$, denote it $$$x$$$.
3. Multiply $$$a_j$$$ by $$$x$$$, divide $$$a_i$$$ by $$$x$$$.
For each $$$i$$$ from $$$1$$$ to $$$k$$$, answer the following query:
What is the maximum GCD of the array after $$$i$$$ operations?
The first line contains two integers $$$n, k$$$ $$$(1 \leq n,k \leq 10^5)$$$.
The second line contains $$$n$$$ integers $$$a_i$$$ $$$(1 \leq a_i \leq 10^6)$$$.
—
Tests in subtasks are numbered from $$$1-25$$$ with samples skipped. Each test is worth $$$\frac{100}{25}=4$$$ points.
Tests $$$1-5$$$ satisfy $$$n,k \leq 200$$$.
Tests $$$6-10$$$ satisfy that each $$$a_i$$$ has at most $$$2$$$ distinct prime factors.
Tests $$$11-25$$$ satisfy no additional constraints.
One line with $$$k$$$ integers; the $$$i$$$-th integer denotes the answer after $$$i$$$ operations.
4 5900 150 6 1
3 6 15 30 30
Initially, the array is:
$$$[900, 150, 6, 1]$$$
We describe one possible way to achieve the optimal answers.
After 1 operation: $$$[300, 150, 6, 3]$$$
After 2 operations: $$$[150, 150, 6, 6]$$$
After 3 operations: $$$[60, 30, 30, 15]$$$
After 4 operations: $$$[30, 30, 30, 30]$$$
After 5 operations: $$$[30, 30, 30, 30]$$$
—
Problem Idea: naturalselection
Problem Preparation: naturalselection
Occurrences: Novice H, Advanced D
Bessie is playing a Geometry Dash level that takes place on an infinite 2D grid. The level contains $$$n$$$ objects, with no two at the same position. Bessie starts and ends the level at the first object, which is always a green orb.
Bessie always faces one of the four cardinal directions: up, down, left or right. At the end of every second, she moves exactly one unit in her current direction.
There are three types of objects. When Bessie enters a cell containing an object, her direction may change based on the object type:
- Green orb: Bessie can change her direction to any of the four cardinal directions.
- Blue pad: Bessie's direction is immediately reversed (e.g., if she was moving right, she now moves left).
- Purple pad: Bessie's direction is set to the direction of the purple pad.
If Bessie enters a cell without an object, she continues moving in her current direction. Bessie can visit a cell any number of times.
Help Bessie determine the maximum number of distinct cells she can visit such that she starts and ends at the first object, or output $$$0$$$ if she can never return to the first object.
The first line contains an integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. For each test case:
The first line contains an integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$), the number of objects.
Each of the next $$$n$$$ lines describes an object:
- 1 $$$x$$$ $$$y$$$: A green orb at $$$(x, y)$$$.
- 2 $$$x$$$ $$$y$$$: A blue pad at $$$(x, y)$$$.
- 3 $$$x$$$ $$$y$$$ $$$d$$$: A purple pad at $$$(x, y)$$$ with direction $$$d \in \{U, L, D, R\}$$$.
The characters U, L, D, and R represent the directions up, left, down, and right respectively.
For each test case, it is guaranteed that all $$$(x, y)$$$ are distinct and $$$|x|, |y| \le 10^9$$$. The first object is always a green orb.
The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
—–
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-4$$$ have an answer that is at most $$$25$$$.
Tests $$$5-20$$$ satisfy no additional constraints.
Output a single integer — the maximum number of distinct cells Bessie can visit and return to the starting cell, or $$$0$$$ is she cannot return.
291 0 01 -1 -11 -1 11 1 -12 -1 03 0 -1 R3 1 0 L3 0 1 L3 1 1 D11 1 1
50
—
Problem Idea: AksLolCoding
Problem Preparation: AksLolCoding
Occurrences: Novice I, Advanced E
The cows have escaped Farmer John's barn and have run loose! Farmer John's pasture is an $$$n$$$ by $$$m$$$ grid, with an indestructible fence surrounding the pasture.
There are $$$k$$$ cows in the pasture, each moving in a cardinal direction$$$^{\text{∗}}$$$. Every second, the cows instantaneously move to a cell in their respective direction. If multiple cattle occupy the same cell, they all simultaneously explode. Alternatively, if a cow leaves the pasture, it also explodes.
Farmer John is attempting to stage an intervention and needs analytics data. Please help Farmer John determine how long each cow survives!
$$$^{\text{∗}}$$$The four cardinal directions are North, East, South, and West.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^3$$$). The description of the test cases follows.
The first line of each test case contains integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \leq n \cdot m \leq 1.5 \cdot 10^{5}$$$, $$$1 \leq k \leq n \cdot m$$$) — the number of rows in the grid, the number of columns in the grid, and the number of cows.
The next $$$k$$$ lines contain two integers, $$$r_i$$$ and $$$c_i$$$, and a character $$$d_i$$$ ($$$1 \leq r_i \leq n, 1 \leq c_i \leq m, d_i \in \{\texttt{N}, \texttt{E}, \texttt{S}, \texttt{W}\}$$$) — the row, column, and direction of the $$$i$$$-th cow. The directions are given as a character $$$\texttt{NESW}$$$, indicating its respective cardinal direction. No two cows will start on the same cell.
It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$1.5 \cdot 10^5$$$.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-2$$$ satisfies $$$\sum n \cdot m \leq 10^{3}$$$.
Tests $$$3-6$$$ satisfy $$$n = 1$$$.
Tests $$$7-20$$$ satisfy no additional constraints.
For each test case, output the number of seconds each cow survived.
32 2 21 1 E1 2 W2 2 21 2 S2 1 E1 4 41 1 E1 2 E1 3 E1 4 E
2 21 14 3 2 1
For the first test case:
- At $$$t=0$$$, cow $$$1$$$ is at $$$(1, 1)$$$, and cow $$$2$$$ is at $$$(1, 2)$$$.
- At $$$t=1$$$, cow $$$1$$$ is at $$$(1, 2)$$$, and cow $$$2$$$ is at $$$(1, 1)$$$.
- At $$$t=2$$$, both cows $$$1$$$ and $$$2$$$ exit the grid and explode.
Note that the cows do not collide, since they move instantaneously.
For the second test case:
- At $$$t=0$$$, cow $$$1$$$ is at $$$(1, 2)$$$, and cow $$$2$$$ is at $$$(2, 1)$$$.
- At $$$t=1$$$, cow $$$1$$$ is at $$$(2, 2)$$$, and cow $$$2$$$ is at $$$(2, 2)$$$. Since they are in the same cell, they both explode.
—
Problem Idea: alexlikemath007
Problem Preparation: eysbutno
Occurrences: Novice J, Advanced F
At the Latin America ICPC Championship 2026, the problemsetter's team ran into a tricky problem. One of the members on the team, Avnith immediately recognized the problem and claimed that it is trivially solved by [REDACTED]. However, the problem was actually solved by Centroid Decomposition and NTT. During the flight back from Chile, the problemsetter could not forget about the incident and made a problem based on [REDACTED]. Now it is your job to figure out what [REDACTED] is and solve the problem.
You are given an undirected tree with $$$n$$$ vertices and an integer $$$k$$$.
For every vertex $$$r$$$ considered as the root, define $$$d_r(v)$$$ to be the distance from $$$r$$$ to $$$v$$$. For every $$$k$$$-vertex subset $$$S$$$, let $$$lca_r(S)$$$ be the lowest common ancestor of all vertices in $$$S$$$ in the tree rooted at $$$r$$$.
Let $$$$$$f(r)=\sum_{\substack{S\in V\\|S|=k}} d_r(lca_r(S))$$$$$$ In other words, the sum of the depths of the least common ancestor of all sets with $$$k$$$ vertices if the tree is rooted at vertex $$$r$$$.
Find $$$f(r)$$$ for each $$$r$$$ from $$$1$$$ to $$$n$$$. Since the answers may be large, output them modulo $$$10^9+7$$$.
The first line contains two integers $$$n$$$, $$$k$$$ $$$(1 \leq n,k \leq 2 \cdot 10^5)$$$ as denoted in the problem statement.
The next $$$n-1$$$ lines contain two integers each line, denoting an edge in the tree.
—
Tests in subtasks are numbered from $$$1−25$$$ with samples skipped. Each test is worth $$$\frac{100}{25}=4$$$ points.
Tests $$$1-4$$$ satisfy $$$n,k \leq 20$$$.
Tests $$$5-12$$$ satisfy $$$n, k \leq 2000$$$.
Tests $$$13-25$$$ satisfy no additional constraints.
One line with $$$n$$$ integers; the $$$i$$$-th integer denotes $$$f(i)$$$ modulo $$$10^9+7$$$.
4 21 22 33 4
4 1 1 4
Consider rooting at $$$r = 1$$$. The tree is a path $$$1 - 2 - 3 - 4$$$, so the depths are $$$d_1(1) = 0$$$, $$$d_1(2) = 1$$$, $$$d_1(3) = 2$$$, $$$d_1(4) = 3$$$. There are $$$\binom{4}{2} = 6$$$ subsets of size $$$k = 2$$$:
- $$$\{1, 2\}$$$: $$$\mathrm{lca} = 1$$$, depth $$$0$$$
- $$$\{1, 3\}$$$: $$$\mathrm{lca} = 1$$$, depth $$$0$$$
- $$$\{1, 4\}$$$: $$$\mathrm{lca} = 1$$$, depth $$$0$$$
- $$$\{2, 3\}$$$: $$$\mathrm{lca} = 2$$$, depth $$$1$$$
- $$$\{2, 4\}$$$: $$$\mathrm{lca} = 2$$$, depth $$$1$$$
- $$$\{3, 4\}$$$: $$$\mathrm{lca} = 3$$$, depth $$$2$$$
So $$$f(1) = 0 + 0 + 0 + 1 + 1 + 2 = 4$$$.
—
Problem Idea: naturalselection
Problem Preparation: naturalselection
Occurrences: Advanced G
There is an array $$$a$$$ of size $$$10^9$$$, initially all containing zeroes. There are $$$n$$$ operations done to the array.
The $$$i$$$-th operation specifies operation number $$$op_i$$$ and bounds $$$l_i \le r_i$$$.
- If $$$op_i=1$$$, then $$$a_l,a_{l+1},\ldots,a_r$$$ will all be incremented by $$$1$$$.
- If $$$op_i=2$$$, then $$$a_l,a_{l+1},\ldots,a_r$$$ will be incremented by $$$1,2,\ldots,r-l+1$$$ respectively.
After all operations, there are $$$q$$$ queries. The $$$j$$$-th query specifies bounds $$$L_j\le R_j$$$, and you have to determine the sum $$$a_{L_j}+a_{L_j+1}+\ldots+a_{R_j}$$$ modulo $$$10^9+7$$$.
The first line contains an integer $$$n$$$ ($$$1\le n\le 10^6$$$).
The $$$i$$$-th of the next $$$n$$$ lines contains three integers $$$op_i$$$, $$$l_i$$$, and $$$r_i$$$ ($$$1\le op_i\le 2$$$, $$$1\le l_i \le r_i\le 10^9$$$).
The next line contains an integer $$$q$$$ ($$$1\le q\le 10^6$$$).
The $$$j$$$-th of the next $$$q$$$ lines contains two integers $$$L_j$$$ and $$$R_j$$$ ($$$1\le L_j\le R_j\le 10^9$$$).
—
Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Test $$$1$$$ satisfies $$$op_i=1$$$, $$$l_i=r_i \le 10^6$$$, and $$$R_j \le 10^6$$$.
Test $$$2$$$ satisfies $$$op_i=1$$$, $$$r_i \le 10^6$$$, and $$$L_j=R_j \le 10^6$$$.
Tests $$$3-4$$$ satisfy $$$op_i=1$$$, $$$r_i \le 10^6$$$, and $$$R_j \le 10^6$$$.
Tests $$$5-6$$$ satisfy $$$r_i \le 10^6$$$, and $$$L_j=R_j \le 10^6$$$.
Tests $$$7-8$$$ satisfy $$$r_i \le 10^6$$$, and $$$R_j \le 10^6$$$.
Tests $$$9-10$$$ satisfy $$$op_i=1$$$ and $$$l_i=r_i$$$.
Tests $$$11-12$$$ satisfy $$$op_i=1$$$ and $$$L_j=R_j$$$.
Tests $$$13-15$$$ satisfy $$$op_i=1$$$.
Tests $$$16-17$$$ satisfy $$$L_j=R_j$$$.
Tests $$$18-20$$$ satisfy no additional constraints.
For the $$$j$$$-th query, output the sum $$$a_{L_j}+a_{L_j+1}+\ldots+a_{R_j}$$$ modulo $$$10^9+7$$$ on a separate line.
31 1 32 2 42 1 531 32 41 5
12 17 24
Since the input size might be large, please add ios_base::sync_with_stdio(0); cin.tie(0); to the start of the main function.
—
Problem Idea: culver0412
Problem Preparation: culver0412
Occurrences: Novice K, Advanced H
Steve has found the perfect location to build his next megabase! Unfortunately, the area he wants to build in is currently occupied by a large network of sculk. Since Steve is busy with collecting materials for his base, he needs your help removing all of the sculk in a safe manner.
The sculk network can be represented by a graph of $$$n$$$ nodes connected by $$$m$$$ edges, where each node is either a sculk sensor (type $$$1$$$) or a sculk shrieker (type $$$2$$$). Initially, all sensors and shriekers are part of a single connected component.
To destroy the sculk network, you can remove nodes one at a time. When a node is removed, all edges connected to that node are removed as well. However, any sensors that were directly adjacent to the removed node enter an activated state. If a shrieker is directly connected to an activated sensor at any moment in time, a Warden will spawn, and the entire location must be evacuated! The sculk network is fully cleared once all nodes have been removed.
Output any node removal order that can be used to clear out the sculk network without spawning a Warden, or report that it is not possible.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 1000)$$$. The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n \leq 2 \cdot 10^5, n-1 \leq m \leq \min(2 \cdot 10^5, \frac{n(n-1)}2))$$$ — the number of nodes and edges, respectively.
The next line contains $$$n$$$ space-separated integers $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$ $$$(a_i \in \{1, 2\})$$$ — the type of each node, either being a sensor ($$$1$$$) or shrieker ($$$2$$$).
The next $$$m$$$ lines each contain two integers $$$u$$$ and $$$v$$$ $$$(1 \leq u, v, \leq n, u \neq v)$$$ — denoting an edge connecting nodes $$$u$$$ and $$$v$$$.
It is guaranteed that all edges are pairwise distinct, and the graph specified in the input is a single connected component.
It is guaranteed that neither the sum of $$$n$$$ nor the sum of $$$m$$$ exceeds $$$2 \cdot 10^5$$$ across all test cases.
—
Tests in subtasks are numbered from $$$1$$$ — $$$20$$$ with samples skipped. Each subtask is worth $$$5$$$ points.
Tests $$$1$$$ — $$$6$$$ satisfy $$$N, M \leq 20$$$ (note: no additional constraint on sum of $$$N$$$ or $$$M$$$).
Tests $$$7$$$ — $$$8$$$ satisfy $$$N, M \leq 200$$$ (note: no additional constraint on sum of $$$N$$$ or $$$M$$$).
Tests $$$9$$$ — $$$20$$$ satisfy no additional constraints.
For each test case, output a permutation of length $$$n$$$, indicating a valid node removal order that can clear the sculk network without spawning any Wardens.
If there are multiple possible orderings, output any valid ordering.
If it is impossible to accomplish the task, output $$$-1$$$ instead.
43 22 2 21 22 33 22 1 21 22 33 21 2 11 22 34 51 1 2 21 21 31 42 32 4
1 2 32 1 31 2 3-1
In the first test case, note that there are no sensors, so you can remove the nodes in any order without triggering any shriekers.
In the second test case, you must remove node $$$2$$$ first, as removing either of the shriekers will trigger the sensor at node $$$2$$$, causing the other shrieker to trigger.
In the third test case, note that although removing node $$$2$$$ triggers both sensors, neither of these sensors will cause a shrieker to activate.
In the fourth test case, it can be shown that it is impossible to remove a node without triggering a shrieker.
—
Problem Idea: pilliamw
Problem Preparation: pilliamw
Occurrences: Novice L, Advanced I
You are given a directed acyclic graph, with each edge $$$i$$$ having a weight in the range $$$[l_i, r_i]$$$. Assign weights to each edge such that all paths from $$$1$$$ to $$$n$$$ have the same cost. It is guaranteed that node $$$1$$$ is the only source$$$^{\text{∗}}$$$ and node $$$n$$$ is the only sink$$$^{\text{†}}$$$.
$$$^{\text{∗}}$$$A source node has no incoming edges, and has outgoing edges.
$$$^{\text{†}}$$$A sink node has no outgoing edges, and has incoming edges.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 10^{2}$$$). The description of the test cases follows.
The first line of each test case contains integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 10^{3}$$$, $$$n - 1 \leq m \leq \min(4 \cdot 10^{3}, \frac{n(n-1)}{2})$$$) — the number of nodes and edges in the graph.
The next $$$m$$$ lines contain two integers $$$u_i$$$, $$$v_i$$$, $$$l_i$$$, and $$$r_i$$$ ($$$1 \leq u_i, v_i \leq n$$$, $$$u_i \neq v_i$$$, $$$1 \leq l_i \leq r_i \leq 10^{9}$$$) — the edge endpoints, and the range bounding the edge weight. It is guaranteed that there are no multiedges.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^3$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^{3}$$$.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-4$$$ satisfies $$$l_i = 1$$$ and $$$r_i = 10^9$$$.
Tests $$$5-20$$$ satisfy no additional constraints.
If no valid construction exists, print $$$-1$$$. Otherwise, print the edge weights, in order of input.
24 41 2 1 101 3 1 102 4 1 103 4 1 104 41 2 5 51 3 10 102 4 1 13 4 1 1
10 10 10 10-1
For the first test case, assigning all the edge weights to $$$10$$$ ensures that all paths from $$$1$$$ to $$$n$$$ have the same cost.
For the second test case, we can show that any weight assignment results in paths from $$$1$$$ to $$$n$$$ with differing weights.
—
Problem Idea: dutin
Problem Preparation: eysbutno
Occurrences: Advanced J
You are given an $$$n \times n$$$ grid where each cell has a label of $$$0$$$ or $$$1$$$. You are given $$$q$$$ operations, each specifying a cell whose label is flipped (from $$$0$$$ to $$$1$$$, or from $$$1$$$ to $$$0$$$). After each operation, determine whether it is possible to travel from cell $$$(1, 1)$$$ to cell $$$(n, n)$$$ by only traversing cells labeled $$$1$$$, moving between adjacent cells.
This problem must be solved online. Each query is given as a cell $$$(x, y)$$$, but the true cell is determined using the previous $$$\mathrm{num}$$$ answers. Specifically, you are given $$$\mathrm{num}$$$ pairs $$$(u_i, v_i)$$$ for $$$i = 0, 1, \ldots, 2^{\mathrm{num}} - 1$$$. Let $$$\mathrm{val}$$$ be the integer formed by writing the previous $$$\mathrm{num}$$$ answers in order from oldest to most recent as a binary string, where $$$\text{YES} = 1$$$ and $$$\text{NO} = 0$$$, and interpreting it as a binary number with the oldest answer as the most significant bit and the most recent answer as the least significant bit. Any answer that does not yet exist is treated as $$$\text{NO}$$$. Then the true cell is: $$$$$$x' = \begin{cases} x + u_{\mathrm{val}} - n & \text{if } x + u_{\mathrm{val}} \gt n \\ x + u_{\mathrm{val}} & \text{otherwise} \end{cases}$$$$$$ $$$$$$y' = \begin{cases} y + v_{\mathrm{val}} - n & \text{if } y + v_{\mathrm{val}} \gt n \\ y + v_{\mathrm{val}} & \text{otherwise} \end{cases}$$$$$$
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2000$$$).
The next $$$n$$$ lines each consist of a length $$$n$$$ binary string, representing the initial state of the $$$n \times n$$$ grid.
The next line contains two integers $$$q$$$ and $$$\mathrm{num}$$$ ($$$1 \le q \le 2000$$$, $$$1 \le \mathrm{num} \le 15$$$).
The next $$$2^{\mathrm{num}}$$$ lines each contain two integers $$$u_i$$$ and $$$v_i$$$ ($$$0 \le u_i, v_i \lt n$$$).
The next $$$q$$$ lines each contain two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, y \le n$$$), denoting the cell to flip.
—
Tests are numbered from $$$1-20$$$ and each test is worth $$$5$$$ points.
Tests $$$1-2$$$ satisfy $$$n, q \le 500$$$.
Tests $$$3-8$$$ satisfy $$$\mathrm{num} = 1$$$ and $$$u_0, u_1, v_0, v_1 = 0$$$. That is, you can solve the problem offline.
Tests $$$9-20$$$ satisfy no additional constraints.
Output $$$q$$$ lines, where the $$$i$$$-th line contains "YES" or "NO" indicating whether cell $$$(1,1)$$$ can reach cell $$$(n,n)$$$ after the $$$i$$$-th operation.
3 101 010 111 3 1 0 2 1 1 3 2 1 3 2 2
NO YES NO
5 01010 11111 11011 10100 11011 5 1 0 0 0 0 1 1 5 3 5 4 4 5 2 2
NO YES NO YES NO
For the first sample, the points that are actually operated after the online constraint are $$$(3,1), (1,2), (3,3)$$$
—
Problem Idea: willy108
Problem Preparation: gg_gong
Occurrences: Advanced K
Arvin is very orz. He is also very rich. He owns the number line, so as to defend it, he has built towers on each integer position of the number line.
Initially, there are $$$n$$$ towers which have a positive number of copies of the magical weapon of bruhopener, in which the $$$i$$$-th tower is at position $$$d_i$$$ and has $$$s_i$$$ bruhopeners. To make the defense stronger, every second, he chooses a tower with at least $$$2$$$ bruhopeners, then moves one of its bruhopeners to the tower on its left and moves the other to the tower on its right. He does this until every tower has at most $$$1$$$ bruhopener.
Arvin can easily figure out how many seconds this process will last for. Therefore, he challenges you to do the same by writing a code. Since the answer might be too large, output the answer modulo $$$10^9+7$$$.
The first line consists of an integer $$$n$$$ ($$$1\le n\le 10^6$$$).
The $$$i$$$-th line of the next $$$n$$$ lines consist of two integers $$$d_i,s_i$$$, the position and number of bruhopeners of the $$$i$$$-th tower which initially has a positive number of bruhopeners ($$$1\le s_i\le 10^6$$$, $$$-10^6\le d_1 \lt d_2 \lt ... \lt d_n\le 10^6$$$).
—
Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Test $$$1$$$ satisfies $$$s_i \le 3$$$ and $$$d_i$$$ is a multiple of $$$3$$$.
Tests $$$2-3$$$ satisfy the sum of $$$s_i$$$ does not exceed $$$100$$$.
Tests $$$4-6$$$ satisfy the sum of $$$s_i$$$ does not exceed $$$1000$$$.
Tests $$$7-9$$$ satisfy $$$n=1$$$.
Tests $$$10-11$$$ satisfy $$$n \le 3$$$.
Tests $$$12-16$$$ satisfy $$$n \le 1000$$$.
Tests $$$17-18$$$ satisfy $$$n \le 10^5$$$.
Tests $$$19-20$$$ satisfy no additional constraints.
Output a single integer, the number of seconds that the process will last for, modulo $$$10^9+7$$$.
2 2 3 3 2
8
Due to the large amount of input, Arvin advises you to append the following two lines of code before input:
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
—
Problem Idea: culver0412
Problem Preparation: culver0412
Occurrences: Advanced L
You are given a rectangular grid (0-indexed) $$$A$$$ with $$$N$$$ rows and $$$M$$$ columns, in which $$$A_{i, j} \gt A_{i + 1, j}$$$ and $$$A_{i, j} \gt A_{i, j + 1}$$$. Consider an undirected graph with $$$(NM)^K$$$ vertices represented as a tuple $$$(P_1, P_2, \dots, P_K)$$$, where $$$P_x$$$ represents some position $$$(i, j)$$$ $$$(0 \leq i \lt N, 0 \leq j \lt M)$$$. Vertices $$$(P_1, P_2, \dots, P_K)$$$ and $$$(Q_1, Q_2, \dots, Q_K)$$$ are connected by an edge if the following two conditions are satisfied:
- There is exactly one index $$$x$$$ where $$$P_x \neq Q_x$$$.
- $$$P_x$$$ and $$$Q_x$$$ differ in either the $$$i$$$ coordinate or the $$$j$$$ coordinate but NOT both.
The first line contains $$$3$$$ positive integers $$$N$$$, $$$M$$$, and $$$K$$$ $$$(1 \leq NM \leq 4 \cdot 10^6, 1 \leq K \leq 10^9)$$$.
The next $$$N$$$ lines contain $$$M$$$ integers representing $$$A_{i, j}$$$ $$$(0\leq A_{i, j} \leq 10^9, A_{i, j} \gt A_{i + 1, j}, A_{i, j} \gt A_{i, j + 1})$$$.
—
Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Test $$$1$$$ satisfies $$$K = 1$$$.
Tests $$$2-4$$$ satisfy $$$N, M \leq 20, K \leq 3$$$.
Tests $$$5-12$$$ satisfy $$$N, M \leq 300$$$.
Tests $$$13-15$$$ satisfy $$$N, M \leq 2000$$$.
Tests $$$16-17$$$ satisfy $$$NM \leq 2 \cdot 10^5$$$.
Tests $$$18-20$$$ satisfy no additional constraints.
Output $$$1$$$ integer, the maximum total weight of the vertices in an independent set of the graph modulo $$$998244353$$$.
2 2 12 11 0
17
2 2 22 11 0
67073
3 3 34 3 23 2 12 1 0
189222073
—
Problem Idea: HaccerKat
Problem Preparation: HaccerKat
Occurrences: Advanced M