1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Character Swap (Easy Version)
Contest: Codeforces Round 599 (Div. 2)
Difficulty rating: 1000
Tags: strings

This problem is different from the hard version. In this version Ujan makes exactly one exchange. You can hack this problem only if you solve both problems.

After struggling and failing many times, Ujan decided to try to clean up his house again. He decided to get his strings in order first.

Ujan has two distinct strings $$$s$$$ and $$$t$$$ of length $$$n$$$ consisting of only of lowercase English characters. He wants to make them equal. Since Ujan is lazy, he will perform the following operation exactly once: he takes two positions $$$i$$$ and $$$j$$$ ($$$1 \le i,j \le n$$$, the values $$$i$$$ and $$$j$$$ can be equal or different), and swaps the characters $$$s_i$$$ and $$$t_j$$$. Can he succeed?

Note that he has to perform this operation exactly once. He has to perform this operation.

Input format:
The first line contains a single integer $$$k$$$ ($$$1 \leq k \leq 10$$$), the number of test cases.

For each of the test cases, the first line contains a single integer $$$n$$$ ($$$2 \leq n \leq 10^4$$$), the length of the strings $$$s$$$ and $$$t$$$.

Each of the next two lines contains the strings $$$s$$$ and $$$t$$$, each having length exactly $$$n$$$. The strings consist only of lowercase English letters. It is guaranteed that strings are different.

Output format:
For each test case, output "Yes" if Ujan can make the two strings equal and "No" otherwise.

You can print each letter in any case (upper or lower).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case, Ujan can swap characters $$$s_1$$$ and $$$t_4$$$, obtaining the word "house".

In the second test case, it is not possible to make the strings equal using exactly one swap of $$$s_i$$$ and $$$t_j$$$.

Example input:
4
5
souse
houhe
3
cat
dog
2
aa
az
3
abc
bca

Example output:
Yes
No
No
No

Editorial:
First, suppose that we make the strings equal by picking some $$$i$$$, $$$j$$$. Then for all $$$p \neq i, j$$$, we must have $$$s_p = t_p$$$, since these letters don't change.
Suppose that $$$i = j$$$. Since the strings are distinct, we then must have $$$s_i \neq t_i$$$. But then the strings are not equal also after the swap; hence, we always need to pick distinct $$$i$$$ and $$$j$$$.
Now, if $$$i \neq j$$$ and the strings are equal after the swap, we must have that $$$s_i = s_j$$$, $$$t_i = t_j$$$ and $$$s_i, s_j \neq t_i, t_j$$$. Therefore, the solution is as follows: if the number of positions where $$$s$$$ and $$$t$$$ differ is not equal to $$$2$$$, the answer is "No". Otherwise we find the two positions $$$i$$$, $$$j$$$, where $$$s$$$ and $$$t$$$ differ, and check that the above conditions hold. Then the answer is "Yes". Complexity of the solution: $$$O(n)$$$.
Genetic Engineering
Contest: Rockethon 2014
Tags: implementation, two pointers

You will receive 3 points for solving this problem.

Manao is designing the genetic code for a new type of algae to efficiently produce fuel. Specifically, Manao is focusing on a stretch of DNA that encodes one protein. The stretch of DNA is represented by a string containing only the characters 'A', 'T', 'G' and 'C'.

Manao has determined that if the stretch of DNA contains a maximal sequence of consecutive identical nucleotides that is of even length, then the protein will be nonfunctional. For example, consider a protein described by DNA string "GTTAAAG". It contains four maximal sequences of consecutive identical nucleotides: "G", "TT", "AAA", and "G". The protein is nonfunctional because sequence "TT" has even length.

Manao is trying to obtain a functional protein from the protein he currently has. Manao can insert additional nucleotides into the DNA stretch. Each additional nucleotide is a character from the set {'A', 'T', 'G', 'C'}. Manao wants to determine the minimum number of insertions necessary to make the DNA encode a functional protein.

Input format:
The input consists of a single line, containing a string s of length n (1 ≤ n ≤ 100). Each character of s will be from the set {'A', 'T', 'G', 'C'}.

This problem doesn't have subproblems. You will get 3 points for the correct submission.

Output format:
The program should print on one line a single integer representing the minimum number of 'A', 'T', 'G', 'C' characters that are required to be inserted into the input string in order to make all runs of identical characters have odd length.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, it is sufficient to insert a single nucleotide of any type between the two 'T's in the sequence to restore the functionality of the protein.

Example input:
GTTAAAG

Example output:
1

Example input:
AACCAACCAAAAC

Example output:
5

Editorial:
Word Folding
Contest: Rockethon 2014
Tags: brute force

You will receive 5 points for solving this problem.

Manao has invented a new operation on strings that is called folding. Each fold happens between a pair of consecutive letters and places the second part of the string above first part, running in the opposite direction and aligned to the position of the fold. Using this operation, Manao converts the string into a structure that has one more level than there were fold operations performed. See the following examples for clarity.

We will denote the positions of folds with '|' characters. For example, the word "ABRACADABRA" written as "AB|RACA|DAB|RA" indicates that it has been folded three times: first, between the leftmost pair of 'B' and 'R' letters; second, between 'A' and 'D'; and third, between the rightmost pair of 'B' and 'R' letters. Here are several examples of folded strings:

One last example for "ABCD|EFGH|IJ|K":

Manao noticed that each folded string can be viewed as several piles of letters. For instance, in the previous example, there are four piles, which can be read as "AHI", "BGJK", "CF", and "DE" from bottom to top. Manao wonders what is the highest pile of identical letters he can build using fold operations on a given word. Note that the pile should not contain gaps and should start at the bottom level. For example, in the rightmost of the four examples above, none of the piles would be considered valid since each of them has gaps, starts above the bottom level, or both.

Input format:
The input will consist of one line containing a single string of n characters with 1 ≤ n ≤ 1000 and no spaces. All characters of the string will be uppercase letters.

This problem doesn't have subproblems. You will get 5 points for the correct submission.

Output format:
Print a single integer — the size of the largest pile composed of identical characters that can be seen in a valid result of folding operations on the given string.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
Consider the first example. Manao can create a pile of three 'A's using the folding "AB|RACAD|ABRA", which results in the following structure:

In the second example, Manao can create a pile of three 'B's using the following folding: "AB|BB|CBDB".

Another way for Manao to create a pile of three 'B's with "ABBBCBDB" is the following folding: "AB|B|BCBDB".

In the third example, there are no folds performed and the string is just written in one line.

Example input:
ABRACADABRA

Example output:
3

Example input:
ABBBCBDB

Example output:
3

Editorial:
Three Trees
Contest: Rockethon 2014

This problem consists of two subproblems: for solving subproblem E1 you will receive 11 points, and for solving subproblem E2 you will receive 13 points.

A tree is an undirected connected graph containing no cycles. The distance between two nodes in an unweighted tree is the minimum number of edges that have to be traversed to get from one node to another.

You are given 3 trees that have to be united into a single tree by adding two edges between these trees. Each of these edges can connect any pair of nodes from two trees. After the trees are connected, the distances between all unordered pairs of nodes in the united tree should be computed. What is the maximum possible value of the sum of these distances?

Input format:
The first line contains three space-separated integers n1, n2, n3 — the number of vertices in the first, second, and third trees, respectively. The following n1 - 1 lines describe the first tree. Each of these lines describes an edge in the first tree and contains a pair of integers separated by a single space — the numeric labels of vertices connected by the edge. The following n2 - 1 lines describe the second tree in the same fashion, and the n3 - 1 lines after that similarly describe the third tree. The vertices in each tree are numbered with consecutive integers starting with 1.

The problem consists of two subproblems. The subproblems have different constraints on the input. You will get some score for the correct submission of the subproblem. The description of the subproblems follows.

- In subproblem E1 (11 points), the number of vertices in each tree will be between 1 and 1000, inclusive.
- In subproblem E2 (13 points), the number of vertices in each tree will be between 1 and 100000, inclusive.

Output format:
Print a single integer number — the maximum possible sum of distances between all pairs of nodes in the united tree.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
Consider the first test case. There are two trees composed of two nodes, and one tree with three nodes. The maximum possible answer is obtained if the trees are connected in a single chain of 7 vertices.

In the second test case, a possible choice of new edges to obtain the maximum answer is the following:

- Connect node 3 from the first tree to node 1 from the second tree;
- Connect node 2 from the third tree to node 1 from the second tree.

Example input:
2 2 3
1 2
1 2
1 2
2 3

Example output:
56

Example input:
5 1 4
1 2
2 5
3 4
4 2
1 2
1 3
1 4

Example output:
151

Editorial:
Friends or Not
Contest: VK Cup 2012 Qualification Round 2
Difficulty rating: 1400
Tags: *special, greedy, implementation

Polycarpus has a hobby — he develops an unusual social network. His work is almost completed, and there is only one more module to implement — the module which determines friends. Oh yes, in this social network one won't have to add friends manually! Pairs of friends are deduced in the following way. Let's assume that user A sent user B a message at time t1, and user B sent user A a message at time t2. If 0 < t2 - t1 ≤ d, then user B's message was an answer to user A's one. Users A and B are considered to be friends if A answered at least one B's message or B answered at least one A's message.

You are given the log of messages in chronological order and a number d. Find all pairs of users who will be considered to be friends.

Input format:
The first line of the input contains two integers n and d (1 ≤ n, d ≤ 1000). The next n lines contain the messages log. The i-th line contains one line of the log formatted as "Ai Bi ti" (without the quotes), which means that user Ai sent a message to user Bi at time ti (1 ≤ i ≤ n). Ai and Bi are non-empty strings at most 20 characters long, consisting of lowercase letters ('a' ... 'z'), and ti is an integer (0 ≤ ti ≤ 10000). It is guaranteed that the lines are given in non-decreasing order of ti's and that no user sent a message to himself. The elements in the lines are separated by single spaces.

Output format:
In the first line print integer k — the number of pairs of friends. In the next k lines print pairs of friends as "Ai Bi" (without the quotes). You can print users in pairs and the pairs themselves in any order. Each pair must be printed exactly once.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first sample test case Vasya and Petya are friends because their messages' sending times are one second apart. Anya and Ivan are not, because their messages' sending times differ by more than one second.

Example input:
4 1
vasya petya 1
petya vasya 2
anya ivan 2
ivan anya 4

Example output:
1
petya vasya

Example input:
1 1000
a b 0

Example output:
0

Editorial:
Matchmaker
Contest: VK Cup 2012 Qualification Round 2
Difficulty rating: 1100
Tags: *special, greedy, sortings

Polycarpus has n markers and m marker caps. Each marker is described by two numbers: xi is the color and yi is the diameter. Correspondingly, each cap is described by two numbers: aj is the color and bj is the diameter. Cap (aj, bj) can close marker (xi, yi) only if their diameters match, that is, bj = yi. Besides, a marker is considered to be beautifully closed, if the cap color and the marker color match, that is, aj = xi.

Find the way to close the maximum number of markers. If there are several such ways, then choose the one that has the maximum number of beautifully closed markers.

Input format:
The first input line contains two space-separated integers n and m (1 ≤ n, m ≤ 105) — the number of markers and the number of caps, correspondingly.

Next n lines describe the markers. The i-th line contains two space-separated integers xi, yi (1 ≤ xi, yi ≤ 1000) — the i-th marker's color and diameter, correspondingly.

Next m lines describe the caps. The j-th line contains two space-separated integers aj, bj (1 ≤ aj, bj ≤ 1000) — the color and diameter of the j-th cap, correspondingly.

Output format:
Print two space-separated integers u, v, where u is the number of closed markers and v is the number of beautifully closed markers in the sought optimal way. Remember that you have to find the way to close the maximum number of markers, and if there are several such ways, you should choose the one where the number of beautifully closed markers is maximum.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
In the first test sample the first marker should be closed by the fourth cap, the second marker should be closed by the first cap and the third marker should be closed by the second cap. Thus, three markers will be closed, and two of them will be beautifully closed — the first and the third markers.

Example input:
3 4
1 2
3 4
2 4
5 4
2 4
1 1
1 2

Example output:
3 2

Example input:
2 2
1 2
2 1
3 4
5 1

Example output:
1 0

Editorial:
String Manipulation 1.0
Contest: VK Cup 2012 Qualification Round 2
Difficulty rating: 1400
Tags: *special, binary search, brute force, data structures, strings

One popular website developed an unusual username editing procedure. One can change the username only by deleting some characters from it: to change the current name s, a user can pick number p and character c and delete the p-th occurrence of character c from the name. After the user changed his name, he can't undo the change.

For example, one can change name "arca" by removing the second occurrence of character "a" to get "arc".

Polycarpus learned that some user initially registered under nickname t, where t is a concatenation of k copies of string s. Also, Polycarpus knows the sequence of this user's name changes. Help Polycarpus figure out the user's final name.

Input format:
The first line contains an integer k (1 ≤ k ≤ 2000). The second line contains a non-empty string s, consisting of lowercase Latin letters, at most 100 characters long. The third line contains an integer n (0 ≤ n ≤ 20000) — the number of username changes. Each of the next n lines contains the actual changes, one per line. The changes are written as "pi ci" (without the quotes), where pi (1 ≤ pi ≤ 200000) is the number of occurrences of letter ci, ci is a lowercase Latin letter. It is guaranteed that the operations are correct, that is, the letter to be deleted always exists, and after all operations not all letters are deleted from the name. The letters' occurrences are numbered starting from 1.

Output format:
Print a single string — the user's final name after all changes are applied to it.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Note:
Let's consider the first sample. Initially we have name "bacbac"; the first operation transforms it into "bacbc", the second one — to "acbc", and finally, the third one transforms it into "acb".

Example input:
2
bac
3
2 a
1 b
2 c

Example output:
acb

Example input:
1
abacaba
4
1 a
1 a
1 c
2 b

Example output:
baa

Editorial:
Palindrome pairs
Contest: VK Cup 2012 Qualification Round 2
Difficulty rating: 1500
Tags: *special, brute force, dp, strings

You are given a non-empty string s consisting of lowercase letters. Find the number of pairs of non-overlapping palindromic substrings of this string.

In a more formal way, you have to find the quantity of tuples (a, b, x, y) such that 1 ≤ a ≤ b < x ≤ y ≤ |s| and substrings s[a... b], s[x... y] are palindromes.

A palindrome is a string that can be read the same way from left to right and from right to left. For example, "abacaba", "z", "abba" are palindromes.

A substring s[i... j] (1 ≤ i ≤ j ≤ |s|) of string s = s1s2... s|s| is a string sisi + 1... sj. For example, substring s[2...4] of string s = "abacaba" equals "bac".

Input format:
The first line of input contains a non-empty string s which consists of lowercase letters ('a'...'z'), s contains at most 2000 characters.

Output format:
Output a single number — the quantity of pairs of non-overlapping palindromic substrings of s.

Please do not use the %lld format specifier to read or write 64-bit integers in С++. It is preferred to use cin, cout streams or the %I64d format specifier.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
aa

Example output:
1

Example input:
aaa

Example output:
5

Editorial:
Zebra Tower
Contest: VK Cup 2012 Qualification Round 2
Difficulty rating: 1700
Tags: *special, data structures, greedy, sortings

Little Janet likes playing with cubes. Actually, she likes to play with anything whatsoever, cubes or tesseracts, as long as they are multicolored. Each cube is described by two parameters — color ci and size si. A Zebra Tower is a tower that consists of cubes of exactly two colors. Besides, the colors of the cubes in the tower must alternate (colors of adjacent cubes must differ). The Zebra Tower should have at least two cubes. There are no other limitations. The figure below shows an example of a Zebra Tower.

A Zebra Tower's height is the sum of sizes of all cubes that form the tower. Help little Janet build the Zebra Tower of the maximum possible height, using the available cubes.

Input format:
The first line contains an integer n (2 ≤ n ≤ 105) — the number of cubes. Next n lines contain the descriptions of the cubes, one description per line. A cube description consists of two space-separated integers ci and si (1 ≤ ci, si ≤ 109) — the i-th cube's color and size, correspondingly. It is guaranteed that there are at least two cubes of different colors.

Output format:
Print the description of the Zebra Tower of the maximum height in the following form. In the first line print the tower's height, in the second line print the number of cubes that form the tower, and in the third line print the space-separated indices of cubes in the order in which they follow in the tower from the bottom to the top. Assume that the cubes are numbered from 1 to n in the order in which they were given in the input.

If there are several existing Zebra Towers with maximum heights, it is allowed to print any of them.

Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.

Constraints:
Time limit: 1.5 s
Memory limit: 256.0 MB

Example input:
4
1 2
1 3
2 4
3 3

Example output:
9
3
2 3 1

Example input:
2
1 1
2 1

Example output:
2
2
2 1

Editorial:
Technical Support
Contest: Codeforces Round 829 (Div. 2)
Difficulty rating: 800
Tags: greedy

You work in the quality control department of technical support for a large company. Your job is to make sure all client issues have been resolved.

Today you need to check a copy of a dialog between a client and a technical support manager. According to the rules of work, each message of the client must be followed by one or several messages, which are the answer of a support manager. However, sometimes clients ask questions so quickly that some of the manager's answers to old questions appear after the client has asked some new questions.

Due to the privacy policy, the full text of messages is not available to you, only the order of messages is visible, as well as the type of each message: a customer question or a response from the technical support manager. It is guaranteed that the dialog begins with the question of the client.

You have to determine, if this dialog may correspond to the rules of work described above, or the rules are certainly breached.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 500$$$). Description of the test cases follows.

The first line of each test case contains one integer $$$n$$$ ($$$1 \le n \le 100$$$) — the total number of messages in the dialog.

The second line of each test case consists of $$$n$$$ characters "Q" and "A", describing types of messages in the dialog in chronological order. Character "Q" denotes the message with client question, and character "A" — the message with technical support manager answer. It is guaranteed that the first character in the line equals to "Q".

Output format:
For each test case print "Yes" (without quotes) if dialog may correspond to the rules of work, or "No" (without quotes) otherwise.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first test case the two questions from the client are followed with two specialist's answers. So this dialog may correspond to the rules of work.

In the second test case one of the first two questions was not answered.

In the third test case the technical support manager sent two messaged as the answer to the only message of the client.

Example input:
5
4
QQAA
4
QQAQ
3
QAA
1
Q
14
QAQQAQAAQQQAAA

Example output:
Yes
No
Yes
No
Yes

Editorial:
Let's process each character of the string from left to right and store the number of unanswered questions $$$cnt$$$. Initially this value equals to zero. Consider the $$$i$$$-th character of the string. If it equals to "Q", increase $$$cnt$$$ by one. If it equals to "A", decrease $$$cnt$$$ by one. If $$$cnt$$$ has become negative, it means that some of the questions was answered several times. In this case let's assign zero to $$$cnt$$$.
If $$$cnt$$$ will be equal to zero after processing all string, then all questions were answered, and the answer is "Yes". Otherwise, the answer is "No".
Time complexity: $$$\mathcal{O}(n)$$$ for each test case.