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$$$.
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
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
You are given a positive integer $$$n.$$$
There is an integer array $$$a$$$ of length $$$n.$$$
We define another array $$$b$$$ of length $$$n$$$ with the following restriction:
For $$$1 \le i \le n,$$$ we have that $$$a_i = \sum_{j=1}^{\lfloor n/i\rfloor} b_{(i\times j)}.$$$
You must support $$$q$$$ queries. The queries can have two types.
1. Update the value of an element of $$$a.$$$
2. Output the value of an element of $$$b.$$$
The first line contains two integers $$$n$$$ and $$$q$$$ $$$(1\le n,q\le 2 \cdot 10^5).$$$
The second line contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ $$$(-10^9\le a_i\le10^9)$$$ — the initial values of $$$a.$$$
Each of the next $$$q$$$ lines contains the queries:
$$$1$$$ $$$i$$$ $$$x$$$ $$$(1\le i\le n,-10^9\le x\le 10^9)$$$ — update the value of $$$a_i$$$ to $$$x.$$$
$$$2$$$ $$$i$$$ $$$(1\le i\le n)$$$ — output the value of $$$b_i.$$$
For each query of the second type, output one integer $$$b_i$$$ on a line.
5 52 4 3 3 22 21 4 62 42 22 1
1 6 -2 -7
2 30 01 2 12 12 2
-1 1
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
Eric is building his own Cereal City, and he needs your help planning it out!
Cereal City can be presented by a unit grid with $$$n+2$$$ vertical lines (numbered $$$0$$$ to $$$n+1$$$ from left to right), and $$$n+2$$$ horizontal lines (numbered $$$0$$$ to $$$n+1$$$ from top to bottom). Let $$$(x, y)$$$ represent the intersection between the $$$x$$$-th horizontal line and $$$y$$$-th vertical line.
There are $$$m$$$ buildings in this city, with the $$$i$$$-th building is located at ($$$x_i, y_i$$$) such that $$$1 \leq x_i, y_i \leq n$$$.
Example of a Cereal City where $$$n=2, m=2,$$$ and there is a building at $$$(1, 2)$$$ and $$$(2, 1)$$$. You want to build some roads along the grid lines such that you can reach any city from any other city via some series of roads. However, Eric wants you to build the roads in a peculiar method:
You want to start at one of the 4 borders of the grid, and build inwards perpendicular to the border along a grid line until you reach an intersecting road or the opposite border. You may not build past this point. The amount of road you use is equivalent to the number of intersections that lies on the road minus $$$1$$$. Furthermore, no roads are to be built along the border of the grid (the $$$0$$$-th or $$$n+1$$$-th horizontal or vertical line).
Note that the order that you build the roads matters.
Some examples of valid / invalid road formations. You have all the time you need to build the roads, but the deadline for ordering supplies is coming fast! Please tell Eric the minimum amount of road you need to connect all cities, so that he can order the supplies!
The first line contains two space separated integers: $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 2 \cdot 10^3$$$) ($$$2 \leq m \leq 2 \cdot 10^5$$$
The $$$i$$$-th of the next $$$m$$$ lines contains two space separated integers representing the location of the $$$i$$$-th building: $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i, y_i \leq n$$$)
Print one integer: the minimum amount of road you need to connect all buildings given Eric's road building method.
4 4 1 3 1 4 2 3 4 3
7
6 73 36 26 61 52 34 13 5
21
Construction for Sample 1
Myth is hungry. Luckily, he just found a cereal tree!
The cereal tree can be represented by a tree rooted at node $$$1$$$ with $$$n$$$ nodes numbered $$$1 \dots n$$$ and $$$n-1$$$ edges. Each node has some cereal with with a deliciousness of $$$v_i$$$, which could be positive or negative.
Myth wants to eat some connected component of the tree. The enjoyment derived from eating a connected component of the tree is the sum of $$$v_i$$$ for all nodes $$$i$$$ in the connected component.
There are $$$q$$$ queries made to the tree in the form of $$$x$$$ $$$c$$$:
Some sugar is sprinkled on node $$$x$$$, which increases the deliciousness $$$v_x$$$ by $$$c$$$. Mythreya then wants to know the maximum enjoyment he can derive from eating a component, such that the highest node in the component (the node closest to the root) is $$$x$$$.
The first line contains two space separated integers: $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 5 \cdot 10^5$$$)
The next line contains $$$n$$$ space separated integers, with the $$$i$$$-th integer representing $$$v_i$$$ ($$$-10^9 \leq v_i \leq 10^9$$$)
The next line contains $$$n-1$$$ space separated integers $$$p_2 \dots p_n$$$, indicating that the parent of node $$$i$$$ is $$$p_i$$$ ($$$1 \leq p_i \leq i-1$$$).
The next $$$q$$$ lines contain two integers: $$$x$$$ and $$$c$$$, indicating a query. ($$$1 \leq x \leq n, 0 \leq c \leq 10^9$$$)
For each query $$$x$$$ $$$c$$$, output the maximum enjoyment of any component, given that the component's closest node to the root is $$$x$$$.
3 3-1 -1 -11 22 21 03 0
1 0 -1
Note: $$$O(n \log^2 (n))$$$ solutions are not intended to pass given constraints.
Ntarsis the red panda is attempting an obstacle course. In this obstacle course, there are $$$n+1$$$ layers numbered $$$0$$$ to $$$n$$$, with layer $$$0$$$ being the top layer and layer $$$n$$$ being the floor.
Each layer may have a vine of length $$$l$$$. If Ntarsis is on layer $$$i$$$ and it has a vine of length $$$l$$$, Ntarsis can then climb the vine and move to layer $$$i+l$$$. If $$$i+l \gt n$$$, Ntarsis ends up on layer $$$n$$$.
Initially there are no vines. You are answer queries of 3 types:
- A vine grows on layer $$$i$$$ with length $$$1$$$. If there is already a vine on layer $$$i$$$, this vine replaces it.
- Each vine on layer $$$i$$$ such that $$$i$$$ mod $$$c$$$ = $$$k$$$ grows $$$1$$$ unit. If a vine used to be length $$$l$$$, it is now length $$$l+1$$$. If a layer has no vines, nothing happens.
- Ntarsis attempts the obstacle course. He starts on layer $$$i$$$, and keeps climbing down until he reaches a layer without a vine. Print the layer Ntarsis ends up at.
The first line contains two space separated integers: $$$n$$$, $$$q$$$, and $$$c$$$ ($$$1 \leq c \leq n \leq 10^5$$$) ($$$1 \leq q \leq 10^5)$$$
The next $$$q$$$ lines indicate the queries. They are in the following format:
- $$$1$$$ $$$i$$$ ($$$0 \leq i \leq n-1$$$): A vine grows on layer $$$i$$$ with length $$$1$$$. If there is already a vine on layer $$$i$$$, this vine replaces it.
- $$$2$$$ $$$k$$$ ($$$0 \leq k \leq c-1$$$): Each vine on layer $$$i$$$ such that $$$i$$$ mod $$$c$$$ = $$$k$$$ grows $$$1$$$ unit.
- $$$3$$$ $$$i$$$ ($$$0 \leq i \leq n-1$$$): Ntarsis starts on layer $$$i$$$, and keeps climbing down until he reaches a layer without a vine. Print the layer Ntarsis ends up at.
For each query of type $$$3$$$, print the layer that Ntarsis ends up at.
4 6 21 01 13 02 13 03 2
2 3 2
Note: Since modulo operation is slow, it may have to be precomputed in order to pass under given constraints.
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 minimize the grid's Super Rank .
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 minimizes the Super Rank.
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.
5 8
10001 00010 00010 01100 10001
3 5
111 100 100
In test case 1, the super rank is 3; the distinct rows and columns are: "$$$10001$$$", "$$$00010$$$", and "$$$01100$$$". It can be proven that this is the minimum super rank.