Tyger has an array of $$$n$$$ values, where each integer is between $$$1$$$ and $$$n$$$ inclusive and occurs exactly once. Regyt is unpleased with the arrangement of values, and provides instructions for Tyger to rearrange his array.
Regyt's instructions come in the form of $$$q$$$ queries. Each query requires Tyger to swap the positions of two values, $$$x$$$ and $$$y$$$, in the array. $$$x$$$ and $$$y$$$ refer to values, not indices. To check his work, Tyger would like you to determine the final array!
The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, representing the size of the permutation.
The second line contains $$$n$$$ integers, representing the array $$$p_1, \dots, p_n$$$
The next line contains a single integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$, representing the number of queries.
Then, $$$q$$$ lines follow. Each line contains two integers $$$x$$$ and $$$y$$$ $$$(1 \leq x, y \leq n)$$$, representing the values to swap.
Output $$$n$$$ integers, the resulting array after performing all the swaps.
In tests worth $$$50$$$ points, it is guaranteed that $$$1 \leq n, q \leq 1000$$$
7 5 2 3 7 4 1 6 4 1 2 6 7 2 5 3 5
2 1 5 6 4 3 7
After each instruction, the array becomes
5 1 3 7 4 2 6
5 1 3 6 4 2 7
2 1 3 6 4 5 7
2 1 5 6 4 3 7
Credit: RandomChicken
Tyger has a bunch of blocks that form a 2 dimensional connected shape on a square grid. He wants to rotate the shape clockwise by 90 degrees, and can only do so by moving some of the blocks around. Note that you can move blocks out of the original $$$n \times n$$$ grid. Please help him calculate the minimum number of blocks he needs to move to successfully rotate the shape!
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 5)$$$, the number of testcases.
The first line of each testcase contains a single integer $$$n$$$ $$$(1 \leq n \leq 50)$$$, denoting the number of rows and columns of the grid.
Then, $$$n$$$ lines follow, each containing $$$n$$$ characters. The character in the $$$i$$$ -th row and the $$$j$$$ -th column is 1 if the corresponding cell contains a block, and 0 otherwise.
For each testcase, output a single integer, the minimum number of blocks Tyger needs to rotate the shape clockwise by 90 degrees.
2 3 100 100 111 4 1111 1010 1010 1010
2 3
In the second testcase, you can move the block at $$$(1, 4)$$$ to $$$(1, 0)$$$, the one at $$$(4, 1)$$$ to $$$(3, 0)$$$, and the block at $$$(2, 1)$$$ to $$$(3, 2)$$$. It can be proven that it's impossible to rotate the shape by moving less than $$$3$$$ blocks.
Credit: jay_jayjay
Cody and Tyger want to play a game. Initially, two integers, $$$x$$$ and $$$y$$$ are written on the board. Then, Cody and Tyger take turns, with Cody going first. In each player's turn, they choose two integers on the board such that their absolute difference isn't currently on the board, then add the absolute difference to the board. The player who cannot make a move loses.
Given an integer $$$n$$$, if both Cody and Tyger play optimally, how many games will Cody win across all starting pairs $$$(x, y)$$$ where $$$1 \leq x, y \leq n$$$?
Each test contains multiple testcases. The first line contains the number of testcases $$$t$$$ $$$(1 \leq t \leq 5)$$$.
Each of the next $$$t$$$ lines contain a single integer $$$n$$$ $$$(1 \leq n \leq 10^6)$$$.
For each testcase, output the number of games Cody will win across all starting pairs $$$(x, y)$$$ where $$$1 \leq x, y \leq n$$$, assuming both players play optimally.
In tests worth $$$30$$$ points, it is guaranteed that for each testcase $$$1 \leq n \leq 1000$$$.
4 1 2 3 1434
1 2 7 1370142
In the third testcase, Cody wins if the starting pair is $$$(1, 1)$$$, $$$(1, 3)$$$, $$$(2, 2)$$$, $$$(2, 3)$$$, $$$(3, 1)$$$, $$$(3, 2)$$$, or $$$(3, 3)$$$.
Credit: eggag32
The high elevations of Machu Picchu can cause altitude sickness. Tourists, such as Gennady Korotkevich, plan to hike to the various attractions at Machu Picchu; each wants to visit a certain number of attractions but cannot exceed their personal elevation capacity (or "peak rating") at any point along their hike.
Tourists can only move one tile north, south, east, or west, to a height that has a difference of at most $$$1$$$ from their current height.
Fortunately, the tour sponsors have made it possible for each tourist to begin their hike anywhere in Machu Picchu. Help each tourist find the best coordinates to start their hike!
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 1000)$$$, representing the number of rows and columns of an elevation map describing the region.
The next $$$n$$$ lines contain $$$m$$$ integers each. The $$$j$$$ -th number in the $$$i$$$ -th row represents the elevation of coordinate $$$(i, j)$$$. It is guaranteed that the elevation of each coordinate does not exceed $$$10^5$$$.
The next line contains a single integer $$$a$$$ $$$(1 \leq a \leq 10)$$$, representing the number of attractions.
The next $$$a$$$ lines each contain two integers $$$r$$$ and $$$c$$$ $$$(1 \leq r \leq n, 1 \leq c \leq m)$$$, the row and column of the attraction.
The next line contains a single integer $$$q$$$ $$$(1 \leq q \leq 10^5)$$$, the number of queries.
The next $$$q$$$ lines each contain two integers $$$c$$$ and $$$v$$$ $$$(1 \leq c \leq 10^5, 1 \leq v \leq a)$$$, the elevation capacity of the tourist (the height that they can never exceed) and the number of attractions they want to visit.
For each query, output two integers $$$y$$$ and $$$x$$$, the row and column where the tourist should start. If there are multiple answers, output the one with the smallest $$$(y \times m + x)$$$. If an answer doesn't exist, output "-1 -1"
8 12 4 5 6 7 8 1 1 1 1 1 3 1 3 2 1 1 9 1 1 1 1 1 3 1 1 1 1 1 10 1 1 1 1 1 1 3 1 1 1 1 11 12 13 1 1 1 1 1 1 1 1 1 12 1 1 1 1 1 1 1 2 7 1 1 13 1 1 1 1 1 1 1 3 6 1 1 14 1 1 1 1 1 1 1 4 5 1 1 15 16 17 99 1 1 1 1 6 8 12 6 2 8 7 4 7 1 12 2 12 5 17 5 1 1 17 4 16 4 1 2
-1 -1 1 6 -1 -1 -1 -1 1 12
In the fifth query, starting from $$$(1, 12)$$$ allows you to visit attractions located at $$$(1, 12)$$$ and $$$(2, 12)$$$.
Credit: RandomChicken
Tyger is at an ice cream shop where $$$n$$$ flavors are laid out in a row. Each flavor has a unique integer price from $$$1$$$ to $$$n$$$, inclusive.
Tyger samples the flavors over $$$n$$$ days using the following process:
- On the first day, Tyger picks any flavor he wants.
- On each following day, he looks at the untried flavors next to the ones he's already had. From these, he picks the one with the lowest cost.
The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1 \leq n, q \leq 10^5)$$$, representing the number of flavors and the number of questions.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, the costs of the flavors. It is guaranteed that $$$a$$$ is a permutation of length $$$n$$$.
The next $$$q$$$ lines each contain two integers $$$p$$$ and $$$k$$$ $$$(1 \leq p \leq n, 1 \leq k \leq n)$$$, representing Cody's questions.
For each of Cody's questions, output a single integer: the number of possible first-day choices that would result in Tyger trying flavor $$$p$$$ on day $$$k$$$.
In tests worth $$$20$$$ points, it is guaranteed that $$$n \leq 1000$$$.
7 3 4 2 6 3 7 1 5 3 1 2 3 5 4
1 1 0
For the first question, Tyger can only start with flavor $$$3$$$ on the first day. For the second question, Tyger can only start with flavor $$$4$$$ on the first day, trying flavor $$$3$$$ on the second day and flavor $$$2$$$ on the third. For the third question, it's impossible no matter which flavor Tyger starts with.
Credit: Mishazher
Tyger has a permutation $$$p_1, p_2, ..., p_n$$$ of size $$$n$$$, and he wants to sort it with his newly invented algorithm — Tyger Sort. The pseudocode of the process of Tyger sort follows:
for x from n to 1
i = 1
while p[i] != x
i := i + 1
while i > 1 and p[i] < p[i - 1]
swap(p[i], p[i - 1])
i := i - 1
You are given a permutation $$$a_1, a_2, ..., a_n$$$ of size $$$n$$$. Your task is to construct a permutation $$$p_1, p_2, ..., p_n$$$ so that the resulting permutation after applying Tyger sort on $$$p$$$ is $$$a$$$, or output $$$-1$$$ if no such permutation exists.
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 100)$$$, representing the number of testcases.
The first line of each testcase contains a single integer $$$n$$$ $$$(1 \leq n \leq 2 \times 10^5)$$$.
The second line of each testcase contains $$$n$$$ integers $$$a_1, a_2, ..., a_n$$$ – denoting the permutation $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \times 10^5$$$.
For each testcase, output a permutation $$$p_1, p_2, ..., p_n$$$ so that it results in $$$a_1, a_2, ..., a_n$$$ after applying Tyger sort, or $$$-1$$$ if no such permutation exists. If multiple solutions exist, output any.
351 2 3 4 531 3 244 3 2 1
1 2 3 4 5 3 1 2 -1
For the first testcase, since no swaps are performed, 1 2 3 4 5 remains as 1 2 3 4 5. For the third testcase, it can be proven that the given permutation can't be a result of Tyger-Sorting a permutation.
Credit: C0DET1GER
Tyger has an array $$$a$$$ that is initially $$$[0]$$$.
He can do any number of Domain Expansions to the array. Each Domain Expansion allows him to first choose any index $$$i$$$, then insert $$$a_i+1$$$ on either the left or right side of the element $$$a_i$$$. Tyger wants to create a target array $$$b$$$ of length $$$n$$$, please help him count the number of ways to get target array $$$b$$$, modulo $$$10^9+7$$$.
Two ways are different if a Domain Expansion (which accounts for both position chosen and whether the new element is inserted left or right) is different at any position.
The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 400)$$$, the length of the target array $$$b$$$.
The next line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ $$$(0 \leq b_i \leq 10^9)$$$, representing the target array.
Output a single integer, the number of different ways to get target array $$$b$$$ modulo $$$10^9 + 7$$$.
In tests worth $$$10$$$ points, it is guaranteed that $$$b_i = i - 1$$$ for all $$$1 \leq i \leq n$$$.
In tests worth $$$10$$$ points, it is guaranteed that $$$1 \leq n \leq 80$$$.
41 2 1 0
3
One of the ways to get target array $$$b$$$ is through this sequence of Domain Expansions:
[0] -> [1, 0] -> [1, 2, 0] -> [1, 2, 1, 0]
Another way is
[0] -> [1, 0] -> [1, 1, 0] -> [1, 2, 1, 0]
Note that this sequence actually accounts for two different ways because the $$$2$$$ can be inserted both by choosing the first $$$1$$$ (and picking right) and choosing the second $$$1$$$ (and picking left).
Credit: Jasonwei08
Cody and Tyger are together in a place with $$$n$$$ stations and $$$m$$$ portals. Each portal is represented by six numbers $$$(a_1, l_1, r_1, a_2, l_2, r_2)$$$, allowing you to travel from station $$$b$$$ to station $$$c$$$ if and only if all the following conditions are satisfied:
- $$$l_1 \leq b \leq r_1$$$
- $$$b \equiv 0 \pmod {a_1}$$$
- $$$l_2 \leq c \leq r_2$$$
- $$$c \equiv 0 \pmod {a_2}$$$
Since Cody and Tyger are enemies, they are unwilling to share the same portal during their transportation (they are allowed to be in the same station though). Therefore, for each query, output whether it is possible for both Cody and Tyger to reach station $$$d$$$ without sharing any portals.
The first line contains two integers $$$n$$$ and $$$m$$$ $$$(1 \leq n, m \leq 2 \times 10^4)$$$, the number of stations and portals.
The next $$$m$$$ lines contain $$$6$$$ integers each: $$$a_1$$$, $$$l_1$$$, $$$r_1$$$, $$$a_2$$$, $$$l_2$$$, and $$$r_2$$$ $$$(1 \leq a_1, a_2 \leq n, 1 \leq l_1 \leq r_1 \leq n, 1 \leq l_2 \leq r_2 \leq n)$$$.
The following line contains two integers $$$d$$$ and $$$q$$$ $$$(1 \leq d \leq n, 1 \leq q \leq 2 \times 10^4)$$$, the destination and the number of queries.
The next $$$q$$$ lines contain two integers each: $$$x$$$ and $$$y$$$ $$$(1 \leq x, y \leq n)$$$.
For each query, output "Yes" if Cody and Tyger can reach station $$$d$$$ without sharing portals, and output "No" otherwise.
6 42 2 4 3 3 61 4 5 1 6 61 1 1 4 3 41 1 4 5 1 46 41 21 54 43 6
Yes Yes Yes No
For the first testcase, Cody can use portal $$$3$$$ to get to station $$$4$$$ and use portal $$$2$$$ to get to station $$$6$$$. Tyger can use portal $$$1$$$ to directly travel to station $$$6$$$.
Credit: C0DET1GER