Laser tag is a team shooting game, where players attempt to shoot other individuals by tagging them with a laser emitting gun.
Ali and Resli decided to play a match, so each one of them gathered a team of $$$n$$$ players.
The Arena where the match will be held is a $$$N\times N$$$ $$$2d$$$ plane, the $$$i_{th}$$$ player of Resli's team will stand at coordinates $$$(i, 0)$$$, while the $$$i_{th}$$$ player of Ali's team will stand at coordinates $$$(i, N)$$$.
To make things challenging, the arena has $$$Q$$$ walls, each wall is parallel to the x-axis and is given by three integers $$$x_1, x_2, y$$$ which means that the wall extends between points $$$(x_1, y)$$$ and $$$(x_2, y)$$$.
To ensure his win, Resli modified his team's guns, such that when a laser beam hits some wall, the beam will stop and two new beams will be generated at the endpoints of the wall (at coordinates $$$(x_1,y)$$$ and $$$(x_2,y)$$$ ) and will continue forward in the same direction as the original laser beam, and if one of these new generated laser beams hits a wall, the previously mentioned process will happen again (see notes for clarification).
Can you help Resli to find out how many players of Ali's team will be tagged by at least one laser beam if each player of Resli's team shot one laser beam in a direction parallel to the y axis towards the opposite team player (the $$$i_{th}$$$ player of Resli's team will shoot one laser beam in the direction of the $$$i_{th}$$$ player of Ali's team).
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$$$ ($$$2\le{n}\le{2}\times{10}^5$$$) and $$$q$$$ ($$$1\le{q}\le{n}$$$).
Each of the next $$$q$$$ lines of each test case contains three integers $$$x_1$$$,$$$x_2$$$,$$$y$$$ ($$$1\le{x_1}\le {x_2}\le{n}$$$), ($$$1\le {y}\le {n-1}$$$), which means there is a wall between coordinates $$$(x_1,y)$$$ and $$$(x_2,y)$$$.
The sum of $$$n$$$ over all test cases will not exceed $$$2\times {10}^5$$$.
$$$\textbf {It's guaranteed that no two walls will overlap or share a common point.}$$$
Output $$$T$$$ lines, the $$$i^{th}$$$ line contains the answer for the $$$i^{th}$$$ test case.
1 5 4 1 4 1 4 5 2 2 3 3 3 5 4
3
This picture demonstrates how the laser beam will move assuming that each team has $$$5$$$ persons and only the third person of Resli's team will shoot a laser, and there is a wall between $$$(1,1)$$$ and $$$(4,1)$$$. The laser will move towards the third person in Ali's team, and will stop after hitting the wall and two new lasers at the endpoints of the wall $$$(1,1)$$$, $$$(4,1)$$$ will be generated and will continue towards the first and fourth persons of Ali's team.
Every weekend you play some board games with your friends. There's one specific game you want to play this weekend, the game consists of a board with $$$N$$$ rows and $$$M$$$ columns, in each cell of the board there is an integer. Initially all integers are hidden. Each player chooses a row or a column, when all players are done choosing the board is revealed, and each player sums the values of the integers in his row or column, then all players with negative sums will lose the game.
The board of the game comes with a switch for each row and each column, and flipping the switch will reverse the sign of each integer of the row or column of that switch.
You realized that next weekend is the birthday of all your friends and you don't want to make anyone sad by losing the game, so you were wondering whether you can use switches on the initial board of the game so that no one will lose the game no matter what row or column they choose?
The first line contains a single integer T ($$$1\le{T}\le 1000 $$$), the number of test cases.
The first line of each test case consists of two integers $$$N$$$ and $$$M$$$($$$1\le{N,M}\le{200}$$$) the number of rows and columns of the board $$$B$$$. Each of the next $$$N$$$ lines will contain $$$M$$$ integers $$$B_{i,j}$$$ ($$$-50 \le {B_{i,j}} \le 50$$$), where $$$B_{i,j}$$$ is the integer in the $$$i_{th}$$$ row and $$$j_{th}$$$ column of the board $$$B$$$.
It is $$$\bf{guaranteed}$$$ that the sum of $$$N \times M$$$ over all test cases does not exceed $$$40\,000$$$.
For each test case, if you can select some rows and columns to flip such that there is a solution then print 'Yes' (without the quotes) in one line, then print in one line $$$R$$$ the number of rows that you want to flip , on the next line print $$$R$$$ ($$$0\le R \le N$$$) numbers, the indices of the rows that you want to flip, on the next line print $$$C$$$ the number of columns that you want to flip, on the next line print $$$C$$$ ($$$0\le C \le M$$$) numbers, the indices of the columns that you want to flip. If no solutions exists then print 'No' (without the quotes) in one line.
The printed rows and columns must be distinct each.
2 4 4 -3 -7 2 1 0 2 -3 1 2 1 2 2 -2 3 -4 0 3 4 1 2 3 5 -2 -2 5 20 7 5 6 0
Yes 2 1 4 0 Yes 0 0
Ammar teaches programming for kindergarteners. The classroom consists of $$$N$$$ desks such that they are put in front of each other, desks are indexed with numbers from $$$1$$$ to $$$N$$$, the desk with index $$$1$$$ is the first one, then desk $$$2$$$ comes behind it and so on..
There are $$$N$$$ children attending Ammar's programming lectures with distinct heights, child $$$i$$$ will sit in desk $$$i$$$, each child has a specific height. A child can see the board clearly if he sits in the first desk, or if he sits in a desk such that all children in front of him have heights strictly smaller than his height.
A seating is perfect if all children can see the board clearly. You will be given the heights of children from $$$1$$$ to $$$N$$$, can you check if their seating is perfect?
The input consists of multiple test cases. The first line contains a single integer $$$T$$$ $$$(1 \le T \le 1000)$$$ — number of test cases.
The first line of each test case contains a single integer $$$N$$$ $$$(1 \le N \le 100)$$$ — Number of children.
The second line of each test case contains $$$N$$$ integers $$$H_1, H_2,..., H_N$$$ ($$$1 \le H_i \le 200$$$) — the heights of children.
For each test case, print 'Yes' (without quotes) if the seating is perfect, otherwise print 'No' (without the quotes).
2 3 1 6 7 4 8 4 6 12
Yes No
You are playing an online game, you have a team of $$$N$$$ players, and you decided to challenge your friend's team that also consists of $$$N$$$ players, let's call them team $$$A$$$ and team $$$B$$$ respectively. Each player has a specific strength, more specifically the $$$i_{th}$$$ player in team $$$A$$$ has strength equal to $$$i$$$ for each $$$i$$$ between $$$1$$$ and $$$N$$$, and the $$$j_{th}$$$ player from team $$$B$$$ has strength equal to $$$j+1$$$ for each $$$j$$$ between $$$1$$$ and $$$N$$$.
The total strength of a team is the product of strengths of all players in the team. To make the game fair, you can swap the $$$i_{th}$$$ player from team $$$A$$$ with the $$$i_{th}$$$ player from team $$$B$$$ for any $$$i$$$ between $$$1$$$ and $$$N$$$, in other words, you can only swap players that have the same index in both teams. You can repeat the previous operation any number of times.
A game is fair when both of the teams have a equal strengths. Can you make the game fair?
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^5$$$). Description of the test cases follows.
Each of the following $$$T$$$ lines, contains a single integer $$$N$$$ ($$$1\le{N}\le{10}^5$$$).
For each test case, if you can make the game fair then print in one line an integer $$$M$$$,the total number of operations needed, on the next line print $$$M$$$ ($$$ 1 \le M \le N$$$) distinct integers, the indices where you want to apply the swap operation. If you can't make the game fair, then print in one line the value $$$-1$$$.
Note that you don't have to minimize the total number of operations. If there exists more than one answer print any of them.
2 8 4
3 1 4 5 -1
In the first test case, the initial strengths are:
team $$$A$$$: $$$1, 2, 3, 4, 5, 6, 7, 8$$$ with total team strength equal to $$$40\,320$$$.
team $$$B$$$: $$$2, 3, 4, 5, 6, 7, 8, 9$$$ with total team strength equal to $$$362\,880$$$.
After swapping the players in indices $$$1, 4$$$ and $$$5$$$, the strengths become like this:
team $$$A$$$: $$$2, 2 ,3, 5, 6, 6, 7, 8$$$ with total team strength equal to $$$120\,960$$$.
team $$$B$$$: $$$1, 3, 4, 4, 5, 7, 8, 9$$$ with total team strength equal to $$$120\,960$$$.
So the strengths are now equal and the game is fair.
In the second test case, you can't make the strengths equal no matter how you perform the swaps.
Edrisov likes to keep his house clean, but knowing that the exams are around the corner, he doesn't have a lot of free time, so he decided it's time to buy a robovac!
Robovac is a short name for robot vaccum cleaner, which -given it's name- does the cleaning automatically.
Edrisov lives inside a line divided into $$$N$$$ cells. Initially the robot is standing on the middle cell (cell with index $$$\lceil \frac {N}{2} \rceil$$$) and faces the right direction (direction of the $$$N_{th}$$$ cell), the robot will keep moving in some direction until it steps on a cell it hasn't visited yet, then it will change direction and repeat the process.
The robot will stop moving when all cells are visited. (see notes for a better understanding on how the robot is moving).
Can you help Edrisov to know how many steps the robot will make during the cleaning process?
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^5$$$). Description of the test cases follows.
Each of the following $$$T$$$ lines, contains a single integer $$$N$$$ ($$$1\le{N}\le{10}^9$$$) — Number of cells in the line.
For each test case, output a single integer denoting the answer for the $$$i_{th}$$$ test case.
2 3 4
3 6
for $$$N=4$$$, the robot starts at cell with index $$$2$$$ and faces the right direction:
I am sure that you are all bored of the classical A + B extreme problem, That's why we came up with a harder version of this problem.
Resli sets a weekly schedule for telling jokes to his friends. A weekly plan consists of $$$7$$$ numbers where each number represents the total number of jokes that Resli is planning to tell from Saturday to Friday.
Resli will give you the number of weeks that he planned, you have to determine the total number of jokes that he is going to tell to his friends in each week.
Since this task is very hard you asked your friend Hano to help you, so he wrote a code to solve this problem using the $$$C++$$$ programming language. Here's his code:
The problem is that hano doesn't know how to submit a problem, can you submit this code for him?
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 1000$$$). Description of the test cases follows.
Each of the following $$$T$$$ lines, contains seven integers $$$j_1, j_2, ... j_7$$$ ($$$1\le{j_1, j_2, ... j_7}\le{10}$$$) — number of jokes in each day of the week.
For each week, print in one line the total number of jokes that will be told by Resli during that week.
3 1 1 1 1 1 1 1 1 2 3 4 5 6 7 9 1 6 2 2 3 9
7 28 32
Coach Ali Zibak was the chief judge of the first local contest, the problem set was very hard and this made coach Bsher very angry so he decided to put this hard problem.
Given $$$N \times M$$$ grid, each cell contains a digit written on it. Two cells are connected if they share a side and have the same digit written on them. Connected cells form a connected component. You have to process two types of queries:
In the first query you are given a sub-grid in the grid, the sub-grid is defined by two points, the first point is the upper left corner with indices $$$x_1$$$ $$$y_1$$$, the second point is the lower right corner with indices $$$x_2$$$ $$$y_2$$$, and you have to count the number of fully and partially contained components in this sub-grid.
A component is said to be fully contained if all its cells are in the given sub-grid, if at least one cell is inside the sub-grid, and at least one cell is outside it. This component is said to be partially contained.
In the second query you put a wall at cell $$$x, y$$$. Blocking it and removing any connected cells to it.
The first line contains a single integer $$$T$$$ ($$$1\le T \le 10^4$$$) — Number of test cases to process.
The first line of each test case contains three integers $$$N$$$, $$$M$$$ and $$$Q$$$ ($$$1 \le N, M \le 500$$$), ($$$1 \le Q \le 10^4$$$) — Width and Height of the grid, and number of queries to process.
Each of the next $$$N$$$ lines contains $$$M$$$ numbers, description of the grid ($$$1\le grid_{i, j} \le 9$$$).
Next $$$Q$$$ lines contain the description of each query, as described in the problem statement.
It's guaranteed that sum of $$$N \times M$$$ over all test cases is at most $$$250\,000$$$ and sum of $$$Q$$$ over all test cases is at most $$$10^4$$$.
For each query of the first type print two numbers, number of fully and partially contained components in this query.
1 4 5 7 1 2 1 3 2 1 1 1 1 2 2 2 2 2 3 4 4 5 4 3 1 1 2 3 4 2 2 3 1 1 2 3 4 2 2 2 1 1 2 3 4 1 1 1 4 5 1 2 4 3 5
2 2 4 2 4 1 11 0 1 3
We call a set $$$S$$$ of $$$K$$$ distinct integers FAT if every integer in the set is greater than or equal to the size of the set. In other words, we call a set of $$$K$$$ integers FAT if for each element $$$s \in S; s \ge K$$$.
For example, sets $$$S_1 = \{3,4,5\}$$$,$$$S_2 = \{1\}$$$ are FAT, but set $$$S_3 = \{1,2,3\}$$$ is not FAT.
Your task is to count the number of FAT sets such that all integers in the sets are not greater than $$$N$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^5$$$). Description of the test cases follows.
Each of the following $$$T$$$ lines, contains a single integer $$$N$$$ ($$$1\le{N}\le{10}^5$$$).
For each test case, output a single integer denoting the answer for the $$$i_{th}$$$ test case, since the answer could be very large, please print the remainder of dividing it by $$$1\,000\,000\,007$$$.
3 1 2 3
1 2 4
In the first example the only possible set is $$$S = \{1\}$$$.
In the second example the possible sets are $$$S_1 = \{1\}$$$ and $$$S_2 = \{2\}$$$.
In the third example the possible sets are $$$S_1 = \{1\}$$$, $$$S_2 = \{2\}$$$, $$$S_3 = \{3\}$$$ and $$$S_4 = \{2,3\}$$$.
After retiring from Competitive Programming coach Ali wanted to discover new horizons and achieve his lifetime dream of buying a farm in the Swiss countryside!
Unlike Farmer John, Coach Ali doesn't want to spend his time running around his cows, years of years in Competitive Programming made him very tired and running around cows is even harder.
Coach Ali bought a farm, and he wants to plant trees in it! There isn't anything much joyful than planting trees and eating fresh fruits everyday. He planted $$$N$$$ trees in different points, tree $$$i$$$ is planted at coordinates $$$X_i, Y_i$$$.
However farming isn't an easy task, there are lots of tasks and challenges, the first one is to make sure that the trees will grow up. Different coordinates have different soil types, and eventually different probability for the trees to grow. Tree planted at point $$$i$$$ has probability $$$\frac{p_i}{100}$$$.
One last thing to consider, watering the trees. You have to buy a rectangular watering system and place it in the farm. This system should have sides parallel to the axes.
Given the point coordinates and the probability of each tree to grow, your task is to find the expected value of the rectangular watering system area.
The first line contains a single integer $$$T$$$ ($$$1\le T \le 10^4$$$) — Number of test cases to process.
The first line of each test case contains a single integer $$$N$$$ ($$$1\le N \le 10^5$$$) — Number of planted trees.
Each of the next $$$N$$$ lines contains three space separated numbers, $$$X_i$$$, $$$Y_i$$$, $$$P_i$$$ ($$$1 \le X_i, Y_i \le 10^5$$$), ($$$0\le P_i \le 100$$$) — Points coordinates, and the probability of each tree to grow.
It is $$$\bf{guaranteed}$$$ that the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$, and all point coordinates are distinct.
For each test case output the expected value of the rectangular watering system area modulo $$$1\,000\,000\,007$$$.
Formally, let $$$M = 1\,000\,000\,007$$$. It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q \not \equiv 0 \pmod{M}$$$. Output the integer equal to $$$p \cdot q^{-1} \bmod M$$$. In other words, output such an integer $$$x$$$ that $$$0 \le x \lt M$$$ and $$$x \cdot q \equiv p \pmod{M}$$$.
2 5 2 3 100 5 9 25 4 3 60 2 7 75 8 9 30 3 1 6 33 2 4 20 3 9 100
880000022 298000005
Nour has just arrived at MIT. He is now standing in front of their gates fully ready to get inside. Unfortunately, there is one more task that the guards asked him to solve to let him get inside.
The guards gave Nour the magical box, which contains $$$N$$$ balls such that the $$$i_{th}$$$ ball has color $$$C_i$$$. Then, they put $$$K$$$ empty boxes in front of Nour and asked him the following question: How many ways there are to partition all $$$N$$$ balls into all $$$K$$$ boxes, such that:
In conclusion, two ways are considered different if they differ by at least one i-th box. For example, if colors of balls in the magical box are $$${1, 2, 2}$$$ and $$$K = 2$$$, then there are $$$4$$$ ways: [$$$\{1\}$$$, $$$\{2, 2\}$$$], [$$$\{2, 2\}$$$, $$$\{1\}$$$], [$$$\{1, 2\}$$$, $$$\{2\}$$$], [$$$\{2\}$$$, $$$\{1, 2\}$$$].
This problem is very hard for Nour, can you help him so that he does not get rejected from MIT? If you can, find the answer and print it modulo $$$1\,000\,000\,007$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$. Description of the test cases follows.
The first line of each test case contains two integers $$$N$$$ and $$$K$$$, $$$(1 \le N \le 10^3)$$$, $$$(1 \le K \le N)$$$ - the number of balls in the magical box and the number of empty boxes.
The second line of each test case contains $$$N$$$ elements of the array $$$C$$$ describing the color of each ball in the magical box $$$(1 \le C_i \le N)$$$.
It's guaranteed that the sum of $$$N\times K$$$ over all test cases does not exceed $$$10^6$$$
For each test case, print a single line containing the described answer modulo $$$1\,000\,000\,007$$$.
2 6 3 1 2 2 1 4 3 4 4 1 2 3 2
219 12
In the second test case, we have $$$4$$$ balls and $$$4$$$ boxes, so it is equal to the number of permutations with repetition of array $$$[1, 2, 2, 3]$$$, which is $$$\frac{4!}{2!} = 12$$$.
You are planning to visit the movies with your friends after the end of the exams. The movie theater has $$$N$$$ movies, you know the start and end moments of each movie. The theater contains many halls, so there could be more than one movie playing at the same time, the movie theater will be open for $$$M$$$ moments.
If you reach the movies at the beginning of moment $$$L$$$ and you stay until the end of moment $$$R$$$, then you can watch any movie that starts at moment $$$L$$$ or later and ends at moment $$$R$$$ or earlier. You are planning to watch exactly $$$2$$$ complete movies, so you can't start watching the second movie until you finish watching the first one.
Since you are sharp-minded, you thought of all possible scenarios of arriving and leaving the movies, in other words, for every possible arriving time $$$L_i$$$ from $$$1$$$ to $$$M$$$, and for every possible leaving time $$$R_j$$$ from $$$L_i + 1$$$ to $$$M$$$. For each scenario you need to count how many pairs of movies are possible to watch during this period. You have to print the sum of pairs for all possible scenarios. Note that if some pair of movies is present in more than one scenario then you should count them independently in each scenario.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 2\times{10^5}$$$). Description of the test cases follows.
The first line of each test case contains two integers $$$N$$$ ($$$1\le{N}\le{2}\times{10}^5$$$) and $$$M$$$ ($$$1\le{M}\le{2}\times{10}^5$$$).
Each of the next $$$N$$$ lines of each test case contains $$$L_i$$$ and $$$R_i$$$($$$1\le{L_i}\le{R_i}\le{M}$$$), the start and the end moments of the $$$i^{th}$$$ movie for each $$$i$$$ from $$$1$$$ to $$$N$$$.
It is $$$\bf{guaranteed}$$$ that the sum of $$$N$$$ and sum of $$$M$$$ over all test cases does not exceed $$$2 \times 10^5$$$.
For each test case, output a single integer denoting the answer for the test case, since the answer could be very large, please print the remainder of dividing it by $$$1\,000\,000\,007$$$.
2 3 6 1 3 2 5 3 6 4 12 1 6 2 8 9 10 11 12
0 21
In the first test case, all the movies are overlapping, in other words you can't pick two movies to watch entirely in any possible period of time, so the answer is $$$0$$$.
Coach Mohammed Resli (A.K.A EleCursity), has a strange phobia, called ResliPhobia. It's a condition when someone has a fear of consecutive numbers having the same parity. A degree $$$K$$$ of this phobia is when you see $$$\bf{strictly}$$$ more than $$$K$$$ consecutive even OR odd numbers.
Coach Tareq is aware of Resli's condition, that's why he wants to help him. Tareq has $$$N$$$ bags, each bag contains $$$A_i$$$ balls. He wants to choose a sub-sequence of these bags, such that this sub-sequence has the most number of balls, and it won't make coach Resli afraid, can you help Tareq find the maximum number of balls in the chosen sub-sequence?
Note that a sub-sequence of an array $$$A$$$ is defined as a sequence that can be obtained from $$$A$$$ by deleting some elements (possibly none), without changing the order of the remaining elements.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^4$$$). Description of the test cases follows.
The first line of each test case contains two integers $$$N$$$ ($$$1\le N \le 1000$$$) and $$$K$$$ ($$$1 \le K \le N$$$) — Number of bags and the phobia degree.
The second line of each test case contains $$$N$$$ numbers $$$A_1$$$, $$$A_2$$$, $$$...$$$, $$$A_n$$$ ($$$1\le A_i \le 1000$$$) — Number of balls in each bag.
It is $$$\bf{guaranteed}$$$ that the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, print a single line containing the maximum number of balls in the chosen sub-sequence.
42 12 34 110 10 11 115 210 100 98 101 35 11 1 1 1 1
5 21 302 1
In the first test case, we can take the whole array as a subsequence, so the corresponding sum will be $$$2$$$ $$$+$$$ $$$3$$$ $$$=$$$ $$$5$$$$$$.$$$
In the second test case, it is optimal to take $$$[$$$$$$10$$$, $$$11$$$$$$]$$$ as a subsequence because since ($$$k$$$ $$$=$$$ $$$1$$$) we can't take two even elements in a row and we can't take two odd elements in a row, so the answer will be $$$10$$$ $$$+$$$ $$$11$$$ $$$=$$$ $$$21$$$$$$.$$$
A permutation of size $$$N$$$ is an array containing distinct values between $$$[1, N]$$$.
Define the score of a permutation $$$P$$$ of size $$$n$$$ as the sum of the number of divisors for every $$$P[i]$$$ that appear strictly before it in the permutation, more formally:
$$$$$$F(P)=\sum_{i=2}^N\sum_{j=1}^{i-1}(P[j] \mid P[i])$$$$$$
For example, the score of permutation $$$\{2,1,3,4\}$$$ is $$$3$$$.
Your task is to find the sum of scores for all permutations of size n.
Since the answer might be very large, output it modulo $$${10}^9+7$$$.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10^5$$$). Description of the test cases follows.
Each of the following $$$T$$$ lines contains a single integer $$$N$$$ ($$$1\le{N}\le{10}^5$$$), the size of the permutations.
For each test case, print in one line the total sum of scores of all permutations in this test case module $$$1\,000\,000\,007$$$.
3 1 2 3
0 1 6