Given the array $$$[ 1,2, \ldots ,2 \cdot n ]$$$, partition it into $$$2$$$ subsequences $$$a$$$ and $$$b$$$ of length $$$n$$$ such that each element of the original array is present in one of $$$a$$$ or $$$b$$$. A subsequence is a sequence that can be derived from the given array by deleting zero or more elements without changing the order of the remaining elements.
For each index $$$i$$$ ($$$ 1 \le i \le n$$$), you are given one of the three following constraints: $$$a_i+b_i = v_i$$$, $$$|a_i-b_i| = v_i$$$, or $$$\text{max}(a_i, b_i) = v_i$$$. Find the number of possible subsequences $$$a$$$ and $$$b$$$, modulo $$$10^9+7$$$. It is guaranteed there exists at least one partition that satisfies the constraints.
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$).
The next $$$n$$$ lines each contain two integers $$$t_i$$$ and $$$v_i$$$ ($$$1 \le t_i \le 3, 1 \le v_i \lt 4 \cdot n$$$) — the constraints on $$$a_i$$$ and $$$b_i$$$.
If $$$t_i=1$$$, $$$v_i=a_i+b_i$$$.
If $$$t_i=2$$$, $$$v_i=|a_i-b_i|$$$.
If $$$t_i=3$$$, $$$v_i=\text{max}(a_i, b_i)$$$.
—
There are $$$10$$$ tests, not including samples. Each test is worth $$$\frac{100}{10}=10$$$ points.
Output a single integer — the number of possible ways to partition the array $$$[ 1,2, \ldots 2 \cdot n ]$$$ into $$$a$$$ and $$$b$$$ that satisfy the constraints. Output your answer modulo $$$10^9+7$$$.
51 53 53 62 21 18
4
In the sample test, the $$$4$$$ ways to partition the array are:
- $$$a=[1,2,3,7,8]$$$ and $$$b=[4,5,6,9,10]$$$
- $$$a=[1,2,3,9,10]$$$ and $$$b=[4,5,6,7,8]$$$
- $$$a=[4,5,6,7,8]$$$ and $$$b=[1,2,3,9,10]$$$
- $$$a=[4,5,6,9,10]$$$ and $$$b=[1,2,3,7,8]$$$
—
Problem Idea: superhelen
Problem Preparation: xug
Occurrences: Novice D
Given an array $$$a$$$ of length $$$n$$$, you need to answer $$$m$$$ queries.
Each query will provide $$$l$$$ and $$$r$$$, and you need to calculate the value of $$$\bigoplus\limits_{i=l}^{r}\bigoplus\limits_{j=l}^{r}(a_i+a_j)$$$, the bitwise XOR of all $$$a_i+a_j$$$ such that $$$l \le i, j \le r$$$.
The first line contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n \leq 2 \cdot 10^5, 1 \leq m \leq 10^6$$$) — the length of the array $$$a$$$ and the number of queries.
The second line contains $$$n$$$ integers $$$a_1,a_2 \ldots a_n$$$ $$$(0 \leq a_i \leq 10^9)$$$ — the elements of the array $$$a$$$.
Then, there are $$$m$$$ lines, each containing two integers $$$l$$$ and $$$r$$$ $$$(1 \leq l \leq r \leq n)$$$.
—
Tests in subtasks are numbered from $$$1 - 10$$$ with samples skipped. Each test is worth $$$\frac{100}{10}=10$$$ points.
Tests $$$1 - 2$$$ satisfy $$$1 \leq n, m \leq 100$$$.
Tests $$$3 - 5$$$ satisfy $$$1 \leq n, m \leq 3366$$$.
The remaining tests do not satisfy any additional constraints.
Output $$$m$$$ lines, each containing an integer, representing the answer to each query.
5 40 1 2 3 43 52 21 41 5
10 2 0 8
The answer to the first query of the sample test is $$$(2+2) \oplus (2+3) \oplus (2+4) \oplus (3+2) \oplus (3+3) \oplus (3+4) \oplus (4+2) \oplus (4+3) \oplus (4+4)$$$, which simplifies to $$$4 \oplus 5 \oplus 6 \oplus 5 \oplus 6 \oplus 7 \oplus 6 \oplus 7 \oplus 8=10$$$.
—
Problem Idea: willy108
Problem Preparation: willy108
Occurrences: Novice C
Given an integer $$$a$$$, count the number of different ways to remove exactly $$$4$$$ digits of $$$a$$$ such that the resulting integer is less than $$$b$$$.
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.
Each test case contains two integers $$$a$$$ and $$$b$$$ ($$$10^4 \le a \lt 10^{10000}, 1 \le b \lt 10^{10000}$$$). It is guaranteed that the number of digits in $$$a$$$ is exactly $$$4$$$ more than the number of digits in $$$b$$$.
—
There are $$$10$$$ tests, not including samples. Each test is worth $$$\frac{100}{10}=10$$$ points.
Output a single integer — the number of ways to make $$$a$$$ less than $$$b$$$ after removing $$$4$$$ digits.
3634272196 223505082349091 19356224211 2
1 56 2
In the first test case of the sample test, the only digits you can remove are $$$6$$$, $$$3$$$, $$$4$$$, and $$$7$$$ to make $$$22196$$$.
In the second test case of the sample test, you can remove the $$$5$$$ and then remove any three digits after the first $$$0$$$ for a total of $$$56$$$ different ways.
—
Problem Idea: CPIdeas
Problem Preparation: xug
Occurrences: Novice H
Given an array $$$a$$$ of $$$n$$$ integers, find the minimum sum of the array after removing two elements of $$$a$$$ and appending their bitwise XOR to the array.
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the length of the array $$$a$$$.
The second line of each test case contains $$$n$$$ integers $$$a_1,a_2, \ldots ,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — the elements of the array $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
—
Tests in subtasks are numbered from $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1 - 5$$$ will satisfy $$$t \le 10$$$, $$$n \le 1000$$$.
The remaining tests do not satisfy any additional constraints.
For each test case, output a single integer — the minimum achievable sum.
255 1 1 3 231 4 9
8 12
In the first test case of the sample test, it is optimal to choose the elements $$$2$$$ and $$$3$$$, deleting them and appending $$$1$$$ to the array. This produces a new sum of $$$8$$$.
In the second test case of the sample test, it is optimal to choose the elements $$$1$$$ and $$$9$$$, deleting them and appending $$$8$$$ to the array. This produces a new sum of $$$12$$$.
—
Problem Idea: xug
Problem Preparation: xug
Occurrences: Novice E
The only difference between easy and hard versions is constraints.
Bashar is trapped in an abandoned city and he wants to escape. In order to escape, he has to pay $$$x$$$ golden coins. So he decided to collect the gold in the houses of that city. The city contains $$$n$$$ houses aligned in a straight line. Each house contains $$$a_i$$$ coins of gold.
Help Bashar to find the shortest distance he has to walk until he collects the needed amount of golden coins to get away.
Note Bashar can start from any house and stop at any house.
First line of input contains two integers $$$x$$$, and $$$n$$$, $$$(1 \leq n \leq 1000 , 1\leq x \leq 10^{6})$$$ The needed amount of gold until Bashar can get away, and The number of houses in the city.
The second line of input contains $$$n$$$ integers $$$a_i$$$, $$$(1 \leq a_i \leq 1000)$$$ the amount of gold in the $$$i^{th}$$$ house.
Print a single represents the minimum distance Bashar has to walk until he reach The needed amount of golden coins, if he can't reach The needed amount of golden coins print -1.
5 12 1 3 4 5 2
3
5 13 5 1 2 3 4
5
5 6 1 1 1 1 1
-1
In the first example, Bashar walked from $$$2^{nd}$$$ house to the $$$4^{th}$$$ house to collect 12 coins (3+4+5=12), so the distance is 3.
The only difference between easy and hard versions is constraints.
Bashar is trapped in an abandoned city and he wants to escape. In order to escape, he has to pay $$$x$$$ golden coins. So he decided to collect the gold in the houses of that city. The city contains $$$n$$$ houses aligned in a straight line. Each house contains $$$a_i$$$ coins of gold.
Help Bashar to find the shortest distance he has to walk until he collects the needed amount of golden coins to get away.
Note Bashar can start from any house and stop at any house.
First line of input contains two integers $$$x$$$, and $$$n$$$, $$$(1 \leq n \leq 10^{5} , 1\leq x \leq 10^{9})$$$ The needed amount of gold until Bashar can get away, and The number of houses in the city.
The second line of input contains $$$n$$$ integers $$$a_i$$$, $$$(1 \leq a_i \leq 10^{5})$$$ the amount of gold in the $$$i^{th}$$$ house.
Print a single represents the minimum distance Bashar has to walk until he reach The needed amount of golden coins, if he can't reach The needed amount of golden coins print -1.
5 12 1 3 4 5 2
3
5 13 5 1 2 3 4
5
5 6 1 1 1 1 1
-1
In the first example, Bashar walked from $$$2^{nd}$$$ house to the $$$4^{th}$$$ house to collect 12 coins (3+4+5=12), so the distance is 3.
Yash really likes monkeys and special arrays. Because he was curious, Curios George gave Yash an array $$$A$$$ of length $$$N$$$, and now Yash wonders how many good subarrays exist in this array.
Specifically, Yash deems a subarray good if $$$X$$$, his favorite number, is the maximum value in the subarray, $$$Y$$$, his second favorite number, is the minimum in the subarray, and $$$K$$$, his least favorite number, is not in the subarray. In other words, in a given subarray, $$$X$$$ should be the maximum value, $$$Y$$$ should be the minimum, and $$$K$$$ should not be in the subarray.
Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ $$$(1 \leq t \leq 5 \cdot 10^4)$$$ — the number of test cases.
The first line of each test case contains four integers $$$N$$$, $$$X$$$, $$$Y$$$, and $$$K$$$ ($$$1 \le N \le 5 \cdot 10^5, 1 \le Y \lt K \lt X \le 10^9$$$).
The second line of each test case contains $$$N$$$ integers $$$A_1,A_2,\ldots,A_N$$$ ($$$1 \le A_i \le 10^9$$$) — the elements of the array $$$A$$$.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.
—
Tests in subtasks are numbered from $$$1-20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.
Tests $$$1-5$$$ satisfy that the sum of $$$N$$$ over all test cases does not exceed $$$100$$$.
Tests $$$6-10$$$ satisfy that the sum of $$$N$$$ over all test cases does not exceed $$$1000$$$.
The remaining tests do not satisfy any additional constraints.
For each test case, output a single integer — the number of good subarrays in the array $$$A$$$.
38 7 4 56 7 4 6 5 4 6 76 5 2 43 2 4 5 1 312 8 3 610 4 3 7 4 8 6 5 1 3 8 2
5 0 3
In the first test case of the sample test, the $$$5$$$ subarrays that are good are $$$[6, 7, 4]$$$, $$$[6, 7, 4, 6]$$$, $$$[7, 4]$$$, $$$[7, 4, 6]$$$, and $$$[4, 6, 7]$$$.
In the second test case of the sample test, there are no good subarrays.
—
Problem Idea: yash_9a3b
Problem Preparation: yash_9a3b, xug
Occurrences: Novice G, Advanced B
XORnet has created the most difficult game yet, and Little Jonny wants to be the first to beat it. He is given a matrix $$$a$$$, consisting of $$$n$$$ rows by $$$m$$$ columns. Each element of the matrix is equal to $$$0$$$ or $$$1$$$, and he needs to reach the bottom right corner starting from the top left corner by only stepping down or right. However, he may only step on $$$1$$$s. Little Jonny is also a very accomplished hacker, so he managed to give himself an XORgun, which, when used, can toggle all the values in a row, changing the $$$1$$$s to $$$0$$$s and $$$0$$$s to $$$1$$$s (unfortunately, his skills did not extend to enable toggling for columns). All uses of the XORgun must be done before he takes his first step. Find the minimum number of uses of the XORgun that allow Little Jonny to beat the game.
Each test contains multiple test cases. The first line of input 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 positive integers $$$n$$$ and $$$m$$$ ($$$1 \le n \cdot m \le 10^6$$$) — the number of rows and the number of columns of the matrix $$$a$$$.
Each of the next $$$n$$$ lines contains a binary string of length $$$m$$$ — the description of matrix $$$a$$$. It is guaranteed that the value of the top left corner is $$$1$$$.
It is guaranteed that the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.
—
There are $$$20$$$ tests, not including samples. Each test is worth $$$\frac{100}{20}=5$$$ points.
For each test case, output a single integer — the minimum number of times Little Jonny can use the XORgun for him to beat the game. If it is impossible for him to beat the game, output $$$-1$$$.
33 41110010010104 31101011100002 51001011011
2 1 -1
In the first test case of the sample test, it is optimal to use the XORgun on rows $$$2$$$ and $$$3$$$.
In the second test case of the sample test, it is optimal to use the XORgun on row $$$4$$$.
—
Problem Idea: Red0
Problem Preparation: xug
Occurrences: Novice F
On an $$$8 \times 8$$$ grid of dots, a word consisting of lowercase Latin letters is written vertically in one column, from top to bottom. What is it?
The input consists of multiple test cases. The first line of the input contains a single integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.
Each test case consists of $$$8$$$ lines, each containing $$$8$$$ characters. Each character in the grid is either $$$\texttt{.}$$$ (representing a dot) or a lowercase Latin letter ($$$\texttt{a}$$$–$$$\texttt{z}$$$).
The word lies entirely in a single column and is continuous from the beginning to the ending (without gaps). See the sample input for better understanding.
For each test case, output a single line containing the word made up of lowercase Latin letters ($$$\texttt{a}$$$–$$$\texttt{z}$$$) that is written vertically in one column from top to bottom.
5...................................i.....................................l.......o.......s.......t....................................................................t.......h.......e................................................g.......a.......m.......ea.......a.......a.......a.......a.......a.......a.......a.......
i lost the game aaaaaaaa
I BET IT DOES!
Ifrit is an operator in Arknights who specializes in mapwide war crimes. You are tasked to increase the efficiency with which said war crimes are committed.
A map in Arknights can be represented as an $$$n$$$ by $$$m$$$ grid with three types of tiles:
- Placeable high-ground tiles (you can place Ifrit here). These tiles are denoted with a H.
- Low ground tiles (enemies walk here). These tiles are denoted with a L.
- Unplaceable high-ground tiles (you cannot place Ifrit here). These tiles are denoted with a #.
Let the upper-left tile be $$$(1, 1)$$$ and the bottom-right tile be $$$(n, m)$$$. We say a tile $$$(x, y)$$$ is an Ifrit Tile if the following conditions hold:
- It is a placeable high-ground tile. We want to place down Ifrit.
- We can pick a direction (up, left, down, right) such that out of the $$$5$$$ tiles immediately in that direction excluding the tile Ifrit is placed on, at least two of them are low-ground tiles. We want Ifrit to hit some enemies.
For a given map, count all Ifrit Tiles.
The first line of input contains two integers $$$n$$$ and $$$m$$$ denoting the length and width of the map $$$(1 \leq n, m \leq 1000)$$$.
The following $$$n$$$ lines each contain a string of length $$$m$$$, the $$$j$$$'th character on the $$$i$$$'th row being either an H, L, or #, denoting that tile $$$(i, j)$$$ is a tile of that type as defined in the statement.
—
Tests in subtasks are numbered from $$$1 - 10$$$ with samples skipped. Each test is worth $$$\frac{100}{10} = 10$$$ points.
Tests $$$1 - 3$$$ satisfy that $$$n, m \leq 10$$$.
The remaining tests do not satisfy any additional constraints.
Output a single integer, denoting the number of Ifrit Tiles on the map.
5 7##HLHH##HHLHH#LLLLLLL##HHLHH##HHLH#
4
The Ifrit Tiles are $$$(1, 5)$$$, $$$(2, 5)$$$, $$$(4, 4)$$$, and $$$(5, 4)$$$. Ifrit should be placed facing down, down, up, and up respectively on these tiles to hit at least two low-ground tiles.
This map is also the stage $$$1-1$$$ in Arknights.
—
Problem Idea: willy108
Problem Preparation: willy108
Occurrences: Novice B
Count all pairs of integers $$$(n, p)$$$ such that $$$0 \le p \le P$$$, $$$p \neq n \cdot p$$$, and $$$p!=n \cdot p$$$.
The input consists of a single integer $$$P$$$ ($$$1 \le P \le 10^5$$$) — the upper bound on $$$p$$$.
—
Tests in subtasks are numbered from $$$1 - 10$$$ with samples skipped. Each test is worth $$$\frac{100}{10}=10$$$ points.
Tests $$$1 - 5$$$ will satisfy $$$P \le 1000$$$.
The remaining tests do not satisfy any additional constraints.
Output a single integer — the number of integer values for $$$n$$$ and $$$p$$$ that satisfy the constraints.
4
2
In the sample test, the $$$2$$$ values of $$$(n,p)$$$ that work are $$$(2,3)$$$ and $$$(6,4)$$$.
—
Problem Idea: willy108
Problem Preparation: xug
Occurrences: Novice A, Advanced A
Mahmoud bought a rectangular shaped land, it's area was $$$n$$$ $$$units^2$$$.
His best friend Ayoub asked him to calculate the height and the width of the land.
Mahmoud hates math, can you help him to calculate the height and the width of the land?
If there are multiple solutions print any of them.
The input contains single integer $$$n$$$ , $$$(1 \leq n \leq 200)$$$ represent the area
Print two integers that represent the height and the width of the rectangle, if there are multiple solutions print any of them.
20
4 5
16
4 4
6
2 3
area = height*width