In the recent few years, this game has been so popular worldwide, it has even become a meme in the competitive programming community. Why would it be a bad idea to set problems about it?
You are given a grid $$$G$$$ of lowercase latin alphabets. A simple path on this grid is defined as a sequence of $$$k \ge 1$$$ distinct cells $$$p_1,p_2,\cdots,p_k$$$, such that $$$p_{i-1}$$$ and $$$p_i$$$ are adjacent either vertically or horizontally. Also, for some simple path $$$d$$$ of $$$m$$$ cells, let $$$f(d)$$$ be the string of length $$$m$$$ such that $$$(f(d))_i$$$ is the letter written on the cell $$$d_i$$$ of the grid $$$G$$$.
Please find the number of simple paths $$$a$$$ of $$$13$$$ cells, such that $$$f(a)$$$ is a cyclic shift of "genshinimpact". As the answer may be very large, you are only required to find the value modulo $$$998 \, 244 \, 353$$$.
The first line contains two integers $$$r$$$ and $$$c$$$ — the number of rows and the number of columns of $$$G$$$. ($$$1 \le r,c \le 500$$$)
Each of the $$$r$$$ following lines contains a string of length $$$c$$$ consisting of lowercase latin letters. The $$$i$$$-th of them is the $$$i$$$-th row of the grid $$$G$$$.
Output the answer modulo $$$998 \, 244 \, 353$$$ on one line.
3 7gshimcteninpagppmpact
8
The grid in the sample input contains $$$8$$$ simple paths satisfying the condition. The $$$8$$$ simple paths are as follows.
A balanced bracket string is a string consisting of '(' and ')', which can make a valid mathematical expression by inserting $$$0$$$ or $$$+$$$ in the string $$$0$$$ or more times.
Bob had learned how to find the balanced bracket string with minimum cost, when the cost is defined as follows.
While rethinking about the solution, Bob became curious about the following problem.
As he was unable to solve the modified problem, he asked you to solve it. As Bob is a very selfish person, he wants you to solve it for each possible value of $$$k$$$. The indices chosen for $$$k=x$$$ need not be a strict subset of the indices chosen for $$$k=x+1$$$. In other words, the problem must be solved independently for all values of $$$k$$$.
The first line contains an even integer $$$n$$$, the length of the bracket sequence. ($$$2 \le n \le 2\cdot 10^5$$$)
The second line contains $$$n$$$ integers $$$a_1,a_2,\cdots,a_n$$$, the costs of using '(' on each index. ($$$0 \le a_i \le 10^9$$$)
The third line contains $$$n$$$ integers $$$b_1,b_2,\cdots,b_n$$$, the costs of using ')' on each index. ($$$0 \le b_i \le 10^9$$$)
Output $$$n+1$$$ integers $$$c_0,c_1,\cdots,c_n$$$ separated by spaces. $$$c_x$$$ is defined by the minimum cost of the problem when $$$k=x$$$.
40 5 0 53 3 3 3
6 3 0 0 0
James has been learning how to solve sudoku puzzles recently. He had recently learned about a concept called "Naked Pairs". A pair of cells $$$P$$$ is called a Naked Pair when it satisfies the following conditions.
Given a naked pair, one can remove the candidates in $$$S$$$ from all other cells in the group, since you know that in a valid sudoku each candidate in $$$S$$$ must appear in one of the two cells.
While learning more about it, James realized that the concept of a "Naked Subset" can generalize the naked pairs. A set of cells $$$Q$$$ with $$$k$$$ cells is called a Naked Subset when it satisfies the following conditions.
Given a naked subset, one can remove the candidates in $$$S'$$$ from all other cells in the group, since you know that in a valid sudoku each candidate in $$$S'$$$ must appear in one of the $$$k$$$ cells.
James has been whining about how hard it is to find naked subsets in very big sudoku puzzles. Given a group, your job is to find every candidate that can be eliminated using exactly one naked subset.
The first line consists of one integer $$$n$$$, the size of one group. ($$$1 \le n \le 10^5$$$)
The following $$$n$$$ lines represent cells that belong to the group. The $$$i$$$-th line consists of one integer $$$S_i$$$, followed by $$$S_i$$$ distinct integers. The $$$S_i$$$ integers represent the candidates possible on the $$$i$$$-th cell.
It is guaranteed that the sum of $$$S_i$$$ is at most $$$5\cdot 10^5$$$.
Additionally, it is guaranteed that there is a valid assignment to all cells in the group. In other words, there exists at least one way to choose one candidate per cell, such that all integers chosen are distinct.
Output $$$n$$$ lines. The $$$i$$$-th line must consist of the candidates that can be removed from the $$$i$$$-th cell in increasing order, with the format being same as the input format.
93 2 4 52 2 52 2 44 4 5 7 82 5 71 31 61 94 1 2 7 8
0 0 0 3 4 5 7 1 5 0 0 0 3 2 7 8
In the first sample, the cells in the group belong to the box with green digits. The removals are done using the following naked subsets.
The sudoku board corresponding to the sample. Generated using HoDoKu, an open source sudoku solver.
The cartesian tree of a sequence of distinct integers, is an unique binary tree defined as follows.
In a binary tree, the depth of a node is defined as the distance from the root to the node.
You are given a permutation $$$p$$$ of elements $$$1,2,\cdots,n$$$. You must solve $$$q$$$ queries of the following kind.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 10^6$$$) — the length of the permutation and number of queries respectively.
The second line contains $$$n$$$ distinct integers $$$p_1, p_2, \cdots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the permutation $$$p$$$.
The next $$$q$$$ lines contain two integers $$$l_i, r_i$$$ ($$$1 \leq l_i \leq r_i \leq n$$$) — the bounds of query $$$i$$$.
For each query, output the answer on a new line.
7 101 5 4 7 2 6 31 71 32 43 54 65 71 42 53 64 7
10 2 3 2 3 2 5 4 4 5
Given a string $$$s$$$ of length $$$n$$$, the Z-function of $$$s$$$ is a sequence of $$$n$$$ integers such that the $$$i$$$-th element is equal to the largest nonnegative integer $$$x$$$ no greater than $$$n$$$ such that $$$s_j=s_{i+j-1}$$$ for all $$$1 \le j \le x$$$. For example, the $$$i$$$-th element is $$$0$$$ if $$$s_i \neq s_1$$$, and the first element is always $$$n$$$.
Your friend recently sent you a string $$$s$$$ of length $$$n$$$. He needs to compute the Z-function of this string but does not have enough time to compute it himself. You quickly compute it for him and send it back to your friend.
However, it seems like your friend made a mistake; he made a typo, and it turned out that the string he sent you had an extra character in the front. Unfortunately, neither you nor your friend kept a copy of the original string. Still, you want to know the Z-function of the intended string.
Please find the Z-function of the intended string $$$t=s_{2\ldots n}$$$. For each position, output $$$-1$$$ instead if the value on the specific position cannot be uniquely determined.
The first line contains a single integer $$$n$$$, the length of the original string. ($$$2 \leq n \leq 10^6$$$)
The second line contains $$$n$$$ integers $$$p_1, p_2, \cdots, p_n$$$, the Z-function of the original string. ($$$0 \leq p_i \leq n$$$)
It is guaranteed that a string corresponding to the given Z-function exists.
Output $$$n - 1$$$ integers $$$q_1, q_2, \cdots, q_{n-1}$$$, the Z-function of the intended string $$$s_{2\ldots n}$$$.
If the value cannot be uniquely determined for some position, output $$$-1$$$ for the position.
55 4 3 2 1
4 3 2 1
77 2 1 0 2 1 0
6 1 0 -1 1 0
77 0 1 0 3 0 1
6 0 0 0 2 0
After reading the paper Steiner minimal trees on sets of four points, one has decided to make things a bit harder. Why not five points instead?
You are given $$$5$$$ points with integer coordinates on the plane. The distance between two points is defined by the Euclidean distance.
Please find the sum of distances of the minimum weight$$$^\dagger$$$ steiner tree$$$^\ddagger$$$ of the given points.
$$$^\dagger$$$ The weight of a tree is defined by the sum of distances between all pairs of points connected by edges.
$$$^\ddagger$$$ A steiner tree is defined as a tree spanning the given points, possibly containing some arbitrary number of points added to the point set. The added points need not have integer coordinates.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). The description of the test cases follows.
Each test case consists of five lines, containing the following input.
For each test case, print the sum of distances of the minimum steiner tree of the given points on one line.
Your output will be accepted if the absolute or relative error does not exceed $$$10^{-5}$$$.
2 -2 -1 -1 1 0 -1 1 1 2 -1 0 2 3 1 -3 1 -1 -2 1 -2
7.464101 11.332503
Sorry, we have had the theme of adding up integers so many times elsewhere. So we give you a different definition of addition — adding an element to a set.
You are given $$$a$$$, a sequence of $$$n$$$ sets. Initially, $$$a_i=\left\{ 0 \right\}$$$ (set only containing $$$0$$$) for all $$$1 \le i \le n$$$.
You are asked to solve $$$q$$$ queries of the following kinds.
$$$^\dagger$$$ Given a set of nonnegative integers $$$S$$$, $$$\text{mex}(S)$$$ is defined as the smallest nonnegative integer not in $$$S$$$.
The first line contains two integers $$$n$$$ and $$$q$$$ — the number of sets and queries. ($$$1 \le n,q \le 5\cdot 10^5$$$)
Each of the $$$q$$$ following lines contains a query. Each query is given in the format described above.
For each query of type $$$2$$$, print the answer on a new line.
5 91 1 52 12 51 2 31 4 51 3 32 22 32 4
2 1 3 4 2
The sample input is explained as follows.
After the first query of type $$$1$$$, $$$a$$$ changes to $$$[\left\{ 0,1 \right\},\left\{ 0,2 \right\},\left\{ 0,3 \right\},\left\{ 0,4 \right\},\left\{ 0,5 \right\}]$$$.
Then, the $$$\text{mex}$$$ of $$$\left\{ 0,1 \right\}$$$ and $$$\left\{ 0,5 \right\}$$$ are $$$2$$$ and $$$1$$$ correspondingly.
After three more queries of type $$$1$$$, $$$a$$$ changes to $$$[\left\{ 0,1 \right\},\left\{ 0,1,2 \right\},\left\{ 0,1,2,3 \right\},\left\{ 0,1,4 \right\},\left\{ 0,2,5 \right\}]$$$.
Then, the $$$\text{mex}$$$ of $$$\left\{ 0,1,2 \right\}$$$, $$$\left\{ 0,1,2,3 \right\}$$$, $$$\left\{ 0,1,4 \right\}$$$ are $$$3$$$, $$$4$$$, $$$2$$$ correspondingly.
One day, dnialh mentioned that optimizing geometric construction perfectly is not possible. Oh, very well. You will see about that.
You are given a positive integer $$$n$$$ such that $$$2 \le n \le 1\,320$$$. Please find a sequence of $$$n$$$ points on the plane, $$$X_1,X_2,\cdots,X_n$$$, satisfying the following constraints.
It is proven that such a sequence of points exists under the constraints of this task.
A positive integer $$$n$$$ is given on one line. ($$$2 \le n \le 1\,320$$$)
Output $$$n$$$ lines. The $$$i$$$-th line must contain $$$x_i$$$ and $$$y_i$$$, the coordinates of $$$X_i$$$, separated by a space. ($$$-1\,000 \le x_i,y_i \le 1\,000$$$)
4
-2 -2 1 2 -2 2 2 1
In the samples, $$$n=4$$$ and $$$X=[(-2,-2),(1,2),(-2,2),(2,1)]$$$.
Here, $$$f(i)$$$ is determined as follows.
Now, one can manually verify that the resultant sequence $$$p=[1,3,2,4]$$$ is a permutation of $$$1,2,3,4$$$. Therefore, the sequence of points satisfies the constraints.
A sequence of three positive integers $$$[a, b, c]$$$ is called a triangle if $$$a+b \gt c$$$ holds when reordered such that $$$a \leq b \leq c$$$.
A sequence of positive integers is triangle-free if no subsequence of length $$$3$$$ forms a triangle.
Given a sequence of positive integers $$$L$$$, count how many non-empty subsequences of $$$L$$$ are triangle-free. As the answer may be very large, you are only required to find the value modulo $$$998 \, 244 \, 353$$$.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 7\,000$$$) — the size of the input sequence.
The second line contains $$$n$$$ integers $$$L_1, L_2, \cdots, L_n$$$ ($$$1 \leq L_i \leq 10^9$$$) — the elements of the sequence $$$L$$$.
Output the number of non-empty triangle-free subsequences modulo $$$998 \, 244 \, 353$$$ on one line.
101 2 3 4 5 6 7 8 9 10
173
69 6 7 8 4 4
23
101 3 9 27 81 243 729 2187 6561 19683
1023
The city of Ruralia is building a tower consisting of $$$n$$$ Jenga blocks.
Each block is rectangular with height $$$1$$$, width $$$r_i - l_i$$$, and density $$$1$$$ and will be placed on the plane, axis-aligned with its bottom left corner lying on the coordinates $$$(l_i,n-i)$$$.
After all the blocks have been placed, all of the scaffolding will be removed, and the tower will stay standing if for each block $$$i$$$ the center of mass of all blocks above $$$i$$$ is between $$$l_i$$$ and $$$r_i$$$.
More formally, a tower is stable if and if only for all $$$2 \leq i \leq n$$$ the following inequality holds.
$$$$$$l_i \leq \frac{\sum_{j=1}^{i-1} (r_j - l_j) \cdot \frac{l_j + r_j}2}{\sum_{j=1}^{i-1} (r_j - l_j)}\leq r_i $$$$$$
Unfortunately, you have received news that one of the Jenga blocks has been missing but you are unsure which one. When the shipment arrives, the builders of Ruralia will place the blocks as originally planned, except the one missing block will not be placed and all blocks above it will be moved downwards by $$$1$$$.
However, before building the tower, the builders want to know if the resulting tower will be stable. Thus, they have asked you to determine for each block $$$i$$$ whether the structure with block $$$i$$$ missing is stable.
Do note that it is not necessarily the case that the original tower plan was stable.
The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 2\cdot 10^5$$$) — the number of blocks in the original tower.
The following $$$n$$$ lines each contain two integers $$$l_i, r_i$$$ ($$$1 \leq l_i \lt r_i \leq 10^6$$$)— the endpoints of block $$$i$$$.
It is not necessary that the tower in the input is stable.
Output $$$n$$$ lines.
On line $$$i$$$, output "YES" or "NO" — corresponding to whether the tower will be stable if block $$$i$$$ is removed.
50 104 100 64 100 6
NO YES NO YES YES
46 80 30 80 6
YES YES NO NO
Kaz is inviting $$$n$$$ of his friends over for a party! He has currently prepared the cocktails for them (each friend has ordered a different drink), with friend $$$i$$$ having a preference for cocktail $$$i$$$.
However, Kaz is looking to pull a prank. When handing out drinks if he hands out a drink to the wrong person, he knows the following round of an 'exchange process' will occur: all partygoers who do not have their desired drinks will leave their drinks on a table. All such drinks will be shuffled and handed back in a completely random order to those still in the exchange process. Any participants who receive their desired drink will leave to enjoy the party, while those still with the wrong drink will shuffle again.
To maximize the humor of his prank, Kaz wants the exchange process to take the maximum expected number of rounds. Help Kaz find an assignment of drinks that will maximize this value.
The input consists of a single integer $$$n$$$ ($$$1 \leq n \leq 1\,000$$$) — the number of friends invited to the party.
On the first line, output a single real number $$$R$$$ — the maximum expected number of rounds.
On the second line, output $$$n$$$ distinct integers $$$p_1, p_2, \cdots, p_n$$$ ($$$1 \leq p_i \leq n$$$) — the assignment of the drinks. Here, drink $$$p_i$$$ will be handed to friend $$$i$$$.
Your answer will be accepted if the output satisfies the following conditions.
2
2.0 2 1
You are given a tree of $$$n$$$ nodes. Each node has a non-negative integer value $$$v_i$$$.
Let a tree subsequence be a sequence of nodes $$$S = s_1, s_2, \dots s_k$$$ such that there exists vertices $$$u, v$$$ in the tree such that $$$S$$$ is a subsequence of the unique shortest path starting at $$$u$$$ and ending at $$$v$$$.
A tree subsequence is increasing if for all $$$1 \leq i \leq k - 1$$$ we have that $$$v_{s_i} \lt v_{s_{i + 1}}$$$ (Note that this corresponds to a strictly increasing sequence).
Find the length of the longest increasing tree subsequence.
The first line of input contains a single integer $$$n$$$ ($$$1 \leq n \leq 3\cdot 10^5$$$) — the number of nodes in the tree.
The second line of input contains $$$n$$$ integers $$$v_1, v_2, \cdots, v_n$$$ ($$$1 \leq v \leq 10^{9}$$$) — the value of each node in the tree.
The following $$$n - 1$$$ lines each contain two integers $$$a_i, b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$)— the endpoints of edge $$$i$$$.
It is guaranteed that the given edges form a tree.
Output a single integer — the length of the longest increasing tree subsequence.
47 7 7 72 42 31 2
1
53 9 14 7 121 43 44 52 3
3
1210 3 8 13 6 2 3 14 1 5 10 61 102 62 107 92 99 113 72 85 74 72 12
4