Note the unusual constraint for n
A number is considered rotationally symmetric if it stays the same when you rotate it $$$180$$$ degrees. In the rotation, digits $$$0, 1, 2, 5,$$$ and $$$8$$$ map onto themselves while $$$6$$$ and $$$9$$$ map onto each other.
In other words, a number is rotationally symmetric if it only contains the digits $$$[0, 1,2,5,6,8,9]$$$, and stays the same when you reverse it and replace its $$$6$$$'s with $$$9$$$'s and $$$9$$$'s with $$$6$$$'s.
For example, the number $$$2112$$$ is rotationally symmetric as shown:
$$$5115$$$, $$$2650592$$$, and $$$88$$$ are all rotationally symmetric, while $$$25$$$, $$$66$$$, and $$$33$$$ are not.
Given a number $$$n$$$ ($$$2 \leq n \leq 6$$$), output an $$$n$$$-digit rotationally symmetric number that is divisible by $$$3$$$.
The first line contains one integer: $$$n$$$ ($$$2 \leq n \leq 6$$$)
Output an $$$n$$$ digit rotationally symmetric number that is divisible by 3. Note that leading zeros don't count as digits, so $$$00$$$ would NOT be a valid answer if $$$n=2$$$.
3
111
Hint: A number is divisible by $$$3$$$ if the sum of its digits is divisible by $$$3$$$.
An array $$$a_1 \dots a_n$$$ is simple if you can negate certain elements to make the array sum to zero. For example, the array $$$[1, 1, 2]$$$ is simple, since you can negate the third element making the array $$$[1, 1, -2]$$$, which sums to zero.
Given an array such that each element is an integer $$$0$$$, $$$1$$$, or $$$2$$$, determine if this array is simple.
The first line contains a single integer $$$n$$$, representing the number of elements in the array. ($$$1 \leq n \leq 10^5$$$)
The next line contains $$$n$$$ space-separated integers describing $$$a_1 \dots a_n$$$. ($$$0 \leq a_i \leq 2$$$)
Print YES if the array is simple. Otherwise, print NO.
Note that capitalization doesn't matter; If the answer was YES and you printed Yes, your code would still be accepted.
3 1 1 2
YES
4 0 2 2 2
NO
In sample case 1, you can negate the third element making the array $$$[1, 1, -2]$$$, which sums to zero.
In sample case 2, it can be proven that no matter which elements you negate, the array does not sum to zero.
Given an $$$n \times m$$$ grid of $$$0$$$s and $$$1$$$s, flip the minimum number of bits such that no $$$0$$$ is vertically or horizontally adjacent to another $$$0$$$, and no $$$1$$$ is vertically or horizontally adjacent to another $$$1$$$.
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 a two integers $$$n$$$ and $$$m$$$ $$$(1 \le n \le 1000, 1 \le m \le 1000)$$$ $$$-$$$ the number of rows and columns of the grid.
Each of the following $$$n$$$ lines contains $$$m$$$ characters describing the cells of the grid. Each character is either $$$0$$$ or $$$1$$$.
It is guaranteed the sum of $$$n \cdot m$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, print a single integer $$$-$$$ the number of bit flips such that no $$$0$$$ is next to another $$$0$$$ and no $$$1$$$ is next to another $$$1$$$.
23 40001101001012 101
1 0
Allen is tired of playing with alphabet cereal, so he found some binary cereal to play with instead! Allen has $$$n^2$$$ pieces of cereal, each with number $$$0$$$ or $$$1$$$.
This time, Allen is trying to place cereal in an $$$n$$$ x $$$n$$$ grid of cells in order to construct a grid with a Super Rank of 5 or less.
The Super Rank is defined as the number of distinct rows and columns (if the rows were read from left to right, and columns were read from top to bottom).
For example, the binary grid:
| $$$1$$$ | $$$1$$$ | $$$1$$$ |
| $$$1$$$ | $$$0$$$ | $$$0$$$ |
| $$$1$$$ | $$$0$$$ | $$$0$$$ |
Has a super rank of $$$2$$$, since the rows and columns are all $$$111$$$ or $$$100$$$.
Given that Allen has $$$k$$$ pieces of $$$1$$$ cereal and $$$n^2 - k$$$ pieces of $$$0$$$ cereal, output any grid that has a Super Rank of 5 or less.
The first line contains two space seperated integers: $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 1000$$$, $$$0 \leq k \leq n^2$$$)
Output $$$N$$$ lines, with the $$$i$$$th line being a binary string representing the $$$i$$$th row on the grid.
4 12
1111 0000 1111 1111
This grid has a super rank of 3, which is less than 5: "1111", "1011", "0000".
There are $$$n$$$ red pandas sitting around a table, numbered from $$$1$$$ to $$$n$$$ in a clockwise order. There are $$$k$$$ initial partnerships, each of which connects two red pandas. Partnerships can be represented in a straight line between two red pandas.
In the end, the red pandas want a total of $$$\frac{n}{2}$$$ partnerships such that each red panda is in exactly $$$1$$$ partnership, such that no two lines representing partnerships intersect (otherwise, they would have to talk over each other)!
Of course, with their initial partnerships, it may not always be possible to form a valid final configuration of partnerships. Please find the minimum initial partnerships that the red pandas have to break in order to reach their goal.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$n$$$ even, $$$2 \leq n \leq 10^5$$$, $$$0 \leq 2k \leq n$$$).
The next $$$k$$$ lines of every test case includes two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$), indicating an initial partnership. It is guaranteed that no red panda will be included in more than one initial partnership, and no two initial partnerships intersect.
It is guaranteed that the sum of all $$$n$$$ does not exceed $$$2 \cdot 10^5$$$.
For each test case, output one number: the minimum initial partnerships that must be broken.
34 11 320 06 31 23 45 6
1 0 0
In the first test case, we must remove the existing partnership, otherwise the other two red pandas cannot have partners.
In the second test case, there are no initial partnerships to remove, so our answer is $$$0$$$.
In the third test case, our existing partnerships already give every red panda a valid partner, so our answer is also $$$0$$$.
You are given an permutation $$$a$$$ of length $$$n$$$ which will consist of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$.
How many pairs $$$(i, j)$$$ are there such that $$$a_i + a_j = a_{i + a_j}$$$?
The first line contains one integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$).
The second line contains $$$n$$$ space separated integers $$$a_1, a_2 \dots a_n$$$ ($$$1 \leq a_i \leq n$$$). It is guaranteed these numbers are all distinct and thus form a permutation of length $$$n$$$.
Output a single integer, which is the number of pairs that satisfy the conditions stated. Note that the answer might not fit into $$$32$$$ bits.
5 3 4 1 2 5
2
For the first testcase, the first pair that works is $$$(i, j) = (1, 3)$$$ since $$$a_1 + a_3 = a_{1 + 1} = 4$$$. The second pair is $$$(i, j) = (3, 3)$$$ since $$$a_3 + a_3 = a_{3 + 1} = 2$$$.
Two red pandas, Oscar and Lura, enjoy pancakes. In fact, they enjoy pancakes so much that they live in a giant circular pancake town called Pandacake. In Pandacake, there are $$$n$$$ pancake stores around the perimeter of the town, labeled $$$1$$$ through $$$n$$$ in clockwise order. The $$$i$$$th store has $$$p_i$$$ pancakes in stock.
Oscar and Lura each want as many pancakes as they can get. They collect pancakes as follows. At the beginning, Lura chooses a store first, and then Oscar chooses a different store.
Afterwards, they move as follows:
- Lura chooses a store that neither red panda has gone to, and she can walk to without crossing any of Oscar's stores. Then, she visits all the stores along the way.
- Oscar chooses a store that neither red panda has gone to, and he can walk to without crossing any of Lura's stores. Then, he visits all the stores along the way.
In each store that a red panda visits, he or she will buy all of the pancakes in stock. Please help Lura maximize the number of pancakes she gets.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$).
The second and final line of every test case includes $$$n$$$ integers $$$p_1, \: p_2, \: p_3, \ldots \: p_n$$$, the number of pancakes in stock at the $$$i$$$th store.
It is guaranteed that the sum of all $$$n$$$ does not exceed $$$2 \cdot 10^5$$$.
For each test case, output one number: the maximum pancakes that Lura can get.
4250 49350 49 50450 49 50 4991000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
50 99 99 5000000000
Over the past $$$n$$$ days, gg_gong have been observing the number of problems his friend has done.
He reached a conclusion that the maximum number of problems his friend did on one of the past $$$n$$$ days is $$$m$$$.
He gives you a sequence $$$a$$$ of $$$n$$$ numbers that denotes the number of problems his friend did each day. But, his friend has been lying to him. So on days where he is not sure how many problems his friend did, gg_gong replaces the corresponding positions in the sequence with $$$-1$$$.
After more detailed observation, he reached $$$k$$$ conclusions, each one given in the form of $$$u$$$ and $$$val$$$, representing the number of problems his friend did on day $$$u$$$ is not $$$val$$$.
He also reached $$$q$$$ more advanced conclusions. Each one gives two values $$$l$$$ and $$$r$$$, meaning that his friend did the same number problems on day $$$l$$$ and $$$r$$$, $$$l+1$$$ and $$$r-1$$$, and so on. In general, his friend did the same number of problems on days $$$l+k$$$ and $$$r-k$$$ where $$$l+k \lt r-k$$$.
How many total possible sequences satisfies all the information he has given you?
The first line contains $$$4$$$ integers: $$$n,m,k,$$$ and $$$q$$$ $$$(1 \leq n \leq 3000,0 \leq m,q \leq 3000,0 \leq k \leq 2000000)$$$.
The second line contains $$$n$$$ integers representing $$$a$$$ $$$(-1 \leq a_i \leq m)$$$.
The next $$$k$$$ lines contains an $$$u$$$ and a $$$val$$$ $$$(1 \leq u \leq n,0 \leq val \leq m)$$$.
The next $$$l$$$ lines line each contain a $$$l$$$ and a $$$r$$$ $$$(1 \leq l \leq r \leq n)$$$, denoting the sequence from $$$l$$$ to $$$r$$$ is palindromic.
Output one line containing the number of possible sequences. Since the answer can be large, output it modulo $$$1000000007$$$.
10 10 5 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10 4 6 4 7 4 8 4 9 4 10 1 10
7986
10 10 11 1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4 0 4 1 4 2 4 3 4 4 4 5 4 6 4 7 4 8 4 9 4 10 1 10
0
You are given two strings $$$s$$$ and $$$t$$$ of lowercase English letters each of length $$$n.$$$
For every lowercase English letter, let its value be the number of letters between it and a in the ordered alphabet (e.g. the value of a is 0, value of z is 25).
We call the reverse of a letter with value $$$val$$$ to be the letter with value $$$25-val$$$ (e.g. the reverse of a is z, the reverse of c is z).
We call the opposite of a letter with value $$$val$$$ to be the letter with value equivalent to $$$val+13\pmod{26}$$$ (e.g. the opposite of a is n, the opposite of m is b).
In one move, you choose a contiguous range of letters in $$$s$$$ and replace each letter in the range with its reverse, or replace each letter in the range with its opposite.
Determine the minimum number of moves it will take to transform $$$s$$$ into $$$t,$$$ or output $$$-1$$$ if it is not possible.
The first line contains an integer $$$n$$$ $$$(1\le n\le 10^6)$$$ — the length of the two strings.
The second line contains a string $$$s$$$ of length $$$n,$$$ consisting of lowercase English letters.
The third line contains a string $$$t$$$ of length $$$n,$$$ consisting of lowercase English letters.
Output a single integer, representing the minimum number of moves to transform $$$s$$$ into $$$t,$$$ or $$$-1$$$ if it is not possible.
5abcdeabcde
0
5aaaaaznmnm
4
1ab
-1
5ngomcmtyzk
3
7ptacnldcgacmlj
4
7ugrcnkmsgvcapz
5
Red pandas have a special type of pantry: the pantree. Pantrees store food in a tree.
Two hungry red pandas, Oscar and Lura, have a pantree $$$T$$$ with $$$n$$$ nodes. They want to tidy up the pantree, so they are willing to perform the following shuffle procedure any number of times on the whole tree $$$T$$$. With each shuffle procedure, they will create a new rooted tree out of the nodes of the old tree.
- Choose any node $$$V$$$ from the original tree $$$T$$$. Create a new tree $$$T_2$$$, with $$$V$$$ as the root.
- Remove $$$V$$$ from $$$T$$$, such that the original tree is split into one or more subtrees (or zero subtrees, if $$$V$$$ is the only node in $$$T$$$).
- Shuffle each subtree with the same procedure (again choosing any node as the root), then connect all shuffled subtrees' roots back to $$$V$$$ to finish constructing $$$T_2$$$.
After this, Oscar and Lura are left with a final pantree. They want this pantree to be a line tree with a specific ordering of nodes, such that the first element of the ordering is the root of the tree. They are very hungry, so please find the minimum number of shuffle procedures to order the pantree. Please help them!
A line tree is a tree where each vertex has a degree of at most 2. A line tree is said to satisfy some ordering if and only if a depth first search from the root of the tree visits nodes in the specified ordering.
Note that you ALWAYS need at least one operation, since the original tree is not rooted.
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.
The first line of every test case contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — the number of nodes within the original tree $$$T$$$.
The next $$$n - 1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \leq u, v \leq n$$$) — an edge within the original tree $$$T$$$. The given edges form a tree.
The last line of every test case will contain $$$n$$$ integers — a permutation $$$p$$$, the desired final ordering of the pantree. $$$p_1$$$ should be the root of the pantree, while $$$p_n$$$ should be the tree's only leaf.
The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For every test case, first output an integer $$$k$$$ — the minimum number of shuffle procedures needed.
On each of the next $$$k$$$ lines, print the shuffle procedure by outputting the order of nodes chosen.
2 5 5 4 1 2 3 4 3 2 1 2 3 4 5 3 1 2 1 3 1 2 3
1 1 2 3 4 5 2 2 3 1 1 2 3