Busy Beaver has a sequence of $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ and a sequence of $$$M$$$ integers $$$b_1, b_2, \dots, b_M$$$.
For every $$$1\le i\le N$$$ and $$$1\le j\le M$$$, he computes the edit distance between the sequences $$$a_1, a_2, \dots, a_i$$$ and $$$b_1, b_2, \dots, b_j$$$. The edit distance between two sequences is defined as the minimum number of operations needed to go from the first sequence to the second sequence if the following three operations are allowed:
- Insertions: Any integer can be inserted in any position in the sequence. The rest of the sequence remains the same. For example, in one operation, the sequence $$$1, 2, 3, 4$$$ can become $$$1, 2, 5, 3, 4$$$.
- Deletions: Any integer present in the sequence can be deleted. The rest of the sequence remains the same. For example, in one operation, the sequence $$$1, 2, 3, 4$$$ can become $$$1, 2, 4$$$.
- Replacements: Any integer present in the sequence can be replaced by another integer. The rest of the sequence remains the same. For example, in one operation, the sequence $$$1, 2, 3, 4$$$ can become $$$1, 2, 5, 4$$$.
As storing each of these values takes too much space, Busy Beaver only stores the least significant bit of each edit distance as $$$d_{i,j}$$$ ($$$0$$$ if it is even and $$$1$$$ if it is odd).
Unfortunately, Busy Beaver has lost the original sequences and only has the values $$$d_{i,j}$$$ for each $$$i$$$ and $$$j$$$. Help him find any pair of sequences $$$a_1, a_2, \dots, a_N$$$ and $$$b_1, b_2, \dots, b_M$$$ that will give the same values for $$$d_{i,j}$$$. It is possible that no original sequences can produce $$$d_{i,j}$$$, in which case you should report this.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 2\cdot 10^3$$$) — the number of test cases.
The first line of each test case contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 2\cdot 10^3$$$).
The $$$i$$$-th of the next $$$N$$$ lines of each test case contains $$$M$$$ integers $$$d_{i,1}, d_{i,2}, \dots, d_{i,M}$$$ ($$$0\le d_{i,j}\le 1$$$).
The sum of $$$N$$$ across all test cases does not exceed $$$2\cdot 10^3$$$.
The sum of $$$M$$$ across all test cases does not exceed $$$2\cdot 10^3$$$.
For each test case, print a sequence of $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ ($$$0\le a_i\le 10^9$$$) on the first line, and a sequence of $$$M$$$ integers $$$b_1, b_2, \dots, b_M$$$ ($$$0\le b_i\le 10^9$$$) on the second line, such that all $$$d_{i,j}$$$ have the same parity as the edit distance between $$$a_1, a_2, \dots, a_i$$$ and $$$b_1, b_2, \dots, b_j$$$.
If there are no such sequences, print $$$-1$$$ on a single line.
It can be shown that if there are any sequences $$$a_1, a_2, \dots, a_N$$$ and $$$b_1, b_2, \dots, b_M$$$ that work, then there are sequences that satisfy $$$0\le a_i\le 10^9$$$ and $$$0\le b_i\le 10^9$$$.
25 31 0 10 0 01 1 11 1 00 1 04 61 1 0 1 0 11 1 1 0 1 00 1 1 1 0 11 0 0 0 0 0
0 1 2 3 33 3 1-1
In the first test case, it can be checked that $$$[0,1,2,3,3]$$$ and $$$[3,3,1]$$$ work. For example, the edit distance for $$$[0, 1, 2, 3]$$$ and $$$[3, 3]$$$ is $$$3$$$ because the following operations work:
- Delete the first element of $$$[0,1,2,3]$$$ to get $$$[1,2,3]$$$
- Delete the first element of $$$[1,2,3]$$$ to get $$$[2,3]$$$
- Replace the first element of $$$[2,3]$$$ to get $$$[3,3]$$$
In the second test case, it can be shown that there do not exist any valid sequences.
Busy Beaver downloaded a new game on his phone and needs your help to play it!
In this game, a level consists of $$$N^2$$$ starting fruits in a line, each of a type numbered $$$1$$$ through $$$N$$$, with $$$N$$$ fruits of each type. A move consists of the following:
- Choose a subset of $$$N$$$ fruits in the line, not necessarily consecutive, such that the chosen fruit types are $$$k, k+1, \dots, N, 1, \dots, k-1$$$ in order for some $$$1 \le k \le N$$$, and such that the starting fruit type $$$k$$$ is different from that of every previous move.
- Remove the chosen fruits from the line.
You are given an array of $$$N^2$$$ integers $$$a_1, \dots, a_{N^2}$$$, each in the range $$$[0, N]$$$. Count the number of ways to replace each $$$0$$$ in the array with an integer in $$$[1, N]$$$, so that the resulting sequence is a winnable level. Output the answer modulo $$$10^9 + 7$$$.
The first line contains a single integer $$$N$$$ ($$$2 \le N \le 11$$$).
The second line contains $$$N^2$$$ space-separated integers $$$a_1, \dots, a_{N^2}$$$ ($$$0 \le a_i \le N$$$).
It is guaranteed that each value in $$$[1, N]$$$ appears at most $$$N$$$ times in the array $$$a$$$.
Output a single nonnegative integer: the number of possible winnable levels modulo $$$10^9 + 7$$$.
There are three subtasks for this problem.
- ($$$20$$$ points): $$$N = 4$$$.
- ($$$20$$$ points): $$$a_i \neq 0$$$ for all $$$1 \le i \le N^2$$$.
- ($$$60$$$ points): No additional constraints.
20 0 1 0
2
41 0 0 0 0 1 0 0 0 0 0 0 0 0 0 3
30608
In the first sample, we count two winnable levels:
- The level $$$[1, 2, 1, 2]$$$, since we can remove the first and last fruits on move $$$1$$$ and remove the remaining fruits on move $$$2$$$.
- The level $$$[2, 1, 1, 2]$$$, since we can remove the first two fruits on move $$$1$$$ and the remaining fruits on move $$$2$$$.
Busy Beaver has a very large tree with $$$N$$$ vertices, where $$$N = 2^k - 1$$$ for some integer $$$k \ge 1$$$. He wants to cut some of its edges such that the resulting forest has exactly $$$k$$$ connected components with $$$1, 2, 4, 8, \dots, 2^{k-1}$$$ vertices, respectively, and each component forms a simple path. Help Busy Beaver count the number of ways to cut edges to satisfy this condition, modulo $$$10^9 + 7$$$.
To reduce the size of the input, the tree is given in a compressed format. There are $$$M$$$ key vertices labelled $$$1,\dots,M$$$, connected by $$$M-1$$$ paths. The $$$i$$$-th path connects key vertices $$$u_i$$$ and $$$v_i$$$ and consists of $$$\ell_i$$$ edges, where $$$1+\sum_{i=1}^{M-1} \ell_i = N$$$.
The first line contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 2^{60}-1$$$, $$$1 \le M \le \min(N,10^5)$$$, $$$N = 2^k - 1$$$ for some integer $$$k \ge 1$$$).
Each of the next $$$M-1$$$ lines contains three integers $$$u_i$$$, $$$v_i$$$, and $$$\ell_i$$$ ($$$1 \le u_i,v_i \le M$$$, $$$u_i \ne v_i$$$, $$$1 \le \ell_i \le N-1$$$), specifying a path between $$$u_i$$$ and $$$v_i$$$ of length $$$\ell_i$$$.
The total number of vertices in the tree is equal to $$$N$$$ (formally, $$$1+\sum_{i=1}^{M-1} \ell_i = N$$$).
Output a single integer: the number of such partitions modulo $$$10^9 + 7$$$.
There are three subtasks for this problem.
- ($$$10$$$ points): $$$N \le 2^9-1$$$.
- ($$$30$$$ points): $$$N \le 2^{17}-1$$$.
- ($$$60$$$ points): No additional constraints.
7 41 2 11 3 21 4 3
5
1 1
1
In the first sample test case, the $$$5$$$ ways to partition the tree are as follows:
Busy Beaver sells mushrooms at his market. Each mushroom has a flavor index, an integer between $$$1$$$ and $$$N$$$ (inclusive). For each $$$i$$$, there are $$$a_i$$$ mushrooms of flavor index $$$i$$$.
Busy Beaver sells mushrooms only in pairs. Each mushroom can be used in at most one pair. A pair can be sold in one of the following ways:
- Type 1: two mushrooms with the same flavor index for price $$$x$$$.
- Type 2: two mushrooms whose flavor indices differ by exactly $$$1$$$ (e.g. $$$(3,4)$$$) for price $$$y$$$.
You are given $$$Q$$$ scenarios. In the $$$j$$$-th scenario, the prices are $$$(x_j, y_j)$$$. For each scenario, compute the maximum total profit Busy Beaver can obtain.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.
The first line of each test case contains two integers $$$N$$$ and $$$Q$$$ ($$$2 \le N \le 3 \cdot 10^5$$$, $$$1 \le Q \le 3 \cdot 10^5$$$).
The second line of each test case contains $$$N$$$ integers $$$a_1, a_2, \dots, a_N$$$ ($$$0 \le a_i \le 10^6$$$).
Each of the next $$$Q$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$0 \le x_i \le 10^6$$$, $$$0 \le y_i \le 10^6$$$), describing each scenario.
The sum of $$$N$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.
The sum of $$$Q$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.
Print $$$Q$$$ lines.
On the $$$i$$$-th line, output the maximum profit Busy Beaver can obtain in the $$$i$$$-th scenario.
There are five subtasks for this problem.
- ($$$15$$$ points): $$$Q = 1$$$, $$$1 \le x_1 \lt y_1$$$
- ($$$30$$$ points): For each $$$i \in \{1, 2, \dots, Q\}$$$, $$$1 \le x_i \lt y_i$$$
- ($$$15$$$ points): $$$Q = 1$$$, $$$1 \le y_1 \lt x_1$$$
- ($$$30$$$ points): For each $$$i \in \{1, 2, \dots, Q\}$$$, $$$1 \le y_i \lt x_i$$$
- ($$$10$$$ points): No additional constraints.
24 52 3 2 17 22 90 24 45 37 35 4 3 6 3 3 410 195 76 3
2136816162479275
Below is the explanation for the first test case.
In the first scenario, it is optimal to sell three type 1 pairs as follows: $$$$$$ (1, 1), (2, 2), (3, 3) $$$$$$ which yields a profit of $$$21$$$.
In the second scenario, it is optimal to sell four type 2 pairs as follows: $$$$$$ (1, 2), (1, 2), (2, 3), (3, 4) $$$$$$ which yields a profit of $$$36$$$.
In the fifth scenario, it is optimal to sell two type 1 pairs and two type 2 pairs as follows: $$$$$$ (1, 1), (2, 2), (2, 3), (3, 4) $$$$$$ which yields a profit of $$$16$$$.
The farmers' market has $$$N$$$ stalls and $$$M$$$ storage barns on a two-dimensional plane. There are $$$6M$$$ roads, each connecting a stall to a storage barn, such that no two roads intersect except at endpoints. In other words, the stalls and barns form a planar bipartite graph. Furthermore, every storage barn is connected to exactly $$$6$$$ distinct stalls.
Busy Beaver wants to select a subset of storage barns such that every stall is connected to exactly one selected barn by a road. How many ways are there to choose such a subset? As the answer may be large, output it modulo $$$10^9+7$$$.
The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^4$$$) — the number of test cases.
The first line of each test case contains two integers $$$N$$$ and $$$M$$$ ($$$6 \le N \le 3 \cdot 10^5$$$, $$$N/6 \le M \le 10^5$$$, $$$N \equiv 0 \pmod 6$$$), the number of stalls and the number of barns, respectively.
The $$$i$$$-th of the next $$$M$$$ lines starts with the integer $$$6$$$, followed by $$$6$$$ distinct integers $$$a_{i1},\dots,a_{i6}$$$ ($$$1 \le a_{ij} \le N$$$ for all $$$1 \le j \le 6$$$), describing the stalls connected to the $$$i$$$-th barn in clockwise order.
The $$$i$$$-th of the next $$$N$$$ lines starts with an integer $$$d_i$$$ ($$$1 \le d_i \le M$$$), followed by $$$d_i$$$ distinct integers $$$b_{i1},\dots,b_{id_i}$$$ ($$$1 \le b_{ij} \le M$$$ for all $$$1 \le j \le d_i$$$), describing the barns connected to the $$$i$$$-th stall in clockwise order.
It is guaranteed that the input describes a valid planar combinatorial embedding.
The sum of $$$N$$$ across all test cases does not exceed $$$3 \cdot 10^5$$$.
The sum of $$$M$$$ across all test cases does not exceed $$$10^5$$$.
Output a single integer for each test case: the number of ways, modulo $$$10^9+7$$$.
There are two subtasks for this problem.
- ($$$50$$$ points): The sum of $$$N$$$ across all test cases does not exceed $$$3 \cdot 10^3$$$, and the sum of $$$M$$$ across all test cases does not exceed $$$10^3$$$.
- ($$$50$$$ points): No additional constraints.
212 46 1 2 3 4 5 66 7 8 9 10 11 126 4 3 2 1 12 116 10 9 8 7 6 52 1 32 1 32 1 32 1 32 1 42 1 42 2 42 2 42 2 42 2 42 2 32 2 312 46 1 2 3 4 5 66 6 7 8 9 10 116 1 12 6 11 10 96 8 7 6 5 4 32 1 31 12 1 42 1 42 1 44 1 4 2 32 2 42 2 42 2 32 2 32 2 31 3
20
In the first test case, the barns and stalls are as follows:
There are $$$2$$$ ways to select the subset: either choosing barns $$$1$$$ and $$$2$$$, or choosing barns $$$3$$$ and $$$4$$$.
In the second test case, the barns and stalls are as follows:
Note that the barns connected to stall $$$6$$$ are listed in clockwise order: $$$1, 4, 2, 3$$$. There are no ways to select a subset of barns such that every stall is connected to exactly one selected barn.