string-suffix-structures

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

CF 204E - Little Elephant and Strings

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

Practice › Codeforces Solutions ›

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

CF 441D - Valera and Swaps

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

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316G2 - Good Substrings

CF 316G2 - Good Substrings Rating: 2200 Tags: string suffix structures Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a main string $s$. We want to count how many different substrings of $s$ are “valid” under a set of constraints. Each constraint gives us another string $p$ and two integers $l$ and $r$. For any candidate substring $t$, we look at how many times $t$ appears...

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

CF 232D - Fence

CF 232D - Fence Rating: 2900 Tags: binary search, data structures, string suffix structures Solve time: 2m 21s Verified: no Solution Problem Understanding We have an array of fence heights. A query gives one contiguous segment of the fence, and we must count how many other segments match it. Two segments match if they have the same length, do not overlap, and their heights differ by the same constant at...

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 › ABBYY Cup 3.0 ›

CF 316G3 - Good Substrings

CF 316G3 - Good Substrings Rating: 2400 Tags: string suffix structures Solve time: 1m 6s Verified: yes Solution Problem Understanding We are asked to count the number of distinct substrings of a string s that satisfy a set of rules. Each rule consists of a string p and a range [l, r] . A substring t of s is good if, for every rule (p, l, r) , the number...

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

CF 149E - Martian Strings

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

Practice › Codeforces Solutions ›

Codeforces Round 106 (Div. 2)

Codeforces Round 106 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 4/5 | Rating range: 900-2300 | Time: 8m 2s Problem Name Rating Tags Solve Time Verified A Business trip 900 greedy, implementation, sortings 1m 33s ✓ B Martian Clock 1600 implementation 1m 25s ✓ C Division into Teams 1500 greedy, math, sortings 1m 40s ✗ D Coloring Brackets 1900 dp 2m 8s ✓ E Martian Strings 2300...

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 252 (Div. 2)

Codeforces Round 252 (Div. 2) Type: Div. 2 | Problems: 3 | Verified: 1/3 | Rating range: 1000-2400 | Time: 4m 27s Problem Name Rating Tags Solve Time Verified A Valera and Antique Items 1000 implementation 1m 21s ✓ D Valera and Swaps 2100 constructive-algorithms, dsu, graphs 1m 26s ✗ E Valera and Number 2400 bitmasks, dp, math 1m 40s ✗

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

CF 128B - String

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 19

Codeforces Beta Round 19 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1400-2900 | Time: 16m 37s Problem Name Rating Tags Solve Time Verified A World Football Cup 1400 implementation 5m 51s ✓ B Checkout Assistant 1900 dp 3m 5s ✓ C Deletion of Repeats 2200 greedy, hashing, string-suffix-structures 2m 2s ✓ D Points 2800 data-structures 3m 49s ✓ E Fairy 2900 dfs-and-similar, divide-and-conquer, dsu 1m 50s...

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

CF 86C - Genetic engineering

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

Practice › Codeforces Solutions ›

Yandex.Algorithm 2011: Round 2

Yandex.Algorithm 2011: Round 2 Type: Special | Problems: 5 | Verified: 5/5 | Rating range: 1600-2700 | Time: 11m 50s Problem Name Rating Tags Solve Time Verified A Reflection 1600 math 2m 9s ✓ B Tetris revisited 2200 constructive-algorithms, graph-matchings, greedy 2m 5s ✓ C Genetic engineering 2500 dp, string-suffix-structures, trees 2m 12s ✓ D Powerful array 2200 data-structures, implementation, math 3m 46s ✓ E Long sequence 2700 brute-force, math,...

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

CF 123D - String

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 94 (Div. 1 Only)

Codeforces Beta Round 94 (Div. 1 Only) Type: Div. 1 | Problems: 5 | Verified: 5/5 | Rating range: 1500-2900 | Time: 8m 36s Problem Name Rating Tags Solve Time Verified A Statues 1500 dfs-and-similar 2m 10s ✓ B String 2100 brute-force, constructive-algorithms, hashing 1m 21s ✓ C Games with Rectangle 2000 combinatorics, dp 1m 52s ✓ D Numbers 2000 constructive-algorithms, implementation 1m 38s ✓ E Birthday 2900 geometry, math...

Practice › Codeforces Solutions ›

Codeforces Beta Round 93 (Div. 1 Only)

Codeforces Beta Round 93 (Div. 1 Only) Type: Div. 1 | Problems: 2 | Verified: 2/2 | Rating range: 1700-1900 | Time: 4m 5s Problem Name Rating Tags Solve Time Verified A Hot Bath 1900 binary-search, brute-force, math 2m 1s ✓ B Password 1700 binary-search, dp, hashing 2m 4s ✓

#string-suffix-structures

CF 2225F - String Cutting

CF 452E - Three strings

CF 471D - MUH and Cube Walls

CF 204E - Little Elephant and Strings

Codeforces Round 146 (Div. 1)

CF 441D - Valera and Swaps

CF 316G2 - Good Substrings

CF 232D - Fence

CF 235C - Cyclical Quest

CF 316G3 - Good Substrings

CF 149E - Martian Strings

Codeforces Round 106 (Div. 2)

CF 427D - Match & Catch

Codeforces Round 252 (Div. 2)

CF 126B - Password

CF 128B - String

Codeforces Beta Round 19

CF 86C - Genetic engineering

Yandex.Algorithm 2011: Round 2

CF 123D - String

Codeforces Beta Round 94 (Div. 1 Only)

Codeforces Beta Round 93 (Div. 1 Only)