Guizhou is home to many cities with a long history and rich cultural heritage. After the third batch of provincial-level historic cities was announced in 2024, Guizhou has the following $$$12$$$ national-level or provincial-level historic cities:
- National-level historic cities: zun yi (遵义) and zhen yuan (镇远);
- Provincial-level historic cities: an shun (安顺), zhi jin (织金), da fang (大方), shi qian (石阡), li ping (黎平), fu quan (福泉), an long (安龙), pu ding (普定), si nan (思南), and zhen feng (贞丰).
Given a place name written in lowercase Pinyin, determine whether it is in the list of provincial-level historic cities above. National-level historic cities are not considered provincial-level historic cities in this problem.
There is only one test case in each test file.
The first line contains two strings $$$a$$$ and $$$b$$$ ($$$1 \le |a|, |b| \le 6$$$), representing the Pinyin of a place name. Each string consists of lowercase English letters. The two strings are separated by exactly one space.
If the place name is in the list of provincial-level historic cities, print Yes. Otherwise, print No.
zun yi
No
zhi jin
Yes
In the first sample, zun yi refers to Zunyi (遵义), which is a national-level historic city. This problem only asks about provincial-level historic cities, so the answer is No.
In the second sample, zhi jin refers to Zhijin (织金), which is a provincial-level historic city, so the answer is Yes.
You are given a sequence of $$$n$$$ non-negative integers $$$a_1, a_2, \ldots, a_n$$$ and $$$q$$$ operations. The $$$t$$$-th operation consists of the following steps in order:
- For every $$$i$$$ ($$$1 \le i \le n$$$), replace $$$a_i$$$ with $$$\max(a_i - 1, 0)$$$.
- Given two integers $$$x_t$$$ and $$$v_t$$$, if $$$x_t \ne 0$$$, replace $$$a_{x_t}$$$ with $$$\max(a_{x_t}, v_t)$$$. If $$$x_t = 0$$$, the sequence is not changed in this step.
After each operation, find the number of positive elements in the sequence. After all operations, also find the final sequence.
There is only one test case in each test file.
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$$$ ($$$0 \le a_i \le 10^9$$$), the initial sequence.
Each of the next $$$q$$$ lines contains two integers $$$x_t$$$ and $$$v_t$$$ ($$$0 \le x_t \le n$$$, $$$0 \le v_t \le 10^9$$$), describing the $$$t$$$-th operation. It is guaranteed that $$$v_t = 0$$$ if $$$x_t = 0$$$.
After each operation, print a single integer — the number of positive elements in the sequence.
After all operations, print one line containing $$$n$$$ integers — the final sequence.
4 52 0 5 12 33 20 01 42 0
3 2 2 2 1 3 0 0 0
After the first step of the first operation, the sequence is $$$[1, 0, 4, 0]$$$. Then the second element becomes $$$\max(0, 3) = 3$$$, so the sequence is $$$[1, 3, 4, 0]$$$ and it has $$$3$$$ positive elements.
The first step is always performed before the second step of the same operation.
There are $$$n$$$ points on the real line at coordinates $$$x_1 \lt x_2 \lt \ldots \lt x_n$$$. A moving point starts at $$$x_1$$$ at time $$$0$$$ and always moves at a constant speed of $$$1$$$ unit of distance per unit of time. It may change its direction of movement at any time.
For every $$$i$$$, the time between any two consecutive visits to $$$x_i$$$ must not exceed $$$t_i$$$. The visit at time $$$0$$$ is considered a visit to every point, regardless of the initial position.
Determine whether there exists an infinite trajectory satisfying all these conditions.
There is only one test case in each test file.
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
The second line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$1 \le x_1 \lt x_2 \lt \ldots \lt x_n \le 10^9$$$).
The third line contains $$$n$$$ integers $$$t_1, t_2, \ldots, t_n$$$ ($$$1 \le t_i \le 10^9$$$), where $$$t_i$$$ is the maximum allowed time between consecutive visits to $$$x_i$$$.
Output Yes if such an infinite trajectory exists, or No otherwise.
You can print each letter in any case (upper or lower).
31 3 58 4 8
Yes
31 3 58 4 7
No
In both examples, the checkpoints are located at coordinates $$$1$$$, $$$3$$$, and $$$5$$$.
In the first example, you can repeatedly move between coordinates $$$1$$$ and $$$5$$$. Moving from $$$1$$$ to $$$5$$$ takes $$$4$$$ seconds, and moving back from $$$5$$$ to $$$1$$$ takes another $$$4$$$ seconds. You visit the checkpoint at coordinate $$$3$$$ whenever you pass through that coordinate. Therefore, the intervals between every two consecutive visits to the checkpoints at coordinates $$$1$$$, $$$3$$$, and $$$5$$$ are $$$8$$$ seconds, $$$4$$$ seconds, and $$$8$$$ seconds, respectively. These intervals are exactly equal to their limits $$$t_1 = 8$$$, $$$t_2 = 4$$$, and $$$t_3 = 8$$$, so this trajectory satisfies all requirements and the answer is Yes.
In the second example, it can be shown that no trajectory satisfies the requirements, so the answer is No.
You are given two integer sequences $$$a_1, a_2, \ldots, a_n$$$ and $$$b_1, b_2, \ldots, b_n$$$, and an integer $$$M$$$.
In one operation, choose two integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$). For every $$$i$$$ ($$$l \le i \le r$$$), replace $$$a_i$$$ with $$$\min(2 \cdot a_i, M)$$$.
Find the minimum number of operations required to transform $$$a$$$ into $$$b$$$. If it is impossible, print $$$-1$$$.
Each test file 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 \le 2 \cdot 10^5$$$, $$$1 \le M \le 10^9$$$).
The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le M$$$), the initial sequence.
The third line contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$0 \le b_i \le M$$$), the target sequence.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.
For each test case, print the minimum number of operations required to transform $$$a$$$ into $$$b$$$. If it is impossible, print a single integer $$$-1$$$.
25 101 3 0 6 24 10 0 10 83 123 4 012 10 0
2-1
In the first test case, apply the operation twice to the interval $$$[1, 5]$$$. After the first operation, the sequence becomes $$$[2, 6, 0, 10, 4]$$$, and after the second operation, it becomes $$$[4, 10, 0, 10, 8]$$$, so the answer is $$$2$$$.
In the second test case, the second element can only be $$$4$$$, $$$8$$$, or $$$12$$$ after any number of operations, so it can never become $$$10$$$.
There are $$$n$$$ vertices, numbered $$$1,2,\ldots,n$$$. The coordinate of vertex $$$i$$$ is $$$x_i$$$, where $$$x_1 \lt x_2 \lt \ldots \lt x_n$$$. Each vertex supports a nonempty subset of $$$k$$$ types. A state is a pair $$$(i,c)$$$ such that vertex $$$i$$$ supports type $$$c$$$.
From a state $$$(i,c)$$$, the following transitions are allowed:
- Choose one direction on the coordinate line and move to the vertex $$$j$$$ nearest to vertex $$$i$$$ in that direction that supports type $$$c$$$. This transition leads to $$$(j,c)$$$ and costs $$$|x_i-x_j|$$$. If no such vertex exists, the transition is unavailable.
- Change the type from $$$c$$$ to any type $$$d$$$ supported by vertex $$$i$$$. This transition leads to $$$(i,d)$$$ and costs $$$w_{i,d}$$$. Keeping type $$$c$$$ costs nothing.
Initially, you are at vertex $$$s$$$ without any type. You may change to any type $$$c$$$ supported by vertex $$$s$$$ at a cost of $$$w_{s,c}$$$. Find the minimum total cost of reaching vertex $$$t$$$. You may reach vertex $$$t$$$ with any type it supports.
Each test file 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 four integers $$$n$$$, $$$k$$$, $$$s$$$, and $$$t$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le k \le 200\,000$$$, $$$1 \le s,t \le n$$$, $$$s \ne t$$$).
The second line contains $$$n$$$ integers $$$x_1, x_2, \ldots, x_n$$$ ($$$0 \le x_1 \lt x_2 \lt \ldots \lt x_n \le 10^9$$$).
The $$$i$$$-th of the next $$$n$$$ lines contains an integer $$$m_i$$$ ($$$1 \le m_i \le k$$$), followed by $$$m_i$$$ pairs of integers $$$c_{i,j}$$$ and $$$w_{i,j}$$$ ($$$1 \le c_{i,j} \le k$$$, $$$0 \le w_{i,j} \le 10^9$$$). Each pair means that the corresponding vertex $$$i$$$ supports type $$$c_{i,j}$$$ and that changing to this type there costs $$$w_{i,j}$$$. All types listed for one vertex are distinct.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$200\,000$$$, the sum of $$$k$$$ over all test cases does not exceed $$$200\,000$$$, and the sum of $$$m_i$$$ over all vertices and test cases does not exceed $$$200\,000$$$.
For each test case, output the minimum total cost of reaching vertex $$$t$$$ from vertex $$$s$$$. If it is impossible, print a single integer $$$-1$$$.
25 3 1 50 4 7 13 202 1 0 2 32 2 1 3 82 1 2 3 11 2 42 1 5 2 23 2 1 30 5 91 1 01 2 11 2 0
20-1
In the first test case, changing to type $$$1$$$ at vertex $$$1$$$ costs $$$0$$$. From vertex $$$1$$$, move right to vertex $$$3$$$, the nearest vertex in that direction that supports type $$$1$$$. From vertex $$$3$$$, move right to vertex $$$5$$$. The transition costs are $$$0$$$, $$$7$$$, and $$$13$$$, respectively, for a total of $$$20$$$.
In the second test case, no type supported by vertex $$$1$$$ is also supported by another vertex, so no movement transition from vertex $$$1$$$ is available.
You are given two binary strings $$$a$$$ and $$$b$$$ of length $$$n$$$. Their positions are indexed from $$$0$$$ to $$$n-1$$$.
For a pair of integers $$$(s,l)$$$ ($$$0 \le s,l \lt n$$$), construct a string $$$a'$$$ from $$$a$$$ by inverting the $$$k$$$ characters at positions $$$(l+j)\bmod n$$$ for all integers $$$j$$$ ($$$0 \le j \lt k$$$).
The pair $$$(s,l)$$$ is valid if $$$a'_i=b_{(i+s)\bmod n}$$$ for every $$$i$$$ ($$$0 \le i \lt n$$$).
Find the number of valid pairs $$$(s,l)$$$. Different pairs $$$(s,l)$$$ are counted separately, even if they produce the same string $$$a'$$$.
Each test file 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 $$$k$$$ ($$$2 \le n \le 10^6$$$, $$$1 \le k \lt n$$$).
The second line contains a binary string $$$a$$$ of length $$$n$$$.
The third line contains a binary string $$$b$$$ of length $$$n$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, print a single integer — the number of valid pairs $$$(s,l)$$$.
26 20000000011005 20101011100
60
In the first test case, the valid pairs $$$(s,l)$$$ are $$$(2,0)$$$, $$$(1,1)$$$, $$$(0,2)$$$, $$$(5,3)$$$, $$$(4,4)$$$, and $$$(3,5)$$$. For the last pair, the inverted positions are $$$5$$$ and $$$0$$$.
There is no valid pair $$$(s,l)$$$ in the second test case.
You are given a binary string $$$s$$$ of length $$$n$$$ and must process $$$q$$$ operations of the following types:
- 1 l r: For every $$$i$$$ ($$$l \le i \le r$$$), replace $$$s_i$$$ with $$$1 - s_i$$$.
- 2 l r: Delete a subsegment of $$$s_l s_{l+1} \ldots s_r$$$ (possibly empty or the entire interval). Among all possible choices, find the maximum absolute difference between the number of characters 1 and the number of characters 0 in the remaining string. The deletion applies only to this operation and does not affect subsequent queries.
There is only one test case in each test file.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n,q \le 2 \cdot 10^5$$$).
The second line contains a binary string $$$s$$$ of length $$$n$$$.
Each of the next $$$q$$$ lines contains three integers $$$t$$$, $$$l$$$, and $$$r$$$ ($$$t \in \{1,2\}$$$, $$$1 \le l \le r \le n$$$), describing an operation.
It is guaranteed that there is at least one operation of type 2.
For each operation of type 2, print one integer — the maximum possible absolute difference between the number of characters 1 and the number of characters 0 in the remaining string.
5 5110102 1 51 2 42 1 52 2 42 3 3
2 2 2 1
4 301012 1 41 1 42 1 4
1 1
In the first example:
- The first operation is a query, and the queried interval is 11010. Deleting the character at position $$$3$$$ leaves 1110 in the queried interval, which contains $$$2$$$ more characters 1 than characters 0.
- The second operation inverts the characters at positions $$$2$$$ through $$$4$$$, so the string becomes 10100.
- The third operation is a query, and the queried interval is 10100. Deleting the character at position $$$1$$$ leaves 0100 in the queried interval, which contains $$$2$$$ more characters 0 than characters 1.
- The fourth operation is a query, and the queried interval is 010. Deleting the character at position $$$2$$$ of this interval leaves 00 in the queried interval, which contains $$$2$$$ more characters 0 than characters 1.
- The fifth operation is a query, and the queried interval is 1. Deleting the empty string leaves 1 in the queried interval, which contains $$$1$$$ more character 1 than characters 0.
You are given a directed graph with $$$n$$$ vertices and $$$m$$$ edges.
Choose a subset of its edges and reverse every chosen edge. Reversing an edge $$$(u, v)$$$ replaces it with $$$(v, u)$$$.
Find the minimum number of chosen edges such that every vertex has an in-degree of at least $$$1$$$ after the reversals. If no such subset exists, print $$$-1$$$.
Each test file 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 two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 2000$$$, $$$0 \le m \le 10000$$$).
Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \ne v$$$), representing a one-way path from vertex $$$u$$$ to vertex $$$v$$$.
The input graph contains no two edges with the same ordered pair of endpoints. It may contain both $$$(u, v)$$$ and $$$(v, u)$$$. After the reversals, multiple edges with the same ordered pair of endpoints are allowed.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2000$$$, and the sum of $$$m$$$ over all test cases does not exceed $$$10000$$$.
For each test case, print one integer — the minimum number of edges that must be reversed. If no solution exists, print $$$-1$$$.
53 31 21 32 34 41 22 34 31 43 21 22 32 21 22 11 0
12-10-1
In the first test case, it is sufficient to replace $$$(1, 3)$$$ with $$$(3, 1)$$$. The three resulting edges form a directed cycle, and every vertex has an in-degree of $$$1$$$.
In the second test case, one can replace $$$(1, 2)$$$ with $$$(2, 1)$$$ and $$$(2, 3)$$$ with $$$(3, 2)$$$. It can be shown that reversing only one edge is insufficient.
You are given two strings $$$u$$$ and $$$v$$$. In one operation, exactly one of the following modifications can be applied to the current string:
- insert one lowercase English letter at any position;
- delete one character at any position;
- replace one character at any position with a lowercase English letter.
An operation is determined by its type, its position at the moment it is performed, and its inserted or replacement character when applicable. Two operation sequences are different if their lengths differ or if their operations differ at some step. Thus, applying the same modifications in different orders may produce different operation sequences.
Count the minimum-length operation sequences that transform $$$u$$$ into $$$v$$$, modulo $$$998~244~353$$$.
Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 5~000$$$). The description of the test cases follows.
The first line of each test case contains a non-empty string $$$u$$$ ($$$1 \le |u| \le 5~000$$$) consisting of lowercase English letters.
The second line contains a non-empty string $$$v$$$ ($$$1 \le |v| \le 5~000$$$) consisting of lowercase English letters.
It is guaranteed that the sum of $$$|u|$$$ over all test cases does not exceed $$$5~000$$$, and the sum of $$$|v|$$$ over all test cases does not exceed $$$5~000$$$.
For each test case, output the number of minimum-length operation sequences that transform $$$u$$$ into $$$v$$$, modulo $$$998~244~353$$$.
2 ab ba paper pepper
6 6
In the first test case, the minimum number of operations is $$$2$$$. There are three optimal alignments: replace both characters; delete the first character and append it; or insert b at the beginning and delete the last character. The two operations for each alignment can be performed in either order, giving $$$3 \cdot 2! = 6$$$ operation sequences.
Let $$$P$$$ be the interior of a simple polygon in the Cartesian plane. For a real number $$$h$$$, define $$$S_h = \{(x, y) \in P \mid y \gt h\}$$$.
Two subsets that intersect only at boundary points are not considered connected.
You are given $$$q$$$ values of $$$h$$$. For each value, find the number of connected components of $$$S_h$$$.
There is only one test case in each test file.
The first line contains two integers $$$n$$$ and $$$q$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$), the number of vertices of the polygon and the number of queries, respectively.
The $$$i$$$-th of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$|x_i|, |y_i| \le 10^9$$$), the coordinates of the $$$i$$$-th vertex. The vertices are given in counterclockwise order along the boundary. It is guaranteed that they form a simple polygon and that all $$$y_i$$$ are pairwise distinct.
The $$$j$$$-th of the next $$$q$$$ lines contains one integer $$$h_j$$$ ($$$|h_j| \le 10^9$$$), the water level of the $$$j$$$-th query. It is guaranteed that $$$h_j$$$ differs from the $$$y$$$-coordinate of every vertex. The values $$$h_j$$$ are not necessarily distinct.
For each query, output one integer on a separate line — the number of connected components of $$$S_{h_j}$$$.
7 40 06 25 124 63 142 41 10-181316
1 3 1 0
For $$$h = -1$$$, $$$S_h$$$ is the entire polygon $$$P$$$, so it has one connected component.
For $$$h = 8$$$, $$$S_h$$$ has $$$3$$$ connected components. For $$$h = 13$$$, $$$S_h$$$ has $$$1$$$ connected component. For $$$h = 16$$$, $$$S_h$$$ is empty and has no connected components.
You are given a string $$$s$$$ consisting of lowercase English letters.
A string $$$p$$$ is a palindrome if $$$p_i = p_{|p|-i+1}$$$ for every $$$i$$$ ($$$1 \le i \le |p|$$$). A string is two-tone if it contains at most $$$2$$$ distinct characters.
Count the substrings of $$$s$$$ that are both palindromes and two-tone. Two substrings are considered different if their left endpoints or right endpoints differ.
Each test file 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 a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$), the length of the string.
The second line contains a string $$$s$$$ of length $$$n$$$ consisting of lowercase English letters.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.
For each test case, print a single integer — the number of substrings that are both palindromes and two-tone.
25ababa6abccba
98
In the first test case, every palindromic substring contains only the characters a and b. Therefore, the answer equals the total number of palindromic substrings, which is $$$9$$$.
In the second test case, the entire string abccba is a palindrome, but it contains $$$3$$$ distinct characters, so it is not counted.