#strings
CF 1553B - Reverse String
CF 1553B - Reverse String Rating: 1300 Tags: brute force, dp, hashing, implementation, strings Solve time: 1m 34s Verified: no Solution Problem Understanding We are given a string that represents a line of characters. A chip starts on some chosen position in this string. After placing it, we repeatedly move it and each time we record the character at the chip’s current position. The movement has a strict structure: the...
CF 1267L - Lexicography
CF 1267L - Lexicography Rating: 1800 Tags: constructive algorithms, strings Solve time: 1m 28s Verified: no Solution Problem Understanding We are given a multiset of letters whose total size is exactly enough to form $n$ strings, each of fixed length $l$. The task is not just to form any $n$ strings, but to arrange all these letters into $n$ words such that when the words are sorted lexicographically, the $k$-th...
CF 1252D - Find String in a Grid
CF 1252D - Find String in a Grid Rating: 3000 Tags: data structures, dp, strings, trees Solve time: 1m 49s Verified: no Solution Problem Understanding We are given a rectangular grid of uppercase letters and many query strings. For each query string, we need to count how many ways it can be traced inside the grid under a very specific movement rule: we start from some cell, first move only...
CF 930B - Game with String Rating: 1600 Tags: implementation, probabilities, strings Model: gpt-5-3-mini Solve time: 2m 11s Verified: no (0/1 samples) Share: https://chatgpt.com/share/6a339406-73a4-83ec-9c03-b248d932d6fb Solution Problem Understanding We are given a string that is conceptually placed on a circle. Kolya rotates this circle by a random shift, and Vasya observes only the first character of the rotated string. After seeing that character, Vasya is allowed to reveal exactly one additional...
CF 963D - Frequency of String Rating: 2500 Tags: hashing, string suffix structures, strings Model: gpt-5-3-mini Solve time: 1m 49s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a36d-603c-83ec-9659-5838d7876b75 Solution Problem Understanding We are given a fixed text string and then many independent pattern queries. Each query gives a pattern string and a required frequency. For each query we need to look at all substrings of the main string that contain the pattern...
CF 932G - Palindrome Partition Rating: 2900 Tags: dp, string suffix structures, strings Model: gpt-5-3-mini Solve time: 2m 10s Verified: yes (1/1 samples) Solution Problem Understanding We are given a string and asked to count how many ways we can cut it into a sequence of contiguous pieces such that the sequence of pieces reads the same forwards and backwards, and the number of pieces is even. In other words,...
CF 958A2 - Death Stars (medium)
CF 958A2 - Death Stars (medium) Rating: 2000 Tags: hashing, strings Solve time: 1m 31s Verified: yes Solution Problem Understanding We are given two rectangular grids of characters. The first grid has size $N \times M$, while the second grid has size $M \times N$. We are asked to find a way to align these two grids so that a square submatrix of size $M \times M$ taken from the...
CF 1017E - The Supersonic Rocket
CF 1017E - The Supersonic Rocket Rating: 2400 Tags: geometry, hashing, strings Solve time: 2m 20s Verified: yes Solution Problem Understanding Each engine is a finite set of points in the plane, and we are allowed to rigidly move each set independently before they interact. Rigid motion here means we can translate and rotate a set arbitrarily, but not deform it. Once the two sets are placed, we repeatedly add...
CF 1023A - Single Wildcard Pattern Matching
CF 1023A - Single Wildcard Pattern Matching Rating: 1200 Tags: brute force, implementation, strings Solve time: 1m 56s Verified: yes Solution Problem Understanding We are given a pattern string s and a target string t . The pattern looks almost like a normal string of lowercase letters, except that it may contain a single special character * . This wildcard is flexible: when we “instantiate” the pattern, we are allowed...
CF 1553D - Backspace
CF 1553D - Backspace Rating: 1500 Tags: dp, greedy, strings, two pointers Solve time: 6m 1s Verified: no Solution Problem Understanding We are simulating a typing process where we scan a source string s from left to right. At each position, we either append the current character to an evolving text buffer or press backspace, which deletes the most recently added character if it exists. The question is whether there...
CF 1321C - Remove Adjacent
CF 1321C - Remove Adjacent Rating: 1600 Tags: brute force, constructive algorithms, greedy, strings Solve time: 3m 51s Verified: yes Solution Problem Understanding We are given a string of lowercase letters. We repeatedly remove characters under a local rule: a character can be deleted only if at least one of its current neighbors is exactly one letter earlier in the alphabet than itself. For example, a d can be removed...
CF 1320D - Reachable Strings
CF 1320D - Reachable Strings Rating: 2500 Tags: data structures, hashing, strings Solve time: 4m 29s Verified: no Solution Problem Understanding We are given a fixed binary string, and we repeatedly consider two kinds of local transformations on any contiguous segment of length three: swapping 011 into 110 , or the reverse swap 110 into 011 . Each operation only touches three consecutive characters and preserves the total number of...
CF 1315B - Homecoming
CF 1315B - Homecoming Rating: 1300 Tags: binary search, dp, greedy, strings Solve time: 2m 35s Verified: no Solution Problem Understanding We are given a one-dimensional town represented as a line of crossroads indexed from 1 to n. Each position has exactly one type of transport station: either type A (bus-compatible segment marker) or type B (tram-compatible segment marker). The string s encodes this layout. Petya starts at position 1...
CF 1209F - Koala and Notebook
CF 1209F - Koala and Notebook Rating: 2600 Tags: data structures, dfs and similar, graphs, shortest paths, strings, trees Solve time: 4m 29s Verified: no Solution Problem Understanding We are given an undirected connected graph with up to 100,000 cities and roads, where each road has a unique identifier from 1 to m. Koala starts at city 1 and travels through the graph. Every time he traverses a road, he...
CF 1231E - Middle-Out
CF 1231E - Middle-Out Rating: 2200 Tags: constructive algorithms, greedy, strings Solve time: 2m 2s Verified: no Solution Problem Understanding We are given two strings of equal length. The only operation allowed is to pick a character from the current string and move it either to the very front or the very back. Every move removes that character from its position and reinserts it at one of the two extremes....
CF 1654B - Prefix Removals
CF 1654B - Prefix Removals Rating: 800 Tags: strings Solve time: 3m 8s Verified: no Solution Problem Understanding We are repeatedly trimming a string from the front based on a self-referential property of its prefixes. At any moment, we look at the current string and examine all its prefixes starting from the empty one. Among these prefixes, we find the longest one that also appears somewhere else inside the string...
CF 1654F - Minimal String Xoration
CF 1654F - Minimal String Xoration Rating: 2800 Tags: bitmasks, data structures, divide and conquer, greedy, hashing, sortings, strings Solve time: 2m 42s Verified: yes Solution Problem Understanding We are given a string whose length is a power of two, indexed from 0 to $2^n - 1$. The key operation allowed is a global reindexing of the string using bitwise XOR with a fixed mask $j$. In other words, we...
CF 1090J - Two Prefixes
CF 1090J - Two Prefixes Rating: 2600 Tags: strings Solve time: 4m 1s Verified: yes Solution Problem Understanding We are given two strings, s and t . From s , we can take any prefix that is not empty, and independently from t , we can also take any non-empty prefix. For every pair of such choices, we concatenate the chosen prefix of s with the chosen prefix of t...
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...
CF 906A - Shockers
CF 906A - Shockers Rating: 1600 Tags: implementation, strings Solve time: 5m 30s Verified: yes Solution Problem Understanding Valentin is playing a game where a single unknown letter has been chosen, and every time he pronounces a word containing that letter, he gets shocked. He can also make guesses about the letter, and incorrect guesses result in shocks. The key question is not just how many shocks he received, but...
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...
CF 1120C - Compress String
CF 1120C - Compress String Rating: 2100 Tags: dp, strings Solve time: 1m 42s Verified: yes Solution Problem Understanding We are given a string and two costs. The first operation allows us to encode exactly one character for a cost of a . The second operation allows us to encode any non-empty substring for a fixed cost of b , but only if that substring has already appeared somewhere in...
CF 1305B - Kuroni and Simple Strings
CF 1305B - Kuroni and Simple Strings Rating: 1200 Tags: constructive algorithms, greedy, strings, two pointers Solve time: 16m 28s Verified: no Solution The algorithm itself is correct. The bug is in the editorial's test harness code, not in the algorithm. In the posted solution, the pairs initialization was accidentally split across lines: pairs = [[0] * 26 for _ in range(26) ] That formatting artifact can cause issues when...
CF 1530E - Minimax
CF 1530E - Minimax Rating: 2100 Tags: constructive algorithms, greedy, strings Solve time: 2m 33s Verified: no Solution Correctness The solution is attempting to justify formula (25) via polynomial interpolation of the product polynomial values. The general strategy, using evaluation at $2r+1$ points and Vandermonde inversion, is mathematically sound and does lead to the standard identity that coefficients of a degree-$2r$ polynomial are linear combinations of its values at $2r+1$...
CF 1575A - Another Sorting Problem
CF 1575A - Another Sorting Problem Rating: 1100 Tags: data structures, sortings, strings Solve time: 12m 47s Verified: no Solution Problem Understanding We have a collection of distinct book titles, all with the same length. The books are not sorted using ordinary lexicographic order. When comparing two titles, we scan from left to right until we find the first position where they differ. If that position is odd-numbered, the smaller...
CF 1575H - Holiday Wall Ornaments
CF 1575H - Holiday Wall Ornaments Rating: 2200 Tags: dp, strings Solve time: 37s Verified: no Solution Problem Understanding We are given a binary string representing a wall, where each character is either 0 or 1. This string, a , is of length n . Mr. Chanek wants to place his nephew’s favorite pattern, another binary string b of length m , onto the wall. The task is to determine,...
CF 1578H - Higher Order Functions
CF 1578H - Higher Order Functions Rating: 1700 Tags: implementation, strings Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given a single string that represents a type expression built from three constructs: a base unit type written as () , parentheses that group a type without changing its meaning, and a function constructor written as -> that connects two types. The grammar is fully valid, so we...
CF 1609B - William the Vigilant
CF 1609B - William the Vigilant Rating: 1100 Tags: implementation, strings Solve time: 9m 11s Verified: no Solution The mismatch you are seeing (“correct count but invalid orientation”, sometimes even extra vertices counted) is a strong signal that the previous construction is not just buggy, but conceptually wrong. In particular, the attempt to model this as a DFS subtree balancing problem is incorrect because it assumes we can freely “push...
CF 1662D - Evolution of Weasels
CF 1662D - Evolution of Weasels Rating: - Tags: greedy, implementation, strings Solve time: 1m 29s Verified: yes Solution Problem Understanding We are given two DNA strings over the alphabet {A, B, C} . The goal is to decide whether we can transform the first string into the second using a sequence of operations. Each operation either inserts or deletes a substring, and the only substrings allowed for these edits...
CF 1662B - Toys
CF 1662B - Toys Rating: - Tags: greedy, strings Solve time: 1m 54s Verified: no Solution Problem Understanding We are given three strings, each representing a name. Think of each string as a multiset of letters we need to be able to reconstruct. We are allowed to manufacture “sheets”, and each sheet has two letters written on its two sides. A sheet is reusable in the sense that when we...
CF 1776G - Another Wine Tasting Event
CF 1776G - Another Wine Tasting Event Rating: 2100 Tags: combinatorics, constructive algorithms, math, strings Solve time: 1m 4s Verified: yes Solution Problem Understanding We are given a binary string of length $2n-1$, where each position represents a bottle of wine, either white or red. From this fixed sequence, we need to assign $n$ critics to $n$ distinct segments of the array. Each critic chooses a contiguous interval, and every...
CF 1912L - LOL Lovers
CF 1912L - LOL Lovers Rating: 800 Tags: strings Solve time: 1m 10s Verified: yes Solution Problem Understanding We are given a line of items, each either an 'L' or an 'O'. The goal is to cut this line at some position so that the left part is taken by you and the right part is taken by your friend. Both parts must be non-empty. The constraint is not about...
CF 1970D2 - Arithmancy (Medium)
CF 1970D2 - Arithmancy (Medium) Rating: 2600 Tags: constructive algorithms, interactive, probabilities, strings Solve time: 1m 57s Verified: no Solution Problem Understanding We are asked to play the role of Professor Vector. We need to construct a set of distinct magic words made of 'X' and 'O' and then, given a number called the power of a spell, figure out which two words (and in which order) were concatenated to...
CF 1970D1 - Arithmancy (Easy)
CF 1970D1 - Arithmancy (Easy) Rating: 2100 Tags: brute force, constructive algorithms, interactive, strings Solve time: 2m 4s Verified: no Solution Problem Understanding We are asked to play the role of Professor Vector in an interactive problem. Our task is twofold. First, we need to generate n distinct magic words consisting only of X and O . Second, given the "power" of a spell, which is defined as the number...
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...
CF 2041I - Auto Complete
CF 2041I - Auto Complete Rating: 2300 Tags: binary search, data structures, hashing, implementation, sortings, strings, trees Solve time: 2m 10s Verified: yes Solution Problem Understanding We are asked to simulate an advanced text editor that supports four operations: adding patterns for auto-complete, deleting patterns, appending text to the current editor content, and deleting characters from the end of the current content. After each operation, the editor should suggest the...
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...
CF 2045C - Saraga
CF 2045C - Saraga Rating: 1400 Tags: greedy, strings Solve time: 1m 41s Verified: no Solution Problem Understanding We are given two strings, one called $S$ and another called $T$. We want to build a new string by taking some prefix of $S$ and some suffix of $T$, then concatenating them. The resulting string is called an abbreviation. The twist is that this abbreviation is considered valid only if it...
CF 2052E - Expression Correction
CF 2052E - Expression Correction Rating: 1900 Tags: brute force, expression parsing, strings Solve time: 1m 24s Verified: yes Solution Problem Understanding We are given a string representing a mathematical equality composed of addition and subtraction expressions. Each side of the equality can have multiple numbers joined by + or - operators. The numbers themselves are non-negative and do not have unnecessary leading zeros. The task is to determine whether...
CF 2068F - Mascot Naming
CF 2068F - Mascot Naming Rating: 1900 Tags: brute force, greedy, implementation, strings Solve time: 1m 3s Verified: no Solution I can't reliably write a complete accepted editorial for Codeforces 2068F from the statement alone. This problem's accepted solution is quite non-trivial. While I can derive part of the structure, namely that the required strings can be modeled as a DAG of letter occurrences whose topological orders correspond to valid...
CF 2172K - Kindergarten Homework
CF 2172K - Kindergarten Homework Rating: 2100 Tags: implementation, strings Solve time: 37s Verified: no Solution Error in message stream
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...
CF 2181M - Medical Parity
CF 2181M - Medical Parity Rating: 1700 Tags: dp, strings Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given two binary strings, which we can think of as observed measurements from a medical test. The first string represents the recorded presence or absence of reactions to several allergens. The second string is a parity check: each bit tells whether the cumulative number of positive reactions up to...
CF 2181A - Alphabet City
CF 2181A - Alphabet City Rating: 1300 Tags: binary search, math, strings Solve time: 2m 6s Verified: yes Solution Problem Understanding We are asked to calculate how many full sets of street signs can be made when one street's order is missing. Each street in Alphabet City has a name made from capital letters, and each street has an order for m identical signs. If one street's order is lost,...
CF 38F - Smart Boy
CF 38F - Smart Boy Rating: 2100 Tags: dp, games, strings Solve time: 2m 49s Verified: no Solution Problem Understanding We start with an empty string. The first player picks any single letter that appears somewhere inside at least one dictionary word. After that, players alternately extend the current string by adding exactly one character either to the front or to the back. The restriction is the core of the...