Baran has a strip of land in the beautiful city of Afrin, a city renowned for its delicious olive oil, lush green nature, and generous people. Visitors to Afrin are always captivated by its stunning scenery.
Baran's land is represented as a single line of $$$n$$$ cells. Each cell can be in one of four states:
Baran plans to walk along this line of cells exactly once, from the first cell to the last. He has a vehicle that can carry a total of $$$M$$$ kilograms of items. For simplicity, we assume one bag of water weighs 1 kg and one unit of harvested olives also weighs 1 kg.
During his single pass, Baran has two objectives:
The total weight of water bags and olive units in his vehicle cannot exceed $$$M$$$ at any point in time.
Can you help Baran determine the maximum number of olive units he can collect while ensuring all needy trees are watered?
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 $$$T$$$ test cases follows.
The first line of each test case contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N \le 10^5$$$, $$$1 \le M \le 10^5$$$), representing the number of cells in the land and the vehicle's capacity, respectively.
The second line of each test case contains a string of length $$$N$$$, describing the land. Each character is one of ., O, T, or W.
It is guaranteed that the sum of $$$N$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, print a single integer on a new line. This integer should be the maximum number of olive units Baran can collect. If it is impossible to water all the trees that need it, print -1.
48 2.OOWTWTO7 2TOOWTWT5 3.OOOO12 3OWWTWTTOOOOO
2 -1 3 3
First Test Case:
The number of 'O's inside the vehicle is 2, so the answer is: $$$2$$$
Second Test Case:
The answer is: $$$-1$$$
Third Test Case:
The answer is: $$$3$$$
Fourth Test Case:
The judges have just landed in Latakia, and they don't want to waste any time, but they are really eager to go swimming in the sea!
So judge Apra proposed going swimming at time $$$a$$$, and judge Mouf proposed going swimming at time $$$b$$$, so they started fighting and couldn't decide on a suitable time.
After much fighting, they decided to go swimming at the minimum time so they get to make it to the contest, but they are currently busy preparing the problems, so can you help them choose the minimum time?
The first and only line of input contains two integers $$$a$$$ and $$$b$$$ $$$(1 \le a, b \le 1000)$$$.
Output a single number, the answer to the problem.
4 2
2
You are given two integers, $$$n$$$ and $$$m$$$. Using these, we define two infinite, 1-indexed sequences, $$$A$$$ and $$$B$$$:
Now, construct a graph with $$$n + m$$$ nodes. In this graph, there exists an undirected edge connecting node $$$u$$$ and node $$$v$$$ if and only if there exists some index $$$i \ge 1$$$ such that $$$A_i = u$$$ and $$$B_i = v$$$.
Note: a cycle is a path in a graph that starts and ends at the same vertex, with no repeated edges and at least one edge.
Your task is to find the smallest cycle in the resulting graph. If there are multiple cycles of the same smallest size, you may print any one of them. If the graph is acyclic, print -1.
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$$$ $$$(2 \le n, m \le 10^5)$$$.
It is guaranteed that the sum of $$$n$$$ and $$$m$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, if the graph is acyclic print -1. Otherwise, in the first line print a single integer k $$$(3 \le k \le n + m)$$$ — the size of the smallest cycle in the graph. In the next line print k distinct integers $$$(c_1, c_2, ..., c_k)$$$, describing the cycle. for $$$1 \lt i \le k$$$ the node $$$c_i$$$ should be connected to the node $$$c_{i - 1}$$$. and node $$$c_k$$$ should be connected to node $$$c_1$$$.
It is guaranteed that the sum of $$$k$$$ over all test cases does not exceed $$$10^6$$$.
3 2 3 2 4 4 6
4 1 5 2 3 -1 4 5 3 7 1
Explanation of the example:
The first test case:
A = $$$[1, 2, 1, 2, 1, 2, ...]$$$
B = $$$[3, 4, 5, 3, 4, 5, ...]$$$
The second test case:
A = $$$[1, 2, 1, 2, 1, 2, ...]$$$
B = $$$[3, 4, 5, 6, 3, 4, ...]$$$
For the first test case, the following cycles (of size 4) are also accepted:
$$$[1, 4, 2, 5]$$$
$$$[3, 2, 4, 1]$$$
 |  |
| the graph for the first test case | the graph for the second test case |
You will be given a tree consisting of $$$n$$$ nodes, rooted at node 1. Each node can be white or black. Initially, all of the nodes are white. Also, you will be given $$$q$$$ queries of the form ($$$x_i$$$).
For each query, you have to toggle the color of the $$$x_i$$$-th node, (i.e. if it is black, it becomes white and vice versa), and then report the following value:
what is the maximum number of black nodes you can choose where no chosen node is an ancestor$$$^{\text{∗}}$$$ of another chosen one?
$$$^{\text{∗}}$$$In a rooted tree, a node $$$x$$$ is an ancestor of a node $$$y$$$ if and only if $$$x$$$ lies on the path from the root to $$$y$$$.
Each test consists of multiple test cases. The first line contains a single integer $$$T$$$ $$$(1 \le T \le 10^3)$$$ — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $$$n$$$ and $$$q$$$ $$$(2 \le n, q \le 10^5)$$$ — the size of the tree and the number of queries.
The second line of each test case contains $$$n - 1$$$ integers $$$p_2, \ldots, p_n$$$ $$$(1 \le p_i \le n)$$$ — the parent of node $$$i$$$.
Each of the next $$$q$$$ lines contains an integer $$$x_i$$$ $$$(1 \le x_i \le n)$$$ — representing the $$$i$$$-th query.
It is guaranteed that the given set of edges forms a tree.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$ and the sum of $$$q$$$ over all test cases does not exceed $$$10^5$$$.
For each query, output the required value.
15 51 1 3 345324
1 2 2 3 2
You are given a tree with $$$n$$$ nodes. Each node $$$i$$$ has an initial value $$$A_i$$$.
You can perform a special eat operation. In this operation, you select two nodes, $$$u$$$ and $$$v$$$, that are directly connected by an edge. Node $$$u$$$ can eat node $$$v$$$ only if both of the following conditions are met:
When $$$u$$$ eats $$$v$$$, node $$$v$$$ and the edge connecting them are removed from the tree. The value of node $$$u$$$ is then updated by absorbing $$$v$$$'s value: $$$A_u = A_u + A_v$$$.
Your task is to determine if there exists a sequence of eat operations that results in the tree being reduced to a single node. If it is possible, give any possible sequence.
$$$^{\text{∗}}$$$A leaf is a node that has exactly one edge.
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 contains a single integer $$$N$$$ ($$$2 \le n \le 2*10^5$$$).
The second line contains $$$n$$$ space-separated integers $$$A_1, A_2, \dots, A_n$$$ ($$$1 \le A_i \le 10^9$$$), the initial values of the nodes.
The next $$$n-1$$$ lines each contain two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n, u \ne v$$$), describing an edge between node $$$u$$$ and node $$$v$$$ . It is guaranteed that these edges form a tree and that sum of n over all testcases doesn't exceed $$$2*10^5$$$.
If it's possible to reduce the tree to a single node, first print Yes. Then, print the $$$n-1$$$ operations that achieve this. Each operation should be printed on a new line as two space-separated integers u v, where node u eats node v.
If it's impossible, print No.
453 9 1 2 24 54 31 42 356 6 2 8 12 32 12 54 135 6 23 22 127 31 2
No No Yes 2 3 2 1 Yes 1 2
Whoever tries to solve this problem will either achieve great honor or face terrible failure!
You are given three integers $$$n$$$, $$$x$$$, and $$$y$$$, along with two arrays $$$a$$$ and $$$b$$$, each of length $$$n$$$.
You need to process $$$n$$$ turns. During the $$$i$$$-th turn, you must perform exactly one of the following actions:
Your initial score is $$$0$$$. Determine the maximum score you can achieve after completing all $$$n$$$ turns.
Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 10^3$$$). The description of the test cases follows.
The first line of each test case contains three integers $$$n$$$, $$$x$$$, and $$$y$$$ ($$$1 \leq n, x, y \leq 2*10^3$$$).
The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 2$$$), representing the array $$$a$$$.
The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 10^6$$$), representing the array $$$b$$$.
It is guaranteed that the sum of $$$n^2$$$ across all test cases does not exceed $$$4 \cdot 10^6$$$.
For each test case, output in a single line the maximum score you can get.
35 1 11 1 1 1 15 4 3 2 14 1 41 2 2 22 2 2 44 2 12 1 2 19 9 1 5
24 100 114
In the first test case, you can achieve a score of $$$24$$$ as follows:
It can be proven that $$$24$$$ is the maximum score you can achieve.
In the second test case, you can achieve a score of $$$100$$$ as follows:
You are given two grids of size $$$N \times M$$$, let's call them the target grid and your grid. The cells in both grids can be in one of two states: 'on' or 'off'. Initially, all cells in your grid are 'off', while the target grid has a specific configuration of 'on' and 'off' cells.
Your goal is to make your grid identical to the target grid by using a specific operation. The operation consists of three steps:
You need to find and print any valid sequence with minimum number of operations that transforms your initially off-state grid into the target grid.
Each test consists of multiple test cases. The first line contains a single integer $$$T$$$ $$$(1 \le T \le 10^3)$$$ — the number of test cases. The description of the test cases follows.
The first line of each testcase contains two integers $$$N$$$ and $$$M$$$ ($$$1 \le N, M \le 1000$$$), the number of rows and columns in the grids.
The next $$$N$$$ lines of each testcase each contain a string of $$$M$$$ characters, representing the target grid. The character '1' denotes an 'on' cell, and '0' denotes an 'off' cell.
It's guaranteed that sum of n overall testcases doesn't exceed 1000 and sum of m doesn't exceed 1000.
For each testcase, On the first line, print a single integer $$$K$$$, the minimum number of operations.
On the next $$$K$$$ lines, print two space-separated integers $$$r$$$ and $$$c$$$ ($$$1 \le r \le N$$$, $$$1 \le c \le M$$$), representing the 1-based coordinates of a cell to perform the operation on. The total number of operations must not exceed $$$N \times M$$$.
21 104 200110101
0 4 2 1 2 2 3 1 4 2
You are given a binary grid of size $$$N \times M$$$ (containing only '0's and '1's). You have a special ability: for any column, you can swap any two elements within that column. This means you can arrange the '0's and '1's in any column in any order you like, but you cannot move elements between different columns.
A grid is considered row-sorted if every row is sorted in non-decreasing order (i.e., all '0's appear before all '1's).
You will be given $$$Q$$$ queries. Each query consists of a cell $$$(r, c)$$$. For each query, you must first flip the value in cell $$$(r, c)$$$ of the current grid (a '0' becomes a '1', and a '1' becomes a '0'). This change is permanent and carries over to subsequent queries. After each flip, you must determine if the resulting grid can be made row-sorted using your column-swapping ability.
Each test consists of multiple test cases. The first line contains a single integer $$$T$$$ $$$(1 \le T \le 10^5)$$$ — the number of test cases. The description of the test cases follows.
The first line of each test case contains integers $$$N, M,$$$ and $$$Q$$$ ($$$1 \le N, M$$$, $$$1 \le N \times M \le 10^5$$$, $$$1 \le Q \le 10^5$$$).
The next $$$N$$$ lines of each testcase each contain a string of $$$M$$$ characters ('0' or '1'), representing the initial grid.
The next $$$Q$$$ lines each contain two integers $$$r$$$ and $$$c$$$ ($$$1 \le r \le N$$$, $$$1 \le c \le M$$$), representi ng the coordinates of the cell to flip for that query. It's guaranteed that sum of N * M overall testcases doesn't exceed $$$10^5$$$ and sum of Q doesn't exceed $$$10^5$$$
For each testcase, For each of the $$$Q$$$ queries, print Yes on a new line if the grid can be made row-sorted after the flip, and No otherwise.
55 2 311110100113 14 24 13 7 20101001011111110111001 41 62 2 411012 22 11 11 13 4 11110111011003 31 1 201 11 1
Yes Yes Yes No Yes Yes No Yes No No Yes Yes
Shaban loves divisibility by 9, he has a number x with $$$n$$$ digits and he wants to transform it to the maximum number that is divisible by 9 by performing exactly $$$k$$$ of the following operation:
Each operation consists of choosing any single digit of x and doing one of the following:
Shaban will do exactly $$$k$$$ operations to transform the initial number into a new $$$n$$$-digit number that satisfies two conditions:
The resulting number can have leading zeros. If it's impossible to create such a number, you should print -1.
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 line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 10^5$$$, $$$0 \le k \le 10^7$$$), representing the number of digits in the number and the number of operations, respectively.
The second line of each test case contains a string of $$$n$$$ digits, representing the initial number. The string can have leading zeros.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.
For each test case, print a single line containing the resulting $$$n$$$-digit number that is as large as possible and divisible by 9. If no such number can be formed within $$$k$$$ operations, print -1.
72 4701 232 3302 21810 16123456789011 53159914600410 1001356849840
90 -1 00 27 9234567810 71599146003 9999999999
First Test Case:
The maximum number you can obtain is $$$90$$$, and it is divisible by 9.
Second Test Case:
No matter how you change the digits, the number will never become divisible by 9. so the answer is $$$-1$$$.
Third Test Case:
Fourth Test Case:
You are an artist working on an infinitely large 2D pixel art canvas. Your goal is to fill a specific rectangular area with color, using the minimum number of new pixels.
The rectangular area to be filled is defined by its top-left corner $$$(X_1, Y_1)$$$ and its bottom-right corner $$$(X_2, Y_2)$$$, inclusive. On this canvas, the y-coordinates increase upwards.
To start, you are given $$$n$$$ pixels that are already colored at positions $$$(x_i, y_i)$$$.
You have two ways to color a new pixel:
Your task is to find the minimum number of new pixels you must color to ensure the entire rectangular area from $$$(X_1, Y_1)$$$ to $$$(X_2, Y_2)$$$ is completely filled.
The first line contains a single integer $$$n$$$ ($$$0 \le n \le 10^5$$$), the number of initially colored pixels.
The second line contains four integers $$$X_1, Y_1, X_2, Y_2$$$ ($$$1 \le X_1 \le X_2 \le 10^9$$$, $$$1 \le Y_2 \le Y_1 \le 10^9$$$), defining the target rectangle.
The next $$$n$$$ lines each contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le 10^9$$$), the coordinates of an initially colored pixel.
Print a single integer: the minimum number of new pixels required to fill the target rectangle.
33 6 6 45 53 28 5
11
04 4 4 4
4
13 4 4 33 2
4
13 6 6 47 5
12
Baran wants to ensure that the problem Shaban prepared for the LCPC contest is approachable for the students. To make it more accessible, he has simplified the task as follows:
Given a very large number $$$n$$$ (where $$$0 \leq n \leq 10^{10^5}$$$), determine if $$$n$$$ is divisible by 9.
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 and only line of each test case contains one integer $$$n$$$ $$$(0 \le n \le 10^{10^5})$$$ — the given large number.
It's guaranteed that the sum of the number of digits for all the test cases won't exceed $$$10^{5}$$$.
Print Yes if the number is divisible by $$$9$$$; otherwise, print No.
10333234180966681111656871
Yes Yes Yes Yes Yes No No No No No
You are given an empty array of strings, let's call it $$$A$$$. You need to process $$$n$$$ queries of three different types.
The queries are as follows:
Your task is to handle these queries and provide the correct output for all type 3 queries.
The first line of input contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of queries.
The following $$$n$$$ lines each describe a query. The format for each query is one of the following:
It is guaranteed that the sum of lengths of all strings $$$S$$$ in type 1 queries and all strings $$$x$$$ in type 3 queries does not exceed $$$10^6$$$.
Note: it is guaranteed that the first query is from type one.
For each query of type 3, print "Yes" on a new line if the string $$$x$$$ is found in the array $$$A$$$. Otherwise, print "No".
51 abc3 abc2 c3 abc3 abcc
Yes No Yes
Let $$$A$$$ be the array of strings. We will trace its state through each query to understand the output.
This is the conclusion of the story from the problem "Codeforces Round (1025) A. It's Time to Duel."
At the end of the Yu-Gi-Oh! tournament, it was time to give out the prizes. The biggest prize was a rare copy of the card "Blue Eyes White Dragon."
But then, something bad happened: someone stole the card. This made Mouf, the person in charge of the tournament, very angry. He thought that everyone in the tournament knew who the thief was, but they were too scared to say anything.
To find out the truth, Mouf came up with a plan. He lined up all the $$$n$$$ players and gave each one a number from $$$1$$$ to $$$n$$$. Then he asked them, "What is the difference between your number and the thief's number?" This question created a list called $$$a$$$, where $$$a_i$$$ was the answer from player number $$$i$$$.
However, exactly one player lied about their distance from the thief. Now, Mouf needs your help to figure out who the thief is or to declare that it's impossible to find out.
Note that the liar may be the one who stole the prize.
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 one integer $$$n$$$ $$$(2 \le n \le 10^5)$$$ — the number of players in the tournament.
The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,…,a_n$$$ $$$(0 \le a_i \le n-1)$$$ — denoting the answer from player number $$$i$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, and that each test case contains exactly 1 liar.
For each test case output in a single line the thief number or $$$-1$$$ if it is impossible to find out the thief.
621 132 0 030 1 043 1 2 341 0 1 051 3 1 2 3
-1 3 -1 1 2 2