string-suffix-structures

Practice › Codeforces Solutions › Baltic Olympiad in Informatics 2020, Day 2 (IOI, Unofficial Mirror Contest, Unrated) ›

CF 1387C - Viruses

CF 1387C - Viruses Rating: 2900 Tags: *special, dp, shortest paths, string suffix structures Solve time: 1m 43s Verified: no Solution Problem Understanding We are given a system where each “gene” is an integer label, and every gene greater than 1 can expand into a sequence of genes according to a fixed mutation rule. Starting from a single gene $x$, we repeatedly replace any non-terminal gene in the current sequence...

Practice › Codeforces Solutions › Codeforces Global Round 6 ›

CF 1266G - Permutation Concatenation

CF 1266G - Permutation Concatenation Rating: 3300 Tags: string suffix structures Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given a fixed integer $n$. From it, we build a very long sequence by listing every permutation of numbers from $1$ to $n$ in lexicographic order and concatenating them one after another. So the sequence is not arbitrary, it is a repetition of all permutations, arranged in a...

Practice › Codeforces Solutions › Educational Codeforces Round 70 (Rated for Div. 2) ›

CF 1202E - You Are Given Some Strings...

CF 1202E - You Are Given Some Strings... Rating: 2400 Tags: brute force, string suffix structures, strings Solve time: 1m 56s Verified: yes Solution Problem Understanding We are given one long reference string t and a collection of strings s1 … sn . For every ordered pair of strings (si, sj) , we form a new string by concatenating them, then we count how many times this concatenated string appears...

Practice › Codeforces Solutions › Educational Codeforces Round 41 (Rated for Div. 2) ›

CF 961F - k-substrings

CF 961F - k-substrings Rating: 2700 Tags: binary search, hashing, string suffix structures Solve time: 1m 46s Verified: no Solution Problem Understanding We are given a string $s$ of length $n$, and we consider all of its suffixes. For each starting position $k$, the corresponding substring is $s[k..n]$. The task is to analyze each of these suffixes independently. For a fixed suffix $T$, we want to find a string $t$...

Practice › Codeforces Solutions ›

Educational Codeforces Round 41 (Rated for Div. 2)

Educational Codeforces Round 41 (Rated for Div. 2) Div. 2 | 4 problems | 2/4 verified | Difficulty 900-2700 | 4m 42s # Problem Rating Tags Accepted Time ✓ A Tetris 900 implementation 10,850 1m 9s ✓ C Chessboard 1400 bitmasks, brute-force, implementation 5,636 1m 22s ✓ F k-substrings 2700 binary-search, hashing, string-suffix-structures 946 1m 46s G Partitions 2700 combinatorics, math, number-theory 1,611 25s

Practice › Codeforces Solutions › Manthan, Codefest 18 (rated, Div. 1 + Div. 2) ›

CF 1037H - Security

CF 1037H - Security Rating: 3200 Tags: data structures, string suffix structures Solve time: 5m 1s Verified: no Solution Problem Understanding We are given a fixed base string s . Each query selects a contiguous segment s[l..r] and a comparison string x . From that segment, we consider every distinct substring, meaning every string formed by choosing a start i and end j with l ≤ i ≤ j ≤...

Practice › Codeforces Solutions › Codeforces Round 519 by Botan Investments ›

CF 1043G - Speckled Band

CF 1043G - Speckled Band Rating: 3500 Tags: data structures, divide and conquer, hashing, string suffix structures, strings Solve time: 6m 55s Verified: no Solution Problem Understanding We are given a long string and many queries, each asking about a substring. For each substring, we imagine splitting it into several consecutive pieces. Among those pieces, identical pieces are considered the same “band”. The game score is the minimum possible number...

Practice › Codeforces Solutions › Codeforces Global Round 7 ›

CF 1326D2 - Prefix-Suffix Palindrome (Hard version)

CF 1326D2 - Prefix-Suffix Palindrome (Hard version) Rating: 1800 Tags: binary search, greedy, hashing, string suffix structures, strings Solve time: 5m 40s Verified: no Solution Problem Understanding We are given a string and we want to build the longest possible palindrome that can be formed by taking a prefix of the string, a suffix of the string, or both, and concatenating them in that order. The middle of this constructed...

Practice › Codeforces Solutions › Educational Codeforces Round 71 (Rated for Div. 2) ›

CF 1207G - Indie Album

CF 1207G - Indie Album Rating: 2700 Tags: data structures, dfs and similar, hashing, string suffix structures, strings, trees Solve time: 4m 10s Verified: no Solution Problem Understanding We are given a growing collection of strings, where each new string is either a single character or an old string extended by exactly one character at the end. This means the entire system forms a rooted tree: every string points to...

Practice › Codeforces Solutions › Codeforces Round 530 (Div. 1) ›

CF 1098F - Ж-function

CF 1098F - \u0416-function Rating: 3500 Tags: string suffix structures, strings Solve time: 8m 7s Verified: no Solution Problem Understanding We are given a fixed string and many substring queries. For each query, we take the substring and compute a specific aggregate over all its suffixes. For a string, the Z-function at position i measures how long the prefix of the string matches the substring starting at i . The...

Practice › Codeforces Solutions › Educational Codeforces Round 53 (Rated for Div. 2) ›

CF 1073G - Yet Another LCP Problem

CF 1073G - Yet Another LCP Problem Rating: 2600 Tags: data structures, string suffix structures Solve time: 4m 26s Verified: yes Solution Problem Understanding We are given a fixed string, and each query asks us to compare two groups of suffixes of this string. Every element in the query is a starting position in the string, so each position represents the suffix beginning there. For one query, we take every...

Practice › Codeforces Solutions › Codeforces Round 516 (Div. 1, by Moscow Team Olympiad) ›

CF 1063F - String Journey

CF 1063F - String Journey Rating: 3300 Tags: data structures, dp, string suffix structures Solve time: 5m 23s Verified: no Solution Problem Understanding We are given a single string and we want to decompose it into a sequence of progressively shorter substrings, where each substring in the sequence must appear inside the previous one. Additionally, all chosen substrings must appear in the original string in left to right order, without...

Practice › Codeforces Solutions › Codeforces Round 869 (Div. 1) ›

CF 1817F - Entangled Substrings

CF 1817F - Entangled Substrings Rating: 3500 Tags: string suffix structures, strings Solve time: 4m 45s Verified: no Solution Problem Understanding We are given a single string and we are asked to count how many ordered pairs of non-empty substrings $(a, b)$ satisfy a very rigid structural property: every occurrence of $a$ inside the string must always be followed by the same fixed middle string $c$ and then $b$, and...

Practice › Codeforces Solutions › Educational Codeforces Round 134 (Rated for Div. 2) ›

CF 1721E - Prefix Function Queries

CF 1721E - Prefix Function Queries Rating: 2200 Tags: dfs and similar, dp, hashing, string suffix structures, strings, trees Solve time: 3m 4s Verified: no Solution Problem Understanding We are given a fixed reference string and then asked to process many short query strings. For each query, we temporarily append the query string to the reference, compute the prefix function on the resulting concatenation, and output only the prefix function...

Practice › Codeforces Solutions › Educational Codeforces Round 107 (Rated for Div. 2) ›

CF 1511F - Chainword

CF 1511F - Chainword Rating: 2700 Tags: brute force, data structures, dp, matrices, string suffix structures, strings Solve time: 5m 50s Verified: no Solution Problem Understanding We are building strings of length $m$, but the string itself is not the only object we care about. Along with the string, we also choose two independent ways to split it into consecutive segments. Each segment must correspond exactly to one of the...

Practice › Codeforces Solutions › Educational Codeforces Round 97 (Rated for Div. 2) ›

CF 1437G - Death DBMS

CF 1437G - Death DBMS Rating: 2600 Tags: data structures, string suffix structures, strings, trees Solve time: 3m 40s Verified: no Solution Problem Understanding We maintain a fixed collection of strings, each representing a “name”, and each name has an associated value that changes over time. The system supports two operations: updating the value of a single name, and querying a text string to find which stored names appear as...

Practice › Codeforces Solutions › Codeforces Round 459 (Div. 1) ›

CF 917E - Upside Down

CF 917E - Upside Down Rating: 3400 Tags: data structures, string suffix structures, strings, trees Solve time: 2m 47s Verified: yes Solution Problem Understanding The tree describes a network of junctions connected by directed tunnels, where each tunnel carries a lowercase letter. Moving between two junctions means walking along the unique simple path in this tree, and collecting the letters on the edges in order, producing a string. Each query...

Practice › Codeforces Solutions › Codeforces Round 454 (Div. 1, based on Technocup 2018 Elimination Round 4) ›

CF 906E - Reverses

CF 906E - Reverses Rating: 3300 Tags: dp, string suffix structures, strings Solve time: 4m 49s Verified: no Solution Problem Understanding We are given two strings of equal length. The first string, s , is the original string. The second string, t , is obtained after several pairwise disjoint substrings of s were reversed. The hurricane has already performed those reversals and produced t . Our task is to recover...

Practice › Codeforces Solutions › Codecraft-18 and Codeforces Round 458 (Div. 1 + Div. 2, combined) ›

CF 914F - Substrings in a String

CF 914F - Substrings in a String Rating: 3000 Tags: bitmasks, brute force, data structures, string suffix structures, strings Solve time: 2m 54s Verified: yes Solution Problem Understanding We are given a mutable string and a sequence of queries. Each query either changes a character at a specific position or asks how many times a smaller string appears as a substring within a specific substring of the main string. The...

Practice › Codeforces Solutions › Codeforces Round 542 [Alex Lopashev Thanks-Round] (Div. 1) ›

CF 1129C - Morse Code

CF 1129C - Morse Code Rating: 2400 Tags: binary search, data structures, dp, hashing, sortings, string suffix structures, strings Solve time: 1m 24s Verified: no Solution Problem Understanding We are asked to track sequences of English letters encoded in Morse code as we build a string incrementally, one character at a time. The string S starts empty and grows by adding either a dot ( 0 ) or a dash...

Practice › Codeforces Solutions › Codeforces Round 578 (Div. 2) ›

CF 1200E - Compress Words

CF 1200E - Compress Words Rating: 2000 Tags: brute force, hashing, implementation, string suffix structures, strings Solve time: 1m 17s Verified: yes Solution Problem Understanding We are given a sequence of words forming a sentence, and the task is to compress them into a single string by merging them left to right. The merging rule is that when we append a word to the current string, any prefix of the...

Practice › Codeforces Solutions › Codeforces Round 606 (Div. 1, based on Technocup 2020 Elimination Round 4) ›

CF 1276F - Asterisk Substrings

CF 1276F - Asterisk Substrings Rating: 3400 Tags: string suffix structures Solve time: 2m 9s Verified: yes Solution Problem Understanding We are given a string s consisting of lowercase English letters, and we want to count all distinct substrings that appear in s or in any version of s where exactly one character has been replaced by an asterisk. Formally, for each position i , we define a string t_i...

Practice › Codeforces Solutions › Codeforces Global Round 7 ›

CF 1326D1 - Prefix-Suffix Palindrome (Easy version)

CF 1326D1 - Prefix-Suffix Palindrome (Easy version) Rating: 1500 Tags: hashing, string suffix structures, strings Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a string consisting of lowercase English letters, and the task is to construct the longest palindrome by combining a prefix and a suffix of this string. Formally, we need a string t such that it can be split into two parts a and...

Practice › Codeforces Solutions › Codeforces Round 662 (Div. 2) ›

CF 1393E2 - Twilight and Ancient Scroll (harder version)

CF 1393E2 - Twilight and Ancient Scroll (harder version) Rating: 3200 Tags: dp, hashing, implementation, string suffix structures, strings, two pointers Solve time: 2m 20s Verified: no Solution Problem Understanding We are given a sequence of words that are supposed to represent an already sorted “original scroll”. The original property is that if you read the words from top to bottom, they are in non-decreasing lexicographic order. However, each word...

Practice › Codeforces Solutions › Codeforces Round 662 (Div. 2) ›

CF 1393E1 - Twilight and Ancient Scroll (easier version)

CF 1393E1 - Twilight and Ancient Scroll (easier version) Rating: 2800 Tags: dp, hashing, implementation, string suffix structures, strings Solve time: 1m 57s Verified: no Solution Problem Understanding We are given a sequence of words that is supposed to come from an originally sorted list, where the original list was non-decreasing in lexicographic order. However, each original word may have been modified by inserting exactly one extra character somewhere inside...

Practice › Codeforces Solutions › Educational Codeforces Round 94 (Rated for Div. 2) ›

CF 1400F - x-prime Substrings

CF 1400F - x-prime Substrings Rating: 2800 Tags: brute force, dfs and similar, dp, string suffix structures, strings Solve time: 1m 28s Verified: no Solution Problem Understanding We are given a digit string and a small integer $x$. Any contiguous piece of the string has a weight equal to the sum of its digits. Among those substrings whose sum is exactly $x$, some are “dangerous” because they contain an internal...

Practice › Codeforces Solutions ›

Codeforces Global Round 7

Codeforces Global Round 7 Global | 6 problems | 2/6 verified | Difficulty 1000-3500 | 24m 1s # Problem Rating Tags Accepted Time ✓ A Bad Ugly Numbers 1000 constructive-algorithms, number-theory 32,675 2m 55s D1 Prefix-Suffix Palindrome (Easy version) 1500 hashing, string-suffix-structures, strings 13,292 1m 10s ✓ D2 Prefix-Suffix Palindrome (Hard version) 1800 binary-search, greedy, hashing 11,749 5m 40s E Bombs 2400 data-structures, two-pointers 2,420 8m 17s F2 Wise Men...

Practice › Codeforces Solutions › Good Bye 2020 ›

CF 1466G - Song of the Sirens

CF 1466G - Song of the Sirens Rating: 2600 Tags: combinatorics, divide and conquer, hashing, math, string suffix structures, strings Solve time: 2m 56s Verified: no Solution Problem Understanding We start with a short string $s_0$. Another string $t$ of length $n$ controls a recursive construction: $$s_{i+1} = s_i + t_i + s_i$$ Each step doubles the current song and inserts one character in the middle. Queries ask for a...

Practice › Codeforces Solutions › Educational Codeforces Round 101 (Rated for Div. 2) ›

CF 1469E - A Bit Similar

CF 1469E - A Bit Similar Rating: 2400 Tags: bitmasks, brute force, hashing, string suffix structures, strings, two pointers Solve time: 10m 7s Verified: yes Solution Problem Understanding We are asked to find a binary string of length k that is "bit similar" to every substring of length k in a given binary string s of length n . Two strings are bit similar if they share at least one...

Practice › Codeforces Solutions › Технокубок 2021 - Финал ›

CF 1482H - Exam

CF 1482H - Exam Rating: 3400 Tags: data structures, string suffix structures, trees Solve time: 6m 9s Verified: no Solution Problem Understanding We are given a list of distinct ninja names, and we need to count the number of fights that will happen. A fight occurs between two ninjas if one ninja's name is a substring of the other's, and there is no third ninja whose name is also a...

Practice › Codeforces Solutions › Codeforces Round 724 (Div. 2) ›

CF 1536F - Omkar and Akmar

CF 1536F - Omkar and Akmar Rating: 2600 Tags: chinese remainder theorem, combinatorics, constructive algorithms, fft, games, geometry, math, meet-in-the-middle, string suffix structures Solve time: 2m 23s Verified: yes Solution Problem Understanding We are asked to count all possible distinct games played on a circular board with $n$ cells, where two players take turns placing letters A or B . Akmar moves first. A letter cannot be placed adjacent to...

Practice › Codeforces Solutions › Codeforces Round 726 (Div. 2) ›

CF 1537E2 - Erase and Extend (Hard Version)

CF 1537E2 - Erase and Extend (Hard Version) Rating: 2200 Tags: binary search, data structures, greedy, hashing, string suffix structures, strings, two pointers Solve time: 4m 39s Verified: no Solution

Practice › Codeforces Solutions › Codeforces Round 726 (Div. 2) ›

CF 1537E1 - Erase and Extend (Easy Version)

CF 1537E1 - Erase and Extend (Easy Version) Rating: 1600 Tags: binary search, brute force, dp, greedy, hashing, implementation, string suffix structures, strings, two pointers Solve time: 7m 36s Verified: yes Solution Problem Understanding We are given a string s of length n and a target length k . Our goal is to construct a string of length exactly k by performing two operations any number of times: removing the...

Practice › Codeforces Solutions › Codeforces Round 741 (Div. 2) ›

CF 1562E - Rescue Niwen!

CF 1562E - Rescue Niwen! Rating: 2500 Tags: dp, greedy, string suffix structures, strings Solve time: 2m 57s Verified: no Solution Solution Program M computes a double-precision product by expanding each normalized operand into high and low halves, forming four partial products, then discarding all terms that lie strictly to the right of the retained word boundary. The only arithmetic operations that combine values are additions of aligned partial results...

Practice › Codeforces Solutions › Educational Codeforces Round 115 (Rated for Div. 2) ›

CF 1598G - The Sum of Good Numbers

CF 1598G - The Sum of Good Numbers Rating: 3200 Tags: hashing, math, string suffix structures, strings Solve time: 1m 56s Verified: no Solution Problem Understanding We are given a string s representing a sequence of positive integers written consecutively, without any delimiters. Each number contains only nonzero digits. Separately, we are given a "good" integer x , which is also composed entirely of nonzero digits. The task is to...

Practice › Codeforces Solutions › Codeforces Round 758 (Div.1 + Div. 2) ›

CF 1608G - Alphabetic Tree

CF 1608G - Alphabetic Tree Rating: 3500 Tags: binary search, data structures, dfs and similar, hashing, string suffix structures, strings, trees Solve time: 1m 37s Verified: no Solution Problem Understanding We are given a tree with nodes connected by edges, each labeled with a lowercase letter. In addition, we have a collection of strings. For any two nodes in the tree, the path connecting them defines a string by concatenating...

Practice › Codeforces Solutions › Hello 2022 ›

CF 1621I - Two Sequences

CF 1621I - Two Sequences Rating: 3500 Tags: data structures, hashing, string suffix structures Solve time: 1m 41s Verified: no Solution Problem Understanding We are given an array A of length n and asked to repeatedly apply a complex transformation to it. The transformation, called op , builds a new array from an old one by repeatedly finding the lexicographically smallest subarray of increasing lengths and updating the last elements...

Practice › Codeforces Solutions ›

Codeforces Round 809 (Div. 2)

Codeforces Round 809 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 2/6 | Rating range: 800-2400 | Time: 13m 42s Problem Name Rating Tags Solve Time Verified A Another String Minimization Problem 800 2-sat, constructive-algorithms, greedy 1m 52s ✓ B Making Towers 1100 dp, greedy, math 3m 3s ✗ C Qpwoeirut And The City 1400 dp, flows, greedy 1m 51s ✗ D1 Chopping Carrots (Easy Version) 1700 binary-search,...

Practice › Codeforces Solutions › Codeforces Round 809 (Div. 2) ›

CF 1706A - Another String Minimization Problem

CF 1706A - Another String Minimization Problem Rating: 800 Tags: 2-sat, constructive algorithms, greedy, string suffix structures, strings Solve time: 1m 52s Verified: yes Solution Problem Understanding We are asked to construct a string of length m , initially filled with the letter 'B', by performing n operations defined by a sequence a_1, a_2, ..., a_n . Each element a_i represents a choice: during the i -th operation, we can...

Practice › Codeforces Solutions › Educational Codeforces Round 136 (Rated for Div. 2) ›

CF 1739F - Keyboard Design

CF 1739F - Keyboard Design Rating: 2600 Tags: bitmasks, data structures, dp, string suffix structures, strings Solve time: 2m 24s Verified: no Solution That request asks for a complete contest editorial, including a fully correct algorithm, proof, implementation, worked traces, complexity analysis, and tests for a specific Codeforces problem. To produce a reliable editorial, I need to derive and verify the optimal solution first. Since this is a nontrivial 2200-rated...

Practice › Codeforces Solutions › Codeforces Round 846 (Div. 2) ›

CF 1780G - Delicious Dessert

CF 1780G - Delicious Dessert Rating: 2400 Tags: binary search, dsu, hashing, math, number theory, string suffix structures Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given a string s of length n representing Tonio's dessert recipe. A substring of s is called delicious if the number of times it appears in s is divisible by its own length. The task is to count all delicious substrings...

Practice › Codeforces Solutions › Codeforces Round 857 (Div. 1) ›

CF 1801G - A task for substrings

CF 1801G - A task for substrings Rating: 3400 Tags: data structures, string suffix structures, strings Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given a very long text string t and a set of distinct dictionary words s₁, s₂, ..., sₙ . For each query [l, r] , we look only at the substring t[l..r] . Inside that interval we must count how many substrings are...

Practice › Codeforces Solutions › Educational Codeforces Round 157 (Rated for Div. 2) ›

CF 1895D - XOR Construction

CF 1895D - XOR Construction Rating: 1900 Tags: bitmasks, constructive algorithms, data structures, math, string suffix structures, trees Solve time: 2m 49s Verified: yes Solution Problem Understanding We are given the XOR values between consecutive elements of an unknown permutation. Let the required permutation be $b$. For every adjacent pair, we know $$b_i \oplus b_{i+1} = a_i.$$ The array $b$ must contain every integer from $0$ to $n-1$ exactly once....

Practice › Codeforces Solutions › Educational Codeforces Round 160 (Rated for Div. 2) ›

CF 1913F - Palindromic Problem

CF 1913F - Palindromic Problem Rating: 2800 Tags: binary search, data structures, hashing, string suffix structures, strings Solve time: 37s Verified: no Solution Problem Understanding We are given a string consisting of lowercase letters, and we are allowed to change at most one character to any other lowercase letter. The goal is to produce a string that maximizes the number of palindromic substrings. A palindromic substring is any contiguous sequence...

Practice › Codeforces Solutions › Good Bye 2023 ›

CF 1916H2 - Matrix Rank (Hard Version)

CF 1916H2 - Matrix Rank (Hard Version) Rating: 2700 Tags: combinatorics, dp, math, matrices, string suffix structures Solve time: 1m 7s Verified: yes Solution Problem Understanding We are asked to count the number of $n \times n$ matrices over a finite field of size $p$ (integers modulo a prime $p$) that have an exact rank $r$, for every $r$ from 0 to $k$. The key detail is that $n$ can...

Practice › Codeforces Solutions › Educational Codeforces Round 162 (Rated for Div. 2) ›

CF 1923F - Shrink-Reverse

CF 1923F - Shrink-Reverse Rating: 2800 Tags: binary search, brute force, greedy, hashing, implementation, string suffix structures, strings Solve time: 43s Verified: no Solution Problem Understanding We are given a binary string s of length n and a number k representing the maximum number of allowed operations. Each operation can either swap two characters of the string or remove all leading zeros and then reverse the string. The task is...

Practice › Codeforces Solutions ›

April Fools Day Contest 2025

April Fools Day Contest 2025 April Fools | 10 problems | 4/10 verified | Difficulty - | 12m 6s # Problem Rating Tags Accepted Time ✓ A Piecing It Together *special, string-suffix-structures 13,814 39s B Plinko *special, games, interactive 5,992 1m 27s C Would It Be Unrated? *special, binary-search, brute-force 3,744 1m 3s ✓ D Where Am I? *special, geometry 5,301 32s E Pair Count *special, number-theory 785 1m 32s...

Practice › Codeforces Solutions › Codeforces Global Round 26 ›

CF 1984D - ''a'' String Problem

CF 1984D - ''a'' String Problem Rating: 2000 Tags: brute force, hashing, implementation, math, string suffix structures, strings Solve time: 2m 7s Verified: no Solution Problem Understanding We are asked to find the number of nonempty strings $t \neq "a"$ such that a given string $s$ can be split into pieces where each piece is either $t$ or the single character "a", with the additional constraint that at least one...

Practice › Codeforces Solutions ›

Testing Round 19 (Div. 3)

Testing Round 19 (Div. 3) Type: Div. 3 | Problems: 4 | Verified: 3/4 | Rating range: 800-1700 | Time: 4m 56s Problem Name Rating Tags Solve Time Verified A Alternating Sum of Numbers 800 brute-force, implementation, math 1m 27s ✓ B Three Brothers 800 brute-force, implementation, math 1m 11s ✗ C1 Message Transmission Error (easy version) 1400 brute-force, strings 39s ✓ C2 Message Transmission Error (hard version) 1700 hashing,...

Practice › Codeforces Solutions › Testing Round 19 (Div. 3) ›

CF 2010C2 - Message Transmission Error (hard version)

CF 2010C2 - Message Transmission Error (hard version) Rating: 1700 Tags: hashing, string suffix structures, strings, two pointers Solve time: 1m 39s Verified: yes Solution Problem Understanding We are asked to determine whether a given string could have resulted from a very specific transmission error in a network. The error occurs when a message s is sent twice consecutively, and the second copy partially overlaps the first at some non-zero...

Practice › Codeforces Solutions › 2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams) ›

CF 2038I - Polyathlon

CF 2038I - Polyathlon Rating: 2500 Tags: binary search, data structures, hashing, string suffix structures, strings Solve time: 1m 33s Verified: yes Solution Problem Understanding We are asked to simulate a multi-sport elimination competition with a twist: each participant has a binary skill vector indicating which sports they are proficient in. When a sport is played, the participants who lack skill in that sport are eliminated, provided that at least...

Practice › Codeforces Solutions › 2024-2025 ICPC Asia Jakarta Regional Contest (Unrated, Online Mirror, ICPC Rules, Teams Preferred) ›

CF 2045H - Missing Separators

CF 2045H - Missing Separators Rating: 2200 Tags: dp, sortings, string suffix structures, strings Solve time: 1m 41s Verified: no Solution Problem Understanding We are given a single long string made by writing several unknown words one after another in alphabetical order and then removing all separators. The original structure is a dictionary: words are distinct and sorted lexicographically. Our task is to recover any valid decomposition of the string...

Practice › Codeforces Solutions › April Fools Day Contest 2025 ›

CF 2095A - Piecing It Together

CF 2095A - Piecing It Together Rating: - Tags: *special, string suffix structures Solve time: 39s Verified: no Solution I can’t reliably reconstruct the full problem from the screenshot link alone, and I don’t want to risk inventing details and giving you a wrong editorial. Please paste the full problem statement (or at least the input/output format and constraints). Once you send that, I’ll write the complete Codeforces-style editorial in...

Practice › Codeforces Solutions › Educational Codeforces Round 182 (Rated for Div. 2) ›

CF 2144F - Bracket Groups

CF 2144F - Bracket Groups Rating: 2700 Tags: brute force, constructive algorithms, dp, string suffix structures, strings Solve time: 1m 12s Verified: yes Solution Problem Understanding We are given several bracket strings, each of length at most $k$, and we must assign every string to exactly one group. For each group we also construct a single “reference” regular bracket sequence of length exactly $k$. The rule for a group is...

Practice › Codeforces Solutions › 2025 ICPC Asia Taichung Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams) ›

CF 2172H - Shuffling Cards with Problem Solver 68!

CF 2172H - Shuffling Cards with Problem Solver 68! Rating: 2500 Tags: hashing, string suffix structures, strings Solve time: 2m 18s Verified: yes Solution Problem Understanding We are given a deck of $2^k$ cards represented as a string of lowercase letters. The deck can be rotated by moving the first $m$ cards to the end. After this optional rotation, the deck is riffle-shuffled $t$ times. A perfect riffle shuffle splits...

Practice › Codeforces Solutions › 2025-2026 ICPC, NERC, Northern Eurasia Finals (Unrated, Online Mirror, ICPC Rules, Teams Preferred) ›

CF 2181L - LLM Training

CF 2181L - LLM Training Rating: 2800 Tags: math, string suffix structures Solve time: 2m 24s Verified: no Solution Problem Understanding We are given several token sequences, each sequence representing a text where some positions are produced by a language model and others are written directly by a user. Only the positions marked as generated contribute to the training loss. For every generated position, the model predicts the token using...

Practice › Codeforces Solutions › Codeforces Round 1079 (Div. 1) ›

CF 2196E2 - Fuzzy Concatenation (Hard version)

CF 2196E2 - Fuzzy Concatenation (Hard version) Rating: 3000 Tags: binary search, bitmasks, data structures, dp, greedy, string suffix structures Solve time: 1m 35s Verified: yes Solution Problem Understanding We are given a source string s and a target string t . We start with an empty string p and want to build it until it becomes exactly equal to t . The only way to extend p is by...

Practice › Codeforces Solutions › Codeforces Round 1079 (Div. 1) ›

CF 2196E1 - Fuzzy Concatenation (Easy Version)

CF 2196E1 - Fuzzy Concatenation (Easy Version) Rating: 2900 Tags: binary search, bitmasks, brute force, data structures, greedy, string suffix structures Solve time: 2m Verified: no Solution Problem Understanding We are given a source string s and a target string t . We start with an empty string p , and our only goal is to build p until it exactly matches t . The only allowed move is to...

Practice › Codeforces Solutions › Codeforces Round 1083 (Div. 2) ›

CF 2205E - Simons and Dividing the Rhythm

CF 2205E - Simons and Dividing the Rhythm Rating: 2100 Tags: combinatorics, data structures, dp, dsu, math, string suffix structures, strings Solve time: 2m 21s Verified: no Solution Problem Understanding We are asked to count how many arrays $S$ exist such that, after a single sequence of independent subarray reversals, the resulting array equals a given array $T$. The operation allows splitting the array into consecutive segments that cover the...

Practice › Codeforces Solutions › Codeforces Round 1087 (Div. 2) ›

CF 2209E - A Trivial String Problem

CF 2209E - A Trivial String Problem Rating: 2200 Tags: brute force, dp, hashing, string suffix structures, strings Solve time: 1m 51s Verified: no Solution Problem Understanding We are given a string and a set of queries. For each query, we take a substring defined by its endpoints, and for every prefix of this substring, we compute the maximum number of pieces it can be split into such that each...

Practice › Codeforces Solutions › Educational Codeforces Round 189 (Rated for Div. 2) ›

CF 2225F - String Cutting

CF 2225F - String Cutting Rating: - Tags: binary search, brute force, greedy, hashing, string suffix structures, strings Solve time: 1m 51s Verified: no Solution Problem Understanding We are given a string and we are allowed to split it into several consecutive pieces. Every piece must have length at least l , and we are required to produce at least k pieces in total. After choosing a valid cut, all...

Practice › Codeforces Solutions › Codeforces Round 943 (Div. 3) ›

CF 1968G2 - Division + LCP (hard version)

CF 1968G2 - Division + LCP (hard version) Rating: 2200 Tags: binary search, brute force, data structures, dp, hashing, math, string suffix structures, strings Solve time: 1m 37s Verified: no Solution Problem Understanding We are given a string and asked to split it into a fixed number of contiguous pieces. For any such split, we look at how long a common prefix all pieces share, meaning we compare the first...

Practice › Codeforces Solutions › Codeforces Round 943 (Div. 3) ›

CF 1968G1 - Division + LCP (easy version)

CF 1968G1 - Division + LCP (easy version) Rating: 1900 Tags: binary search, data structures, dp, hashing, string suffix structures, strings Solve time: 1m 26s Verified: yes Solution Problem Understanding The problem asks us to split a string into exactly $k$ consecutive substrings and then compute the longest common prefix (LCP) shared among those substrings. For the easy version, the range of $k$ is a single value $l=r$, so we...

Practice › Codeforces Solutions › Codeforces Round 246 (Div. 2) ›

CF 432D - Prefixes and Suffixes

CF 432D - Prefixes and Suffixes Rating: 2000 Tags: dp, string suffix structures, strings, two pointers Solve time: 4m 11s Verified: yes Solution Problem Understanding We are given a single string of uppercase letters. Our goal is to identify all prefixes of the string that are identical to some suffix, and for each such prefix, count how many times it occurs anywhere inside the string as a contiguous substring. For...

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316G2 - Good Substrings

CF 316G2 - Good Substrings Rating: 2200 Tags: string suffix structures Solve time: 3m 7s Verified: no Solution Problem Understanding We are given a source string s . We are interested only in substrings that appear inside s , and we count each distinct substring once, regardless of how many times it occurs. A substring is considered good if it satisfies every rule. Each rule consists of a pattern string...

Practice › Codeforces Solutions › Codeforces Round 189 (Div. 1) ›

CF 319D - Have You Ever Heard About the Word?

CF 319D - Have You Ever Heard About the Word? Rating: 2800 Tags: greedy, hashing, string suffix structures, strings Solve time: 1m 27s Verified: no Solution Problem Understanding We are given a single string and we repeatedly compress certain patterns inside it. The only pattern that matters is a substring that consists of two identical halves placed back to back, so a segment of the form X + X ,...

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316G3 - Good Substrings

CF 316G3 - Good Substrings Rating: 2400 Tags: string suffix structures Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a main string $s$ and several constraints, each constraint consists of a pattern string $p$ and a numeric interval $[l, r]$. For any candidate string $t$, we can count how many times $t$ appears as a substring inside $p$, where occurrences are counted by positions in $p$,...

Practice › Codeforces Solutions ›

Codeforces Round 146 (Div. 1)

Codeforces Round 146 (Div. 1) Div. 1 | 5 problems | 4/5 verified | Difficulty 1600-3000 | 11m 29s # Problem Rating Tags Accepted Time ✓ A LCM Challenge 1600 number-theory 20,976 2m 32s ✓ B Let's Play Osu! 2000 dp, math, probabilities 4,306 1m 33s ✓ C Cyclical Quest 2700 data-structures, string-suffix-structures, strings 2,466 2m 36s ✓ D Graph Game 3000 graphs 573 2m 41s ✓ E Number Challenge...

Practice › Codeforces Solutions › Codeforces Round 146 (Div. 1) ›

CF 235C - Cyclical Quest

CF 235C - Cyclical Quest Rating: 2700 Tags: data structures, string suffix structures, strings Solve time: 2m 36s Verified: yes Solution Problem Understanding We are given one large text string s , which is fixed for the entire input. Then we receive many query strings x . For a query x , we are not interested only in x itself. Any cyclic rotation of x is considered equivalent. For example,...

Practice › Codeforces Solutions › Codeforces Round 144 (Div. 1) ›

CF 232D - Fence

CF 232D - Fence Rating: 2900 Tags: binary search, data structures, string suffix structures Solve time: 6m 50s Verified: no Solution Problem Understanding We have an array of plank heights. A fence piece is simply a contiguous segment. For a query segment $[l,r]$, we must count how many other segments of the same length match it. Matching has three requirements. The two segments must have equal length. They must be...

Practice › Codeforces Solutions ›

Codeforces Beta Round 93 (Div. 1 Only)

Codeforces Beta Round 93 (Div. 1 Only) Div. 1 | 5 problems | 2/5 verified | Difficulty 1700-2900 | 9m 33s # Problem Rating Tags Accepted Time ✓ A Hot Bath 1900 binary-search, brute-force, math 1,597 2m 2s ✓ B Password 1700 binary-search, dp, hashing 24,742 2m 4s ✓ C E-reader Display 2000 constructive-algorithms, greedy 817 2m 23s D Fibonacci Sums 2300 dp, math 946 1m 53s E Pills 2900...

Practice › Codeforces Solutions › Codeforces Round 269 (Div. 2) ›

CF 471D - MUH and Cube Walls

CF 471D - MUH and Cube Walls Rating: 1800 Tags: string suffix structures, strings Solve time: 1m 58s Verified: yes Solution Problem Understanding We have two walls represented by sequences of tower heights. The bears' wall contains n towers, while Horace's wall contains w towers. Horace is allowed to shift his entire wall vertically by any amount. Every tower in his wall must be shifted by the same value, but...

Practice › Codeforces Solutions › MemSQL Start[c]UP 2.0 - Round 1 ›

CF 452E - Three strings

CF 452E - Three strings Rating: 2400 Tags: data structures, dsu, string suffix structures, strings Solve time: 2m 7s Verified: yes Solution Problem Understanding We have three strings. For every length $l$ from $1$ up to the length of the shortest string, we must count how many triples of positions $$(i_1,i_2,i_3)$$ produce three equal substrings of length $l$, one taken from each string. Another way to view the task is...

Practice › Codeforces Solutions ›

Codeforces Round 246 (Div. 2)

Codeforces Round 246 (Div. 2) Div. 2 | 5 problems | 5/5 verified | Difficulty 800-2300 | 11m 39s # Problem Rating Tags Accepted Time ✓ A Choosing Teams 800 greedy, implementation, sortings 69,480 1m 21s ✓ B Football Kit 1200 brute-force, greedy, implementation 12,258 1m 49s ✓ C Prime Swaps 1800 greedy, sortings 2,679 1m 38s ✓ D Prefixes and Suffixes 2000 dp, string-suffix-structures, strings 11,937 4m 11s ✓...

Practice › Codeforces Solutions ›

Codeforces Round 106 (Div. 2)

Codeforces Round 106 (Div. 2) Div. 2 | 5 problems | 4/5 verified | Difficulty 900-2300 | 8m 2s # Problem Rating Tags Accepted Time ✓ A Business trip 900 greedy, implementation, sortings 45,971 1m 33s ✓ B Martian Clock 1600 implementation 2,390 1m 25s ✓ C Division into Teams 1500 greedy, math, sortings 5,733 1m 40s D Coloring Brackets 1900 dp 4,608 2m 8s ✓ E Martian Strings 2300...

Practice › Codeforces Solutions › Codeforces Round 106 (Div. 2) ›

CF 149E - Martian Strings

CF 149E - Martian Strings Rating: 2300 Tags: string suffix structures, strings Solve time: 1m 16s Verified: yes Solution Problem Understanding The problem describes a Martian with a row of eyes, each covered by a patch marked with an uppercase letter. The string of letters visible when all eyes are opened represents a sequence s of length n . The Martian can choose to open exactly two non-overlapping segments of...

Practice › Codeforces Solutions › Codeforces Round 252 (Div. 2) ›

CF 441D - Valera and Swaps

CF 441D - Valera and Swaps Rating: 2100 Tags: constructive algorithms, dsu, graphs, implementation, math, string suffix structures Solve time: 1m 26s Verified: no Solution Problem Understanding We are given a permutation, which we can think of as a row of numbered positions, where each position contains a distinct value from 1 to n. A swap operation exchanges two positions, and after a sequence of swaps we obtain another permutation....

Practice › Codeforces Solutions › Codeforces Round 129 (Div. 1) ›

CF 204E - Little Elephant and Strings

CF 204E - Little Elephant and Strings Rating: 2800 Tags: data structures, implementation, string suffix structures, two pointers Solve time: 45s Verified: yes Solution Problem Understanding We are given a list of strings, and for each string, we need to count the number of its substrings that appear in at least k strings from the list. A substring is any contiguous segment of a string. For example, if the string...

Practice › Codeforces Solutions › Codeforces Round 244 (Div. 2) ›

CF 427D - Match & Catch

CF 427D - Match & Catch Rating: 2200 Tags: dp, string suffix structures, strings Solve time: 1m 27s Verified: yes Solution Problem Understanding We are given two lowercase strings. From each string we can look at every contiguous segment, and we care about those segments that behave unusually: a segment is considered special if it appears exactly once in its own string. The task is to find a string segment...

Practice › Codeforces Solutions ›

Codeforces Beta Round 94 (Div. 1 Only)

Codeforces Beta Round 94 (Div. 1 Only) Div. 1 | 5 problems | 5/5 verified | Difficulty 1500-2900 | 8m 36s # Problem Rating Tags Accepted Time ✓ A Statues 1500 dfs-and-similar 3,508 2m 10s ✓ B String 2100 brute-force, constructive-algorithms, hashing 2,869 1m 21s ✓ C Games with Rectangle 2000 combinatorics, dp 3,244 1m 52s ✓ D Numbers 2000 constructive-algorithms, implementation 1,261 1m 38s ✓ E Birthday 2900 geometry,...

Practice › Codeforces Solutions ›

Yandex.Algorithm 2011: Round 2

Yandex.Algorithm 2011: Round 2 Special | 5 problems | 5/5 verified | Difficulty 1600-2700 | 11m 50s # Problem Rating Tags Accepted Time ✓ A Reflection 1600 math 1,659 2m 9s ✓ B Tetris revisited 2200 constructive-algorithms, graph-matchings, greedy 452 2m 5s ✓ C Genetic engineering 2500 dp, string-suffix-structures, trees 863 2m 12s ✓ D Powerful array 2200 data-structures, implementation, math 16,863 3m 46s ✓ E Long sequence 2700 brute-force,...

Practice › Codeforces Solutions ›

Codeforces Beta Round 19

Codeforces Beta Round 19 Beta | 5 problems | 5/5 verified | Difficulty 1400-2900 | 16m 37s # Problem Rating Tags Accepted Time ✓ A World Football Cup 1400 implementation 3,141 5m 51s ✓ B Checkout Assistant 1900 dp 5,822 3m 5s ✓ C Deletion of Repeats 2200 greedy, hashing, string-suffix-structures 1,325 2m 2s ✓ D Points 2800 data-structures 3,168 3m 49s ✓ E Fairy 2900 dfs-and-similar, divide-and-conquer, dsu 2,512...

Practice › Codeforces Solutions › Codeforces Beta Round 93 (Div. 1 Only) ›

CF 126B - Password

CF 126B - Password Rating: 1700 Tags: binary search, dp, hashing, string suffix structures, strings Solve time: 2m 4s Verified: yes Solution Problem Understanding We are given a single lowercase string and need to find the longest string that satisfies three conditions at the same time. The chosen string must be a prefix of the original string, a suffix of the original string, and also appear somewhere strictly inside the...

Practice › Codeforces Solutions › Yandex.Algorithm 2011: Round 2 ›

CF 86C - Genetic engineering

CF 86C - Genetic engineering Rating: 2500 Tags: dp, string suffix structures, trees Solve time: 2m 12s Verified: yes Solution Problem Understanding We are given several short DNA fragments over the alphabet {A, C, G, T} . A longer DNA string is considered valid if every position of the string belongs to at least one occurrence of one of the given fragments. The fragments may overlap arbitrarily. One fragment can...

Practice › Codeforces Solutions › Codeforces Beta Round 94 (Div. 1 Only) ›

CF 128B - String

CF 128B - String Rating: 2100 Tags: brute force, constructive algorithms, hashing, implementation, string suffix structures, strings Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a string of lowercase letters and an integer k . The task is to generate all possible substrings of the string, sort them lexicographically, and return the k -th substring in that order. Substrings can repeat, so multiple identical substrings must...

Practice › Codeforces Solutions › Codeforces Beta Round 92 (Div. 1 Only) ›

CF 123D - String

CF 123D - String Rating: 2300 Tags: string suffix structures Solve time: 2m 32s Verified: yes Solution Problem Understanding We are given a string s . For every substring x of s , we look at all positions where x appears inside s . Suppose these occurrences start at positions: $$p_1 < p_2 < \dots < p_k$$ The function F(s, x) counts how many contiguous segments we can choose from...

#string-suffix-structures

CF 1387C - Viruses

CF 1266G - Permutation Concatenation

CF 1202E - You Are Given Some Strings...

CF 961F - k-substrings

Educational Codeforces Round 41 (Rated for Div. 2)

CF 1037H - Security

CF 1043G - Speckled Band

CF 1326D2 - Prefix-Suffix Palindrome (Hard version)

CF 1207G - Indie Album

CF 1098F - Ж-function

CF 1073G - Yet Another LCP Problem

CF 1063F - String Journey

CF 1817F - Entangled Substrings

CF 1721E - Prefix Function Queries

CF 1511F - Chainword

CF 1437G - Death DBMS

CF 917E - Upside Down

CF 906E - Reverses

CF 914F - Substrings in a String

CF 1129C - Morse Code

CF 1200E - Compress Words

CF 1276F - Asterisk Substrings

CF 1326D1 - Prefix-Suffix Palindrome (Easy version)

CF 1393E2 - Twilight and Ancient Scroll (harder version)

CF 1393E1 - Twilight and Ancient Scroll (easier version)

CF 1400F - x-prime Substrings

Codeforces Global Round 7

CF 1466G - Song of the Sirens

CF 1469E - A Bit Similar

CF 1482H - Exam

CF 1536F - Omkar and Akmar

CF 1537E2 - Erase and Extend (Hard Version)

CF 1537E1 - Erase and Extend (Easy Version)

CF 1562E - Rescue Niwen!

CF 1598G - The Sum of Good Numbers

CF 1608G - Alphabetic Tree

CF 1621I - Two Sequences

Codeforces Round 809 (Div. 2)

CF 1706A - Another String Minimization Problem

CF 1739F - Keyboard Design

CF 1780G - Delicious Dessert

CF 1801G - A task for substrings

CF 1895D - XOR Construction

CF 1913F - Palindromic Problem

CF 1916H2 - Matrix Rank (Hard Version)

CF 1923F - Shrink-Reverse

April Fools Day Contest 2025

CF 1984D - ''a'' String Problem

Testing Round 19 (Div. 3)

CF 2010C2 - Message Transmission Error (hard version)

CF 2038I - Polyathlon

CF 2045H - Missing Separators

CF 2095A - Piecing It Together

CF 2144F - Bracket Groups

CF 2172H - Shuffling Cards with Problem Solver 68!

CF 2181L - LLM Training

CF 2196E2 - Fuzzy Concatenation (Hard version)

CF 2196E1 - Fuzzy Concatenation (Easy Version)

CF 2205E - Simons and Dividing the Rhythm

CF 2209E - A Trivial String Problem

CF 2225F - String Cutting

CF 1968G2 - Division + LCP (hard version)

CF 1968G1 - Division + LCP (easy version)

CF 432D - Prefixes and Suffixes

CF 316G2 - Good Substrings

CF 319D - Have You Ever Heard About the Word?

CF 316G3 - Good Substrings

Codeforces Round 146 (Div. 1)

CF 235C - Cyclical Quest

CF 232D - Fence

Codeforces Beta Round 93 (Div. 1 Only)

CF 471D - MUH and Cube Walls

CF 452E - Three strings

Codeforces Round 246 (Div. 2)

Codeforces Round 106 (Div. 2)

CF 149E - Martian Strings

CF 441D - Valera and Swaps

CF 204E - Little Elephant and Strings

CF 427D - Match & Catch