strings | brain

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.14 Longest Common Substring

16.14 Longest Common Substring Problem Given two strings, find the longest contiguous block of characters that appears in both. For example: A = banana B = ananas The longest common substring is: anana This differs from the longest common subsequence. A substring must be contiguous. A subsequence may skip characters. substring: consecutive characters subsequence: characters in order, with gaps allowed The challenge is to find the longest shared contiguous region...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.19 Token Streams

16.19 Token Streams Problem Most string algorithms operate on characters. Many real systems operate on tokens. A compiler does not usually search raw source code character by character. It first groups characters into tokens: if identifier = number { } A search engine does not usually index raw characters. It tokenizes documents into words, terms, phrases, or normalized units. The challenge is to apply string-algorithm ideas to sequences whose elements...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.6 Trie Matching

16.6 Trie Matching Problem Suppose you need to search for many patterns simultaneously. Consider a dictionary: he her hers hero help hello and a text: hello hero and her helpers A straightforward approach searches for each word independently. search("he") search("her") search("hers") search("hero") search("help") search("hello") If there are thousands of patterns, the same text characters may be scanned repeatedly. The cost grows with both the text length and the number of...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.24 Testing String Algorithms

16.24 Testing String Algorithms Problem String algorithms are easy to implement incorrectly. Most failures are small: Off-by-one error Wrong boundary condition Incorrect empty-pattern behavior Unicode mismatch Duplicate match omission Failure to report overlapping matches These bugs often pass simple tests. For example, a matcher may work for: Text: hello world Pattern: world but fail for: Text: aaaaa Pattern: aaa because overlapping matches are mishandled. The challenge is to test string...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.17 Compressed Strings

16.17 Compressed Strings Problem Many strings contain repeated structure. Examples: aaaaaa abababab the the the the A direct representation stores every character explicitly. That is simple, but it can waste space and make repeated operations expensive. Suppose a string is represented as: a repeated 1,000,000 times It is inefficient to store and scan one million characters when the structure can be described compactly. The challenge is to represent repetitive strings...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.16 String Hashing

16.16 String Hashing Problem Many string algorithms repeatedly compare substrings. Consider: Text = abracadabra Suppose you want to determine whether: abra appears multiple times. A direct comparison examines characters one by one. abra abra This is inexpensive for a single query. Now imagine: Millions of substring comparisons Large documents Plagiarism detection Search indexing DNA analysis Duplicate detection Repeated character-by-character comparison becomes a bottleneck. The challenge is to compare substrings quickly...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.9 Longest Common Prefix (LCP) Arrays

16.9 Longest Common Prefix (LCP) Arrays Problem In the previous recipe, you built a suffix array and used it to perform efficient substring searches. Consider the suffix array for: banana Rank Position Suffix 0 5 a 1 3 ana 2 1 anana 3 0 banana 4 4 na 5 2 nana Suppose you want to answer questions such as: What is the longest repeated substring? How many distinct substrings exist?...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.12 Manacher Algorithm

16.12 Manacher Algorithm Problem You need to find palindromic substrings efficiently. Given: forgeeksskeegfor the longest palindromic substring is: geeksskeeg A brute-force solution checks every substring and tests whether it is a palindrome. There are O(n²) substrings, and each check may cost O(n) , giving O(n³) time if implemented directly. Even a better expand-around-center approach still costs O(n²) in the worst case. The challenge is to find all palindrome radii, and...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.5 Boyer-Moore Overview

16.5 Boyer-Moore Overview Problem Most exact matching algorithms process the text from left to right. Consider: Text: HERE IS A SIMPLE EXAMPLE Pattern: EXAMPLE A typical algorithm begins by comparing: E E then: X X and continues forward. This approach works well, but it often examines many characters that ultimately contribute nothing to the search. Human readers rarely search this way. When looking for a word in a sentence, we...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.3 Z Algorithm

16.3 Z Algorithm Problem Many string algorithms need to answer the question: How many characters match between a string prefix and a substring starting at a particular position? Consider: ABABABCA At position 2: ABABABCA ABABCA The substring beginning at position 2 shares four characters with the prefix: ABAB A naive solution compares characters one by one for every position. For a string of length n , this may require: O(n²)...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.15 Lexicographic Order

16.15 Lexicographic Order Problem Many string algorithms depend on a precise ordering of strings. Suffix arrays sort suffixes. Dictionaries sort words. Search systems compare terms. Databases compare keys. Compression algorithms order repeated fragments. In all of these cases, the algorithm must answer a basic question: Which string comes first? For example: apple < banana app < apple cat < catalog The challenge is to define this ordering exactly and implement...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.11 Palindromic Trees (Eertrees)

16.11 Palindromic Trees (Eertrees) Problem Many string algorithms focus on prefixes, suffixes, or arbitrary substrings. Palindromes introduce a different type of structure. A palindrome reads the same forward and backward. Examples: a aa aba abba racecar Given a string, you may want to answer questions such as: What palindromes occur in the text? How many distinct palindromes exist? How often does each palindrome appear? What is the longest palindromic substring?...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.7 Aho-Corasick

16.7 Aho-Corasick Problem Suppose you need to search a text for thousands of patterns simultaneously. Consider a dictionary: he her hers hero help hello world search engine algorithm and a text stream: the hero helped her while the search engine processed the world A straightforward solution runs a separate search for every pattern. search("he") search("her") search("hers") search("hero") ... Even if each search uses KMP or Boyer-Moore, the text must be...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.13 Edit Distance

16.13 Edit Distance Problem Exact matching assumes that strings must be identical. Consider: kitten sitting An exact matcher reports failure immediately because the strings differ. In many applications, however, similarity matters more than equality. Examples include: Spell checking Search suggestions OCR correction DNA sequence alignment Plagiarism detection Data deduplication Natural language processing The challenge is to measure how different two strings are and to do so efficiently. Solution Edit distance...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.18 Unicode and Normalization

16.18 Unicode and Normalization Problem Many string algorithms assume that a string is simply a sequence of characters. For English text, this assumption often appears correct. hello world algorithm A character seems to correspond to: One symbol One storage unit One display position Unicode breaks this assumption. Consider: é This character may be represented as: U+00E9 or as: U+0065 U+0301 which means: e + combining acute accent Visually they appear...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.23 Complexity Analysis

16.23 Complexity Analysis Problem String algorithms often look deceptively simple. A few nested loops may be harmless for short text but catastrophic for large input. A suffix-array comparison may appear to take O(log n) binary-search steps, while each comparison secretly scans many characters. A hash-based algorithm may appear constant time, but only after preprocessing and with collision assumptions. The challenge is to analyze string algorithms honestly, including hidden costs such...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.10 Suffix Automata

16.10 Suffix Automata Problem Suppose you need to answer questions such as: Does a substring occur in the text? How many distinct substrings exist? What is the longest repeated substring? How many times does a substring appear? What is the longest common substring between two strings? A suffix array and LCP array can answer many of these questions efficiently, but they are fundamentally indexing structures. Queries often require binary searches,...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.4 Rabin-Karp

16.4 Rabin-Karp Problem Suppose you need to search for a pattern inside a large text. Text: THEQUICKBROWNFOXJUMPSOVERTHELAZYDOG Pattern: BROWN A straightforward algorithm compares characters one by one. Even efficient algorithms such as KMP and the Z Algorithm ultimately rely on direct character comparisons. Now consider a different situation: Text length = 10,000,000 Patterns = thousands Searches/day = millions Repeated character-by-character comparison becomes expensive. The challenge is to compare substrings quickly...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.8 Suffix Arrays

16.8 Suffix Arrays Problem Suppose you need to answer many substring queries against the same text. For one query, a linear scan is acceptable: Text: bananabandana Pattern: ana But if the text is large and the number of queries is high, scanning from the beginning each time is wasteful. You want a structure that preprocesses the text once and then answers substring queries quickly. Solution A suffix array stores all...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.25 Real-World String Processing Patterns

16.25 Real-World String Processing Patterns Problem After learning dozens of string algorithms, a natural question remains: What do real systems actually do? Textbooks often present algorithms in isolation: KMP solves pattern matching. Tries solve prefix search. Suffix arrays solve substring search. Edit distance solves similarity. Production systems rarely look like this. Instead, they combine multiple techniques into processing pipelines. The challenge is to recognize recurring architectural patterns that appear across...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.20 Choosing the Right String Algorithm

16.20 Choosing the Right String Algorithm Problem This chapter introduced a large collection of string-processing techniques: Naive matching KMP Z Algorithm Rabin-Karp Boyer-Moore Tries Aho-Corasick Suffix Arrays LCP Arrays Suffix Automata Eertrees Manacher's Algorithm Edit Distance String Hashing A common question arises: Which algorithm should I use? Many algorithms solve related problems, but their strengths differ significantly. Choosing the wrong algorithm can increase complexity, memory usage, implementation effort, or runtime....

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.1 Exact Matching

16.1 Exact Matching Problem Given a text string and a pattern string, determine whether the pattern occurs in the text and, if so, find all positions where the match begins. This is one of the oldest and most fundamental problems in computer science. Search engines look for query terms inside documents. Compilers search for keywords inside source code. Text editors perform find-and-replace operations. DNA analysis systems search for gene sequences...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.21 Text Indexing

16.21 Text Indexing Problem A single pattern search scans one text once. A text index solves a different problem: one or more large texts are stored, and many queries arrive later. Examples: Find all documents containing "algorithm" Find every occurrence of "banana" Find phrases beginning with "dynamic programming" Find logs containing both "timeout" and "database" Scanning every document for every query is too slow. The challenge is to preprocess text...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.22 Building a Search Engine

16.22 Building a Search Engine Problem Throughout this chapter, we studied individual string-processing techniques: Tokenization Tries Hashing Aho-Corasick Suffix Arrays Edit Distance Text Indexes Real systems rarely use these algorithms in isolation. Consider a search engine. Users expect: Fast queries Typo tolerance Phrase search Prefix completion Relevant ranking Large-scale indexing No single algorithm provides all of these capabilities. The challenge is to combine multiple string-processing techniques into a practical search...

Programming › Algorithm Cookbook › Chapter 16. String Algorithms ›

16.2 Knuth-Morris-Pratt (KMP)

16.2 Knuth-Morris-Pratt (KMP) Problem The naive exact matching algorithm repeatedly compares the same characters after every mismatch. When the text and pattern contain repeated prefixes, large amounts of work are duplicated. Consider: Text: AAAAAAAAAAAAAAAA Pattern: AAAAAB The naive algorithm repeatedly verifies the same sequence of A characters before discovering that the final character differs. The challenge is to reuse information gained from previous comparisons instead of restarting from the beginning...

Programming › Algorithm Cookbook ›

Chapter 16. String Algorithms

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

CF 2226G - Stop Spot

CF 2226G - Stop Spot Rating: - Tags: implementation, strings, trees Solve time: 2m 32s Verified: no Solution Problem Understanding An array $a$ is fixed, and we append to it a permutation $p$ of ${1,2,\dots,m}$ to form a longer array $b_p$. For each such permutation, we count how many subarrays of $b_p$ with even length are palindromes. This produces a value $i$, and over all permutations we define $f(i)$ as...

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: 2m 54s Verified: no Solution Problem Understanding A string $s$ must be split into several contiguous pieces. Each piece has length at least $l$, and the total number of pieces is at least $k$. After cutting, all pieces are sorted lexicographically, and the piece in position $k$ of this sorted...

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

CF 1974B - Symmetric Encoding

CF 1974B - Symmetric Encoding Rating: 800 Tags: implementation, sortings, strings Solve time: 5m 18s Verified: no Solution

Practice › Codeforces Solutions ›

Codeforces Round 279 (Div. 2)

Codeforces Round 279 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 0/5 | Rating range: 1500-2200 | Time: 44m 5s Problem Name Rating Tags Solve Time Verified B Queue 1500 dsu, implementation 11m 48s ✗ C Hacking Cypher 1700 brute-force, math, number-theory 5m 25s ✗ D Chocolate 1900 brute-force, dfs-and-similar, math 5m 18s ✗ E Restoring Increasing Sequence 2000 binary-search, brute-force, greedy 10m 45s ✗ F Treeland Tour...

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

CF 1943B - Non-Palindromic Substring

CF 1943B - Non-Palindromic Substring Rating: 2000 Tags: hashing, implementation, math, strings Solve time: 1m 20s Verified: no Solution Problem Understanding We are given a string and multiple queries, each asking for a contiguous substring of the original string. For each query, we need to calculate a value f(t) for that substring t . The function f(t) is the sum of all lengths k such that there exists at least...

Practice › Codeforces Solutions ›

Codeforces Round 937 (Div. 4)

Codeforces Round 937 (Div. 4) Type: Div. 4 | Problems: 7 | Verified: 6/7 | Rating range: 800-1900 | Time: 7m 41s Problem Name Rating Tags Solve Time Verified A Stair, Peak, or Neither? 800 implementation 1m 4s ✓ B Upscaling 800 implementation 45s ✓ C Clock Conversion 800 implementation, math 51s ✓ D Product of Binary Decimals 1100 brute-force, dp, implementation 1m 17s ✓ E Nearly Shortest Repeating Substring...

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

CF 1975H - 378QAQ and Core

CF 1975H - 378QAQ and Core Rating: 3500 Tags: greedy, strings Solve time: 5m 19s Verified: no Solution

Practice › Codeforces Solutions ›

Codeforces Round 946 (Div. 3)

Codeforces Round 946 (Div. 3) Type: Div. 3 | Problems: 7 | Verified: 0/7 | Rating range: 800-2000 | Time: 36m 53s Problem Name Rating Tags Solve Time Verified A Phone Desktop 800 greedy, math 5m 17s ✗ B Symmetric Encoding 800 implementation, sortings, strings 5m 18s ✗ C Beautiful Triple Pairs 1400 combinatorics, data-structures 5m 16s ✗ D Ingenuity-2 1400 constructive-algorithms, greedy, implementation 5m 16s ✗ E Money Buys...

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

CF 1948D - Tandem Repeats?

CF 1948D - Tandem Repeats? Rating: 1700 Tags: brute force, strings, two pointers Solve time: 2m 48s Verified: no Solution Problem Understanding We are given a string consisting of lowercase letters and wildcard characters. Each wildcard can later be replaced by any lowercase letter we choose. After fixing all wildcards, we look at every substring of the resulting string and ask whether it can be split into two consecutive halves...

Practice › Codeforces Solutions › April Fools Day Contest 2024 ›

CF 1952B - Is it stated?

CF 1952B - Is it stated? Rating: - Tags: *special, strings Solve time: 41s Verified: yes Solution Problem Understanding We are given a list of strings, each consisting of lowercase English letters, and for each string, we are asked to answer either "YES" or "NO" based on a hidden pattern. Observing the sample inputs and outputs, the strings "it", "submit", and "timelimitexceeded" yield "YES", while others like "is", "stated", or...

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

CF 1975G - Zimpha Fan Club

CF 1975G - Zimpha Fan Club Rating: 3000 Tags: fft, greedy, math, strings Solve time: 5m 19s Verified: no Solution

Practice › Codeforces Solutions ›

Codeforces Round 934 (Div. 1)

Codeforces Round 934 (Div. 1) Type: Div. 1 | Problems: 8 | Verified: 1/8 | Rating range: 1300-3500 | Time: 10m 17s Problem Name Rating Tags Solve Time Verified A MEX Game 1 1300 games, greedy 1m 9s ✓ B Non-Palindromic Substring 2000 hashing, implementation, math 1m 20s ✗ C Tree Compass 2300 constructive-algorithms, dfs-and-similar, greedy 1m 16s ✗ D1 Counting Is Fun (Easy Version) 2400 brute-force, combinatorics, dp 1m...

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

CF 1965C - Folding Strip

CF 1965C - Folding Strip Rating: 2300 Tags: constructive algorithms, greedy, strings Solve time: 1m 8s Verified: no Solution Problem Understanding We are given a binary string that represents a long paper strip with 0/1 values printed on it. We are allowed to choose any number of cut positions between adjacent characters, and then fold segments of the strip on top of each other simultaneously. After folding, multiple original positions...

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

CF 1976A - Verify Password

CF 1976A - Verify Password Rating: 800 Tags: implementation, sortings, strings Solve time: 5m 18s Verified: no Solution

Practice › Codeforces Solutions ›

Educational Codeforces Round 166 (Rated for Div. 2)

Educational Codeforces Round 166 (Rated for Div. 2) Type: Div. 2 | Problems: 6 | Verified: 0/6 | Rating range: 800-2800 | Time: 31m 36s Problem Name Rating Tags Solve Time Verified A Verify Password 800 implementation, sortings, strings 5m 18s ✗ B Increase/Decrease/Copy 1100 greedy, implementation 5m 15s ✗ C Job Interview 1600 binary-search, dp, greedy 5m 16s ✗ D Invertible Bracket Sequences 2000 binary-search, combinatorics, data-structures 5m 14s...

Practice › Codeforces Solutions › Codeforces Round 937 (Div. 4) ›

CF 1950G - Shuffling Songs

CF 1950G - Shuffling Songs Rating: 1900 Tags: bitmasks, dfs and similar, dp, graphs, hashing, implementation, strings Solve time: 1m 22s Verified: yes Solution Problem Understanding Each song has two attributes, a genre and a writer. After removing some songs, we are allowed to reorder the remaining songs arbitrarily. The goal is to arrange them so that every pair of neighboring songs shares at least one attribute: either the same...

Practice › Codeforces Solutions › April Fools Day Contest 2024 ›

CF 1952A - Are You a Robot, Again?

CF 1952A - Are You a Robot, Again? Rating: - Tags: *special, strings Solve time: 32s Verified: yes Solution Problem Understanding In this problem, we are given a string of digits that a robot has produced. The robot operates under a simple but peculiar rule: for each digit in the string, if the digit is even, it will remain in the output string as-is. If the digit is odd, the...

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

CF 494B - Obsessive String

CF 494B - Obsessive String Rating: 2000 Tags: dp, strings Solve time: 10m 58s Verified: no Solution Problem Understanding We are given two strings, s and t . Our goal is to count the number of ways to select one or more non-overlapping substrings from s such that each selected substring contains t somewhere inside it. A substring is defined by its starting and ending indices, and “non-overlapping” means that...

Practice › Codeforces Solutions › Codeforces Round 937 (Div. 4) ›

CF 1950E - Nearly Shortest Repeating Substring

CF 1950E - Nearly Shortest Repeating Substring Rating: 1500 Tags: brute force, implementation, number theory, strings Solve time: 1m 22s Verified: yes Solution Problem Understanding We are given a string s of length n . We want to find the smallest possible length L such that there exists a pattern string k of length L , repeated exactly n / L times, producing a string c of length n ,...

Practice › Codeforces Solutions › April Fools Day Contest 2024 ›

CF 1952H - Palindrome

CF 1952H - Palindrome Rating: - Tags: *special, implementation, strings Solve time: 1m 12s Verified: no Solution Problem Understanding The task is to determine, for each given string, whether it reads the same forwards and backwards. A palindrome is such a string, like "radar" or "racecar", while a string like "ac" is not. The input consists of multiple test cases, each providing a string of up to 100 lowercase English...

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

CF 490C - Hacking Cypher

CF 490C - Hacking Cypher Rating: 1700 Tags: brute force, math, number theory, strings Solve time: 5m 25s Verified: no Solution

Practice › Codeforces Solutions ›

Codeforces Round 282 (Div. 1)

Codeforces Round 282 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 1/4 | Rating range: 2000-3200 | Time: 24m 13s Problem Name Rating Tags Solve Time Verified B Obsessive String 2000 dp, strings 10m 58s ✗ C Helping People 2600 dp, probabilities 42s ✓ D Birthday 2700 data-structures, dfs-and-similar, dp 1m 4s ✗ E Sharti 3200 data-structures, games 11m 29s ✗

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

CF 1951E - No Palindromes

CF 1951E - No Palindromes Rating: 2000 Tags: brute force, constructive algorithms, divide and conquer, greedy, hashing, implementation, math, strings Solve time: 1m 1s Verified: no Solution Problem Understanding We are given a string and we are allowed to cut it into contiguous pieces. The goal is to decide whether we can cut it so that every resulting piece is not a palindrome. If it is possible, we must also...

Practice › Codeforces Solutions ›

April Fools Day Contest 2024

April Fools Day Contest 2024 Type: April Fools | Problems: 8 | Verified: 5/8 | Rating range: - | Time: 7m 9s Problem Name Rating Tags Solve Time Verified A Are You a Robot, Again? - *special, strings 32s ✓ B Is it stated? - *special, strings 41s ✓ C They Have Fooled - *special, brute-force, schedules 52s ✓ F Grid - *special, brute-force 1m 12s ✗ G Mathematician Takeover...

Practice › Codeforces Solutions ›

MemSQL Start[c]UP 2.0 - Round 1

MemSQL Start[c]UP 2.0 - Round 1 Type: Special | Problems: 5 | Verified: 4/5 | Rating range: 1000-2700 | Time: 9m 36s Problem Name Rating Tags Solve Time Verified A Eevee 1000 brute-force, implementation, strings 1m 6s ✓ B 4-point polyline 1800 brute-force, constructive-algorithms, geometry 2m 2s ✓ C Magic Trick 2100 combinatorics, math, probabilities 1m 44s ✓ E Three strings 2400 data-structures, dsu, string-suffix-structures 2m 7s ✓ F Permutation...

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

CF 452A - Eevee

CF 452A - Eevee Rating: 1000 Tags: brute force, implementation, strings Solve time: 1m 6s Verified: yes Solution Problem Understanding We are given a partially filled crossword slot and asked to identify which of Eevee's evolutions fits it. The input specifies the length of the word and a string pattern using lowercase letters and dots, where a dot represents an unknown character. Our task is to find which Pokémon name...

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 ›

Codeforces Round 272 (Div. 1)

Codeforces Round 272 (Div. 1) Type: Div. 1 | Problems: 2 | Verified: 0/2 | Rating range: 2700-3100 | Time: 3m 11s Problem Name Rating Tags Solve Time Verified D Dreamoon and Binary 2700 dp, strings 1m 36s ✗ E Dreamoon and Notepad 3100 data-structures 1m 35s ✗

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

CF 461E - Appleman and a Game

CF 461E - Appleman and a Game Rating: 3000 Tags: binary search, shortest paths, strings Solve time: 2m 16s Verified: yes Solution Problem Understanding Appleman starts with an empty string. In one second he may append any substring of t to the end of the string he is building. For a fixed target string s , Appleman chooses an optimal sequence of substrings and finishes s in the minimum possible...

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

CF 467D - Fedor and Essay

CF 467D - Fedor and Essay Rating: 2400 Tags: dfs and similar, dp, graphs, hashing, strings Solve time: 1m 26s Verified: no Solution Problem Understanding We are given an essay, which is a sequence of words, and a dictionary of synonym pairs. Each synonym pair allows us to replace one word with another, but only in the direction specified. Fedor wants to modify his essay to minimize the number of...

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

CF 476E - Dreamoon and Strings

CF 476E - Dreamoon and Strings Rating: 2200 Tags: dp, strings Solve time: 5m 45s Verified: yes Solution Problem Understanding We start with a string s . We may delete exactly x characters, keeping the remaining characters in their original order. The resulting string is a subsequence of s . Inside that resulting string, we look for as many non-overlapping occurrences of a pattern p as possible. For every deletion...

Practice › Codeforces Solutions ›

Codeforces Round 260 (Div. 1)

Codeforces Round 260 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2900 | Time: 7m 50s Problem Name Rating Tags Solve Time Verified A Boredom 1500 dp 1m 31s ✓ B A Lot of Games 1900 dfs-and-similar, dp, games 1m 49s ✓ C Civilization 2100 dfs-and-similar, dp, dsu 2m 1s ✓ D Serega and Fun 2700 data-structures 1m 27s ✓ E Function 2900 data-structures...

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 272 (Div. 1) ›

CF 477D - Dreamoon and Binary

CF 477D - Dreamoon and Binary Rating: 2700 Tags: dp, strings Solve time: 1m 36s Verified: no Solution Problem Understanding We are given a binary string that represents a positive integer $x$. Instead of directly printing this binary number, we are forced into a strange process that maintains a single integer variable $n$, starting at zero, and builds the output by repeatedly applying only two kinds of operations. The first...

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

CF 455B - A Lot of Games

CF 455B - A Lot of Games Rating: 1900 Tags: dfs and similar, dp, games, implementation, strings, trees Solve time: 1m 49s Verified: yes Solution Problem Understanding The game can be viewed as moving through a trie built from the given strings. We start at the root, which represents the empty string. On each turn a player chooses one outgoing edge, corresponding to appending a character. The current string must...

Practice › Codeforces Solutions › VK Cup 2012 Qualification Round 2 ›

CF 159D - Palindrome pairs

CF 159D - Palindrome pairs Rating: 1500 Tags: *special, brute force, dp, strings Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a string of lowercase letters and need to count the number of pairs of non-overlapping palindromic substrings. Formally, we are looking for tuples (a, b, x, y) such that the substring from a to b and the substring from x to y are both palindromes...

Practice › Codeforces Solutions ›

Codeforces Round 116 (Div. 2, ACM-ICPC Rules)

Codeforces Round 116 (Div. 2, ACM-ICPC Rules) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1200-2300 | Time: 8m 3s Problem Name Rating Tags Solve Time Verified A Defragmentation 1800 implementation 1m 20s ✓ B Divisibility Rules 2300 math, number-theory 1m 50s ✓ C Letter 1400 dp 1m 46s ✓ D Name 1900 greedy, strings 1m 39s ✓ F Mathematical Analysis Rocks! 1200 constructive-algorithms, implementation, math...

Practice › Codeforces Solutions ›

Codeforces Round 127 (Div. 2)

Codeforces Round 127 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-1700 | Time: 4m 35s Problem Name Rating Tags Solve Time Verified A LLPS 800 binary-search, bitmasks, brute-force 1m 6s ✓ B Brand New Easy Problem 1700 brute-force 3m 29s ✓

Practice › Codeforces Solutions ›

Codeforces Round 155 (Div. 2)

Codeforces Round 155 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 2/5 | Rating range: 1200-2300 | Time: 37m 47s Problem Name Rating Tags Solve Time Verified A Cards with Numbers 1200 constructive-algorithms, sortings 2m 30s ✗ B Jury Size 1500 brute-force, implementation 14m 52s ✓ C Anagram 1800 greedy, strings 14m 52s ✓ D Rats 2300 brute-force, dfs-and-similar, graphs 3m 1s ✗ E Dormitory 2100 dp, implementation...

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

CF 141A - Amusing Joke

CF 141A - Amusing Joke Rating: 800 Tags: implementation, sortings, strings Solve time: 1m 31s Verified: yes Solution Problem Understanding We are given three uppercase strings. The first two strings are the names written on the door, and the third string is the pile of letters found the next morning after somebody mixed everything together. The task is to check whether the third string contains exactly the same letters as...

Practice › Codeforces Solutions ›

Codeforces Round 146 (Div. 2)

Codeforces Round 146 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-1300 | Time: 5m 12s Problem Name Rating Tags Solve Time Verified A Boy or Girl 800 brute-force, implementation, strings 3m 27s ✓ B Easy Number Challenge 1300 implementation, number-theory 1m 45s ✓

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

CF 208A - Dubstep

CF 208A - Dubstep Rating: 900 Tags: strings Solve time: 59s Verified: yes Solution Problem Understanding We are given a single compressed string that represents a song that was modified by repeatedly inserting the marker string "WUB" before, after, and between the original words. After these insertions, everything was concatenated into one continuous string, so the original word boundaries are lost and all separators are hidden inside this pattern. The...

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

CF 143B - Help Kingdom of Far Far Away 2

CF 143B - Help Kingdom of Far Far Away 2 Rating: 1200 Tags: implementation, strings Solve time: 2m 19s Verified: yes Solution Problem Understanding We are given a number as a string and must print it in a banking-style money format. The formatting rules combine several independent transformations. The integer part must contain commas every three digits, counting from the right. The fractional part must contain exactly two digits. If...

Practice › Codeforces Solutions ›

Codeforces Round 124 (Div. 1)

Codeforces Round 124 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1100-2600 | Time: 6m 40s Problem Name Rating Tags Solve Time Verified A Lexicographically Maximum Subsequence 1100 greedy, strings 1m 2s ✓ B Infinite Maze 2000 dfs-and-similar, graphs 1m 39s ✓ C Paint Tree 2200 constructive-algorithms, divide-and-conquer, geometry 1m 40s ✗ E Opening Portals 2600 dsu, graphs, shortest-paths 2m 19s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 98 (Div. 2) ›

CF 137D - Palindromes

CF 137D - Palindromes Rating: 1900 Tags: dp, strings Solve time: 2m 9s Verified: yes Solution Problem Understanding We are given a string and an integer k . We may change any characters we want, and the goal is to transform the string into a concatenation of at most k palindromes while minimizing the number of modified characters. The partition boundaries are not fixed. We must decide both where to...

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

CF 223B - Two Strings

CF 223B - Two Strings Rating: 1900 Tags: data structures, dp, strings Solve time: 1m 42s Verified: yes Solution Problem Understanding We are given two lowercase strings, s and t . The task is not simply to check whether t is a subsequence of s . We must answer a stronger question. Consider every possible way to obtain t as a subsequence of s . A position i in s...

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

CF 259A - Little Elephant and Chess

CF 259A - Little Elephant and Chess Rating: 1000 Tags: brute force, strings Solve time: 1m 8s Verified: yes Solution Problem Understanding We are given an 8×8 grid representing a chessboard, but the colors of the squares may not be correct. Each square is either black, represented by "B", or white, represented by "W". The task is to determine whether we can transform this board into a proper chessboard by...

Practice › Codeforces Solutions ›

CROC-MBTU 2012, Final Round (Online version, Div. 2)

CROC-MBTU 2012, Final Round (Online version, Div. 2) Type: Div. 2 | Problems: 5 | Verified: 2/5 | Rating range: 1000-2000 | Time: 11m 54s Problem Name Rating Tags Solve Time Verified A Paper Work 1000 greedy 3m 9s ✗ B Restoring IPv6 1500 implementation, strings 1m 5s ✓ C Movie Critics 1600 greedy 3m 12s ✗ D Building Bridge 1900 geometry, ternary-search, two-pointers 1m 13s ✓ E Mad Joe...

Practice › Codeforces Solutions › Croc Champ 2013 - Qualification Round ›

CF 291B - Command Line Arguments

CF 291B - Command Line Arguments Rating: 1300 Tags: *special, implementation, strings Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a single string representing a command line in a simplified Pindows operating system. Each "lexeme" in this command line is either a contiguous sequence of non-space characters or a sequence of characters enclosed in double quotes. The first lexeme is the program name, and all subsequent...

Practice › Codeforces Solutions ›

Codeforces Round 112 (Div. 2)

Codeforces Round 112 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1000-2200 | Time: 8m 54s Problem Name Rating Tags Solve Time Verified A Supercentral Point 1000 implementation 1m 52s ✗ B Burning Midnight Oil 1500 binary-search, implementation 1m 42s ✓ C Another Problem on Strings 1600 binary-search, brute-force, dp 1m 20s ✓ D Beard Graph 2100 data-structures, dsu, trees 2m 13s ✓ E...

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

CF 165C - Another Problem on Strings

CF 165C - Another Problem on Strings Rating: 1600 Tags: binary search, brute force, dp, math, strings, two pointers Solve time: 1m 20s Verified: yes Solution Problem Understanding We are asked to count substrings of a binary string that contain exactly k ones. A substring is any contiguous sequence of characters within the string, and different occurrences at different positions count separately. For instance, in the string "1010", the substring...

Practice › Codeforces Solutions › CROC-MBTU 2012, Elimination Round (ACM-ICPC) ›

CF 245B - Internet Address

CF 245B - Internet Address Rating: 1100 Tags: implementation, strings Solve time: 1m 53s Verified: yes Solution Problem Understanding Vasya scribbled an Internet address in his notebook, but he was in a hurry and omitted all punctuation characters like : , / , and . . The original address followed the conventional structure of a URL: it had a protocol ( http or ftp ), a domain name consisting of...

Practice › Codeforces Solutions ›

Codeforces Round 135 (Div. 2)

Codeforces Round 135 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 3/3 | Rating range: 1000-1600 | Time: 5m 50s Problem Name Rating Tags Solve Time Verified A k-String 1000 implementation, strings 1m 22s ✓ B Special Offer! Super Price 999 Bourles! 1400 implementation 1m 29s ✓ C Color Stripe 1600 brute-force, dp, greedy 2m 59s ✓

Practice › Codeforces Solutions ›

Codeforces Round 146 (Div. 1)

Codeforces Round 146 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1600-3000 | Time: 11m 16s Problem Name Rating Tags Solve Time Verified A LCM Challenge 1600 number-theory 3m 2s ✓ C Cyclical Quest 2700 data-structures, string-suffix-structures, strings 2m 55s ✓ D Graph Game 3000 graphs 1m 37s ✗ E Number Challenge 2600 combinatorics, dp, implementation 3m 42s ✓

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

CF 150D - Mission Impassable

CF 150D - Mission Impassable Rating: 2600 Tags: dp, strings Solve time: 2m 26s Verified: yes Solution Problem Understanding We start with a string of length l . In one move we may choose any contiguous substring that is a palindrome and whose length k is allowed, meaning a[k] != -1 . After deleting it, the remaining characters concatenate together. The score gained from this move is a[k] . The...

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

CF 271D - Good Substrings

CF 271D - Good Substrings Rating: 1800 Tags: data structures, strings Solve time: 1m 42s Verified: yes Solution Problem Understanding We are given a lowercase string and a classification of the 26 English letters into two groups, good and bad. A substring is considered valid if it contains at most k bad characters. Among all such valid substrings, we must count how many different strings appear. The word "distinct" changes...

Practice › Codeforces Solutions ›

Coder-Strike 2014 - Round 1

Coder-Strike 2014 - Round 1 Type: Special | Problems: 4 | Verified: 1/4 | Rating range: 900-2000 | Time: 8m 35s Problem Name Rating Tags Solve Time Verified A Poster 900 greedy, implementation 2m 3s ✗ C Pattern 1200 implementation, strings 2m ✗ D Giving Awards 2000 dfs-and-similar 1m 55s ✓ E E-mail Addresses 1900 implementation 2m 37s ✗

Practice › Codeforces Solutions ›

Codeforces Round 185 (Div. 2)

Codeforces Round 185 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 0/1 | Rating range: 1100-1100 | Time: 3m 13s Problem Name Rating Tags Solve Time Verified A Whose sentence is it? 1100 implementation, strings 3m 13s ✗

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

CF 312A - Whose sentence is it?

CF 312A - Whose sentence is it? Rating: 1100 Tags: implementation, strings Solve time: 3m 13s Verified: no Solution Problem Understanding Each input line represents a sentence from a chat log, and the task is to classify who likely said it based on simple pattern clues at the beginning and end of the string. A sentence is attributed to Freda if it ends with the substring "lala." . A sentence...

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

CF 269E - String Theory

CF 269E - String Theory Rating: 3100 Tags: geometry, math, strings Solve time: 1m 58s Verified: no Solution Problem Understanding We are given a rectangular harp represented as a grid of size n × m , where pins are placed along the edges: n pins on the left and right sides, and m pins on the top and bottom sides. Each string connects exactly two pins located on different sides...

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

CF 236A - Boy or Girl

CF 236A - Boy or Girl Rating: 800 Tags: brute force, implementation, strings Solve time: 3m 27s Verified: yes Solution Problem Understanding We are given a username consisting only of lowercase English letters. The task is to count how many different characters appear in that username. The decision rule is simple. If the number of distinct characters is even, we print "CHAT WITH HER!" . If the number is odd,...

Practice › Codeforces Solutions ›

Codeforces Round 157 (Div. 2)

Codeforces Round 157 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 1/1 | Rating range: 1000-1000 | Time: 1m 8s Problem Name Rating Tags Solve Time Verified A Little Elephant and Chess 1000 brute-force, strings 1m 8s ✓

Practice › Codeforces Solutions ›

Codeforces Round 138 (Div. 1)

Codeforces Round 138 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 3/4 | Rating range: 1700-3000 | Time: 8m 30s Problem Name Rating Tags Solve Time Verified A Bracket Sequence 1700 data-structures, expression-parsing, implementation 1m 41s ✓ B Two Strings 1900 data-structures, dp, strings 1m 42s ✓ C Partial Sums 1900 combinatorics, math, number-theory 1m 25s ✓ D Spider 3000 geometry, graphs 3m 42s ✗

Practice › Codeforces Solutions › Codeforces Round 116 (Div. 2, ACM-ICPC Rules) ›

CF 180D - Name

CF 180D - Name Rating: 1900 Tags: greedy, strings Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given a multiset of characters in string s . We may rearrange these characters in any order, but we must use every character exactly once. Among all such permutations, we want the lexicographically smallest string that is still strictly larger than another string t . This is not asking for...

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

CF 281A - Word Capitalization

CF 281A - Word Capitalization Rating: 800 Tags: implementation, strings Solve time: 1m 15s Verified: yes Solution Problem Understanding We are given a single English word and need to modify it so that only the first character becomes uppercase. Every other character must stay exactly as it originally appeared. The input contains just one non-empty string. The string may already start with an uppercase letter, or it may start with...

Practice › Codeforces Solutions ›

Codeforces Round 101 (Div. 2)

Codeforces Round 101 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 800-2300 | Time: 10m 27s Problem Name Rating Tags Solve Time Verified A Amusing Joke 800 implementation, sortings, strings 1m 31s ✓ B Hopscotch 1400 geometry, math 1m 26s ✓ C Queue 1800 constructive-algorithms, greedy, sortings 2m 24s ✗ D Take-off Ramps 2300 graphs, shortest-paths 2m 15s ✓ E Clearing Up 2300 constructive-algorithms,...

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

CF 182D - Common Divisors

CF 182D - Common Divisors Rating: 1400 Tags: brute force, hashing, implementation, math, strings Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given two lowercase strings. A string d is called a divisor of another string s if s can be formed by concatenating d several times in a row. For example, "ab" divides "ababab" because repeating "ab" three times gives the full string. On the other...

Practice › Codeforces Solutions ›

CROC-MBTU 2012, Elimination Round (ACM-ICPC)

CROC-MBTU 2012, Elimination Round (ACM-ICPC) Type: ICPC/IOI | Problems: 8 | Verified: 8/8 | Rating range: 800-2200 | Time: 18m 42s Problem Name Rating Tags Solve Time Verified A System Administrator 800 implementation 3m 27s ✓ B Internet Address 1100 implementation, strings 1m 53s ✓ C Game with Coins 1700 greedy 1m 37s ✓ D Restoring Table 1500 constructive-algorithms, greedy 3m 10s ✓ E Mishap in Club 1400 greedy, implementation...

Practice › Codeforces Solutions ›

Codeforces Round 103 (Div. 2)

Codeforces Round 103 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2200 | Time: 8m 5s Problem Name Rating Tags Solve Time Verified A Arrival of the General 800 implementation 1m 52s ✓ B Meeting 1300 implementation 1m 15s ✓ C Anagram Search 1500 implementation, strings 1m 23s ✓ D Missile Silos 1900 data-structures, dfs-and-similar, graphs 2m 10s ✓ E Competition 2200 data-structures, greedy...

Practice › Codeforces Solutions ›

Codeforces Round 187 (Div. 1)

Codeforces Round 187 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 2/3 | Rating range: 2000-2900 | Time: 6m 22s Problem Name Rating Tags Solve Time Verified B Sereja and Periods 2000 binary-search, dfs-and-similar, strings 1m 23s ✓ D Sereja and Straight Lines 2500 binary-search, data-structures, geometry 1m 45s ✓ E Sereja and Squares 2900 dp 3m 14s ✗

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

CF 213E - Two Permutations

CF 213E - Two Permutations Rating: 2700 Tags: data structures, hashing, strings Solve time: 1m 3s Verified: yes Solution Problem Understanding We are given two permutations, one of length n and another of length m ( n ≤ m ). A permutation is a sequence containing all numbers from 1 to its length exactly once. We are asked to count how many distinct integers d exist such that if we...

Practice › Codeforces Solutions › Coder-Strike 2014 - Round 1 ›

CF 412C - Pattern

CF 412C - Pattern Rating: 1200 Tags: implementation, strings Solve time: 2m Verified: no Solution Problem Understanding Each pattern is a string made of lowercase English letters and the wildcard character ? . A wildcard can represent any lowercase letter. Two patterns intersect if there exists at least one concrete string that matches both of them. For example, a?c and abc intersect because the string abc satisfies both patterns. On...

Practice › Codeforces Solutions › Croc Champ 2013 - Qualification Round ›

CF 291E - Tree-String Problem

CF 291E - Tree-String Problem Rating: 2000 Tags: *special, dfs and similar, hashing, strings Solve time: 1m 51s Verified: yes Solution Problem Understanding We have a rooted tree with root 1 . Every edge from a parent to a child contains a lowercase string. If we walk downward through the tree and read characters along the edges, we obtain a long text embedded into the tree. A position is not...

Practice › Codeforces Solutions › Codeforces Testing Round 4 ›

CF 147A - Punctuation

CF 147A - Punctuation Rating: 1300 Tags: implementation, strings Solve time: 1m 18s Verified: yes Solution Problem Understanding We are given a string containing lowercase letters, spaces, and a limited set of punctuation marks: comma, dot, exclamation mark, and question mark. Our goal is to reformat this string so that words are separated by exactly one space, no spaces appear before punctuation, and each punctuation mark is followed by exactly...

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 Round 107 (Div. 2) ›

CF 151B - Phone Numbers

CF 151B - Phone Numbers Rating: 1200 Tags: implementation, strings Solve time: 1m 46s Verified: yes Solution Problem Understanding Each friend has a phone book containing numbers written in the format XX-XX-XX . Every phone number belongs to exactly one of three categories. A taxi number uses the same digit everywhere. Examples are 11-11-11 or 55-55-55 . A pizza number is strictly decreasing when we read its digits from left...

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

CF 196A - Lexicographically Maximum Subsequence

CF 196A - Lexicographically Maximum Subsequence Rating: 1100 Tags: greedy, strings Solve time: 1m 2s Verified: yes Solution Problem Understanding We are given a string composed of lowercase English letters, and our goal is to select a subsequence from it that is lexicographically the largest possible. A subsequence is formed by taking zero or more characters in order without reordering them. Lexicographical comparison is just dictionary order, so "bca" is...

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

CF 202A - LLPS

CF 202A - LLPS Rating: 800 Tags: binary search, bitmasks, brute force, greedy, implementation, strings Solve time: 1m 6s Verified: yes Solution Problem Understanding We are given a lowercase string and must choose some characters, in order, to form a subsequence that is both a palindrome and lexicographically as large as possible. A subsequence does not need to stay contiguous. We may skip characters, but the remaining characters must keep...

Practice › Codeforces Solutions › CROC-MBTU 2012, Final Round (Online version, Div. 2) ›

CF 250B - Restoring IPv6

CF 250B - Restoring IPv6 Rating: 1500 Tags: implementation, strings Solve time: 1m 5s Verified: yes Solution Problem Understanding An IPv6 address in its full form is a fixed structure made of eight blocks. Each block represents 16 bits and is written as exactly four hexadecimal characters, including leading zeros when necessary. The blocks are separated by colons, so a fully expanded address always has the same length pattern and...

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

CF 339A - Helpful Maths

CF 339A - Helpful Maths Rating: 800 Tags: greedy, implementation, sortings, strings Solve time: 4m 3s Verified: yes Solution Problem Understanding We are given a single string that represents a sum of small integers. The expression is written using digits and plus signs, where every number is guaranteed to be either 1, 2, or 3. The task is to rearrange the numbers so that the resulting expression is sorted in...

Practice › Codeforces Solutions ›

Codeforces Round 254 (Div. 1)

Codeforces Round 254 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 2/3 | Rating range: 1600-2700 | Time: 4m 8s Problem Name Rating Tags Solve Time Verified A DZY Loves Physics 1600 greedy, math 1m 32s ✓ D DZY Loves Strings 2500 binary-search, hashing, strings 1m 6s ✓ E DZY Loves Planting 2700 binary-search, dsu, trees 1m 30s ✗

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177G2 - Fibonacci Strings

CF 177G2 - Fibonacci Strings Rating: 2600 Tags: matrices, strings Solve time: 1m 59s Verified: yes Solution Problem Understanding We build strings using the Fibonacci recurrence, except concatenation replaces addition. The first two strings are: f1 = "a" f2 = "b" Every later string is formed by concatenating the previous string with the one before it: fn = f(n-1) + f(n-2) The beginning looks like this: f1 = a f2...

Practice › Codeforces Solutions ›

Codeforces Testing Round 4

Codeforces Testing Round 4 Type: Special | Problems: 2 | Verified: 2/2 | Rating range: 1300-2500 | Time: 2m 45s Problem Name Rating Tags Solve Time Verified A Punctuation 1300 implementation, strings 1m 18s ✓ B Smile House 2500 binary-search, graphs, matrices 1m 27s ✓

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

CF 260B - Ancient Prophesy

CF 260B - Ancient Prophesy Rating: 1600 Tags: brute force, implementation, strings Solve time: 2m 12s Verified: yes Solution Problem Understanding The input is a long string made only of digits and hyphens. Somewhere inside this string, there may be many substrings that look like dates written in the exact format dd-mm-yyyy . We must find which valid date appears most often as a substring. A valid date must satisfy...

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

CF 444D - DZY Loves Strings

CF 444D - DZY Loves Strings Rating: 2500 Tags: binary search, hashing, strings, two pointers Solve time: 1m 6s Verified: yes Solution Problem Understanding We are given a long string s and a list of pairs of small strings (a_i, b_i) . For each pair, we need to find the shortest substring of s that contains both a_i and b_i as substrings. If no substring contains both, we report -1...

Practice › Codeforces Solutions › CROC-MBTU 2012, Elimination Round (ACM-ICPC) ›

CF 245F - Log Stream Analysis

CF 245F - Log Stream Analysis Rating: 2000 Tags: binary search, brute force, implementation, strings Solve time: 3m 5s Verified: yes Solution Problem Understanding We are given a chronologically ordered stream of log entries, where each entry has an exact timestamp down to the second and an associated message describing a program warning. The task is not to process the messages themselves, but to reason purely about the timing of...

Practice › Codeforces Solutions › VK Cup 2012 Qualification Round 2 ›

CF 159C - String Manipulation 1.0

CF 159C - String Manipulation 1.0 Rating: 1400 Tags: *special, binary search, brute force, data structures, strings Solve time: 1m 31s Verified: yes Solution Problem Understanding We are given a string s and an integer k . The user initially registers a username t which is simply the string s repeated k times consecutively. After that, a sequence of edits occurs, each removing the p -th occurrence of a specified...

Practice › Codeforces Solutions ›

Croc Champ 2013 - Qualification Round

Croc Champ 2013 - Qualification Round Type: Special | Problems: 2 | Verified: 2/2 | Rating range: 1300-2000 | Time: 3m 17s Problem Name Rating Tags Solve Time Verified B Command Line Arguments 1300 *special, implementation, strings 1m 26s ✓ E Tree-String Problem 2000 *special, dfs-and-similar, hashing 1m 51s ✓

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

CF 186A - Comparing Strings

CF 186A - Comparing Strings Rating: 1100 Tags: implementation, strings Solve time: 3m 47s Verified: yes Solution Problem Understanding We are given two strings representing the genomes of two dwarves. The goal is to determine whether these two genomes could belong to the same race under a very specific definition: the first genome can be transformed into the second genome by swapping exactly two characters in the first genome. The...

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316G1 - Good Substrings

CF 316G1 - Good Substrings Rating: 1700 Tags: hashing, strings Solve time: 2m 24s Verified: no Solution Problem Understanding We are given a main string s . From this string, we consider every possible substring and want to count how many distinct substrings are considered “good”. Whether a candidate substring t is good is not decided by properties of s itself, but by a small set of constraints. Each constraint...

Practice › Codeforces Solutions ›

Codeforces Round 102 (Div. 2)

Codeforces Round 102 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 1000-1200 | Time: 4m 38s Problem Name Rating Tags Solve Time Verified A Help Vasilisa the Wise 2 1000 brute-force, math 2m 19s ✓ B Help Kingdom of Far Far Away 2 1200 implementation, strings 2m 19s ✓

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

CF 144C - Anagram Search

CF 144C - Anagram Search Rating: 1500 Tags: implementation, strings Solve time: 1m 23s Verified: yes Solution Problem Understanding We are asked to count the number of substrings of a string s that can be transformed into an anagram of a given string p . The string s can contain question marks ? , which can be replaced by any lowercase letter. A substring is defined as a contiguous segment...

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 55s Verified: yes Solution Problem Understanding We are given one large text string s , then many query strings x . For every query, we must count how many substrings of s are rotations of x . If x = "abcd" , then all of these strings are considered equivalent: abcd , bcda...

Practice › Codeforces Solutions ›

Codeforces Round 107 (Div. 2)

Codeforces Round 107 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-1200 | Time: 3m 17s Problem Name Rating Tags Solve Time Verified A Soft Drinking 800 implementation, math 1m 31s ✓ B Phone Numbers 1200 implementation, strings 1m 46s ✓

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

CF 254C - Anagram

CF 254C - Anagram Rating: 1800 Tags: greedy, strings Solve time: 14m 52s Verified: yes Solution Problem Understanding We have two uppercase strings of equal length. We may replace characters in the first string, and after all replacements the final string only needs to be an anagram of the second string. The order does not matter for the multiset of characters, but among all valid answers using the minimum number...

Practice › Codeforces Solutions ›

Codeforces Round 130 (Div. 2)

Codeforces Round 130 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 4/4 | Rating range: 900-2100 | Time: 4m 49s Problem Name Rating Tags Solve Time Verified A Dubstep 900 strings 59s ✓ C Police Station 1900 dp, graphs, shortest-paths 1m 18s ✓ D Prizes, Prizes, more Prizes 1200 implementation 1m 26s ✓ E Blood Cousins 2100 binary-search, data-structures, dfs-and-similar 1m 6s ✓

Practice › Codeforces Solutions ›

Codeforces Round 172 (Div. 2)

Codeforces Round 172 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 1/1 | Rating range: 800-800 | Time: 1m 15s Problem Name Rating Tags Solve Time Verified A Word Capitalization 800 implementation, strings 1m 15s ✓

Practice › Codeforces Solutions ›

Codeforces Round 118 (Div. 2)

Codeforces Round 118 (Div. 2) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 1100-1200 | Time: 6m 28s Problem Name Rating Tags Solve Time Verified A Comparing Strings 1100 implementation, strings 3m 47s ✓ B Growing Mushrooms 1200 greedy, sortings 2m 41s ✓

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

CF 219A - k-String

CF 219A - k-String Rating: 1000 Tags: implementation, strings Solve time: 1m 22s Verified: yes Solution Problem Understanding We are given a lowercase string and an integer k . We may rearrange the letters however we want. The goal is to build a new string that consists of exactly k identical blocks placed one after another. For example, if k = 3 , then the final string must look like:...

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

CF 314B - Sereja and Periods

CF 314B - Sereja and Periods Rating: 2000 Tags: binary search, dfs and similar, strings Solve time: 1m 23s Verified: yes Solution Problem Understanding We are given two base strings, call them a and c , and two integers b and d . From these, two longer strings are conceptually constructed: the first string is a repeated b times, and the second is c repeated p times for some unknown...

Practice › Codeforces Solutions › ABBYY Cup 2.0 - Easy ›

CF 177G1 - Fibonacci Strings

CF 177G1 - Fibonacci Strings Rating: 2400 Tags: strings Solve time: 3m 11s Verified: yes Solution Problem Understanding The problem asks us to count occurrences of query strings inside Fibonacci strings. Fibonacci strings are defined recursively: the first string is "a" , the second is "b" , and each subsequent string is the concatenation of the previous string followed by the one before that. For example, the third string is...

Practice › Codeforces Solutions ›

Codeforces Round 197 (Div. 2)

Codeforces Round 197 (Div. 2) Type: Div. 2 | Problems: 1 | Verified: 1/1 | Rating range: 800-800 | Time: 4m 3s Problem Name Rating Tags Solve Time Verified A Helpful Maths 800 greedy, implementation, sortings 4m 3s ✓

Practice › Codeforces Solutions › VK Cup 2012 Round 2 ›

CF 163E - e-Government

CF 163E - e-Government Rating: 2800 Tags: data structures, dfs and similar, dp, strings, trees Solve time: 2m 16s Verified: yes Solution Problem Understanding We have a fixed set of surnames. Each surname can be either active or inactive. Initially every surname is active. The system must process three kinds of operations. A query +i activates the i-th surname. A query -i deactivates the i-th surname. A query ?text asks...

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 › CROC-MBTU 2012, Elimination Round (ACM-ICPC) ›

CF 245H - Queries for Number of Palindromes

CF 245H - Queries for Number of Palindromes Rating: 1800 Tags: dp, hashing, strings Solve time: 3m Verified: yes Solution Problem Understanding We are given a fixed string consisting of lowercase letters, and many independent queries. Each query specifies a contiguous segment of this string, and for that segment we must count how many substrings are palindromes. A substring is determined by choosing two indices inside the query range and...

Practice › Codeforces Solutions ›

Codeforces Beta Round 70 (Div. 2)

Codeforces Beta Round 70 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 800-2300 | Time: 12m 16s Problem Name Rating Tags Solve Time Verified A Haiku 800 implementation, strings 3m 30s ✓ B Easter Eggs 1200 constructive-algorithms, implementation 1m 59s ✗ C Beaver Game 2000 dp, games, number-theory 2m 6s ✓ D Archer's Shot 2300 binary-search, geometry, math 2m 7s ✓ E Evacuation 2300...

Practice › Codeforces Solutions › Codeforces Beta Round 78 (Div. 2 Only) ›

CF 99A - Help Far Away Kingdom

CF 99A - Help Far Away Kingdom Rating: 800 Tags: strings Solve time: 1m 25s Verified: yes Solution Problem Understanding We are given a decimal number as a string. The number contains an integer part, then a dot, then a fractional part. The task is to simulate the kingdom's strange rounding rules. The rules are intentionally incomplete. If the integer part ends with digit 9 , nobody except Vasilisa can...

Practice › Codeforces Solutions › Codeforces Beta Round 77 (Div. 2 Only) ›

CF 96A - Football

CF 96A - Football Rating: 900 Tags: implementation, strings Solve time: 1m 24s Verified: yes Solution Problem Understanding We are given a string made only of '0' and '1' . Each character represents the team of a football player standing in a line. A dangerous situation happens if at least seven consecutive players belong to the same team. The task is simply to check whether the string contains either seven...

Practice › Codeforces Solutions ›

Codeforces Beta Round 95 (Div. 2)

Codeforces Beta Round 95 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 5/6 | Rating range: 1000-2000 | Time: 10m 6s Problem Name Rating Tags Solve Time Verified A cAPS lOCK 1000 implementation, strings 1m 16s ✓ B Opposites Attract 1200 implementation, math 1m 34s ✓ C The World is a Theatre 1400 combinatorics, math 1m 35s ✓ D Subway 1600 dfs-and-similar, graphs 1m 14s ✓ E Yet...

Practice › Codeforces Solutions › Yandex.Algorithm Open 2011: Qualification 1 ›

CF 81B - Sequence Formatting

CF 81B - Sequence Formatting Rating: 1700 Tags: implementation, strings Solve time: 1m 43s Verified: yes Solution Problem Understanding We are given a messy textual representation of a sequence. The string may contain positive integers, commas, spaces, and the special token ... . Spaces may appear in the wrong places or appear multiple times. The task is purely formatting. We must rewrite the string so that every token follows a...

Practice › Codeforces Solutions ›

Codeforces Beta Round 65 (Div. 2)

Codeforces Beta Round 65 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 800-2200 | Time: 8m 23s Problem Name Rating Tags Solve Time Verified A Way Too Long Words 800 strings 1m 28s ✓ B Progress Bar 1300 implementation, math 1m 7s ✓ C Round Table Knights 1600 dp, math, number-theory 1m 40s ✓ D Solitaire 2200 brute-force, implementation 2m 18s ✓ E Nuclear...

Practice › Codeforces Solutions › Codeforces Beta Round 5 ›

CF 5B - Center Alignment

CF 5B - Center Alignment Rating: 1200 Tags: implementation, strings Solve time: 1m 24s Verified: yes Solution Problem Understanding We are given several lines of text. Every line may contain letters, digits, and spaces inside the line, but never at the beginning or end. The task is to print all lines inside a rectangular frame made of * characters. The inside width of the frame must equal the length of...

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

CF 113A - Grammar Lessons

CF 113A - Grammar Lessons Rating: 1600 Tags: implementation, strings Solve time: 4m 41s Verified: yes Solution Problem Understanding We are given a single line containing several lowercase words separated by spaces. Every valid word in Petya's language belongs to exactly one grammatical category and exactly one gender, determined entirely by its suffix. There are only six legal suffixes: lios for masculine adjectives liala for feminine adjectives etr for masculine...

Practice › Codeforces Solutions ›

Unknown Language Round 3

Unknown Language Round 3 Type: Special | Problems: 10 | Verified: 10/10 | Rating range: 1100-2400 | Time: 23m 31s Problem Name Rating Tags Solve Time Verified A Carpeting the Room 1100 *special, implementation 2m 19s ✓ B Friendly Numbers 1500 *special, implementation 2m 19s ✓ C A+B 1400 *special, implementation 1m 27s ✓ D World of Mouth 1500 *special, strings 2m 18s ✓ E Lamps in a Line 1600...

Practice › Codeforces Solutions › Codeforces Beta Round 98 (Div. 2) ›

CF 137E - Last Chance

CF 137E - Last Chance Rating: 2000 Tags: data structures, implementation, strings Solve time: 1m 19s Verified: yes Solution Problem Understanding We are given a string s consisting of uppercase and lowercase Latin letters, and we are asked to analyze its substrings according to a specific property: a substring is "good" if the number of vowels it contains is at most twice the number of consonants. We want to find...

Practice › Codeforces Solutions › School Team Contest 1 (Winter Computer School 2010/11) ›

CF 39J - Spelling Check

CF 39J - Spelling Check Rating: 1500 Tags: hashing, implementation, strings Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given two lowercase strings. The first string is exactly one character longer than the second. We want to find every position in the first string such that removing the character at that position makes the two strings identical. The task is not to perform arbitrary edits. Only one...

Practice › Codeforces Solutions ›

Codeforces Beta Round 98 (Div. 2)

Codeforces Beta Round 98 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 900-2000 | Time: 7m 45s Problem Name Rating Tags Solve Time Verified A Postcards and photos 900 implementation 1m 28s ✓ B Permutation 1000 greedy 1m 13s ✓ C History 1500 sortings 1m 36s ✓ D Palindromes 1900 dp, strings 2m 9s ✓ E Last Chance 2000 data-structures, implementation, strings 1m 19s...

Practice › Codeforces Solutions › Codeforces Beta Round 85 (Div. 2 Only) ›

CF 112A - Petya and Strings

CF 112A - Petya and Strings Rating: 800 Tags: implementation, strings Solve time: 1m 37s Verified: yes Solution Problem Understanding We are given two strings made of English letters. Both strings have the same length, but letters may appear in either uppercase or lowercase form. The task is to compare the two strings lexicographically while completely ignoring letter case. Ignoring case means that 'A' and 'a' must be treated as...

Practice › Codeforces Solutions › Codeforces Beta Round 64 ›

CF 70B - Text Messaging

CF 70B - Text Messaging Rating: 1600 Tags: expression parsing, greedy, strings Solve time: 1m 39s Verified: yes Solution Problem Understanding We are given the maximum length of a single SMS message and one complete text consisting of sentences separated by spaces. A sentence always ends with one of . , ? , or ! . Words contain only letters. The task is to split the text into the minimum...

Practice › Codeforces Solutions › Codeforces Beta Round 83 (Div. 2 Only) ›

CF 108A - Palindromic Times

CF 108A - Palindromic Times Rating: 1000 Tags: implementation, strings Solve time: 4m 56s Verified: yes Solution Problem Understanding The task is to find the next time on a 24-hour digital clock that reads as a palindrome. The input is a string formatted as "HH:MM", representing hours and minutes in 24-hour notation. A palindromic time reads the same forwards and backwards when ignoring the colon, such as "12:21" or "03:30"....

Practice › Codeforces Solutions ›

Codeforces Beta Round 40 (Div. 2)

Codeforces Beta Round 40 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-1900 | Time: 7m 28s Problem Name Rating Tags Solve Time Verified A Translation 800 implementation, strings 1m 14s ✓ B Martian Dollar 1400 brute-force 1m 8s ✓ C Email address 1300 expression-parsing, implementation 1m 41s ✗ D Pawn 1900 dp 1m 37s ✓ E 3-cycles 1900 constructive-algorithms, graphs, greedy 1m 48s...

Practice › Codeforces Solutions › School Personal Contest #1 (Winter Computer School 2010/11) - Codeforces Beta Round 38 (ACM-ICPC Rules) ›

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...

Practice › Codeforces Solutions ›

Codeforces Beta Round 74 (Div. 2 Only)

Codeforces Beta Round 74 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 1000-1100 | Time: 3m 17s Problem Name Rating Tags Solve Time Verified A Cableway 1000 greedy, math 1m 33s ✓ B African Crossword 1100 implementation, strings 1m 44s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 5 ›

CF 5C - Longest Regular Bracket Sequence

CF 5C - Longest Regular Bracket Sequence Rating: 1900 Tags: constructive algorithms, data structures, dp, greedy, sortings, strings Solve time: 1m 21s Verified: yes Solution Problem Understanding We are given a string made only of ( and ) . Among all contiguous substrings, we need to find the maximum length of a substring that forms a valid bracket sequence. We also need to count how many substrings achieve that maximum...

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

CF 87B - Vasya and Types

CF 87B - Vasya and Types Rating: 1800 Tags: implementation, strings Solve time: 1m 56s Verified: yes Solution Problem Understanding The language in this problem has only two real base types, void and errtype . Every other type is defined through typedef , and every query asks us to evaluate a type expression with typeof . A type expression is built from a base name plus some number of *...

Practice › Codeforces Solutions ›

Codeforces Beta Round 86 (Div. 1 Only)

Codeforces Beta Round 86 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1600-2700 | Time: 15m 15s Problem Name Rating Tags Solve Time Verified A Grammar Lessons 1600 implementation, strings 4m 41s ✓ B Petr# 2000 brute-force, data-structures, hashing 3m 20s ✓ C Double Happiness 2200 brute-force, math, number-theory 3m 20s ✓ D Museum 2700 math, matrices, probabilities 1m 55s ✓ E Sleeping...

Practice › Codeforces Solutions › Codeforces Beta Round 42 (Div. 2) ›

CF 43A - Football

CF 43A - Football Rating: 1000 Tags: strings Solve time: 1m 29s Verified: yes Solution Problem Understanding We are given the sequence of goals scored during a football match. Every line after the first contains the name of the team that scored one goal. The task is to determine which team scored more goals overall. The input guarantees that at most two distinct team names appear, and the match never...

Practice › Codeforces Solutions ›

Codeforces Beta Round 67 (Div. 2)

Codeforces Beta Round 67 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1000-2400 | Time: 9m 31s Problem Name Rating Tags Solve Time Verified A Life Without Zeros 1000 implementation 1m 34s ✓ B Facetook Priority Wall 1500 expression-parsing, implementation, strings 2m 14s ✗ C Modified GCD 1600 binary-search, number-theory 1m 40s ✓ D Big Maximum Sum 2000 data-structures, dp, greedy 1m 34s ✓...

Practice › Codeforces Solutions › Codeforces Beta Round 42 (Div. 2) ›

CF 43B - Letter

CF 43B - Letter Rating: 1100 Tags: implementation, strings Solve time: 1m 31s Verified: yes Solution Problem Understanding We are given two strings. The first string is the newspaper headline, and the second string is the anonymous letter Vasya wants to build from it. Every non-space character from the headline can be used at most once. Spaces are special, they do not consume anything. If the letter text contains spaces,...

Practice › Codeforces Solutions › Codeforces Beta Round 54 (Div. 2) ›

CF 58A - Chat room

CF 58A - Chat room Rating: 1000 Tags: greedy, strings Solve time: 1m 20s Verified: yes Solution Problem Understanding The problem asks whether Vasya, who typed a string of lowercase letters, effectively managed to say "hello". The goal is not to check if the typed string is exactly "hello", but whether we can remove some letters (possibly zero) to produce the sequence h , e , l , l ,...

Practice › Codeforces Solutions ›

Codeforces Beta Round 47

Codeforces Beta Round 47 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 800-2300 | Time: 6m 55s Problem Name Rating Tags Solve Time Verified A Domino piling 800 greedy, math 1m 5s ✓ B Choosing Symbol Pairs 1500 strings 1m 15s ✓ C Happy Farm 5 2000 geometry 55s ✓ D Bombing 2100 binary-search, dp, probabilities 1m 42s ✗ E Square Equation Roots 2300 math 1m 58s...

Practice › Codeforces Solutions ›

Codeforces Beta Round 90

Codeforces Beta Round 90 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 800-2500 | Time: 9m 34s Problem Name Rating Tags Solve Time Verified A Epic Game 800 implementation 1m 29s ✓ B Before Exam 1900 constructive-algorithms, implementation, sortings 2m 2s ✓ C Education Reform 2000 dp 2m 59s ✗ D String Transformation 2500 hashing, strings 1m 34s ✓ E Alternative Reality 2400 geometry 1m 30s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 95 (Div. 2) ›

CF 131A - cAPS lOCK

CF 131A - cAPS lOCK Rating: 1000 Tags: implementation, strings Solve time: 1m 16s Verified: yes Solution Problem Understanding The problem gives us a single word consisting of uppercase and lowercase Latin letters. This word may have been typed with the Caps Lock key unintentionally engaged. We are asked to correct such accidental capitalization. Specifically, we need to change the case of all letters in the word if either the...

Practice › Codeforces Solutions ›

Codeforces Beta Round 76 (Div. 2 Only)

Codeforces Beta Round 76 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 900-1300 | Time: 3m 35s Problem Name Rating Tags Solve Time Verified A Restoring Password 900 implementation, strings 1m 58s ✓ B Friends 1300 graphs, implementation, math 1m 37s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 17 ›

CF 17E - Palisection

CF 17E - Palisection Rating: 2900 Tags: strings Solve time: 3m 50s Verified: yes Solution Problem Understanding We are given a string and we consider every palindromic substring inside it. Each occurrence matters separately, even if two substrings have the same text. For example, in "aaa" there are three different occurrences of "a" . Every palindrome corresponds to an interval [l, r] . We must count how many unordered pairs...

Practice › Codeforces Solutions › Codeforces Beta Round 8 ›

CF 8A - Train and Peter

CF 8A - Train and Peter Rating: 1200 Tags: strings Solve time: 1m 17s Verified: yes Solution Problem Understanding We are given a string that represents the sequence of station flags seen while traveling from city A to city B. Peter woke up twice during the trip and wrote down two substrings he saw, in chronological order. The question is whether these two observations could appear while traveling forward, backward,...

Practice › Codeforces Solutions › Codeforces Beta Round 70 (Div. 2) ›

CF 78A - Haiku

CF 78A - Haiku Rating: 800 Tags: implementation, strings Solve time: 3m 30s Verified: yes Solution Problem Understanding We are given three lines representing the three phrases of a poem. A valid haiku must contain exactly 5 vowel letters in the first phrase, 7 in the second, and 5 in the third. For this problem, syllables are simplified into vowel counts. Only the lowercase letters a , e , i...

Practice › Codeforces Solutions ›

Codeforces Beta Round 91 (Div. 1 Only)

Codeforces Beta Round 91 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1100-2500 | Time: 9m 56s Problem Name Rating Tags Solve Time Verified A Lucky Sum 1100 implementation 1m 36s ✓ B Lucky Transformation 1500 strings 2m 26s ✓ C Lucky Permutation 1900 brute-force, combinatorics, number-theory 1m 34s ✓ D Lucky Segments 2500 binary-search, implementation, two-pointers 1m 59s ✓ E Lucky Array...

Practice › Codeforces Solutions › Codeforces Beta Round 71 ›

CF 79C - Beaver

CF 79C - Beaver Rating: 1800 Tags: data structures, dp, greedy, hashing, strings, two pointers Solve time: 1m 27s Verified: yes Solution Problem Understanding We are asked to find the longest contiguous substring of a string s that avoids certain "boring" substrings. In other words, given a string s and a small list of forbidden patterns b1, b2, ..., bn , we must identify the longest segment of s that...

Practice › Codeforces Solutions ›

Codeforces Beta Round 61 (Div. 2)

Codeforces Beta Round 61 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 1100-2000 | Time: 9m 20s Problem Name Rating Tags Solve Time Verified A Petya and Java 1300 implementation, strings 1m 33s ✓ B Petya and Countryside 1100 brute-force, implementation 1m 25s ✓ C Petya and File System 1800 data-structures, implementation 2m 13s ✓ D Petya and His Friends 1700 constructive-algorithms, math, number-theory...

Practice › Codeforces Solutions › Codeforces Beta Round 84 (Div. 2 Only) ›

CF 110B - Lucky String

CF 110B - Lucky String Rating: 1100 Tags: constructive algorithms, strings Solve time: 2m 58s Verified: yes Solution Problem Understanding We need to build a lowercase string of length n that satisfies a special condition on repeated letters. For every character, we look at all positions where it appears. If a character appears multiple times, the difference between consecutive positions must always be a lucky number. In this problem, lucky...

Practice › Codeforces Solutions ›

Codeforces Beta Round 42 (Div. 2)

Codeforces Beta Round 42 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1000-2300 | Time: 9m 18s Problem Name Rating Tags Solve Time Verified A Football 1000 strings 1m 29s ✓ B Letter 1100 implementation, strings 1m 31s ✓ C Lucky Tickets 1300 greedy 1m 12s ✓ D Journey 2000 brute-force, constructive-algorithms, implementation 1m 39s ✓ E Race 2300 brute-force, implementation, two-pointers 3m 27s...

Practice › Codeforces Solutions ›

Codeforces Beta Round 55 (Div. 2)

Codeforces Beta Round 55 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 800-2000 | Time: 8m 58s Problem Name Rating Tags Solve Time Verified A Word 800 implementation, strings 1m 11s ✓ B Fortune Telling 1200 implementation, number-theory 1m 57s ✗ C Title 1600 expression-parsing 1m 53s ✓ D Team Arrangement 2000 constructive-algorithms, greedy, implementation 2m 39s ✗ E Shortest Path 2000 graphs, shortest-paths...

Practice › Codeforces Solutions › Codeforces Beta Round 34 (Div. 2) ›

CF 34C - Page Numbers

CF 34C - Page Numbers Rating: 1300 Tags: expression parsing, implementation, sortings, strings Solve time: 1m 7s Verified: yes Solution Problem Understanding We are asked to process a user-entered sequence of page numbers for printing. The input is a single string of positive integers separated by commas, such as 1,2,3,1,1,2,6,6,2 . Some numbers may repeat, possibly non-consecutively. Our goal is to produce a condensed, canonical representation: consecutive numbers are merged...

Practice › Codeforces Solutions ›

Codeforces Beta Round 16 (Div. 2 Only)

Codeforces Beta Round 16 (Div. 2 Only) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-1900 | Time: 7m 6s Problem Name Rating Tags Solve Time Verified A Flag 800 implementation 1m 8s ✓ B Burglar and Matches 900 greedy, implementation, sortings 1m 13s ✓ C Monitor 1800 binary-search, number-theory 1m 37s ✓ D Logging 1900 implementation, strings 1m 34s ✓ E Fish 1900 bitmasks, dp,...

Practice › Codeforces Solutions › Codeforces Beta Round 76 (Div. 2 Only) ›

CF 94A - Restoring Password

CF 94A - Restoring Password Rating: 900 Tags: implementation, strings Solve time: 1m 58s Verified: yes Solution Problem Understanding We are given an encrypted password represented as a binary string of length 80. The original password had exactly 8 decimal digits, and each digit was encoded into a block of 10 binary characters. The mapping between digits and binary blocks is also provided: after the encrypted string, we receive 10...

Practice › Codeforces Solutions ›

Codeforces Beta Round 83 (Div. 2 Only)

Codeforces Beta Round 83 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 1000-1400 | Time: 9m 3s Problem Name Rating Tags Solve Time Verified A Palindromic Times 1000 implementation, strings 4m 56s ✓ B Datatypes 1400 math, sortings 4m 7s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 90 ›

CF 119D - String Transformation

CF 119D - String Transformation Rating: 2500 Tags: hashing, strings Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given two strings, a and b , of equal length up to one million characters. The task is to find indices i and j in a such that if we perform a specific transformation, we get b . The transformation works as follows: take the substring between i+1 and...

Practice › Codeforces Solutions › Codeforces Beta Round 16 (Div. 2 Only) ›

CF 16D - Logging

CF 16D - Logging Rating: 1900 Tags: implementation, strings Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given a sequence of log entries in the exact order they were written. Originally every entry had both a date and a time, but the dates were lost, so only the 12-hour clock timestamps remain. The task is to reconstruct the smallest possible number of distinct days that could produce...

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 › Codeforces Beta Round 31 (Div. 2, Codeforces format) ›

CF 31B - Sysadmin Bob

CF 31B - Sysadmin Bob Rating: 1500 Tags: greedy, implementation, strings Solve time: 1m 11s Verified: yes Solution Problem Understanding We are given a single string that represents multiple email addresses concatenated together with no separators. Each email address has the form A@B , where A and B are non-empty strings consisting of lowercase Latin letters. Our task is to split the string into a sequence of valid email addresses....

Practice › Codeforces Solutions ›

Codeforces Beta Round 85 (Div. 2 Only)

Codeforces Beta Round 85 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-1200 | Time: 3m 19s Problem Name Rating Tags Solve Time Verified A Petya and Strings 800 implementation, strings 1m 37s ✓ B Petya and Square 1200 implementation, math 1m 42s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 65 (Div. 2) ›

CF 71A - Way Too Long Words

CF 71A - Way Too Long Words Rating: 800 Tags: strings Solve time: 1m 28s Verified: yes Solution Problem Understanding We are given several lowercase words and must shorten only the ones that are considered "too long". A word is too long if its length is greater than 10. The shortening rule is very specific. We keep the first character and the last character, then replace everything in between with...

Practice › Codeforces Solutions › Codeforces Beta Round 89 (Div. 2) ›

CF 118C - Fancy Number

CF 118C - Fancy Number Rating: 1900 Tags: brute force, greedy, sortings, strings Solve time: 2m 51s Verified: yes Solution Problem Understanding We are given a string of digits representing a car number. The number is considered beautiful if at least k positions contain the same digit. We may change any digit into another digit, and changing digit a into digit b costs |a - b| . The task has...

Practice › Codeforces Solutions › Unknown Language Round 2 ›

CF 72E - Ali goes shopping

CF 72E - Ali goes shopping Rating: 1800 Tags: *special, brute force, strings Solve time: 7m 34s Verified: yes Solution Problem Understanding We are given a lowercase string and must find the substring that appears the largest number of times inside it. Occurrences may overlap. Among all substrings with the same maximum frequency, we choose the longest one. If there is still a tie, we choose the lexicographically largest substring....

Practice › Codeforces Solutions › Codeforces Beta Round 40 (Div. 2) ›

CF 41A - Translation

CF 41A - Translation Rating: 800 Tags: implementation, strings Solve time: 1m 14s Verified: yes Solution Problem Understanding We are given two lowercase strings. The first string is a word in one language, and the second string is supposed to be its translation into another language where every word is written backwards. The task is simply to check whether the second string is exactly the reverse of the first one....

Practice › Codeforces Solutions › Unknown Language Round 4 ›

CF 130B - Gnikool Ssalg

CF 130B - Gnikool Ssalg Rating: 1400 Tags: *special, implementation, strings Solve time: 1m 24s Verified: yes Solution Problem Understanding The problem asks us to reverse a string. Given a sequence of characters, the output should be the same sequence but in the opposite order, so that the first character becomes the last, the second becomes the second-to-last, and so on. The input string is guaranteed to have between 1...

Practice › Codeforces Solutions ›

Codeforces Beta Round 31 (Div. 2, Codeforces format)

Codeforces Beta Round 31 (Div. 2, Codeforces format) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1200-2400 | Time: 6m 52s Problem Name Rating Tags Solve Time Verified A Worms Evolution 1200 implementation 1m 46s ✓ B Sysadmin Bob 1500 greedy, implementation, strings 1m 11s ✓ C Schedule 1700 implementation 58s ✓ D Chocolate 2000 dfs-and-similar, implementation 59s ✓ E TV Game 2400 dp 1m 58s...

Practice › Codeforces Solutions ›

Codeforces Beta Round 78 (Div. 2 Only)

Codeforces Beta Round 78 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-1300 | Time: 2m 45s Problem Name Rating Tags Solve Time Verified A Help Far Away Kingdom 800 strings 1m 25s ✓ B Help Chef Gerasim 1300 implementation, sortings 1m 20s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 57 (Div. 2) ›

CF 61B - Hard Work

CF 61B - Hard Work Rating: 1300 Tags: strings Solve time: 6m 35s Verified: yes Solution Problem Understanding We are given three original strings. A student's answer is considered correct if it can be formed by concatenating these three strings in any order, after ignoring two kinds of differences. The first difference is letter casing. Uppercase and lowercase versions of the same letter should be treated as equal. The second...

Practice › Codeforces Solutions ›

Codeforces Beta Round 64

Codeforces Beta Round 64 Type: Beta | Problems: 5 | Verified: 4/5 | Rating range: 1300-2700 | Time: 11m 7s Problem Name Rating Tags Solve Time Verified A Cookies 1300 math 1m 46s ✓ B Text Messaging 1600 expression-parsing, greedy, strings 1m 39s ✓ C Lucky Tickets 2200 binary-search, data-structures, sortings 2m 11s ✓ D Professor's task 2700 data-structures, geometry 2m 2s ✓ E Information Reform 2700 dp, implementation, trees...

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

CF 123A - Prime Permutation

CF 123A - Prime Permutation Rating: 1300 Tags: implementation, number theory, strings Solve time: 2m 19s Verified: no Solution Problem Understanding We are given a string s composed of lowercase letters, with length n . The task is to determine if we can rearrange the letters so that for every prime p less than or equal to n , all positions in the string that are multiples of p can...

Practice › Codeforces Solutions › Unknown Language Round 3 ›

CF 100D - World of Mouth

CF 100D - World of Mouth Rating: 1500 Tags: *special, strings Solve time: 2m 18s Verified: yes Solution Problem Understanding We start with an initial string and pass it around a circle of n people. Every person is allowed to modify the string in only one of two ways: Remove exactly one character from the end. Add exactly one character to the end. A person may also choose to do...

Practice › Codeforces Solutions ›

Codeforces Beta Round 77 (Div. 2 Only)

Codeforces Beta Round 77 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 900-1300 | Time: 6m 15s Problem Name Rating Tags Solve Time Verified A Football 900 implementation, strings 1m 24s ✓ B Lucky Numbers (easy) 1300 binary-search, bitmasks, brute-force 4m 51s ✓

Practice › Codeforces Solutions › Codeforces Beta Round 59 (Div. 2) ›

CF 63A - Sinking Ship

CF 63A - Sinking Ship Rating: 900 Tags: implementation, sortings, strings Solve time: 1m 31s Verified: yes Solution Problem Understanding We are given a list of people standing in a fixed left-to-right order on a sinking ship. Every person has a name and a role. The evacuation order depends entirely on the role priority. Rats leave first. Women and children share the next priority level. Men leave after them. The...

Practice › Codeforces Solutions ›

Codeforces Beta Round 8

Codeforces Beta Round 8 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1200-2600 | Time: 6m 59s Problem Name Rating Tags Solve Time Verified A Train and Peter 1200 strings 1m 17s ✓ B Obsession with Robots 1400 constructive-algorithms, graphs, implementation 56s ✓ C Looking for Order 2000 bitmasks, dp 1m 48s ✓ D Two Friends 2600 binary-search, geometry 1m 54s ✓ E Beads 2600 dp, graphs...

Practice › Codeforces Solutions ›

Codeforces Beta Round 73 (Div. 1 Only)

Codeforces Beta Round 73 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2600 | Time: 9m 48s Problem Name Rating Tags Solve Time Verified A Trains 1500 implementation, math 1m 15s ✓ B Vasya and Types 1800 implementation, strings 1m 56s ✓ C Interesting Game 2000 dp, games, math 1m 9s ✓ D Beautiful Road 2300 dfs-and-similar, dp, dsu 2m 12s ✓ E...

Practice › Codeforces Solutions ›

Unknown Language Round 4

Unknown Language Round 4 Type: Special | Problems: 10 | Verified: 10/10 | Rating range: 900-2300 | Time: 16m 22s Problem Name Rating Tags Solve Time Verified A Hexagonal numbers 900 *special, implementation 1m 24s ✓ B Gnikool Ssalg 1400 *special, implementation, strings 1m 24s ✓ C Decimal sum 1500 *special 1m 48s ✓ D Exponentiation 1500 *special 1m 51s ✓ E Tribonacci numbers 1600 *special 2m 6s ✓ F...

Practice › Codeforces Solutions ›

Codeforces Beta Round 92 (Div. 1 Only)

Codeforces Beta Round 92 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1300-2500 | Time: 14m 53s Problem Name Rating Tags Solve Time Verified A Prime Permutation 1300 implementation, number-theory, strings 2m 19s ✗ B Squares 1800 math 5m 4s ✓ C Brackets 2300 combinatorics, dp, greedy 2m 19s ✓ D String 2300 string-suffix-structures 2m 32s ✓ E Maze 2500 dfs-and-similar, dp, probabilities...

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 Alpha Round 21 (Codeforces format) ›

CF 21A - Jabber ID

CF 21A - Jabber ID Rating: 1900 Tags: implementation, strings Solve time: 1m 37s Verified: no Solution Problem Understanding We need to validate whether a string follows the exact syntax of a Jabber ID. A valid ID has three possible pieces: username@hostname or username@hostname/resource The username and resource follow the same rules. They may contain only English letters, digits, and underscores. Their lengths must be between 1 and 16. The...

Practice › Codeforces Solutions › Codeforces Beta Round 55 (Div. 2) ›

CF 59A - Word

CF 59A - Word Rating: 800 Tags: implementation, strings Solve time: 1m 11s Verified: yes Solution Problem Understanding The task is to normalize the case of a single word so that either all letters are lowercase or all are uppercase. The decision depends on which case dominates in the input: if there are more uppercase letters than lowercase letters, the word should be transformed entirely to uppercase; otherwise, it should...

Practice › Codeforces Solutions ›

Codeforces Beta Round 59 (Div. 2)

Codeforces Beta Round 59 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 900-2000 | Time: 8m 47s Problem Name Rating Tags Solve Time Verified A Sinking Ship 900 implementation, sortings, strings 1m 31s ✓ B Settlers' Training 1200 implementation 1m 35s ✓ C Bulls and Cows 1700 brute-force, implementation 1m 48s ✓ D Dividing Island 1900 constructive-algorithms 1m 40s ✗ E Sweets Game 2000...

Practice › Codeforces Solutions ›

Codeforces Beta Round 84 (Div. 2 Only)

Codeforces Beta Round 84 (Div. 2 Only) Type: Div. 2 | Problems: 2 | Verified: 2/2 | Rating range: 800-1100 | Time: 5m 34s Problem Name Rating Tags Solve Time Verified A Nearly Lucky Number 800 implementation 2m 36s ✓ B Lucky String 1100 constructive-algorithms, strings 2m 58s ✓

Practice › Codeforces Solutions ›

Codeforces Beta Round 77 (Div. 1 Only)

Codeforces Beta Round 77 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1600-2500 | Time: 7m 52s Problem Name Rating Tags Solve Time Verified A Hockey 1600 implementation, strings 1m 15s ✓ B Lucky Numbers 1800 dp, greedy 1m 52s ✓ C Volleyball 1900 shortest-paths 1m 21s ✓ D Horse Races 2500 dp, math 2m ✓ E Lucky Country 2500 dp, dsu, graphs...

Practice › Codeforces Solutions › Codeforces Beta Round 61 (Div. 2) ›

CF 66A - Petya and Java

CF 66A - Petya and Java Rating: 1300 Tags: implementation, strings Solve time: 1m 33s Verified: yes Solution Problem Understanding We are given a decimal integer as a string. The number can be extremely large, up to 100 digits long, so it may not fit into normal integer types in many programming languages. The task is to determine the smallest Java integer type that can store this value. The available...

Practice › Codeforces Solutions ›

Codeforces Beta Round 75 (Div. 1 Only)

Codeforces Beta Round 75 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2600 | Time: 12m 45s Problem Name Rating Tags Solve Time Verified A Newspaper Headline 1500 greedy, strings 1m 57s ✓ B Queue 1500 binary-search, data-structures 2m 10s ✓ C Ski Base 2300 combinatorics, dsu, graphs 3m 29s ✓ D Grocer's Problem 2600 constructive-algorithms, graphs, greedy 2m 25s ✓ E Igloo...

Practice › Codeforces Solutions › Codeforces Beta Round 47 ›

CF 50B - Choosing Symbol Pairs

CF 50B - Choosing Symbol Pairs Rating: 1500 Tags: strings Solve time: 1m 15s Verified: yes Solution Problem Understanding We are given a string of characters consisting of lowercase letters and digits. The task is to count the number of ordered pairs of positions in the string where the characters at those positions are identical. A pair is ordered, so for positions i and j , both (i, j) and...

Practice › Codeforces Solutions ›

Codeforces Beta Round 57 (Div. 2)

Codeforces Beta Round 57 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2000 | Time: 14m 51s Problem Name Rating Tags Solve Time Verified A Ultra-Fast Mathematician 800 implementation 2m 4s ✓ B Hard Work 1300 strings 6m 35s ✓ C Capture Valerian 2000 math 2m 49s ✓ D Eternal Victory 1800 dfs-and-similar, graphs, greedy 1m 29s ✓ E Enemy is weak 1900 data-structures,...

Practice › Codeforces Solutions › Codeforces Beta Round 67 (Div. 2) ›

CF 75B - Facetook Priority Wall

CF 75B - Facetook Priority Wall Rating: 1500 Tags: expression parsing, implementation, strings Solve time: 2m 14s Verified: no Solution Problem Understanding We are given the name of a user on a social network and a sequence of activity messages between users. Every activity contributes a certain number of points between the two people involved. The three possible activities are: posting on someone's wall, worth 15 points commenting on someone's...

Practice › Codeforces Solutions ›

Codeforces Beta Round 54 (Div. 2)

Codeforces Beta Round 54 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 1000-2400 | Time: 7m 51s Problem Name Rating Tags Solve Time Verified A Chat room 1000 greedy, strings 1m 20s ✓ B Coins 1300 greedy 1m 51s ✗ C Trees 1800 brute-force 1m 13s ✓ D Calendar 2000 greedy, strings 1m 23s ✓ E Expression 2400 dp 2m 4s ✗

Practice › Codeforces Solutions › Codeforces Beta Round 74 (Div. 2 Only) ›

CF 90B - African Crossword

CF 90B - African Crossword Rating: 1100 Tags: implementation, strings Solve time: 1m 44s Verified: yes Solution Problem Understanding We are given a small grid of lowercase letters. A cell survives only if its letter is unique both inside its row and inside its column. If the same character appears somewhere else in the same row, that cell is removed. The same happens if the character appears somewhere else in...

Practice › Codeforces Solutions ›

Yandex.Algorithm Open 2011: Qualification 1

Yandex.Algorithm Open 2011: Qualification 1 Type: Special | Problems: 5 | Verified: 3/5 | Rating range: 1400-2700 | Time: 13m 8s Problem Name Rating Tags Solve Time Verified A Plug-in 1400 implementation 1m 36s ✓ B Sequence Formatting 1700 implementation, strings 1m 43s ✓ C Average Score 1700 greedy, math, sortings 3m 31s ✓ D Polycarp's Picture Gallery 2100 constructive-algorithms, greedy 2m 48s ✗ E Pairs 2700 dfs-and-similar, dp, dsu...

Practice › Codeforces Solutions ›

Codeforces Beta Round 34 (Div. 2)

Codeforces Beta Round 34 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 800-2000 | Time: 7m 19s Problem Name Rating Tags Solve Time Verified A Reconnaissance 2 800 implementation 1m 18s ✓ B Sale 900 greedy, sortings 1m 19s ✓ C Page Numbers 1300 expression-parsing, implementation, sortings 1m 7s ✓ D Road Map 1600 dfs-and-similar, graphs 1m 29s ✓ E Collisions 2000 brute-force, implementation,...

Practice › Codeforces Solutions › Codeforces Beta Round 89 (Div. 2) ›

CF 118A - String Task

CF 118A - String Task Rating: 1000 Tags: implementation, strings Solve time: 1m 38s Verified: yes Solution Problem Understanding We receive a single string containing uppercase and lowercase English letters. The task is to transform this string according to three rules. First, every vowel must be removed. The vowels in this problem are A, O, Y, E, U, I in both uppercase and lowercase forms. Second, every remaining character is...

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

CF 121B - Lucky Transformation

CF 121B - Lucky Transformation Rating: 1500 Tags: strings Solve time: 2m 26s Verified: yes Solution Problem Understanding We are given a decimal string and an operation count k . Each operation looks for the leftmost occurrence of the substring "47" . Suppose the substring "47" starts at position x using 1-based indexing. If x is odd, we replace both digits with '4' , so "47" becomes "44" . If...

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

CF 113B - Petr#

CF 113B - Petr# Rating: 2000 Tags: brute force, data structures, hashing, strings Solve time: 3m 20s Verified: yes Solution Problem Understanding We are asked to count how many distinct substrings of a given string t start with a string sbegin and end with another string send . The key detail is that substrings are considered different only by their content, not by their position in t . This means...

Practice › Codeforces Solutions ›

Codeforces Alpha Round 21 (Codeforces format)

Codeforces Alpha Round 21 (Codeforces format) Type: Special | Problems: 4 | Verified: 3/4 | Rating range: 1900-2400 | Time: 5m 6s Problem Name Rating Tags Solve Time Verified A Jabber ID 1900 implementation, strings 1m 37s ✗ B Intersection 2000 implementation, math 1m 21s ✓ C Stripe 2 2000 binary-search, dp, sortings 1m 26s ✓ D Traveling Graph 2400 bitmasks, graph-matchings, graphs 42s ✓

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

CF 91A - Newspaper Headline

CF 91A - Newspaper Headline Rating: 1500 Tags: greedy, strings Solve time: 1m 57s Verified: yes Solution Problem Understanding We have a source string s1 , which represents the headline of one newspaper. We may take as many copies of this headline as we want and concatenate them together. From the resulting long string, we are allowed to delete arbitrary characters while keeping the remaining characters in order. The target...

Practice › Codeforces Solutions › Codeforces Beta Round 54 (Div. 2) ›

CF 58D - Calendar

CF 58D - Calendar Rating: 2000 Tags: greedy, strings Solve time: 1m 23s Verified: yes Solution Problem Understanding We are asked to construct a calendar from a list of city names. Each line of the calendar must contain exactly two city names separated by a given symbol, and all lines must have identical length. The calendar must use each city name exactly once. Among all possible arrangements that satisfy these...

Practice › Codeforces Solutions › Codeforces Beta Round 25 (Div. 2 Only) ›

CF 25E - Test

CF 25E - Test Rating: 2200 Tags: hashing, strings Solve time: 1m 28s Verified: yes Solution Problem Understanding We are given three lowercase strings. We want to build a single string that contains all three as substrings, and we want this resulting string to be as short as possible. Another way to view the task is as a shortest common superstring problem, but only for three strings. Since there are...

Practice › Codeforces Solutions › Codeforces Beta Round 7 ›

CF 7D - Palindrome Degree

CF 7D - Palindrome Degree Rating: 2200 Tags: hashing, strings Solve time: 1m 5s Verified: yes Solution Problem Understanding We are given a string consisting of letters and digits, and we are asked to compute a special measure for every prefix called the palindrome degree . A string has a palindrome degree k if it is a palindrome and its first half and last half of length len(s) // 2...

Practice › Codeforces Solutions › Codeforces Beta Round 30 (Codeforces format) ›

CF 30E - Tricky and Clever Password

CF 30E - Tricky and Clever Password Rating: 2800 Tags: binary search, constructive algorithms, data structures, greedy, hashing, strings Solve time: 1m 50s Verified: yes Solution Problem Understanding We are given a single lowercase string. Somewhere inside this string, there exists a hidden palindrome of odd length, but the palindrome was split into three consecutive parts: a prefix, a middle part, a suffix. The prefix and suffix have the same...

Practice › Codeforces Solutions ›

Codeforces Beta Round 5

Codeforces Beta Round 5 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1000-2400 | Time: 5m 59s Problem Name Rating Tags Solve Time Verified A Chat Servers Outgoing Traffic 1000 implementation 1m 9s ✓ B Center Alignment 1200 implementation, strings 1m 24s ✓ C Longest Regular Bracket Sequence 1900 constructive-algorithms, data-structures, dp 1m 21s ✓ D Follow Traffic Rules 2100 implementation, math 54s ✓ E Bindian Signalizing...

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

CF 95A - Hockey

CF 95A - Hockey Rating: 1600 Tags: implementation, strings Solve time: 1m 15s Verified: yes Solution Problem Understanding We are given a string representing a hockey team name and a list of forbidden substrings. Our task is to modify the original string so that any letter that is part of a forbidden substring can be replaced with another letter of our choosing. The replacements must maximize the occurrence of a...

Practice › Codeforces Solutions ›

Codeforces Beta Round 89 (Div. 2)

Codeforces Beta Round 89 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 1000-2000 | Time: 10m 4s Problem Name Rating Tags Solve Time Verified A String Task 1000 implementation, strings 1m 38s ✓ B Present from Lena 1000 constructive-algorithms, implementation 1m 42s ✓ C Fancy Number 1900 brute-force, greedy, sortings 2m 51s ✓ D Caesar's Legions 1700 dp 1m 37s ✓ E Bertown roads...

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

CF 1941C - Rudolf and the Ugly String

CF 1941C - Rudolf and the Ugly String Rating: 900 Tags: dp, greedy, strings Solve time: 2m 41s Verified: yes Solution Problem Understanding We are given a string and want to remove the minimum number of characters so that the resulting string no longer contains "pie" or "map" as a substring. The key detail is that deletions can happen at arbitrary positions. We are not rearranging characters, only deleting some...

Practice › Codeforces Solutions ›

Codeforces Round 933 (Div. 3)

Codeforces Round 933 (Div. 3) Type: Div. 3 | Problems: 7 | Verified: 6/7 | Rating range: 800-2000 | Time: 12m 58s Problem Name Rating Tags Solve Time Verified A Rudolf and the Ticket 800 brute-force, math 1m 23s ✓ B Rudolf and 121 1000 brute-force, dp, greedy 2m 47s ✓ C Rudolf and the Ugly String 900 dp, greedy, strings 2m 41s ✓ D Rudolf and the Ball Game...

Programming › Algorithm Cookbook › Chapter 5. Hashing and Maps ›

5.11 Rolling Hashes

5.11 Rolling Hashes Problem You need to compare many substrings quickly. Direct substring comparison can be expensive because comparing two substrings of length m may take O(m) time. If an algorithm compares many substrings, this cost can dominate the whole computation. A rolling hash assigns each prefix of a string a numeric summary so that the hash of any substring can be computed in constant time after preprocessing. Solution Choose...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.24 Common Patterns

Array and string problems often look different on the surface, but many reduce to a small number of reusable patterns. The value of these patterns is that they provide a known invariant, a known complexity bound, and a known set of boundary cases. Once the pattern is recognized, the remaining work is mostly adapting the state and update rules. Pattern 1: Linear Scan Use a linear scan when every element...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.25 Boundary Conditions

Boundary conditions define the valid domain of indices, ranges, and states in an algorithm. Many bugs arise not from the main logic, but from incorrect handling of edges such as empty input, single-element cases, or off-by-one errors. This section provides a systematic approach to designing and verifying boundaries. Problem Given an algorithm over arrays or strings, ensure correctness for all valid inputs, including edge cases: empty input single element full...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.22 Spiral Traversal

Spiral traversal visits a matrix layer by layer, moving right across the top row, down the right column, left across the bottom row, and up the left column, then shrinking the boundaries and repeating. Problem Given a matrix: 1 2 3 4 5 6 7 8 9 Spiral order: 1, 2, 3, 6, 9, 8, 7, 4, 5 Boundaries Maintain four boundaries: top, bottom, left, right Initialize: top = 0...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.23 Flood Fill

Flood fill explores a connected region in a grid starting from a seed cell and marks or transforms all cells that belong to the same region. Connectivity is defined by a neighborhood relation, typically 4-directional or 8-directional. Problem Given a grid a , a starting cell (sr, sc) , and a new value newVal , replace all cells connected to (sr, sc) that have the same original value with newVal...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.18 String Comparison

String comparison determines the ordering or equality of two strings. The simplest form compares byte sequences. More advanced forms compare Unicode code points, normalized text, or locale-specific collation units. Algorithmically, the important point is that comparison is usually linear in the length of the common prefix. Problem Given two strings a and b , decide whether: a == b a < b a > b For example: "apple" < "apply"...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.21 Matrix Traversal

Matrix traversal processes a two-dimensional array in a defined order. It is the two-dimensional form of array traversal, but the extra dimension adds boundary choices, coordinate conventions, and common patterns such as row-major order, column-major order, diagonal scans, and grid-neighbor exploration. Problem Given a matrix a with rows rows and cols columns, visit every cell exactly once. Example: 1 2 3 4 5 6 7 8 9 A row-major traversal...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.20 Tries

A trie is a tree structure for storing a set of strings so that common prefixes are shared. Each edge corresponds to a symbol, and each node represents a prefix. Tries support fast insertion, lookup, prefix queries, and lexicographic traversal. Problem Maintain a dynamic set of strings and support: Insert(s) Contains(s) HasPrefix(p) List all strings with prefix p A naive approach compares strings directly and costs O(length) per comparison. A...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.17 Rolling Hashes

Rolling hashes assign numeric fingerprints to substrings so that many substring comparisons can be done quickly. After preprocessing, the hash of any substring can be computed in constant time. This is useful in substring search, duplicate detection, palindrome checks, longest common substring, and approximate text indexing. The method is usually probabilistic. Equal hashes suggest equal strings, but collisions can occur unless the algorithm uses a collision-free representation or verifies matches...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.19 Parsing Expressions

Parsing expressions converts a sequence of tokens into a structured form that reflects operator precedence and associativity. The result is typically an abstract syntax tree (AST) or a computed value. This section presents a practical method, the shunting-yard algorithm, followed by a direct recursive descent approach. Problem Given an expression: 3 + 4 * (2 - 1) Produce either: a value: 7 or a structured representation such as an AST...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.14 Anagrams

Anagrams are strings or sequences that contain the same elements with the same multiplicities, possibly in different order. For example, "listen" and "silent" are anagrams because each letter appears the same number of times in both strings. The usual algorithmic task is to compare frequency tables. Sorting also works, but counting is often faster when the alphabet is small or bounded. Problem Given two strings a and b , decide...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.13 Palindromes

A palindrome is a sequence that reads the same forward and backward. In array and string algorithms, palindrome problems usually reduce to symmetric comparison, center expansion, dynamic programming, or hashing. For strings, first decide whether the unit of comparison is a byte, a Unicode code point, or a normalized user-visible character. The examples here use byte strings for clarity. Problem Given a string s , determine whether it is a...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.15 Frequency Tables

A frequency table records how many times each value appears in an array, string, or stream. It is one of the simplest and most useful summaries of linear data. Many problems about duplicates, anagrams, modes, majority elements, histograms, and sliding windows reduce to maintaining counts. Problem Given a sequence, count how often each element occurs. Example: [4, 1, 4, 2, 1, 4] Frequency table: 1 -> 2 2 -> 1...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.16 Run-Length Encoding

Run-Length Encoding (RLE) compresses sequences by replacing consecutive equal values with a pair (value, count) . It is effective when the input contains long runs of the same element and serves as a simple pre-processing step for more complex compression or for speeding up certain algorithms. Problem Given a sequence, produce its run-length encoding. Example: [1, 1, 1, 2, 2, 3, 1, 1] Encoding: [(1, 3), (2, 2), (3, 1),...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.12 Substring Search

Substring search locates occurrences of a pattern p inside a text s . The objective is to find all indices i such that: s[i : i + m] == p where m = len(p) . The choice of algorithm depends on input size, number of queries, and tolerance for probabilistic error. Problem Given: s = "abracadabra" p = "abra" Return all starting indices: [0, 7] Baseline: Naive Search Check every...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.6 Partitioning

Partitioning rearranges an array so that elements are grouped by a predicate. The order inside each group may or may not be preserved, depending on the algorithm. This pattern appears in quicksort, selection, filtering, deduplication, stream compaction, and many in-place array transformations. The central idea is to maintain a boundary between elements that are already classified and elements that are still unknown. Problem Given an array a and a predicate...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.7 Rotation

Array rotation moves elements by a fixed offset while preserving their relative circular order. A left rotation by k moves each element at index i to index i - k modulo n . A right rotation by k moves each element at index i to index i + k modulo n . Rotation appears in cyclic buffers, scheduling, string matching, block rearrangement, and in-place array transformations. Problem Given an array:...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.10 String Scanning

String scanning is the basic operation behind parsing, tokenization, validation, search, and text normalization. The algorithm reads a string from left to right, maintains a small state, and decides what to do with each character or byte. The main difference between string scanning and array traversal is representation. A string may be treated as bytes, Unicode code points, or higher level text units. The correct choice depends on the problem....

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.9 Deduplication

Deduplication removes repeated values while preserving a chosen notion of identity and, optionally, order. The design depends on two decisions: whether the input is sorted whether the output must preserve original order These decisions determine both the algorithm and its complexity. Problem Given an array a , produce a sequence that contains each value at most once. Example: [3, 1, 3, 2, 1, 4] Possible outputs: preserve first occurrence order:...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.11 Tokenization

Tokenization converts a string into a sequence of meaningful units called tokens. A token may be a word, number, identifier, operator, delimiter, quoted string, or whitespace block, depending on the grammar. Tokenization is the first stage of many parsers because it separates low level character scanning from higher level syntactic analysis. Problem Given an input string, split it into tokens while preserving enough information for later processing. For example: sum...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.8 In-Place Modification

In-place modification changes an array without allocating another array of the same size. The goal is to reuse the input storage while preserving the part of the data that has not yet been read. This pattern is common in filtering, deduplication, partitioning, reversing, rotation, merging, and compaction. Problem Given an array a , transform it using only O(1) extra space. For example, remove all zero values: [0, 3, 0, 4,...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.5 Sliding Windows

Sliding windows maintain a contiguous subarray [l, r) while both endpoints move forward. The window expands to include new elements and contracts to restore a constraint. When both pointers are monotone, each index is visited a constant number of times, giving linear time. This technique applies when a property over a range can be updated incrementally as elements enter or leave the window. Problem Given an array or string, find...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.4 Two Pointers

The two pointers technique uses two indices that move through an array or string in a controlled way. The main idea is to avoid restarting a scan from the beginning when useful information has already been discovered. When the pointers move monotonically, the total number of pointer movements is linear. This pattern is useful when the problem has an ordered structure: sorted arrays, contiguous ranges, opposite-end searches, or windows whose...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.1 Array Traversal

Array traversal is the base operation for all algorithms over linear data. The task is to visit elements in a defined order, maintain a small amount of state, and ensure that every access is valid. Most higher level patterns reduce to controlled traversal with stronger invariants. Problem You have an array A of length n . You want to process each element, possibly combining information from earlier positions, while maintaining...

Programming › Algorithm Cookbook ›

Chapter 2. Arrays and Strings

This chapter studies linear data as the primary substrate for algorithm design. Arrays and strings appear simple, but most high performance solutions reduce to controlled traversal, local state maintenance, and careful boundary handling on these structures. The objective here is to make these operations predictable and composable. An array is treated as a contiguous block of memory with constant time indexed access. A string is treated as a sequence with...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.2 Prefix Sums

Prefix sums are a preprocessing technique for answering repeated range sum queries on an array. Instead of summing a range from scratch each time, we build an auxiliary array that stores cumulative totals. After this preprocessing step, each range sum can be computed in constant time. Problem You have an array A of length n . You need to answer many queries of the form: sum of A[l] through A[r]...

Programming › Algorithm Cookbook › Chapter 2. Arrays and Strings ›

2.3 Difference Arrays

A difference array is the inverse pattern of a prefix sum. Prefix sums make range queries fast. Difference arrays make range updates fast. The typical problem is this: you have an array A of length n , and you need to apply many updates of the form "add x to every element from index l through index r ." Updating each element directly costs O(r - l + 1) per...

#strings

16.14 Longest Common Substring

16.19 Token Streams

16.6 Trie Matching

16.24 Testing String Algorithms

16.17 Compressed Strings

16.16 String Hashing

16.9 Longest Common Prefix (LCP) Arrays

16.12 Manacher Algorithm

16.5 Boyer-Moore Overview

16.3 Z Algorithm

16.15 Lexicographic Order

16.11 Palindromic Trees (Eertrees)

16.7 Aho-Corasick

16.13 Edit Distance

16.18 Unicode and Normalization

16.23 Complexity Analysis

16.10 Suffix Automata

16.4 Rabin-Karp

16.8 Suffix Arrays

16.25 Real-World String Processing Patterns

16.20 Choosing the Right String Algorithm

16.1 Exact Matching

16.21 Text Indexing

16.22 Building a Search Engine

16.2 Knuth-Morris-Pratt (KMP)

Chapter 16. String Algorithms

CF 2226G - Stop Spot

CF 2225F - String Cutting

CF 1974B - Symmetric Encoding

Codeforces Round 279 (Div. 2)

CF 1943B - Non-Palindromic Substring

Codeforces Round 937 (Div. 4)

CF 1975H - 378QAQ and Core

Codeforces Round 946 (Div. 3)

CF 1948D - Tandem Repeats?

CF 1952B - Is it stated?

CF 1975G - Zimpha Fan Club

Codeforces Round 934 (Div. 1)

CF 1965C - Folding Strip

CF 1976A - Verify Password

Educational Codeforces Round 166 (Rated for Div. 2)

CF 1950G - Shuffling Songs

CF 1952A - Are You a Robot, Again?

CF 494B - Obsessive String

CF 1950E - Nearly Shortest Repeating Substring

CF 1952H - Palindrome

CF 490C - Hacking Cypher

Codeforces Round 282 (Div. 1)

CF 1951E - No Palindromes

April Fools Day Contest 2024

MemSQL Start[c]UP 2.0 - Round 1

CF 452A - Eevee

CF 471D - MUH and Cube Walls

Codeforces Round 272 (Div. 1)

CF 461E - Appleman and a Game

CF 467D - Fedor and Essay

CF 476E - Dreamoon and Strings

Codeforces Round 260 (Div. 1)

CF 452E - Three strings

CF 477D - Dreamoon and Binary

CF 455B - A Lot of Games

CF 159D - Palindrome pairs

Codeforces Round 116 (Div. 2, ACM-ICPC Rules)

Codeforces Round 127 (Div. 2)

Codeforces Round 155 (Div. 2)

CF 141A - Amusing Joke

Codeforces Round 146 (Div. 2)

CF 208A - Dubstep

CF 143B - Help Kingdom of Far Far Away 2

Codeforces Round 124 (Div. 1)

CF 137D - Palindromes

CF 223B - Two Strings

CF 259A - Little Elephant and Chess

CROC-MBTU 2012, Final Round (Online version, Div. 2)

CF 291B - Command Line Arguments

Codeforces Round 112 (Div. 2)

CF 165C - Another Problem on Strings

CF 245B - Internet Address

Codeforces Round 135 (Div. 2)