1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Number Replacement
Contest: Codeforces Round  828 (Div. 3)
Difficulty rating: 800
Tags: greedy, implementation

An integer array $$$a_1, a_2, \ldots, a_n$$$ is being transformed into an array of lowercase English letters using the following prodecure:

While there is at least one number in the array:

- Choose any number $$$x$$$ from the array $$$a$$$, and any letter of the English alphabet $$$y$$$.
- Replace all occurrences of number $$$x$$$ with the letter $$$y$$$.

For example, if we initially had an array $$$a = [2, 3, 2, 4, 1]$$$, then we could transform it the following way:

- Choose the number $$$2$$$ and the letter c. After that $$$a = [c, 3, c, 4, 1]$$$.
- Choose the number $$$3$$$ and the letter a. After that $$$a = [c, a, c, 4, 1]$$$.
- Choose the number $$$4$$$ and the letter t. After that $$$a = [c, a, c, t, 1]$$$.
- Choose the number $$$1$$$ and the letter a. After that $$$a = [c, a, c, t, a]$$$.

After the transformation all letters are united into a string, in our example we get the string "cacta".

Having the array $$$a$$$ and the string $$$s$$$ determine if the string $$$s$$$ could be got from the array $$$a$$$ after the described transformation?

Input format:
The first line contains a single integer $$$t$$$ $$$(1 \leq t \leq 10^3$$$) — the number of test cases.

Then the description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 50$$$) — the length of the array $$$a$$$ and the string $$$s$$$.

The second line of each test case contains exactly $$$n$$$ integers: $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 50$$$) — the elements of the array $$$a$$$.

The third line of each test case contains a string $$$s$$$ of length $$$n$$$, consisting of lowercase English letters.

Output format:
For each test case, output "YES", if we can get the string $$$s$$$ from the array $$$a$$$, and "NO" otherwise. You can output each letter in any case.

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

Note:
The first test case corresponds to the sample described in the statement.

In the second test case we can choose the number $$$50$$$ and the letter a.

In the third test case we can choose the number $$$11$$$ and the letter a, after that $$$a = [a, 22]$$$. Then we choose the number $$$22$$$ and the letter b and get $$$a = [a, b]$$$.

In the fifth test case we can change all numbers one by one to the letter a.

Example input:
7
5
2 3 2 4 1
cacta
1
50
a
2
11 22
ab
4
1 2 2 1
aaab
5
1 2 3 2 1
aaaaa
6
1 10 2 9 3 8
azzfdb
7
1 2 3 4 1 1 2
abababb

Example output:
YES
YES
YES
NO
YES
YES
NO

Editorial:
Let's note that if $$$a_i = a_j$$$, then $$$s_i$$$ must be equal to $$$s_j$$$, since we must change the same value to the same letter. If we check this for all pairs of $$$i$$$ and $$$j$$$ and find no such contradictions, then the answer is "YES", otherwise "NO".
We got the solution for $$$O(n^2)$$$ for one test case.
Divisible Numbers (easy version)
Contest: Codeforces Round  828 (Div. 3)
Difficulty rating: 1500
Tags: brute force, math, number theory

This is an easy version of the problem. The only difference between an easy and a hard version is the constraints on $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$.

You are given $$$4$$$ positive integers $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ with $$$a < c$$$ and $$$b < d$$$. Find any pair of numbers $$$x$$$ and $$$y$$$ that satisfies the following conditions:

- $$$a < x \leq c$$$, $$$b < y \leq d$$$,
- $$$x \cdot y$$$ is divisible by $$$a \cdot b$$$.

Note that required $$$x$$$ and $$$y$$$ may not exist.

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

The descriptions of the test cases follow.

The only line of each test case contains four integers $$$a$$$, $$$b$$$, $$$c$$$ and $$$d$$$ ($$$1 \leq a < c \leq 10^5$$$, $$$1 \leq b < d \leq 10^5$$$).

Output format:
For each test case print a pair of numbers $$$a < x \leq c$$$ and $$$b < y \leq d$$$ such that $$$x \cdot y$$$ is divisible by $$$a \cdot b$$$. If there are multiple answers, print any of them. If there is no such pair of numbers, then print -1 -1.

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

Example input:
5
1 1 2 2
3 4 5 7
8 9 15 18
12 21 14 24
36 60 48 66

Example output:
2 2
4 6
12 12
-1 -1
-1 -1

Editorial:
Clothes
Contest: Codeforces Beta Round 79 (Div. 2 Only)
Difficulty rating: 1200
Tags: brute force

A little boy Gerald entered a clothes shop and found out something very unpleasant: not all clothes turns out to match. For example, Gerald noticed that he looks rather ridiculous in a smoking suit and a baseball cap.

Overall the shop sells n clothing items, and exactly m pairs of clothing items match. Each item has its price, represented by an integer number of rubles. Gerald wants to buy three clothing items so that they matched each other. Besides, he wants to spend as little money as possible. Find the least possible sum he can spend.

Input format:
The first input file line contains integers n and m — the total number of clothing items in the shop and the total number of matching pairs of clothing items ($$3 \leq n \leq 100, 0 \leq m \leq \frac{n(n-1)}{2}$$).

Next line contains n integers ai (1 ≤ ai ≤ 106) — the prices of the clothing items in rubles.

Next m lines each contain a pair of space-separated integers ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi). Each such pair of numbers means that the ui-th and the vi-th clothing items match each other. It is guaranteed that in each pair ui and vi are distinct and all the unordered pairs (ui, vi) are different.

Output format:
Print the only number — the least possible sum in rubles that Gerald will have to pay in the shop. If the shop has no three clothing items that would match each other, print "-1" (without the quotes).

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

Note:
In the first test there only are three pieces of clothing and they all match each other. Thus, there is only one way — to buy the 3 pieces of clothing; in this case he spends 6 roubles.

The second test only has three pieces of clothing as well, yet Gerald can't buy them because the first piece of clothing does not match the third one. Thus, there are no three matching pieces of clothing. The answer is -1.

In the third example there are 4 pieces of clothing, but Gerald can't buy any 3 of them simultaneously. The answer is -1.

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

Example output:
6

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

Example output:
-1

Editorial:
Sum of Digits
Contest: Codeforces Beta Round 79 (Div. 2 Only)
Difficulty rating: 1000
Tags: implementation

Having watched the last Harry Potter film, little Gerald also decided to practice magic. He found in his father's magical book a spell that turns any number in the sum of its digits. At the moment Gerald learned that, he came across a number n. How many times can Gerald put a spell on it until the number becomes one-digit?

Input format:
The first line contains the only integer n (0 ≤ n ≤ 10100000). It is guaranteed that n doesn't contain any leading zeroes.

Output format:
Print the number of times a number can be replaced by the sum of its digits until it only contains one digit.

Constraints:
Time limit: 2.0 s
Memory limit: 265.0 MB

Note:
In the first sample the number already is one-digit — Herald can't cast a spell.

The second test contains number 10. After one casting of a spell it becomes 1, and here the process is completed. Thus, Gerald can only cast the spell once.

The third test contains number 991. As one casts a spell the following transformations take place: 991 → 19 → 10 → 1. After three transformations the number becomes one-digit.

Example input:
0

Example output:
0

Example input:
10

Example output:
1

Editorial:
Equal or Not Equal
Contest: Educational Codeforces Round 119 (Rated for Div. 2)
Difficulty rating: 800
Tags: constructive algorithms, dsu, implementation

You had $$$n$$$ positive integers $$$a_1, a_2, \dots, a_n$$$ arranged in a circle. For each pair of neighboring numbers ($$$a_1$$$ and $$$a_2$$$, $$$a_2$$$ and $$$a_3$$$, ..., $$$a_{n - 1}$$$ and $$$a_n$$$, and $$$a_n$$$ and $$$a_1$$$), you wrote down: are the numbers in the pair equal or not.

Unfortunately, you've lost a piece of paper with the array $$$a$$$. Moreover, you are afraid that even information about equality of neighboring elements may be inconsistent. So, you are wondering: is there any array $$$a$$$ which is consistent with information you have about equality or non-equality of corresponding pairs?

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Next $$$t$$$ cases follow.

The first and only line of each test case contains a non-empty string $$$s$$$ consisting of characters E and/or N. The length of $$$s$$$ is equal to the size of array $$$n$$$ and $$$2 \le n \le 50$$$. For each $$$i$$$ from $$$1$$$ to $$$n$$$:

- if $$$s_i =$$$ E then $$$a_i$$$ is equal to $$$a_{i + 1}$$$ ($$$a_n = a_1$$$ for $$$i = n$$$);
- if $$$s_i =$$$ N then $$$a_i$$$ is not equal to $$$a_{i + 1}$$$ ($$$a_n \neq a_1$$$ for $$$i = n$$$).

Output format:
For each test case, print YES if it's possible to choose array $$$a$$$ that are consistent with information from $$$s$$$ you know. Otherwise, print NO.

It can be proved, that if there exists some array $$$a$$$, then there exists an array $$$a$$$ of positive integers with values less or equal to $$$10^9$$$.

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

Note:
In the first test case, you can choose, for example, $$$a_1 = a_2 = a_3 = 5$$$.

In the second test case, there is no array $$$a$$$, since, according to $$$s_1$$$, $$$a_1$$$ is equal to $$$a_2$$$, but, according to $$$s_2$$$, $$$a_2$$$ is not equal to $$$a_1$$$.

In the third test case, you can, for example, choose array $$$a = [20, 20, 4, 50, 50, 50, 20]$$$.

In the fourth test case, you can, for example, choose $$$a = [1, 3, 3, 7]$$$.

Example input:
4
EEE
EN
ENNEENE
NENN

Example output:
YES
NO
YES
YES

Editorial:
Let's look at a group of E: it's easy to see that each such a group is equal to the same number. Now, let's look at how these groups are distributed on the circle:
1. If there are no N then all $$$a_i$$$ are just equal to each other. It's okay.
2. If there is exactly one N then from one side, all of them are still in one group, so they should be equal, but from the other side, one pair should have different values. It's contradiction.
3. If there are more than one N then all numbers are divided in several groups with different values. It's okay.
As a result, array $$$a$$$ exists as long as the number of N isn't $$$1$$$.
Business trip
Contest: Codeforces Round 106 (Div. 2)
Difficulty rating: 900
Tags: greedy, implementation, sortings

What joy! Petya's parents went on a business trip for the whole year and the playful kid is left all by himself. Petya got absolutely happy. He jumped on the bed and threw pillows all day long, until...

Today Petya opened the cupboard and found a scary note there. His parents had left him with duties: he should water their favourite flower all year, each day, in the morning, in the afternoon and in the evening. "Wait a second!" — thought Petya. He know for a fact that if he fulfills the parents' task in the i-th (1 ≤ i ≤ 12) month of the year, then the flower will grow by ai centimeters, and if he doesn't water the flower in the i-th month, then the flower won't grow this month. Petya also knows that try as he might, his parents won't believe that he has been watering the flower if it grows strictly less than by k centimeters.

Help Petya choose the minimum number of months when he will water the flower, given that the flower should grow no less than by k centimeters.

Input format:
The first line contains exactly one integer k (0 ≤ k ≤ 100). The next line contains twelve space-separated integers: the i-th (1 ≤ i ≤ 12) number in the line represents ai (0 ≤ ai ≤ 100).

Output format:
Print the only integer — the minimum number of months when Petya has to water the flower so that the flower grows no less than by k centimeters. If the flower can't grow by k centimeters in a year, print -1.

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

Note:
Let's consider the first sample test. There it is enough to water the flower during the seventh and the ninth month. Then the flower grows by exactly five centimeters.

In the second sample Petya's parents will believe him even if the flower doesn't grow at all (k = 0). So, it is possible for Petya not to water the flower at all.

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

Example output:
2

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

Example output:
0

Editorial:
Division into Teams
Contest: Codeforces Round 106 (Div. 2)
Difficulty rating: 1500
Tags: greedy, math, sortings

Petya loves football very much, especially when his parents aren't home. Each morning he comes to the yard, gathers his friends and they play all day. From time to time they have a break to have some food or do some chores (for example, water the flowers).

The key in football is to divide into teams fairly before the game begins. There are n boys playing football in the yard (including Petya), each boy's football playing skill is expressed with a non-negative characteristic ai (the larger it is, the better the boy plays).

Let's denote the number of players in the first team as x, the number of players in the second team as y, the individual numbers of boys who play for the first team as pi and the individual numbers of boys who play for the second team as qi. Division n boys into two teams is considered fair if three conditions are fulfilled:

- Each boy plays for exactly one team (x + y = n).
- The sizes of teams differ in no more than one (|x - y| ≤ 1).
- The total football playing skills for two teams differ in no more than by the value of skill the best player in the yard has. More formally: $$\left| \sum_{i=1}^{x} a_{p_i} - \sum_{i=1}^{y} a_{q_i} \right| \leq \max_{i=1}^{n} a_i$$

Your task is to help guys divide into two teams fairly. It is guaranteed that a fair division into two teams always exists.

Input format:
The first line contains the only integer n (2 ≤ n ≤ 105) which represents the number of guys in the yard. The next line contains n positive space-separated integers, ai (1 ≤ ai ≤ 104), the i-th number represents the i-th boy's playing skills.

Output format:
On the first line print an integer x — the number of boys playing for the first team. On the second line print x integers — the individual numbers of boys playing for the first team. On the third line print an integer y — the number of boys playing for the second team, on the fourth line print y integers — the individual numbers of boys playing for the second team. Don't forget that you should fulfil all three conditions: x + y = n, |x - y| ≤ 1, and the condition that limits the total skills.

If there are multiple ways to solve the problem, print any of them.

The boys are numbered starting from one in the order in which their skills are given in the input data. You are allowed to print individual numbers of boys who belong to the same team in any order.

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

Note:
Let's consider the first sample test. There we send the first and the second boy to the first team and the third boy to the second team. Let's check all three conditions of a fair division. The first limitation is fulfilled (all boys play), the second limitation on the sizes of groups (|2 - 1| = 1 ≤ 1) is fulfilled, the third limitation on the difference in skills ((2 + 1) - (1) = 2 ≤ 2) is fulfilled.

Example input:
3
1 2 1

Example output:
2
1 2
1
3

Example input:
5
2 3 3 1 1

Example output:
3
4 1 3
2
5 2

Editorial:
Coloring Brackets
Contest: Codeforces Round 106 (Div. 2)
Difficulty rating: 1900
Tags: dp

Once Petya read a problem about a bracket sequence. He gave it much thought but didn't find a solution. Today you will face it.

You are given string s. It represents a correct bracket sequence. A correct bracket sequence is the sequence of opening ("(") and closing (")") brackets, such that it is possible to obtain a correct mathematical expression from it, inserting numbers and operators between the brackets. For example, such sequences as "(())()" and "()" are correct bracket sequences and such sequences as ")()" and "(()" are not.

In a correct bracket sequence each bracket corresponds to the matching bracket (an opening bracket corresponds to the matching closing bracket and vice versa). For example, in a bracket sequence shown of the figure below, the third bracket corresponds to the matching sixth one and the fifth bracket corresponds to the fourth one.

You are allowed to color some brackets in the bracket sequence so as all three conditions are fulfilled:

- Each bracket is either not colored any color, or is colored red, or is colored blue.
- For any pair of matching brackets exactly one of them is colored. In other words, for any bracket the following is true: either it or the matching bracket that corresponds to it is colored.
- No two neighboring colored brackets have the same color.

Find the number of different ways to color the bracket sequence. The ways should meet the above-given conditions. Two ways of coloring are considered different if they differ in the color of at least one bracket. As the result can be quite large, print it modulo 1000000007 (109 + 7).

Input format:
The first line contains the single string s (2 ≤ |s| ≤ 700) which represents a correct bracket sequence.

Output format:
Print the only number — the number of ways to color the bracket sequence that meet the above given conditions modulo 1000000007 (109 + 7).

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

Note:
Let's consider the first sample test. The bracket sequence from the sample can be colored, for example, as is shown on two figures below.

The two ways of coloring shown below are incorrect.

Example input:
(())

Example output:
12

Example input:
(()())

Example output:
40

Editorial:
Martian Strings
Contest: Codeforces Round 106 (Div. 2)
Difficulty rating: 2300
Tags: string suffix structures, strings

During the study of the Martians Petya clearly understood that the Martians are absolutely lazy. They like to sleep and don't like to wake up.

Imagine a Martian who has exactly n eyes located in a row and numbered from the left to the right from 1 to n. When a Martian sleeps, he puts a patch on each eye (so that the Martian morning doesn't wake him up). The inner side of each patch has an uppercase Latin letter. So, when a Martian wakes up and opens all his eyes he sees a string s consisting of uppercase Latin letters. The string's length is n.

"Ding dong!" — the alarm goes off. A Martian has already woken up but he hasn't opened any of his eyes. He feels that today is going to be a hard day, so he wants to open his eyes and see something good. The Martian considers only m Martian words beautiful. Besides, it is hard for him to open all eyes at once so early in the morning. So he opens two non-overlapping segments of consecutive eyes. More formally, the Martian chooses four numbers a, b, c, d, (1 ≤ a ≤ b < c ≤ d ≤ n) and opens all eyes with numbers i such that a ≤ i ≤ b or c ≤ i ≤ d. After the Martian opens the eyes he needs, he reads all the visible characters from the left to the right and thus, he sees some word.

Let's consider all different words the Martian can see in the morning. Your task is to find out how many beautiful words are among them.

Input format:
The first line contains a non-empty string s consisting of uppercase Latin letters. The strings' length is n (2 ≤ n ≤ 105). The second line contains an integer m (1 ≤ m ≤ 100) — the number of beautiful words. Next m lines contain the beautiful words pi, consisting of uppercase Latin letters. Their length is from 1 to 1000. All beautiful strings are pairwise different.

Output format:
Print the single integer — the number of different beautiful strings the Martian can see this morning.

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

Note:
Let's consider the sample test. There the Martian can get only the second beautiful string if he opens segments of eyes a = 1, b = 2 and c = 4, d = 5 or of he opens segments of eyes a = 1, b = 2 and c = 6, d = 7.

Example input:
ABCBABA
2
BAAB
ABBA

Example output:
1

Editorial:
Sereja and Dima
Contest: Codeforces Round 223 (Div. 2)
Difficulty rating: 800
Tags: greedy, implementation, two pointers

Sereja and Dima play a game. The rules of the game are very simple. The players have n cards in a row. Each card contains a number, all numbers on the cards are distinct. The players take turns, Sereja moves first. During his turn a player can take one card: either the leftmost card in a row, or the rightmost one. The game ends when there is no more cards. The player who has the maximum sum of numbers on his cards by the end of the game, wins.

Sereja and Dima are being greedy. Each of them chooses the card with the larger number during his move.

Inna is a friend of Sereja and Dima. She knows which strategy the guys are using, so she wants to determine the final score, given the initial state of the game. Help her.

Input format:
The first line contains integer n (1 ≤ n ≤ 1000) — the number of cards on the table. The second line contains space-separated numbers on the cards from left to right. The numbers on the cards are distinct integers from 1 to 1000.

Output format:
On a single line, print two integers. The first number is the number of Sereja's points at the end of the game, the second number is the number of Dima's points at the end of the game.

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

Note:
In the first sample Sereja will take cards with numbers 10 and 2, so Sereja's sum is 12. Dima will take cards with numbers 4 and 1, so Dima's sum is 5.

Example input:
4
4 1 2 10

Example output:
12 5

Example input:
7
1 2 3 4 5 6 7

Example output:
16 12

Editorial:
Sereja and Stairs
Contest: Codeforces Round 223 (Div. 2)
Difficulty rating: 1100
Tags: greedy, implementation, sortings

Sereja loves integer sequences very much. He especially likes stairs.

Sequence a1, a2, ..., a|a| (|a| is the length of the sequence) is stairs if there is such index i (1 ≤ i ≤ |a|), that the following condition is met:

a1 < a2 < ... < ai - 1 < ai > ai + 1 > ... > a|a| - 1 > a|a|.

For example, sequences [1, 2, 3, 2] and [4, 2] are stairs and sequence [3, 1, 2] isn't.

Sereja has m cards with numbers. He wants to put some cards on the table in a row to get a stair sequence. What maximum number of cards can he put on the table?

Input format:
The first line contains integer m (1 ≤ m ≤ 105) — the number of Sereja's cards. The second line contains m integers bi (1 ≤ bi ≤ 5000) — the numbers on the Sereja's cards.

Output format:
In the first line print the number of cards you can put on the table. In the second line print the resulting stairs.

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

Example input:
5
1 2 3 4 5

Example output:
5
5 4 3 2 1

Example input:
6
1 1 2 2 3 3

Example output:
5
1 2 3 2 1

Editorial: