Filip has a row of cells, some of which are blocked, and some are empty. He wants all empty cells to have water in them. He has two actions at his disposal:
- $$$1$$$ — place water in an empty cell.
- $$$2$$$ — remove water from a cell and place it in any other empty cell.
If at some moment cell $$$i$$$ ($$$2 \le i \le n-1$$$) is empty and both cells $$$i-1$$$ and $$$i+1$$$ contains water, then it becomes filled with water.
Find the minimum number of times he needs to perform action $$$1$$$ in order to fill all empty cells with water.
Note that you don't need to minimize the use of action $$$2$$$. Note that blocked cells neither contain water nor can Filip place water in them.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 100$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 100$$$) — the number of cells.
The next line contains a string $$$s$$$ of length $$$n$$$. The $$$i$$$-th character of $$$s$$$ is '.' if the cell $$$i$$$ is empty and '#' if cell $$$i$$$ is blocked.
For each test case, output a single number — the minimal amount of actions $$$1$$$ needed to fill all empty cells with water.
53...7##....#7..#.#..4####10#...#..#.#
2 2 5 0 2
Test Case 1
In the first test case, Filip can put water in cells $$$1$$$ and $$$3$$$. As cell $$$2$$$ is between $$$2$$$ cells with water, it gets filled with water too.
Test Case 2
In the second case, he can put water sources in cells $$$3$$$ and $$$5$$$. That results in cell $$$4$$$ getting filled with water. Then he will remove water from cell $$$5$$$ and place it into cell $$$6$$$. As cell $$$5$$$'s neighbors, cell $$$4$$$ and cell $$$6$$$, have water in them, cell $$$5$$$ also gets filled with water. You can see the illustration of this case below.
Operations in the second test case. White cells are empty, grey ones are blocked, and blue ones are water. Test Case 3
In the third case, he can put water in all the empty cells. That requires $$$5$$$ actions of type $$$1$$$.
Test Case 4
In the fourth case, there are no empty cells. Therefore, he does not have to put any water in them.
Test Case 5
In the fifth test case, there exists a sequence of actions that requires only $$$2$$$ type $$$1$$$ actions.
Laura is a girl who does not like combinatorics. Nemanja will try to convince her otherwise.
Nemanja wrote some digits on the board. All of them are either $$$1$$$, $$$2$$$, or $$$3$$$. The number of digits $$$1$$$ is $$$a$$$. The number of digits $$$2$$$ is $$$b$$$ and the number of digits $$$3$$$ is $$$c$$$. He told Laura that in one operation she can do the following:
- Select two different digits and erase them from the board. After that, write the digit ($$$1$$$, $$$2$$$, or $$$3$$$) different from both erased digits.
For example, let the digits be $$$1$$$, $$$1$$$, $$$1$$$, $$$2$$$, $$$3$$$, $$$3$$$. She can choose digits $$$1$$$ and $$$3$$$ and erase them. Then the board will look like this $$$1$$$, $$$1$$$, $$$2$$$, $$$3$$$. After that, she has to write another digit $$$2$$$, so at the end of the operation, the board will look like $$$1$$$, $$$1$$$, $$$2$$$, $$$3$$$, $$$2$$$.
Nemanja asked her whether it was possible for only digits of one type to remain written on the board after some operations. If so, which digits can they be?
Laura was unable to solve this problem and asked you for help. As an award for helping her, she will convince Nemanja to give you some points.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^5$$$). The description of the test cases follows.
The first and only line of each test case contains three integers $$$a$$$, $$$b$$$, $$$c$$$ ($$$1 \le a, b, c \le 100$$$) — the number of ones, number of twos, and number of threes, respectively.
For each test case, output one line containing $$$3$$$ integers.
The first one should be $$$1$$$ if it is possible that after some operations only digits $$$1$$$ remain on the board, and $$$0$$$ otherwise.
Similarly, the second one should be $$$1$$$ if it is possible that after some operations only digits $$$2$$$ remain on the board, and $$$0$$$ otherwise.
Similarly, the third one should be $$$1$$$ if it is possible that after some operations only digits $$$3$$$ remain on the board, and $$$0$$$ otherwise.
31 1 12 3 282 47 59
1 1 1 0 1 0 1 0 0
In the first test case, Laura can remove digits $$$2$$$ and $$$3$$$ and write digit $$$1$$$. After that, the board will have $$$2$$$ digits $$$1$$$. She can make it have only digits $$$2$$$ or $$$3$$$ left by performing a similar operation.
In the second test case, she can remove digits $$$1$$$ and $$$3$$$ and write a digit $$$2$$$. After performing that operation $$$2$$$ times, the board will have only digits $$$2$$$ left. It can be proven that there is no way to have only digits $$$1$$$ or only digits $$$3$$$ left.
In the third test case, there is a sequence of operations that leaves only digits $$$1$$$ on the board. It can be proven that there is no way to have only digits $$$2$$$ or only digits $$$3$$$ left.
Keksic keeps getting left on seen by Anji. Through a mutual friend, he's figured out that Anji really likes binary trees and decided to solve her problem in order to get her attention.
Anji has given Keksic a binary tree with $$$n$$$ vertices. Vertex $$$1$$$ is the root and does not have a parent. All other vertices have exactly one parent. Each vertex can have up to $$$2$$$ children, a left child, and a right child. For each vertex, Anji tells Keksic index of both its left and its right child or tells him that they do not exist.
Additionally, each of the vertices has a letter $$$s_i$$$ on it, which is either 'U', 'L' or 'R'.
Keksic begins his journey on the root, and in each move he does the following:
- If the letter on his current vertex is 'U', he moves to its parent. If it doesn't exist, he does nothing.
- If the letter on his current vertex is 'L', he moves to its left child. If it doesn't exist, he does nothing.
- If the letter on his current vertex is 'R', he moves to its right child. If it doesn't exist, he does nothing.
You are interested in the minimal number of operations he needs to do before his journey, such that when he starts his journey, he will reach a leaf at some point. A leaf is a vertex that has no children. It does not matter which leaf he reaches. Note that it does not matter whether he will stay in the leaf, he just needs to move to it. Additionally, note that it does not matter how many times he needs to move before reaching a leaf.
Help Keksic solve Anji's tree so that he can win her heart, and make her come to Čačak.
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 5 \cdot 10^4$$$) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — the number of vertices in a tree.
The second line of each test case contains a string $$$s$$$ of $$$n$$$ characters — characters are written on the vertices. It is guaranteed that $$$s$$$ consists only of characters 'U', 'L', and 'R'.
The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$0 \le l_i, r_i \le n$$$) — indices of left and right child of the vertex $$$i$$$. If $$$l_i = 0$$$, it means that vertex $$$i$$$ does not have a left child. If $$$r_i = 0$$$, it means that vertex $$$i$$$ does not have a right child. It is guaranteed that this data describes a valid binary tree rooted at $$$1$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.
For each test case, output a single integer — the minimal number of operations Keksic needs to do to reach a leaf.
53LRU2 30 00 03ULR3 20 00 02LU0 20 04RULR3 00 00 42 07LLRRRLU5 23 60 07 04 00 00 0
0 1 1 3 1
In the first test case, vertex $$$1$$$ has $$$2$$$ as its left child and $$$3$$$ as its right child. Vertices $$$2$$$ and $$$3$$$ do not have children and are therefore leaves. As 'L' is written on vertex $$$1$$$, Keksic will go to vertex $$$2$$$, therefore he has to do no operations.
In the second test case, vertex $$$1$$$ has $$$3$$$ as its left child and $$$2$$$ as its right child. Vertices $$$2$$$ and $$$3$$$ are leaves. As 'U' is written on vertex $$$1$$$, Keksic needs to change it to either 'L' or 'R' in order for him to reach a leaf.
In the third case, vertex $$$1$$$ has only a right child, which is vertex $$$2$$$. As 'L' is written on it, Keksic needs to change it to 'R', otherwise he would be stuck on vertex $$$1$$$.
In the fourth case, he can change $$$3$$$ characters so that letters on the vertices are "LURL", which makes him reach vertex $$$2$$$.
In the fifth case, there are $$$3$$$ leaves, $$$3$$$, $$$6$$$ and $$$7$$$. To reach either leaf $$$6$$$ or leaf $$$7$$$, he needs to change $$$2$$$ characters. However, if he changes character on vertex $$$1$$$ to 'R', he will reach leaf $$$3$$$, therefore the answer is $$$1$$$.
The initial tree in test case 5.
Let $$$a$$$, $$$b$$$, and $$$c$$$ be integers. We define function $$$f(a, b, c)$$$ as follows:
Order the numbers $$$a$$$, $$$b$$$, $$$c$$$ in such a way that $$$a \le b \le c$$$. Then return $$$\gcd(a, b)$$$, where $$$\gcd(a, b)$$$ denotes the greatest common divisor (GCD) of integers $$$a$$$ and $$$b$$$.
So basically, we take the $$$\gcd$$$ of the $$$2$$$ smaller values and ignore the biggest one.
You are given an array $$$a$$$ of $$$n$$$ elements. Compute the sum of $$$f(a_i, a_j, a_k)$$$ for each $$$i$$$, $$$j$$$, $$$k$$$, such that $$$1 \le i \lt j \lt k \le n$$$.
More formally, compute $$$$$$\sum_{i = 1}^n \sum_{j = i+1}^n \sum_{k =j +1}^n f(a_i, a_j, a_k).$$$$$$
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10$$$). The description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$3 \le n \le 8 \cdot 10^4$$$) — 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^5$$$) — elements of the array $$$a$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$8 \cdot 10^4$$$.
For each test case, output a single number — the sum from the problem statement.
252 3 6 12 1786 12 8 10 15 12 18 16
24 203
In the first test case, the values of $$$f$$$ are as follows:
- $$$i=1$$$, $$$j=2$$$, $$$k=3$$$, $$$f(a_i,a_j,a_k)=f(2,3,6)=\gcd(2,3)=1$$$;
- $$$i=1$$$, $$$j=2$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(2,3,12)=\gcd(2,3)=1$$$;
- $$$i=1$$$, $$$j=2$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,3,17)=\gcd(2,3)=1$$$;
- $$$i=1$$$, $$$j=3$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(2,6,12)=\gcd(2,6)=2$$$;
- $$$i=1$$$, $$$j=3$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,6,17)=\gcd(2,6)=2$$$;
- $$$i=1$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(2,12,17)=\gcd(2,12)=2$$$;
- $$$i=2$$$, $$$j=3$$$, $$$k=4$$$, $$$f(a_i,a_j,a_k)=f(3,6,12)=\gcd(3,6)=3$$$;
- $$$i=2$$$, $$$j=3$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(3,6,17)=\gcd(3,6)=3$$$;
- $$$i=2$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(3,12,17)=\gcd(3,12)=3$$$;
- $$$i=3$$$, $$$j=4$$$, $$$k=5$$$, $$$f(a_i,a_j,a_k)=f(6,12,17)=\gcd(6,12)=6$$$.
In the second test case, there are $$$56$$$ ways to choose values of $$$i$$$, $$$j$$$, $$$k$$$. The sum over all $$$f(a_i,a_j,a_k)$$$ is $$$203$$$.
You are given a directed graph $$$G$$$ with $$$n$$$ vertices and $$$m$$$ edges between them.
Initially, graph $$$H$$$ is the same as graph $$$G$$$. Then you decided to perform the following actions:
- If there exists a triple of vertices $$$a$$$, $$$b$$$, $$$c$$$ of $$$H$$$, such that there is an edge from $$$a$$$ to $$$b$$$ and an edge from $$$b$$$ to $$$c$$$, but there is no edge from $$$a$$$ to $$$c$$$, add an edge from $$$a$$$ to $$$c$$$.
- Repeat the previous step as long as there are such triples.
Note that the number of edges in $$$H$$$ can be up to $$$n^2$$$ after performing the actions.
You also wrote some values on vertices of graph $$$H$$$. More precisely, vertex $$$i$$$ has the value of $$$a_i$$$ written on it.
Consider a simple path consisting of $$$k$$$ distinct vertices with indexes $$$v_1, v_2, \ldots, v_k$$$. The length of such a path is $$$k$$$. The value of that path is defined as $$$\sum_{i = 1}^k a_{v_i}$$$.
A simple path is considered the longest if there is no other simple path in the graph with greater length.
Among all the longest simple paths in $$$H$$$, find the one with the smallest value.
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n,m \le 2 \cdot 10^5$$$) — the number of vertices and the number of edges.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the numbers written on the vertices of graph $$$H$$$.
The $$$i$$$-th of the next $$$m$$$ lines contains two integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — meaning that there is an edge going from vertex $$$v_i$$$ to vertex $$$u_i$$$ in graph $$$G$$$. Note that edges are directed. Also note that the graph may have self-loops and multiple edges.
It is guaranteed that neither the sum of $$$n$$$ nor the sum of $$$m$$$ over all test cases exceeds $$$2 \cdot 10^5$$$.
For each test case, output two numbers — the length of the longest simple path in $$$H$$$ and the minimal possible value of such path.
35 62 2 4 1 31 21 32 43 44 55 27 7999999999 999999999 999999999 999999999 1000000000 999999999 10000000001 22 33 44 14 54 66 714 222 3 5 7 3 4 1 4 3 4 2 2 5 11 22 32 43 14 44 55 65 65 126 76 87 57 77 98 49 1110 911 1011 1012 1313 1414 12
5 12 6 5999999995 11 37
In the first test case, the longest path in both graphs is $$$1 \to 3 \to 4 \to 5 \to 2$$$. As the path includes all vertices, the minimal possible value of the longest path is the sum of values on all vertices, which is $$$12$$$.
In the second test case, the longest possible path is $$$1 \to 2 \to 3 \to 4 \to 6 \to 7$$$. As there are no longest paths with vertex $$$5$$$ in them, this path has the minimal possible value of $$$5\,999\,999\,995$$$.
In the third test case, it can be proven that there is no path longer than $$$11$$$ and that the value of the longest path cannot be less than $$$37$$$. Also, notice that the given graph has both self-loops and multiple edges.
For an array $$$b_1, b_2, \ldots, b_m$$$, for some $$$i$$$ ($$$1 \lt i \lt m$$$), element $$$b_i$$$ is said to be a local minimum if $$$b_i \lt b_{i-1}$$$ and $$$b_i \lt b_{i+1}$$$. Element $$$b_1$$$ is said to be a local minimum if $$$b_1 \lt b_2$$$. Element $$$b_m$$$ is said to be a local minimum if $$$b_m \lt b_{m-1}$$$.
For an array $$$b_1, b_2, \ldots, b_m$$$, for some $$$i$$$ ($$$1 \lt i \lt m$$$), element $$$b_i$$$ is said to be a local maximum if $$$b_i \gt b_{i-1}$$$ and $$$b_i \gt b_{i+1}$$$. Element $$$b_1$$$ is said to be a local maximum if $$$b_1 \gt b_2$$$. Element $$$b_m$$$ is said to be a local maximum if $$$b_m \gt b_{m-1}$$$.
Let $$$x$$$ be an array of distinct elements. We define two operations on it:
- $$$1$$$ — delete all elements from $$$x$$$ that are not local minima.
- $$$2$$$ — delete all elements from $$$x$$$ that are not local maxima.
Define $$$f(x)$$$ as follows. Repeat operations $$$1, 2, 1, 2, \ldots$$$ in that order until you get only one element left in the array. Return that element.
For example, take an array $$$[1,3,2]$$$. We will first do type $$$1$$$ operation and get $$$[1, 2]$$$. Then we will perform type $$$2$$$ operation and get $$$[2]$$$. Therefore, $$$f([1,3,2]) = 2$$$.
You are given a permutation$$$^\dagger$$$ $$$a$$$ of size $$$n$$$ and $$$q$$$ queries. Each query consists of two integers $$$l$$$ and $$$r$$$ such that $$$1 \le l \le r \le n$$$. The query asks you to compute $$$f([a_l, a_{l+1}, \ldots, a_r])$$$.
$$$^\dagger$$$ A permutation of length $$$n$$$ is an array of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$, but there is $$$4$$$ in the array).
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 10^5$$$) — the length of the permutation $$$a$$$ and the number of queries.
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — the elements of permutation $$$a$$$.
The $$$i$$$-th of the next $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the description of $$$i$$$-th query.
For each query, output a single integer — the answer to that query.
7 5 1 4 3 6 2 7 5 1 1 1 2 2 3 1 4 1 7
1 1 3 3 3
10 1 1 2 3 4 5 6 7 8 9 10 1 10
1
In the first query of the first example, the only number in the subarray is $$$1$$$, therefore it is the answer.
In the second query of the first example, our subarray initially looks like $$$[1, 4]$$$. After performing type $$$1$$$ operation we get $$$[1]$$$.
In the third query of the first example, our subarray initially looks like $$$[4, 3]$$$. After performing type $$$1$$$ operation we get $$$[3]$$$.
In the fourth query of the first example, our subarray initially looks like $$$[1, 4, 3, 6]$$$. After performing type $$$1$$$ operation we get $$$[1, 3]$$$. Then we perform type $$$2$$$ operation and we get $$$[3]$$$.
In the fifth query of the first example, our subarray initially looks like $$$[1, 4, 3, 6, 2, 7, 5]$$$. After performing type $$$1$$$ operation we get $$$[1,3,2,5]$$$. After performing type $$$2$$$ operation we get $$$[3,5]$$$. Then we perform type $$$1$$$ operation and we get $$$[3]$$$.
In the first and only query of the second example our subarray initially looks like $$$[1,2,3,4,5,6,7,8,9,10]$$$. Here $$$1$$$ is the only local minimum, so only it is left after performing type $$$1$$$ operation.