Busy Beaver likes data structure problems, but he thinks that data structure problems on arrays with interval queries are boring. So he came up with a different kind of data structure problem, with multisets!
There is a sequence $$$a_1, \dots, a_L$$$, where each $$$a_i$$$ is a multiset of positive integers. Initially, the sequence is empty, i.e. $$$L=0$$$. Implement the following operations:
The first line of input contains a single integer $$$Q$$$ ($$$1 \le Q \le 5 \cdot 10^5$$$), the number of operations.
The next $$$Q$$$ lines contain one operation each.
It is guaranteed that:
For each type $$$4$$$ operation, output a line with the answer.
81 5 11 6 24 12 1 23 3 6 43 4 6 53 5 5 14 6
5 6
The multisets are as follows:
In programming contests, beavers solve problems in order, from first to last. Revaebs, on the other hand, are a special type of rodent that solve problems in reverse order, from last to first.
$$$N$$$ beavers and $$$N$$$ revaebs will compete against each other in the upcoming programming contest! The contest consists of $$$N$$$ problems, the $$$k^{\text{th}}$$$ problem having an integer point value $$$p_k$$$ between $$$l_k$$$ and $$$r_k$$$, inclusive. A contestant's score is the sum of the point values of the problems they solve.
On contest day, it is known that the $$$i^{\text{th}}$$$ beaver solved the first $$$i$$$ problems, and the $$$j^{\text{th}}$$$ revaeb solved the last $$$j$$$ problems. Additionally, the only pair of contestants with the same score are the two that solved all problems, the $$$N^{\text{th}}$$$ beaver and the $$$N^{\text{th}}$$$ revaeb. Given this information, count the number of possible assignments of points values to the problems in the contest. Since this number might be large, output its remainder when divided by $$$10^9 + 7$$$.
The first line contains $$$N$$$ ($$$1 \leq N \leq 50$$$), the number of problems in the contest.
$$$N$$$ lines follow. The $$$k^{\text{th}}$$$ of these lines contains two space-separated integers, $$$l_k$$$ and $$$r_k$$$ ($$$1 \le l_k \le r_k \le 2000$$$).
Output one line containing the answer: the number of sequences of point values modulo $$$10^9+7$$$.
41 12 23 310 10
1
11 2000
2000
41 21 21 21 2
2
51 32 41 41 23 3
18
61 51 51 51 51 51 5
5120
Sample Explanation 1
The point values of the problems can only be $$$1, 2, 3, 10$$$. Using these point values, the scores of the beavers are $$$1, 3, 6, 16$$$ respectively and the scores of the revaebs are $$$10, 13, 15, 16$$$ respectively. All of these are different other than the score of $$$16$$$ attained by the $$$4^{\text{th}}$$$ beaver and revaeb, so this one sequence is valid, making the answer $$$1$$$.
Sample Explanation 2
This sample satisfies the constraints for the second subtask.
Sample Explanation 3
This sample satisfies the constraints for the second subtask.
The only valid sequences of point values are $$$1, 2, 2, 2$$$ and $$$2, 2, 2, 1$$$, making the answer $$$2$$$.
Sample Explanation 5
This sample satisfies the constraints for the second subtask.
The MITIT club regularly hosts "social mixers", which are fun events meant for club members to socialize and take a break from schoolwork, problem writing, or contest organization. Snacks and games are provided. But the games can be a little weird...
Amy and Aimee, members of the MITIT club, are playing a new board game they invented!
The board consists of a row of $$$N$$$ squares, each colored either red, green, or white. The players have also agreed on a parameter $$$K$$$ (satisfying $$$0 \le K \le \min(N-1, 7)$$$), which is a nonnegative integer. Amy goes first and they take turns.
In each turn, the player makes a move following the below procedure:
In particular, it is always acceptable for $$$S$$$ to have exactly one white cell, and it is never possible for $$$|S|$$$ to exceed $$$K + 1$$$ (of course, $$$|S|$$$ must be odd as well).
The first player unable to make a legal move loses.
Given the state of the board before Amy makes her first move, with no red squares adjacent to green squares, determine which player will win if both play optimally.
The input consists of several test cases. The first line contains an integer $$$T$$$ ($$$1 \le T \le 5 \cdot 10^4$$$): the number of test cases.
The first line of each test case contains $$$N$$$ and $$$K$$$ ($$$1 \le N \le 2\cdot 10^5$$$, $$$\mathbf{0 \le K \le \min(N-1, 7)}$$$).
The second line of each test case contains a string of $$$N$$$ characters describing the initial state of the board. Each character is either R (red), G (green), or W (white). It is guaranteed that no R is adjacent to a G.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.
For each test case, output either Amy or Aimee, indicating the player who will win.
55 4WWWWW16 3RRRRWGGGGGWRRRRR6 5WWWWWW12 0WWWWRRWGGGWW13 7WRRWWGWRWRWWW
Amy Aimee Aimee Amy Amy
In the first sample test case, Amy can win by choosing $$$S$$$ to be the entire board and coloring it all red on her first turn.
In the second sample, Amy cannot make a legal move on her first turn, and she loses immediately.
In the third sample, no matter what Amy does on her first move, Aimee is always able to color the entire board with the same color on her turn, thus winning the game.
Busy Beaver is too lazy to write an interesting story for this problem, so he just gave you a formal statement.
Define a $$$M$$$-sequence as a sequence of positive integers, each between $$$1$$$ and $$$M$$$ inclusive.
A $$$M$$$-sequence is called $$$K$$$-good if the absolute difference between any pair of adjacent elements is at most $$$K$$$. For example, $$$[1, 2, 3, 5, 5, 3, 2, 1]$$$ is $$$2$$$-good and $$$2024$$$-good, but not $$$1$$$-good. We also consider $$$M$$$-sequences of length $$$0$$$ or $$$1$$$ to be $$$K$$$-good.
Given positive integers $$$N$$$, $$$M$$$, $$$K$$$, $$$L$$$, and a $$$M$$$-sequence $$$a_1, \dots, a_N$$$ of length $$$N$$$, find the maximum possible number of elements in a $$$M$$$-sequence $$$b$$$, such that:
Recall that a subsequence of a sequence is obtained by deleting some elements (possibly all or none) from a sequence, without reordering the remaining elements.
There are multiple test cases. The first line contains a positive integer $$$T$$$ ($$$1 \le T \le 2 \cdot 10^5$$$), the number of test cases.
The first line of each test case contains four integers $$$N$$$, $$$M$$$, $$$K$$$, $$$L$$$ ($$$0 \le N \le 2 \cdot 10^5$$$, $$$1 \le M \le 10^9$$$, $$$0 \le K \le 10^9$$$, $$$1 \le L \le 10^9$$$).
The second line of a test case contains $$$a_1, \dots, a_N$$$ ($$$1 \le a_i \le M$$$). If $$$N = 0$$$, then this line is skipped.
It is guaranteed that every $$$K$$$-good subsequence of $$$a$$$ has at most $$$L$$$ elements. Furthermore, the sum of $$$N$$$ over all test cases does not exceed $$$4 \cdot 10^5$$$.
For each test case, output one line with the maximum number of elements in $$$b$$$. It can be shown that under the problem's constraints, the maximum always exists and does not exceed $$$9 \cdot 10^{18}$$$.
33 3 1 31 3 20 5 2 37 7 2 31 4 2 7 7 1 6
5 6 7
In the first sample test case, one possible $$$M$$$-sequence $$$b$$$ is $$$[1, 3, 2, 3, 1]$$$, whose $$$1$$$-good subsequences, such as $$$[3, 2, 3]$$$ and $$$[3, 2, 1]$$$, all have length at most $$$L = 3$$$.
In the second sample test case, one possible $$$M$$$-sequence $$$b$$$ is $$$[1, 1, 5, 4, 2, 5]$$$, whose $$$2$$$-good subsequences, such as $$$[5, 4, 2]$$$ and $$$[1, 1, 2]$$$, all have length at most $$$L = 3$$$.
In the third sample test case, it can be shown that the only possible $$$b$$$ is $$$b = a$$$.
The Monitored Industrious Timbercrafters Infrastructure Technology (MITIT) is composed of $$$N$$$ beavers numbered $$$1,\dots,N$$$. There are $$$M$$$ pairs of beavers $$$(u_i,v_i)$$$, where initially, beaver $$$u_i$$$ is responsible for monitoring beaver $$$v_i$$$. Each beaver is monitored by at least one other beaver.
Busy Beaver, the manager of MITIT, would like to reconfigure these monitoring relations. In one operation, he can take a pair $$$(u,v)$$$ where beaver $$$u$$$ is currently monitoring beaver $$$v$$$ and make beaver $$$v$$$ monitor beaver $$$u$$$ instead. However, he must ensure that every beaver is monitored by at least one other beaver at all times.
Busy Beaver's desired final configuration can be described by a string $$$d$$$ of length $$$M$$$, where $$$d_i = 0$$$ if beaver $$$u_i$$$ monitors beaver $$$v_i$$$ at the end and $$$d_i = 1$$$ if beaver $$$v_i$$$ monitors beaver $$$u_i$$$ at the end. Find a shortest sequence of operations necessary to reach this final configuration, or report that it is impossible.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$N$$$ and $$$M$$$ ($$$3 \le N \le M \le 10^5$$$).
The $$$i$$$th of the next $$$M$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le N, u_i \ne v_i$$$). There does not exist $$$1 \le i \lt j \le M$$$ where $$$(u_i,v_i) = (u_j,v_j)$$$ or $$$(u_i,v_i) = (v_j,u_j)$$$.
The next line contains a string $$$d_1 \dots d_M$$$, where $$$d_i \in \{0,1\}$$$ for all $$$1 \le i \le M$$$.
It is guaranteed that in both the initial and final configurations, each beaver is monitored by at least one other beaver.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.
It is guaranteed that the sum of $$$M$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, if the task is impossible, output a single integer $$$-1$$$.
Otherwise, first output an integer $$$K$$$, the number of operations used. On the next line, output $$$K$$$ integers $$$a_1,\dots,a_K$$$ ($$$1 \le a_i \le M$$$), representing that your solution performs operations on $$$(u_{a_i},v_{a_i})$$$ in order.
For full points, $$$K$$$ should always be the minimum possible number of operations. Otherwise, you will receive $$$50\%$$$ of the points for each subtask if you correctly output any valid sequence of operations where the sum of $$$K$$$ across all test cases does not exceed $$$10^6$$$.
34 51 22 33 11 44 3110006 61 22 33 14 55 66 41111113 31 22 33 1000
2 2 1 -1 0
The operations in the first test case are shown below. Note that performing the operations in the opposite order is not acceptable because beaver $$$2$$$ must be monitored at all times.
In the second test case, it is not possible to reach the final configuration.
In the third test case, no operations need to be performed.
This is an output-only problem. In other words, the test cases are available to you and you will compute the answers on your own machine and submit them as a text file, instead of submitting a program.
Busy Beaver started his math homework a few hours before it is due (don't do that!) There are $$$100$$$ questions on the homework; how many of them can Busy Beaver do before the contest ends?
Each question is a set of simultaneous equations (see the input format for more details on what these equations look like). The task is to find positive integer solutions to as many of these sets as possible. Each set is worth one point, for $$$100$$$ points total.
Please download the test data using this link.
Each set of equations begins with one line with two numbers: the number of variables, $$$N$$$, in the equations (represented by this many of the initial letters in the alphabet), and the number of equations, $$$K$$$, present. This is followed by $$$K$$$ lines, each with one equation.
Each term on the left-hand side of the equation is formatted simply as [positive integer coefficient, at most 1000][list of at most 6 variables]; the left-hand side is always just a sum of at most $$$20$$$ of these terms (separated by plus signs: no term ever has a negative coefficient), and the right-hand side is always a positive integer. Exponents are not used; for example, $$$a^2bc$$$ may be written as aabc or caab.
Every equation set has a solution with all variables not exceeding $$$10^{12}$$$. The equations were generated using a simple random method, not intended to cause worst-case behavior in any algorithm.
First output a positive integer, $$$A$$$ ($$$1 \le A \le 100$$$), on its own line: the number of equations that you have solved.
Then output $$$A$$$ lines, each containing the index of the set you solved (from $$$1$$$ to $$$100$$$), followed by a space-separated list of positive integers: the values for the variables, in alphabetical order.
For example, if you solved equation set $$$5$$$ and the answer was $$$a = 1234$$$, $$$b = 5678$$$, and you solved equation set $$$10$$$ and the answer was $$$a = 123$$$, $$$b = 456$$$, $$$c = 789$$$, your output file may be as follows:
2
5 1234 5678
10 123 456 789
Each equation set may be listed at most once as an index. Your $$$A$$$ solutions do not have to be in any particular order (so you could have the solution to set $$$10$$$ before the solution to set $$$5$$$). If there are multiple solutions, print any solution with all variables at most $$$10^{18}$$$ (although, as mentioned above, all sets have solutions with all variables at most $$$10^{12}$$$).
If your output format is invalid, or if any solution you provided to any equation set is incorrect, you will receive zero points. Otherwise you will receive $$$A$$$ points.
To help you design your algorithm, we provide a table with information about the $$$100$$$ equation sets below, where $$$M$$$ is a number such that the set has a solution with all variables at most $$$M$$$: