Busy Beaver has collected some pairs of seashells, and he is trying to make them into two beautiful bracelets!
He has $$$N$$$ pairs of seashells, where both seashells in the $$$i$$$-th pair have type $$$a_i$$$. He wants to make two bracelets, such that each bracelet has one seashell from each pair. Busy Beaver decides his own metric for a beautiful pair of bracelets, which is minimizing the length of the longest common subsequence$$$^{\text{∗}}$$$ between two bracelets.
Formally, let $$$s$$$ and $$$t$$$ be two permutations of the original array $$$a$$$. We want to find $$$(s,t)$$$ that minimizes the length of the longest cyclic common subsequence, $$$f(s,t)$$$, defined by the following:
- Consider all cyclic shifts of array $$$t$$$, denoted as $$$t_1,t_2,\dots,t_n$$$$$$^{\text{†}}$$$.
- Let $$$\text{LCS}(s,t)$$$ be the length of the Longest Common Subsequence between $$$s$$$ and $$$t$$$. Then $$$$$$f(s,t) = \max_{1\le i \le n}\text{LCS}(s,t_i).$$$$$$
Unfortunately, Busy Beaver has too many seashells to find the most beautiful bracelet pairs by hand. Please help him!
$$$^{\text{∗}}$$$An array $$$s$$$ is a subsequence of an array $$$t$$$ if $$$s$$$ can be obtained from $$$t$$$ by deleting some (possibly none or all) elements from $$$t$$$, without reordering the remaining elements.
$$$^{\text{†}}$$$A cyclic shift $$$t_i$$$ of an array $$$t=[t^{(1)},t^{(2)},\dots,t^{(n)}]$$$ by $$$i$$$ places is given by $$$[t^{(1+i)},t^{(2+i)},\dots,t^{(n+i)}]$$$, where indices are taken modulo $$$n$$$.
Each test contains multiple test cases. The first line of input contains a single integer $$$T$$$ $$$(1\le T\le 500)$$$, the number of test cases. The description of each test case follows.
The first line of each test case contains a single positive integer $$$N$$$ $$$(1\le N\le 500)$$$.
The second line of each test case contains $$$N$$$ integers $$$a_1,a_2,\dots, a_N$$$ $$$(1\le a_i\le 10^9)$$$ — the types of seashells Busy Beaver has collected.
It is guaranteed that the sum of $$$N$$$ across all test cases does not exceed $$$500$$$.
For each test case, output two lines. The first line consists of $$$N$$$ integers $$$s_1,s_2,\dots,s_N$$$, and the second line consists of $$$N$$$ integers $$$t_1,t_2,\dots,t_N$$$, representing some $$$(s,t)$$$ that minimizes $$$f(s,t)$$$.
If there are multiple solutions, print any of them.
1 3 1 2 3
1 2 3 1 3 2
Note that $$$f([1,2,3],[1,3,2])$$$ is $$$2$$$ because $$$\text{LCS}([1,2,3],[1,3,2]) = 2$$$ ($$$[1,2]$$$ is a shared subsequence). This is the maximum $$$\text{LCS}$$$ over all cyclic shifts of $$$t$$$:
- $$$\text{LCS}([1,2,3],[1,3,2]) = 2$$$ ($$$[1,2]$$$ is a shared subsequence).
- $$$\text{LCS}([1,2,3],[3,2,1]) = 1$$$ ($$$[1]$$$ is a shared subsequence).
- $$$\text{LCS}([1,2,3],[2,1,3]) = 2$$$ ($$$[2,3]$$$ is a shared subsequence).
Nike Nirzayanov, the founder of the popular competitive typing platform SpeedForces, has recently added a new feature allowing users to create random mashups of past contests.
A contest on SpeedForces consists of $$$N$$$ implementation problems, each with a difficulty rating among $$$\{800,900,1000,1100,1200\}$$$. The $$$N$$$ problems in a single contest are always arranged in nondecreasing order of difficulty and assigned problem slots from $$$1$$$ to $$$N$$$ in order.
Busy Beaver is testing out the new feature. He first specifies $$$N$$$ past contests, where the $$$i$$$-th contest he specifies has $$$a_{ij}$$$ problems of difficulty $$$800+100(j-1)$$$ for each $$$1 \le j \le 5$$$, where $$$\sum_{j=1}^5 a_{ij} = N$$$.
The feature will select a random permutation $$$p_1,p_2,\dots,p_N$$$ of $$$1,2,\dots,N$$$ and generate for Busy Beaver a contest where the $$$i$$$-th problem is the $$$i$$$-th problem in the $$$p_i$$$-th contest he specified.
Busy Beaver wonders: How many such permutations will result in a contest with reverse difficulty order (i.e., the problem difficulties are in nonincreasing order)? For some reason, he only wants the answer modulo 2.
Each test contains multiple test cases. 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 the integer $$$N$$$ ($$$1 \le N \le 2 \cdot 10^5$$$) — the number of past contests and problems.
The next $$$N$$$ lines of each test case each contain $$$5$$$ integers $$$a_{i1},a_{i2},a_{i3},a_{i4},a_{i5}$$$ ($$$a_{ij} \ge 0$$$ and $$$\sum_{j=1}^5 a_{ij} = N$$$).
It is guaranteed that the sum of $$$N$$$ across all test cases is no more than $$$2 \cdot 10^5$$$.
For each test case, output a single integer, the number of such permutations modulo $$$2$$$.
There are five subtasks for this problem. Let $$$\sum N$$$ be the sum of $$$N$$$ across all test cases. Let $$$K$$$ be the largest $$$j$$$ such that $$$a_{ij} \gt 0$$$ for some $$$1 \le i \le N$$$.
- ($$$10$$$ points): $$$K \le 2$$$.
- ($$$20$$$ points): $$$K \le 3$$$, $$$\sum N \le 500$$$.
- ($$$20$$$ points): $$$K \le 3$$$.
- ($$$25$$$ points): $$$\sum N \le 500$$$.
- ($$$25$$$ points): No additional constraints.
331 2 0 0 00 3 0 0 00 0 3 0 044 0 0 0 01 3 0 0 00 3 1 0 00 2 2 0 011 0 0 0 0
0 1 1
In the first test case, the $$$N = 3$$$ past contests have the following problem difficulties:
- Contest $$$1$$$: $$$800, 900, 900$$$.
- Contest $$$2$$$: $$$900, 900, 900$$$.
- Contest $$$3$$$: $$$1000, 1000, 1000$$$.
In the second test case, the $$$N = 4$$$ past contests have the following problem difficulties:
- Contest $$$1$$$: $$$800, 800, 800, 800$$$.
- Contest $$$2$$$: $$$800, 900, 900, 900$$$.
- Contest $$$3$$$: $$$900, 900, 900, 1000$$$.
- Contest $$$4$$$: $$$900, 900, 1000, 1000$$$.
In the third test case, the only permutation $$$p = [1]$$$ generates a reverse difficulty order contest, so the answer is $$$1 \bmod 2 = 1$$$.
Busy Beaver is designing an escape room! His current design is a maze with $$$N$$$ different sites, where each of the $$$\frac{N(N-1)}{2}$$$ pairs of sites is directly connected by a bidirectional tunnel.
To make the maze more interesting, each tunnel is locked with one of $$$K$$$ ($$$1 \leq K \leq 10$$$) keys, numbered $$$1, 2, \dots, K$$$. One can only traverse a tunnel between sites $$$i$$$ and $$$j$$$ if they have its corresponding key $$$a_{ij}$$$.
Additionally, Busy Beaver wants to design the maze such that only certain sets of keys let you traverse the entire maze. In particular, there are $$$x_S \in \{0, 1\}$$$ for each subset $$$S \subseteq \{1, 2, \dots, K\}$$$ such that
- If $$$x_S = 1$$$, it is possible to move between any two sites in the maze using only the keys in $$$S$$$.
- If $$$x_S = 0$$$, there exists some pair of sites that cannot be accessed from each other using only the keys in $$$S$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 300$$$). The description of the test cases follows.
The first line of each test case contains the integer $$$K$$$ ($$$1 \le K \le 10$$$) — the number of keys.
The second line of each test case contains a string $$$x$$$ ($$$|x| = 2^K$$$, $$$x_i \in \{\texttt{0}, \texttt{1}\}$$$) such that for each $$$S$$$, if $$$i = \sum_{t \in S} 2^{t - 1}$$$ then $$$x_S := x_i$$$. Note that the string $$$x$$$ is zero-indexed, that is, $$$0 \leq i \lt 2^K$$$.
It is guaranteed that the sum of $$$2^K$$$ across all test cases is no more than $$$2^{10}$$$.
For each test case, if it is possible to satisfy the given constraints, the first line of output should contain an integer $$$N$$$ ($$$1 \leq N \leq 300$$$) — the number of sites. The $$$i$$$-th of the next $$$N$$$ lines of output should then contain $$$N$$$ integers $$$a_{ij}$$$ ($$$a_{ii} = 0, a_{ij} = a_{ji}, 1 \leq a_{ij} \leq K$$$ for $$$i \neq j$$$), where for $$$i \neq j$$$, the tunnel between sites $$$i$$$ and $$$j$$$ uses key $$$a_{ij}$$$.
If there are multiple solutions, print any of them. Otherwise, if there is no solution, print a single integer $$$-1$$$ instead.
Due to judging constraints, the sum of $$$N^2$$$ over your outputs should not exceed $$$2 \cdot 10^5$$$. It can be shown that this is enough to solve the problem.
You will receive $$$20\%$$$ of the points for each subtask if you correctly decide if a solution exists, but your constructions are incorrect. Specifically, in order to receive these points, when a solution does not exist, you must output $$$-1$$$. When a solution exists, you must output some $$$N$$$ ($$$1 \leq N \leq 300$$$) and a matrix $$$a$$$ that meets the specifications of ($$$a_{ii} = 0, a_{ij} = a_{ji}, 1 \leq a_{ij} \leq K$$$ for $$$i \neq j$$$).
There are three subtasks for this problem.
- ($$$10$$$ points): The sum of $$$2^K$$$ across all test cases does not exceed $$$2^4$$$.
- ($$$30$$$ points): The sum of $$$2^K$$$ across all test cases does not exceed $$$2^6$$$.
- ($$$60$$$ points): No additional constraints.
5100201012011030001111141111111111111111
-1 2 0 1 1 0 -1 4 0 1 3 3 1 0 2 3 3 2 0 1 3 3 1 0 1 0
In the first test case, it can be shown that it is impossible to construct the desired maze.
In the second test case, a possible construction is a maze with $$$2$$$ sites connected by a tunnel using key $$$1$$$.
- With keys $$$S = \varnothing$$$ corresponding to $$$x_0 = \texttt{0}$$$, it is impossible to traverse the entire maze.
- With keys $$$S = \{1\}$$$ corresponding to $$$x_1 = \texttt{1}$$$, it is possible to traverse the entire maze.
- With keys $$$S = \{2\}$$$ corresponding to $$$x_2 = \texttt{0}$$$, it is impossible to traverse the entire maze.
- With keys $$$S = \{1, 2\}$$$ corresponding to $$$x_3 = \texttt{1}$$$, it is possible to traverse the entire maze.
In the third test case, it can be shown that it is impossible to construct the desired maze.
In the fourth test case, a possible construction is the following maze with $$$4$$$ sites:
In the fifth test case, a possible construction is a maze with only $$$1$$$ site. With any set of keys, it is possible to traverse the entire maze.
In this problem, all strings consist only of four characters: $$$\texttt{a}$$$, $$$\texttt{b}$$$, $$$\texttt{c}$$$, and $$$\texttt{d}$$$.
Busy Beaver has three strings $$$x$$$, $$$y$$$, and $$$z$$$ that he's really scared of. In particular, he only likes strings that are not a subsequence$$$^{\text{∗}}$$$ of any of them.
Answer $$$Q$$$ queries. In query $$$i$$$, you are given a string $$$s_i$$$, such that $$$x$$$, $$$y$$$, and $$$z$$$ are all subsequences of $$$s_i$$$ and $$$|s_i| \gt \max(|x|, |y|, |z|)$$$. Help Busy Beaver find the length of the shortest subsequence of $$$s_i$$$ that is not a subsequence of any of $$$x$$$, $$$y$$$, or $$$z$$$.
$$$^{\text{∗}}$$$A string $$$s$$$ is a subsequence of a string $$$t$$$ if $$$s$$$ can be obtained from $$$t$$$ by deleting some (possibly none or all) characters from $$$t$$$, without reordering the remaining characters.
The first three lines of the input contain the strings $$$x$$$, $$$y$$$, and $$$z$$$ ($$$1 \le |x|, |y|, |z| \le 60$$$), consisting of characters $$$\texttt{a}$$$, $$$\texttt{b}$$$, $$$\texttt{c}$$$, $$$\texttt{d}$$$.
The next line contains a single positive integer $$$Q$$$ ($$$1 \le Q \le 1.5 \cdot 10^5$$$).
The next $$$Q$$$ lines each contain a string, the $$$i$$$-th of which is $$$s_i$$$ ($$$\max(|x|, |y|, |z|) \lt |s_i| \leq 3 \cdot 10^5$$$), consisting of characters $$$\texttt{a}$$$, $$$\texttt{b}$$$, $$$\texttt{c}$$$, $$$\texttt{d}$$$ such that $$$s_i$$$ has $$$x$$$, $$$y$$$, and $$$z$$$ as subsequences.
The sum of $$$|s_i|$$$ over all queries does not exceed $$$3 \cdot 10^5$$$.
On the $$$i$$$-th line, output a single positive integer — the shortest possible length of a subsequence of $$$s_i$$$ that is not a subsequence of any of $$$x$$$, $$$y$$$, or $$$z$$$.
abbbccabcc3abcbcdabcabcabbcc
2 1 3
In the first query, all length $$$1$$$ subsequences of $$$\texttt{abcbc}$$$ are subsequences of one of $$$x$$$, $$$y$$$, or $$$z$$$, but the subsequence $$$\texttt{cb}$$$ is not, so the answer is $$$2$$$.
In the second query, $$$\texttt{d}$$$ is a subsequence of $$$\texttt{dabcabc}$$$ that is not a subsequence of any of $$$x$$$, $$$y$$$, or $$$z$$$.
In the third query, $$$\texttt{bbc}$$$ is a subsequence of $$$\texttt{abbcc}$$$ that is not a subsequence of any of $$$x$$$, $$$y$$$, or $$$z$$$, and it is the shortest such subsequence.
Busy Beaver has a polynomial equation that he doesn't know how to solve, and he needs your help!
For a bivariate polynomial $$$P(x,y)=\sum\limits_{i,j \ge 0}a_{i,j}x^iy^j$$$, define its degree $$$\deg P = \max\limits_{a_{i,j}\neq 0}(i+j)$$$. For example, $$$\deg (x + y + xy) = 2$$$. Furthermore, we take the degree of the zero polynomial $$$\deg 0$$$ to be $$$-1$$$.
Given a bivariate polynomial $$$P(x,y)$$$ with integer coefficients and an integer $$$d \geq -1$$$, determine whether there exists a bivariate polynomial $$$S(x, y)$$$ and non-constant univariate polynomials $$$Q, R$$$ such that
- for $$$p = 10^9 + 7$$$, we have $$$$$$(P(x, y) + S(x, y))(Q(x) - Q(y)) = R(x) - R(y)$$$$$$ as polynomials in $$$\mathbb F_p[x, y]$$$$$$^{\text{∗}}$$$,
- $$$\deg S \leq d$$$.
$$$^{\text{∗}}$$$i.e. when expanded, the two sides of the equation have equal coefficients modulo $$$p$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 100$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n, d$$$ ($$$1 \leq n \leq 2.5 \cdot 10^3$$$, $$$-1 \leq d \lt n$$$) — the value of $$$\deg P$$$ and the upper bound on $$$\deg S$$$, respectively.
The $$$i$$$-th of the next $$$n + 1$$$ lines contains $$$n + 2 - i$$$ integers $$$a_{i-1, 0}, \dots, a_{i-1, n+1-i}$$$ ($$$0 \leq a_{i,j} \lt 10^9 + 7$$$) — the coefficients of $$$P$$$ so that $$$P(x,y)=\sum\limits_{i,j \ge 0, i+j \leq n}a_{i,j}x^iy^j$$$. It is guaranteed that $$$P$$$ has degree $$$n$$$, i.e. at least one of $$$a_{0,n}, a_{1,n-1}, \dots, a_{n,0}$$$ is nonzero.
It is guaranteed that the sum of $$$n$$$ across all test cases is no more than $$$2.5 \cdot 10^3$$$.
The first line of output for each test case should contain the string "YES" (without quotes) if a solution exists, and "NO" (without quotes) otherwise.
If you claim that a solution exists, continue outputting the solution as follows:
The second line of output for each test case should contain three integers $$$q, r$$$ ($$$1 \leq q, r \leq 5 \cdot 10^3$$$) — the degrees of the polynomials $$$Q, R$$$ respectively.
The third line of output for each test case should contain $$$q + 1$$$ integers $$$b_0, \dots, b_q$$$ ($$$0 \leq b_i \lt 10^9 + 7$$$, $$$b_q \neq 0$$$) — the coefficients of $$$Q(t) = \sum_{i=0}^q b_i t^i$$$.
The fourth line of output for each test case should contain $$$r + 1$$$ integers $$$c_0, \dots, c_r$$$ ($$$0 \leq c_i \lt 10^9 + 7$$$, $$$c_r \neq 0$$$) — the coefficients of $$$R(t) = \sum_{i=0}^r c_i t^i$$$.
Note that you do not need to output $$$S$$$ — the judge will determine if a suitable choice of $$$S$$$ exists for your claimed $$$Q, R$$$.
You can output "YES" and "NO" in any case (for example, strings "yES", "yes" and "Yes" will be recognized as a positive response).
There are five subtasks for this problem.
- ($$$5$$$ points): The sum of $$$n$$$ across all test cases is no more than $$$10$$$, and $$$d = -1$$$, i.e. we constrain that $$$S$$$ is the zero polynomial.
- ($$$5$$$ points): $$$d = n - 1$$$.
- ($$$30$$$ points): $$$d = -1$$$, i.e. we constrain that $$$S$$$ is the zero polynomial.
- ($$$30$$$ points): The sum of $$$n$$$ across all test cases is no more than $$$500$$$.
- ($$$30$$$ points): No additional constraints.
52 -140 9 139 0134 21000000000 1 1000000001 2 11 1000000000 2 0999999999 2 12 014 21000000000 1 1000000001 2 11 1000000000 1 0999999999 1 12 014 2120 50 61 235 16950 81 119 061 119 169235 01699 517 18 19 20 21 22 2 6 0 116 8 8 4 8 0 2 0 015 8 0 4 0 0 0 014 4 4 2 4 0 113 8 0 4 0 012 0 0 0 02 2 0 16 0 00 01
YES 2 4 20 9 13 400 360 601 234 169 NO YES 2 6 1 1 1 2 4 7 7 6 3 1 NO YES 3 12 0 2 0 1 0 0 0 16 16 24 32 12 24 2 8 0 1
In the first test case, the given polynomial is $$$$$$P(x, y) = 13x^2 + 13y^2 + 9x + 9y + 40.$$$$$$ We can take $$$S = 0$$$, $$$Q(t) = 13t^2 + 9t + 20$$$, $$$R(t) = (13t^2 + 9t + 20)^2$$$, which gives a valid solution.
In the second test case, it can be shown that no solution exists.