1337xyz1337xyz/codeforces-editorial-full-2026-07-16 huggingface dataset:
Non-Palindromic Substring
Contest: Codeforces Round 934 (Div. 1)
Difficulty rating: 2000
Tags: hashing, implementation, math, strings

A string $$$t$$$ is said to be $$$k$$$-good if there exists at least one substring$$$^\dagger$$$ of length $$$k$$$ which is not a palindrome$$$^\ddagger$$$. Let $$$f(t)$$$ denote the sum of all values of $$$k$$$ such that the string $$$t$$$ is $$$k$$$-good.

You are given a string $$$s$$$ of length $$$n$$$. You will have to answer $$$q$$$ of the following queries:

- Given $$$l$$$ and $$$r$$$ ($$$l < r$$$), find the value of $$$f(s_ls_{l + 1}\ldots s_r)$$$.

$$$^\dagger$$$ A substring of a string $$$z$$$ is a contiguous segment of characters from $$$z$$$. For example, "$$$\mathtt{defor}$$$", "$$$\mathtt{code}$$$" and "$$$\mathtt{o}$$$" are all substrings of "$$$\mathtt{codeforces}$$$" while "$$$\mathtt{codes}$$$" and "$$$\mathtt{aaa}$$$" are not.

$$$^\ddagger$$$ A palindrome is a string that reads the same backwards as forwards. For example, the strings "$$$\texttt{z}$$$", "$$$\texttt{aa}$$$" and "$$$\texttt{tacocat}$$$" are palindromes while "$$$\texttt{codeforces}$$$" and "$$$\texttt{ab}$$$" are not.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 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 \le 2 \cdot 10^5, 1 \le q \le 2 \cdot 10^5$$$), the size of the string and the number of queries respectively.

The second line of each test case contains the string $$$s$$$. It is guaranteed the string $$$s$$$ only contains lowercase English characters.

The next $$$q$$$ lines each contain two integers, $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$).

It is guaranteed the sum of $$$n$$$ and the sum of $$$q$$$ both do not exceed $$$2 \cdot 10^5$$$.

Output format:
For each query, output $$$f(s_ls_{l + 1}\ldots s_r)$$$.

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

Note:
In the first query of the first test case, the string is $$$\mathtt{aaab}$$$. $$$\mathtt{aaab}$$$, $$$\mathtt{aab}$$$ and $$$\mathtt{ab}$$$ are all substrings that are not palindromes, and they have lengths $$$4$$$, $$$3$$$ and $$$2$$$ respectively. Thus, the string is $$$2$$$-good, $$$3$$$-good and $$$4$$$-good. Hence, $$$f(\mathtt{aaab}) = 2 + 3 + 4 = 9$$$.

In the second query of the first test case, the string is $$$\mathtt{aaa}$$$. There are no non-palindromic substrings. Hence, $$$f(\mathtt{aaa}) = 0$$$.

In the first query of the second test case, the string is $$$\mathtt{abc}$$$. $$$\mathtt{ab}$$$, $$$\mathtt{bc}$$$ and $$$\mathtt{abc}$$$ are all substrings that are not palindromes, and they have lengths $$$2$$$, $$$2$$$ and $$$3$$$ respectively. Thus, the string is $$$2$$$-good and $$$3$$$-good. Hence, $$$f(\mathtt{abc}) = 2 + 3 = 5$$$. Note that even though there are $$$2$$$ non-palindromic substrings of length $$$2$$$, we count it only once.

Example input:
5
4 4
aaab
1 4
1 3
3 4
2 4
3 2
abc
1 3
1 2
5 4
pqpcc
1 5
4 5
1 3
2 4
2 1
aa
1 2
12 1
steponnopets
1 12

Example output:
9
0
2
5
5
2
14
0
2
5
0
65

Editorial:
Counting Is Fun (Easy Version)
Contest: Codeforces Round 934 (Div. 1)
Difficulty rating: 2400
Tags: brute force, combinatorics, dp, math

This is the easy version of the problem. The only difference between the two versions is the constraint on $$$n$$$. You can make hacks only if both versions of the problem are solved.

An array $$$b$$$ of $$$m$$$ non-negative integers is said to be good if all the elements of $$$b$$$ can be made equal to $$$0$$$ using the following operation some (possibly, zero) times:

- Select two distinct indices $$$l$$$ and $$$r$$$ ($$$1 \leq l \color{red}{<} r \leq m$$$) and subtract $$$1$$$ from all $$$b_i$$$ such that $$$l \leq i \leq r$$$.

You are given two positive integers $$$n$$$, $$$k$$$ and a prime number $$$p$$$.

Over all $$$(k+1)^n$$$ arrays of length $$$n$$$ such that $$$0 \leq a_i \leq k$$$ for all $$$1 \leq i \leq n$$$, count the number of good arrays.

Since the number might be too large, you are only required to find it modulo $$$p$$$.

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

The first line of each test case contains three positive integers $$$n$$$, $$$k$$$ and $$$p$$$ ($$$3 \leq n \leq 400$$$, $$$1 \leq k \leq n$$$, $$$10^8 < p < 10^9$$$) — the length of the array $$$a$$$, the upper bound on the elements of $$$a$$$ and modulus $$$p$$$.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and $$$p$$$ is prime.

Output format:
For each test case, on a new line, output the number of good arrays modulo $$$p$$$.

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

Note:
In the first test case, the $$$4$$$ good arrays $$$a$$$ are:

- $$$[0,0,0]$$$;
- $$$[0,1,1]$$$;
- $$$[1,1,0]$$$;
- $$$[1,1,1]$$$.

Example input:
4
3 1 998244853
4 1 998244353
3 2 998244353
343 343 998244353

Example output:
4
7
10
456615865

Editorial:
Counting Is Fun (Hard Version)
Contest: Codeforces Round 934 (Div. 1)
Difficulty rating: 2800
Tags: combinatorics, dp

This is the hard version of the problem. The only difference between the two versions is the constraint on $$$n$$$. You can make hacks only if both versions of the problem are solved.

An array $$$b$$$ of $$$m$$$ non-negative integers is said to be good if all the elements of $$$b$$$ can be made equal to $$$0$$$ using the following operation some (possibly, zero) times:

- Select two distinct indices $$$l$$$ and $$$r$$$ ($$$1 \leq l \color{red}{<} r \leq m$$$) and subtract $$$1$$$ from all $$$b_i$$$ such that $$$l \leq i \leq r$$$.

You are given two positive integers $$$n$$$, $$$k$$$ and a prime number $$$p$$$.

Over all $$$(k+1)^n$$$ arrays of length $$$n$$$ such that $$$0 \leq a_i \leq k$$$ for all $$$1 \leq i \leq n$$$, count the number of good arrays.

Since the number might be too large, you are only required to find it modulo $$$p$$$.

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

The first line of each test case contains three positive integers $$$n$$$, $$$k$$$ and $$$p$$$ ($$$3 \leq n \leq 3000$$$, $$$1 \leq k \leq n$$$, $$$10^8 < p < 10^9$$$) — the length of the array $$$a$$$, the upper bound on the elements of $$$a$$$ and modulus $$$p$$$.

It is guaranteed that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^7$$$, and $$$p$$$ is prime.

Output format:
For each test case, on a new line, output the number of good arrays modulo $$$p$$$.

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

Note:
In the first test case, the $$$4$$$ good arrays $$$a$$$ are:

- $$$[0,0,0]$$$;
- $$$[0,1,1]$$$;
- $$$[1,1,0]$$$;
- $$$[1,1,1]$$$.

Example input:
4
3 1 998244853
4 1 998244353
3 2 998244353
343 343 998244353

Example output:
4
7
10
456615865

Editorial:
Minimum Hamming Distance
Contest: Codeforces Round 934 (Div. 1)
Difficulty rating: 3500
Tags: dp

You are given a binary string$$$^\dagger$$$ $$$s$$$ of length $$$n$$$.

A binary string $$$p$$$ of the same length $$$n$$$ is called good if for every $$$i$$$ ($$$1 \leq i \leq n$$$), there exist indices $$$l$$$ and $$$r$$$ such that:

- $$$1 \leq l \leq i \leq r \leq n$$$
- $$$s_i$$$ is a mode$$$^\ddagger$$$ of the string $$$p_lp_{l+1}\ldots p_r$$$

You are given another binary string $$$t$$$ of length $$$n$$$. Find the minimum Hamming distance$$$^\S$$$ between $$$t$$$ and any good string $$$g$$$.

$$$^\dagger$$$ A binary string is a string that only consists of characters $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$.

$$$^\ddagger$$$ Character $$$c$$$ is a mode of string $$$p$$$ of length $$$m$$$ if the number of occurrences of $$$c$$$ in $$$p$$$ is at least $$$\lceil \frac{m}{2} \rceil$$$. For example, $$$\mathtt{0}$$$ is a mode of $$$\mathtt{010}$$$, $$$\mathtt{1}$$$ is not a mode of $$$\mathtt{010}$$$, and both $$$\mathtt{0}$$$ and $$$\mathtt{1}$$$ are modes of $$$\mathtt{011010}$$$.

$$$^\S$$$ The Hamming distance of strings $$$a$$$ and $$$b$$$ of length $$$m$$$ is the number of indices $$$i$$$ such that $$$1 \leq i \leq m$$$ and $$$a_i \neq b_i$$$.

Input format:
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 a single integer $$$n$$$ ($$$1 \le n \le 10^4$$$) — the length of the binary string $$$s$$$.

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$ consisting of characters 0 and 1.

The third line of each test case contains a binary string $$$t$$$ of length $$$n$$$ consisting of characters 0 and 1.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$, with the additional assurance that the sum of $$$n^2$$$ over all test cases does not exceed $$$10^8$$$

Output format:
For each test case, print the minimum Hamming distance between $$$t$$$ and any good string $$$g$$$.

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

Note:
In the first test case, $$$g=\mathtt{000}$$$ is a good string which has Hamming distance $$$0$$$ from $$$t$$$.

In the second test case, $$$g=\mathtt{0011}$$$ is a good string which has Hamming distance $$$2$$$ from $$$t$$$. It can be proven that there are no good strings with Hamming distance less than $$$2$$$ from $$$t$$$.

In the third test case, $$$g=\mathtt{001100}$$$ is a good string which has Hamming distance $$$1$$$ from $$$t$$$.

Example input:
3
3
000
000
4
0000
1111
6
111111
000100

Example output:
0
2
1

Editorial:
Down the Hatch!
Contest: Codeforces Round 193 (Div. 2)
Difficulty rating: 1300
Tags: implementation

Everybody knows that the Berland citizens are keen on health, especially students. Berland students are so tough that all they drink is orange juice!

Yesterday one student, Vasya and his mates made some barbecue and they drank this healthy drink only. After they ran out of the first barrel of juice, they decided to play a simple game. All n people who came to the barbecue sat in a circle (thus each person received a unique index bi from 0 to n - 1). The person number 0 started the game (this time it was Vasya). All turns in the game were numbered by integers starting from 1. If the j-th turn was made by the person with index bi, then this person acted like that:

1. he pointed at the person with index (bi + 1) mod n either with an elbow or with a nod (x mod y is the remainder after dividing x by y);
2. if j ≥ 4 and the players who had turns number j - 1, j - 2, j - 3, made during their turns the same moves as player bi on the current turn, then he had drunk a glass of juice;
3. the turn went to person number (bi + 1) mod n.

The person who was pointed on the last turn did not make any actions.

The problem was, Vasya's drunk too much juice and can't remember the goal of the game. However, Vasya's got the recorded sequence of all the participants' actions (including himself). Now Vasya wants to find out the maximum amount of juice he could drink if he played optimally well (the other players' actions do not change). Help him.

You can assume that in any scenario, there is enough juice for everybody.

Input format:
The first line contains a single integer n (4 ≤ n ≤ 2000) — the number of participants in the game. The second line describes the actual game: the i-th character of this line equals 'a', if the participant who moved i-th pointed at the next person with his elbow, and 'b', if the participant pointed with a nod. The game continued for at least 1 and at most 2000 turns.

Output format:
Print a single integer — the number of glasses of juice Vasya could have drunk if he had played optimally well.

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

Note:
In both samples Vasya has got two turns — 1 and 5. In the first sample, Vasya could have drunk a glass of juice during the fifth turn if he had pointed at the next person with a nod. In this case, the sequence of moves would look like "abbbb". In the second sample Vasya wouldn't drink a single glass of juice as the moves performed during turns 3 and 4 are different.

Example input:
4
abbba

Example output:
1

Example input:
4
abbab

Example output:
0

Editorial:
Maximum Absurdity
Contest: Codeforces Round 193 (Div. 2)
Difficulty rating: 1500
Tags: data structures, dp, implementation

Reforms continue entering Berland. For example, during yesterday sitting the Berland Parliament approved as much as n laws (each law has been assigned a unique number from 1 to n). Today all these laws were put on the table of the President of Berland, G.W. Boosch, to be signed.

This time mr. Boosch plans to sign 2k laws. He decided to choose exactly two non-intersecting segments of integers from 1 to n of length k and sign all laws, whose numbers fall into these segments. More formally, mr. Boosch is going to choose two integers a, b (1 ≤ a ≤ b ≤ n - k + 1, b - a ≥ k) and sign all laws with numbers lying in the segments [a; a + k - 1] and [b; b + k - 1] (borders are included).

As mr. Boosch chooses the laws to sign, he of course considers the public opinion. Allberland Public Opinion Study Centre (APOSC) conducted opinion polls among the citizens, processed the results into a report and gave it to the president. The report contains the absurdity value for each law, in the public opinion. As mr. Boosch is a real patriot, he is keen on signing the laws with the maximum total absurdity. Help him.

Input format:
The first line contains two integers n and k (2 ≤ n ≤ 2·105, 0 < 2k ≤ n) — the number of laws accepted by the parliament and the length of one segment in the law list, correspondingly. The next line contains n integers x1, x2, ..., xn — the absurdity of each law (1 ≤ xi ≤ 109).

Output format:
Print two integers a, b — the beginning of segments that mr. Boosch should choose. That means that the president signs laws with numbers from segments [a; a + k - 1] and [b; b + k - 1]. If there are multiple solutions, print the one with the minimum number a. If there still are multiple solutions, print the one with the minimum b.

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

Note:
In the first sample mr. Boosch signs laws with numbers from segments [1;2] and [4;5]. The total absurdity of the signed laws equals 3 + 6 + 1 + 6 = 16.

In the second sample mr. Boosch signs laws with numbers from segments [1;2] and [3;4]. The total absurdity of the signed laws equals 1 + 1 + 1 + 1 = 4.

Example input:
5 2
3 6 1 1 6

Example output:
1 4

Example input:
6 2
1 1 1 1 1 1

Example output:
1 3

Editorial:
Students' Revenge
Contest: Codeforces Round 193 (Div. 2)
Difficulty rating: 2200
Tags: data structures, greedy, sortings

A student's life is fraught with complications. Some Berland University students know this only too well. Having studied for two years, they contracted strong antipathy towards the chairperson of some department. Indeed, the person in question wasn't the kindest of ladies to begin with: prone to reforming groups, banning automatic passes and other mean deeds. At last the students decided that she just can't get away with all this anymore...

The students pulled some strings on the higher levels and learned that the next University directors' meeting is going to discuss n orders about the chairperson and accept exactly p of them. There are two values assigned to each order: ai is the number of the chairperson's hairs that turn grey if she obeys the order and bi — the displeasement of the directors if the order isn't obeyed. The students may make the directors pass any p orders chosen by them. The students know that the chairperson will obey exactly k out of these p orders. She will pick the orders to obey in the way that minimizes first, the directors' displeasement and second, the number of hairs on her head that turn grey.

The students want to choose p orders in the way that maximizes the number of hairs on the chairperson's head that turn grey. If there are multiple ways to accept the orders, then the students are keen on maximizing the directors' displeasement with the chairperson's actions. Help them.

Input format:
The first line contains three integers n (1 ≤ n ≤ 105), p (1 ≤ p ≤ n), k (1 ≤ k ≤ p) — the number of orders the directors are going to discuss, the number of orders to pass and the number of orders to be obeyed by the chairperson, correspondingly. Each of the following n lines contains two integers ai and bi (1 ≤ ai, bi ≤ 109), describing the corresponding order.

Output format:
Print in an arbitrary order p distinct integers — the numbers of the orders to accept so that the students could carry out the revenge. The orders are indexed from 1 to n in the order they occur in the input. If there are multiple solutions, you can print any of them.

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

Note:
In the first sample one of optimal solutions is to pass orders 1, 2, 3. In this case the chairperson obeys orders number 1 and 2. She gets 10 new grey hairs in the head and the directors' displeasement will equal 3. Note that the same result can be achieved with order 4 instead of order 3.

In the second sample, the chairperson can obey all the orders, so the best strategy for the students is to pick the orders with the maximum sum of ai values. The chairperson gets 58 new gray hairs and the directors' displeasement will equal 0.

Example input:
5 3 2
5 6
5 8
1 3
4 3
4 11

Example output:
3 1 2

Example input:
5 3 3
10 18
18 17
10 20
20 18
20 18

Example output:
2 4 5

Editorial:
Binary Key
Contest: Codeforces Round 193 (Div. 2)
Difficulty rating: 2400
Tags: dp, greedy, implementation

Let's assume that p and q are strings of positive length, called the container and the key correspondingly, string q only consists of characters 0 and 1. Let's take a look at a simple algorithm that extracts message s from the given container p:

In the given pseudocode i, j are integer variables, s is a string, '=' is an assignment operator, '==' is a comparison operation, '[]' is the operation of obtaining the string character with the preset index, '<>' is an empty string. We suppose that in all strings the characters are numbered starting from zero.

We understand that implementing such algorithm is quite easy, so your task is going to be slightly different. You need to construct the lexicographically minimum key of length k, such that when it is used, the algorithm given above extracts message s from container p (otherwise find out that such key doesn't exist).

Input format:
The first two lines of the input are non-empty strings p and s (1 ≤ |p| ≤ 106, 1 ≤ |s| ≤ 200), describing the container and the message, correspondingly. The strings can contain any characters with the ASCII codes from 32 to 126, inclusive.

The third line contains a single integer k (1 ≤ k ≤ 2000) — the key's length.

Output format:
Print the required key (string of length k, consisting only of characters 0 and 1). If the key doesn't exist, print the single character 0.

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

Note:
String x = x1x2... xp is lexicographically smaller than string y = y1y2... yq, if either p < q and x1 = y1, x2 = y2, ... , xp = yp, or there exists such integer r (0 ≤ r < min(p, q)) that x1 = y1, x2 = y2, ... , xr = yr and xr + 1 < yr + 1. Symbols are compared according to their ASCII codes.

Example input:
abacaba
aba
6

Example output:
100001

Example input:
abacaba
aba
3

Example output:
0

Editorial:
Liars and Serge
Contest: Codeforces Round 156 (Div. 1)
Difficulty rating: 2700
Tags: dp

There are n people, sitting in a line at the table. For each person we know that he always tells either the truth or lies.

Little Serge asked them: how many of you always tell the truth? Each of the people at the table knows everything (who is an honest person and who is a liar) about all the people at the table. The honest people are going to say the correct answer, the liars are going to say any integer from 1 to n, which is not the correct answer. Every liar chooses his answer, regardless of the other liars, so two distinct liars may give distinct answer.

Serge does not know any information about the people besides their answers to his question. He took a piece of paper and wrote n integers a1, a2, ..., an, where ai is the answer of the i-th person in the row. Given this sequence, Serge determined that exactly k people sitting at the table apparently lie.

Serge wonders, how many variants of people's answers (sequences of answers a of length n) there are where one can say that exactly k people sitting at the table apparently lie. As there can be rather many described variants of answers, count the remainder of dividing the number of the variants by 777777777.

Input format:
The first line contains two integers n, k, (1 ≤ k ≤ n ≤ 28). It is guaranteed that n — is the power of number 2.

Output format:
Print a single integer — the answer to the problem modulo 777777777.

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

Example input:
1 1

Example output:
0

Example input:
2 1

Example output:
2

Editorial:
Lucky Arrays
Contest: Codeforces Round 156 (Div. 1)
Difficulty rating: 2400
Tags: data structures

Little Maxim loves interesting problems. He decided to share one such problem with you.

Initially there is an array a, consisting of n zeroes. The elements of the array are indexed, starting from 1. Then follow queries to change array a. Each query is characterized by two integers vi, ti. In the answer to the query we should make the vi-th array element equal ti (avi = ti; 1 ≤ vi ≤ n).

Maxim thinks that some pairs of integers (x, y) are good and some are not. Maxim thinks that array a, consisting of n integers, is lucky, if for all integer i, (1 ≤ i ≤ n - 1) the pair of integers (ai, ai + 1) — is good. Note that the order of numbers in the pairs is important, that is, specifically, (1, 2) ≠ (2, 1).

After each query to change array a Maxim wants to know, how many ways there are to replace all zeroes in array a with integers from one to three so as to make the resulting array (without zeroes) lucky. Of course, distinct zeroes can be replaced by distinct integers.

Maxim told you the sequence of queries and all pairs of integers he considers lucky. Help Maxim, solve this problem for him.

Input format:
The first line contains integers n and m (1 ≤ n, m ≤ 77777) — the number of elements in the array and the number of commands.

The next three lines contain matrix w, consisting only of zeroes and ones; the j-th number in the i-th of these lines — wi, j. If wi, j = 1 (1 ≤ i, j ≤ 3), then pair (i, j) is good, otherwise it is not good. Matrix does not have to be symmetric relative to the main diagonal.

Next m lines contain pairs of integers vi, ti (1 ≤ vi ≤ n, 0 ≤ ti ≤ 3) — the queries to change the array.

Output format:
Print m integers — the i-th number should equal to the number of ways to replace all zeroes in array a (changed after the i-th query) by integers from one to three so as to make the resulting array (without zeroes) lucky. Separate the numbers by whitespaces. As the answers can be rather large, print the remainder from dividing them by 777777777.

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

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

Example output:
3
6
1
1
2
2
1
3
3
6

Editorial: