#hashing

CF 1553B - Reverse String

CF 1553B - Reverse String Rating: 1300 Tags: brute force, dp, hashing, implementation, strings Solve time: 1m 34s Verified: no Solution Problem Understanding We are given a string that represents a line of characters. A chip starts on some chosen position in this string. After placing it, we repeatedly move it and each time we record the character at the chip’s current position. The movement has a strict structure: the...

CF 1360F - Spy-string

CF 1360F - Spy-string Rating: 1700 Tags: bitmasks, brute force, constructive algorithms, dp, hashing, strings Solve time: 1m 13s Verified: no Solution Problem Understanding We are given several strings of equal length, and we want to construct a new string of the same length. The requirement is that this constructed string must be extremely close to every given string: for each input string, it is allowed to differ from our...

CF 1045B - Space Isaac Rating: 2400 Tags: hashing, number theory Model: gpt-5-3-mini Solve time: 2m 41s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a337f8c-9b3c-83ec-af57-a49cf10acf5c Solution Problem Understanding We are given a complete partition of the set of residues modulo $M$. One part of this partition is explicitly listed: a sorted array $A$ of size $N$. Every other number from $0$ to $M-1$ belongs to the second hidden bag, which we never...

CF 963D - Frequency of String Rating: 2500 Tags: hashing, string suffix structures, strings Model: gpt-5-3-mini Solve time: 1m 49s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33a36d-603c-83ec-9659-5838d7876b75 Solution Problem Understanding We are given a fixed text string and then many independent pattern queries. Each query gives a pattern string and a required frequency. For each query we need to look at all substrings of the main string that contain the pattern...

CF 1045I - Palindrome Pairs Rating: 1600 Tags: hashing, strings Model: gpt-5-5 Solve time: 59s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a33bdce-336c-83ec-b034-a73a04354470 Solution Problem Understanding We are given a multiset of strings, and we need to count how many unordered pairs of indices form a “good pair”. A pair is good if, after concatenating the two strings, it is possible to rearrange the characters of the result into a palindrome. A...

CF 898F - Restoring the Expression

CF 898F - Restoring the Expression Rating: 2300 Tags: brute force, hashing, math Solve time: 3m Verified: yes Solution Problem Understanding We are given a single long string consisting only of digits. This string is known to come from a correct arithmetic identity of the form a + b = c , but the symbols + and = were removed and the digits were concatenated. The task is to split...

Codeforces Round 451 (Div. 2)

Codeforces Round 451 (Div. 2) Div. 2 | 2 problems | 2/2 verified | Difficulty 800-2300 | 4m 3s # Problem Rating Tags Accepted Time ✓ A Rounding 800 implementation, math 17,579 1m 3s ✓ F Restoring the Expression 2300 brute-force, hashing, math 1,457 3m ✓

Helvetic Coding Contest 2018 online mirror (teams allowed, unrated)

Helvetic Coding Contest 2018 online mirror (teams allowed, unrated) Special | 7 problems | 3/7 verified | Difficulty 1500-3100 | 12m 46s # Problem Rating Tags Accepted Time ✓ A2 Death Stars (medium) 2000 hashing, strings 1,058 1m 31s ✓ A3 Death Stars (hard) 3100 53 59s ✓ B2 Maximum Control (medium) 2200 data-structures, dfs-and-similar, graphs 747 2m 35s C2 Encryption (medium) 2000 dp 1,378 1m 26s E1 Guard Duty...

CF 958A2 - Death Stars (medium)

CF 958A2 - Death Stars (medium) Rating: 2000 Tags: hashing, strings Solve time: 1m 31s Verified: yes Solution Problem Understanding We are given two rectangular grids of characters. The first grid has size $N \times M$, while the second grid has size $M \times N$. We are asked to find a way to align these two grids so that a square submatrix of size $M \times M$ taken from the...

CF 961F - k-substrings

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

Educational Codeforces Round 41 (Rated for Div. 2)

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

CF 985F - Isomorphic Strings

CF 985F - Isomorphic Strings Rating: 2300 Tags: hashing, strings Solve time: 2m 20s Verified: no Solution Problem Understanding We are given a base string and many queries, each query picks two equal-length substrings and asks whether one substring can be transformed into the other by consistently renaming characters, with the restriction that different characters must map to different characters. The core requirement is not about the letters themselves, but...

CF 1003F - Abbreviation

CF 1003F - Abbreviation Rating: 2200 Tags: dp, hashing, strings Solve time: 1m 18s Verified: yes Solution Problem Understanding We are given a document as a sequence of words. The structure is fixed: words are separated by single spaces, so the underlying object is really just an array of strings. A segment is a contiguous slice of this array, and two segments are considered identical when they have the same...

CF 1017E - The Supersonic Rocket

CF 1017E - The Supersonic Rocket Rating: 2400 Tags: geometry, hashing, strings Solve time: 2m 20s Verified: yes Solution Problem Understanding Each engine is a finite set of points in the plane, and we are allowed to rigidly move each set independently before they interact. Rigid motion here means we can translate and rotate a set arbitrarily, but not deform it. Once the two sets are placed, we repeatedly add...

CF 1043G - Speckled Band

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

CF 1553G - Common Divisor Graph

CF 1553G - Common Divisor Graph Rating: 2700 Tags: brute force, constructive algorithms, dsu, graphs, hashing, math, number theory Solve time: 3m 40s Verified: yes Solution Problem Understanding We are given a fixed set of nodes, each labeled by a distinct integer. Two nodes are connected if their labels share any prime factor. This means the graph is determined entirely by the prime factorizations of the given numbers. For each...

CF 1538E - Funny Substrings

CF 1538E - Funny Substrings Rating: 2100 Tags: data structures, hashing, implementation, matrices, strings Solve time: 6m 39s Verified: yes Solution Problem Understanding We are given a very small “programming language” where variables store strings. Each variable is either assigned a literal string of length at most five, or defined as the concatenation of two previously defined variables. The program is a sequence of such assignments, and only the value...

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

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

Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics)

Codeforces Round 626 (Div. 1, based on Moscow Open Olympiad in Informatics) Div. 1 | 3 problems | 1/3 verified | Difficulty 1300-3500 | 12m 47s # Problem Rating Tags Accepted Time ✓ A Unusual Competitions 1300 greedy 12,886 4m 47s C Instant Noodles 2300 graphs, hashing, math 2,703 2m 42s F Assigning Fares 3500 dp, trees 162 5m 18s ✓

CF 1320D - Reachable Strings

CF 1320D - Reachable Strings Rating: 2500 Tags: data structures, hashing, strings Solve time: 4m 29s Verified: no Solution Problem Understanding We are given a fixed binary string, and we repeatedly consider two kinds of local transformations on any contiguous segment of length three: swapping 011 into 110 , or the reverse swap 110 into 011 . Each operation only touches three consecutive characters and preserves the total number of...

CF 1286C2 - Madhouse (Hard version)

CF 1286C2 - Madhouse (Hard version) Rating: 2800 Tags: brute force, constructive algorithms, hashing, interactive, math Solve time: 6m 2s Verified: no Solution Problem Understanding A hidden string of length $n$ is fixed before the game starts. The player’s goal is to recover this exact string. Instead of being given it directly, the only way to gain information is by querying substrings of ranges. When a range $[l, r]$ is...

CF 1284D - New Year and Conference

CF 1284D - New Year and Conference Rating: 2100 Tags: binary search, data structures, hashing, sortings Solve time: 2m 35s Verified: yes Solution Problem Understanding Each lecture in the conference has two possible time schedules, depending on which venue is chosen. If we pick venue A, every lecture follows its A-interval. If we pick venue B, every lecture follows its B-interval. The key restriction is that a participant can attend...

CF 1252F - Regular Forestation

CF 1252F - Regular Forestation Rating: 2400 Tags: hashing, trees Solve time: 4m 24s Verified: no Solution Problem Understanding We are given a tree with up to 4000 nodes, and we are allowed to pick a single node and remove it. Removing a node splits the tree into several connected components, each of which is itself a tree. The number of components equals the degree of the removed node. The...

CF 1225D - Power Products

CF 1225D - Power Products Rating: 1800 Tags: hashing, math, number theory Solve time: 3m 50s Verified: yes Solution Problem Understanding We are given a sequence of positive integers and asked to count how many pairs of indices produce a product that is a perfect k-th power. In other words, for two distinct elements $a_i$ and $a_j$, we want to know whether their product can be written as $x^k$ for...

CF 1223F - Stack Exterminable Arrays

CF 1223F - Stack Exterminable Arrays Rating: 2600 Tags: data structures, divide and conquer, dp, hashing Solve time: 2m 53s Verified: yes Solution Problem Understanding We are given an array and a peculiar cancellation process that behaves like a stack with annihilation. We scan the array from left to right, maintaining a stack. When we see a value, if the stack top is different, we push it. If it is...

CF 1214D - Treasure Island

CF 1214D - Treasure Island Rating: 1900 Tags: dfs and similar, dp, flows, hashing Solve time: 3m 29s Verified: yes Solution Problem Understanding We are given an $n \times m$ grid that represents a map. Each cell is either blocked or free. We start at the top-left cell $(1,1)$ and want to reach the bottom-right cell $(n,m)$. Movement is highly restricted: from any cell we can only go either one...

CF 1207G - Indie Album

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

CF 1175F - The Number of Subpermutations

CF 1175F - The Number of Subpermutations Rating: 2500 Tags: brute force, data structures, divide and conquer, hashing, math Solve time: 6m 21s Verified: no Solution Problem Understanding We are given a sequence of integers, and we want to count how many contiguous segments behave like a perfect permutation of consecutive integers starting from 1. A segment is valid if, after taking all values inside it, every number from 1...

CF 1051E - Vasya and Big Integers

CF 1051E - Vasya and Big Integers Rating: 2600 Tags: binary search, data structures, dp, hashing, strings Solve time: 3m 4s Verified: yes Solution Problem Understanding We are given one very long decimal string a , and we want to split it into a sequence of contiguous pieces. Each piece is a substring of a , taken in order, and the concatenation of all pieces must reproduce a exactly. Each...

CF 1056E - Check Transcription

CF 1056E - Check Transcription Rating: 2100 Tags: brute force, data structures, hashing, strings Solve time: 2m 32s Verified: yes Solution Problem Understanding We are given a binary template string s , where each character is either 0 or 1 , and a target string t consisting of lowercase letters. The task is to imagine that every 0 in s is replaced by some fixed non-empty string r0 , and...

CF 1081H - Palindromic Magic

CF 1081H - Palindromic Magic Rating: 3500 Tags: data structures, hashing, strings Solve time: 2m 10s Verified: yes Solution Problem Understanding We are given two long strings, and from each string we are allowed to pick a single substring that is a palindrome. From the first string we choose one palindromic substring, from the second string we choose another palindromic substring, and we concatenate them in that order. Different choices...

CF 1830C - Hyperregular Bracket Strings

CF 1830C - Hyperregular Bracket Strings Rating: 2400 Tags: combinatorics, greedy, hashing, math, number theory, sortings Solve time: 1m 14s Verified: no Solution Working

CF 1773B - BinCoin

CF 1773B - BinCoin Rating: 2200 Tags: binary search, divide and conquer, hashing, implementation, probabilities, trees Solve time: 2m 27s Verified: no Solution Problem Understanding We are given a rooted binary tree with $n$ employees. Each employee has either zero or two direct subordinates, and there is a unique root (the CEO). The company runs a procedure that produces a full ordering of all employees, and this procedure is executed...

CF 1731C - Even Subarrays

CF 1731C - Even Subarrays Rating: 1700 Tags: bitmasks, brute force, hashing, math, number theory Solve time: 3m 54s Verified: yes Solution Problem Understanding We are given an array of integers, and we look at every contiguous segment of it. For each segment we compute the bitwise XOR of its elements, producing a single number. The task is to count how many of these segments produce a XOR value whose...

CF 1729G - Cut Substrings

CF 1729G - Cut Substrings Rating: 2100 Tags: combinatorics, dp, hashing, strings, two pointers Solve time: 3m 58s Verified: no Solution Problem Understanding We are given a text string and a pattern string. The operation allowed is to pick any occurrence of the pattern inside the text and replace that entire occurrence with dots. Those dots still occupy positions but no longer participate in further pattern matches. The goal is...

CF 1721E - Prefix Function Queries

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

CF 1658E - Gojou and Matrix Game

CF 1658E - Gojou and Matrix Game Rating: 2500 Tags: data structures, dp, games, hashing, implementation, math, number theory, sortings Solve time: 3m Verified: no Solution Problem Understanding The game is played on an $n \times n$ grid where each cell has a fixed value, and all values are distinct so there are no ties in scoring from identical weights. Marin always starts the game by choosing a specific starting...

CF 1654F - Minimal String Xoration

CF 1654F - Minimal String Xoration Rating: 2800 Tags: bitmasks, data structures, divide and conquer, greedy, hashing, sortings, strings Solve time: 2m 42s Verified: yes Solution Problem Understanding We are given a string whose length is a power of two, indexed from 0 to $2^n - 1$. The key operation allowed is a global reindexing of the string using bitwise XOR with a fixed mask $j$. In other words, we...

Codeforces Round 724 (Div. 2)

Codeforces Round 724 (Div. 2) Div. 2 | 6 problems | 2/6 verified | Difficulty 800-2600 | 21m 12s # Problem Rating Tags Accepted Time ✓ A Omkar and Bad Story 800 brute-force, constructive-algorithms 20,771 1m 42s B Prinzessin der Verurteilung 1200 brute-force, constructive-algorithms, strings 25,013 2m 40s ✓ C Diluc and Kaeya 1500 data-structures, dp, hashing 16,117 3m 49s D Omkar and Medians 2000 data-structures, greedy, implementation 5,056 3m...

Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2)

Harbour.Space Scholarship Contest 2021-2022 (open for everyone, rated, Div. 1 + Div. 2) Div. 1+2 | 9 problems | 5/9 verified | Difficulty 800-3400 | 37m 13s # Problem Rating Tags Accepted Time ✓ A Digits Sum 800 math, number-theory 34,257 4m 41s ✓ B Reverse String 1300 brute-force, dp, hashing 15,480 1m 34s C Penalty 1200 bitmasks, brute-force, dp 19,800 2m 51s ✓ D Backspace 1500 dp, greedy, strings...

CF 1536C - Diluc and Kaeya

CF 1536C - Diluc and Kaeya Rating: 1500 Tags: data structures, dp, hashing, number theory Solve time: 3m 49s Verified: no Solution Problem Understanding We are given a binary string made only of the characters D and K . For every prefix of this string, we want to determine how finely we can split that prefix into contiguous pieces such that every piece has the same internal balance between D...

Kotlin Heroes: Episode 7

Kotlin Heroes: Episode 7 Kotlin | 10 problems | 9/10 verified | Difficulty - | 43m 35s # Problem Rating Tags Accepted Time ✓ A Travel to Bertown *special, implementation, math 1,130 4m 13s ✓ B Nearest Point Function *special, implementation 816 4m 12s ✓ C Sweets *special, data-structures, implementation 484 4m 14s ✓ D String Searching *special, hashing 514 3m 31s ✓ E Chess Team Forming *special, binary-search, data-structures...

CF 1533D - String Searching

CF 1533D - String Searching Rating: - Tags: *special, hashing Solve time: 3m 31s Verified: yes Solution Problem Understanding We are given a fixed collection of strings, all of the same length, and we are asked to answer many queries about a slightly longer string. Each stored string has length $m$. Each query string has length $m+1$. For a query string $t$, we want to count how many of the...

CF 1340F - Nastya and CBS Rating: 3300 Tags: brute force, data structures, hashing Model: gpt-5-3-mini Solve time: 2m 14s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2e192c-6700-83ec-99f6-87faf42c34b3 Solution Problem Understanding We are given a sequence of integers where each value represents a bracket token. A positive number means an opening bracket of a specific type, and the corresponding negative number is the matching closing bracket of that same type. So the...

CF 1313E - Concatenation with intersection Rating: 2700 Tags: data structures, hashing, strings, two pointers Model: gpt-5-3-mini Solve time: 3m 20s Verified: yes (1/1 samples) Share: https://chatgpt.com/share/6a2de325-48b4-83ec-b5e4-21871b1e6570 Solution Problem Understanding We are given two strings of equal length, call them the first and second source strings, and a target string. We are allowed to pick any contiguous segment from the first string and any contiguous segment from the second string,...

CF 1257F - Make Them Similar

CF 1257F - Make Them Similar Rating: 2400 Tags: bitmasks, brute force, hashing, meet-in-the-middle Solve time: 7m 36s Verified: no Solution Problem Understanding We are given a fixed array of integers. We are allowed to choose a single integer x and apply it to every element using XOR. After this transformation, each original value a_i becomes b_i = a_i XOR x . The goal is not to make the resulting...

Technocup 2020 - Elimination Round 2

Technocup 2020 - Elimination Round 2 Special | 8 problems | 6/8 verified | Difficulty 900-3100 | 31m 49s # Problem Rating Tags Accepted Time ✓ A Forgetting Things 900 math 16,621 8m 53s B1 TV Subscriptions (Easy Version) 1000 implementation 12,518 2m 41s ✓ B2 TV Subscriptions (Hard Version) 1300 implementation, two-pointers 12,194 1m 46s ✓ C p-binary 1600 bitmasks, brute-force, math 9,787 2m 54s ✓ D Power Products...

CF 1228D - Complete Tripartite

CF 1228D - Complete Tripartite Rating: 1900 Tags: brute force, constructive algorithms, graphs, hashing, implementation Solve time: 5m 56s Verified: yes Solution Problem Understanding We are given an undirected graph with up to 100,000 vertices and up to 300,000 edges. The task is to split all vertices into exactly three non-empty groups so that the structure between every pair of groups is perfectly regular. The rule between any two groups...

CF 1166F - Vicky's Delivery Service

CF 1166F - Vicky's Delivery Service Rating: 2400 Tags: data structures, dsu, graphs, hashing Solve time: 3m 29s Verified: no Solution Problem Understanding The task describes a growing undirected graph where each edge also carries a color. Edges only ever get added, never removed. Interleaved with these updates are connectivity queries, but connectivity is not defined in the usual sense of arbitrary walks. Instead, a valid path must satisfy a...

Educational Codeforces Round 34 (Rated for Div. 2)

Educational Codeforces Round 34 (Rated for Div. 2) Type: Div. 2 | Problems: 7 | Verified: 5/7 | Rating range: 900-2700 | Time: 29m 10s Problem Name Rating Tags Solve Time Verified A Hungry Student Problem 900 greedy, implementation 4m 14s ✓ B The Modcrab 1200 greedy, implementation 8m 59s ✓ C Boxes Packing 1200 greedy 5m 15s ✓ D Almost Difference 2200 data-structures, math 4m 2s ✓ E Swapping...

CF 903E - Swapping Characters

CF 903E - Swapping Characters Rating: 2200 Tags: brute force, hashing, implementation, strings Solve time: 2m 19s Verified: no Solution Problem Understanding We are given $k$ strings of the same length $n$. Each of them was produced from a single unknown original string by performing exactly one swap of two different positions. The swapped characters are allowed to be equal, so a string may remain unchanged after the operation. We...

Codeforces Round 539 (Div. 1)

Codeforces Round 539 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 4/6 | Rating range: 1600-3200 | Time: 12m 1s Problem Name Rating Tags Solve Time Verified A Sasha and a Bit of Relax 1600 dp, implementation 1m 10s ✓ B Sasha and One More Name 1800 constructive-algorithms, hashing, strings 1m 13s ✓ C Sasha and a Patient Friend 2800 binary-search, data-structures, implementation 5m 14s ✗ D Sasha...

CF 1109B - Sasha and One More Name

CF 1109B - Sasha and One More Name Rating: 1800 Tags: constructive algorithms, hashing, strings Solve time: 1m 13s Verified: yes Solution Problem Understanding We are given a string that is already a palindrome, and our goal is to transform it into a different palindrome by cutting it into some number of contiguous pieces and then reordering these pieces. The task is to find the minimum number of cuts required...

CF 1129C - Morse Code

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

Codeforces Round 544 (Div. 3)

Codeforces Round 544 (Div. 3) Type: Div. 3 | Problems: 7 | Verified: 5/7 | Rating range: 1000-1900 | Time: 9m 17s Problem Name Rating Tags Solve Time Verified A Middle of the Contest 1000 implementation 1m 7s ✓ B Preparation for International Women's Day 1200 math, number-theory 1m 14s ✓ C Balanced Team 1200 sortings, two-pointers 1m 9s ✓ D Zero Quantity Maximization 1500 hashing, math, number-theory 1m 13s...

CF 1133D - Zero Quantity Maximization

CF 1133D - Zero Quantity Maximization Rating: 1500 Tags: hashing, math, number theory Solve time: 1m 13s Verified: yes Solution Problem Understanding We are given two arrays of integers, a and b , each with n elements. We are asked to construct a new array c using a single real number d such that each element c_i equals d * a_i + b_i . Our goal is to choose d...

Codeforces Round 545 (Div. 1)

Codeforces Round 545 (Div. 1) Type: Div. 1 | Problems: 6 | Verified: 3/6 | Rating range: 1600-3400 | Time: 9m 34s Problem Name Rating Tags Solve Time Verified A Skyscrapers 1600 implementation, sortings 1m 41s ✗ B Camp Schedule 1600 greedy, hashing, strings 1m 51s ✓ C Museums Tour 2500 dp, graphs, implementation 1m 25s ✓ D Cooperative Game 2400 constructive-algorithms, interactive, number-theory 1m 47s ✗ E Train Car...

CF 1137B - Camp Schedule

CF 1137B - Camp Schedule Rating: 1600 Tags: greedy, hashing, strings Solve time: 1m 51s Verified: yes Solution Problem Understanding We are given two binary strings. The first string s is not the schedule we must output directly. Instead, it acts as a multiset of characters. We are allowed to rearrange its symbols in any order, but the total number of '0' characters and '1' characters must remain exactly the...

CF 1156G - Optimizer

CF 1156G - Optimizer Rating: 2700 Tags: graphs, greedy, hashing, implementation Solve time: 1m 29s Verified: no Solution Problem Understanding We are given a program written in a strange language where each variable has a short name of up to four alphanumeric characters, with the first character not being a digit. Each line either assigns a variable the value of another variable or computes a new value using a binary...

CF 1182D - Complete Mirror

CF 1182D - Complete Mirror Rating: 2400 Tags: constructive algorithms, dfs and similar, dp, hashing, implementation, trees Solve time: 1m 17s Verified: yes Solution Problem Understanding We are given a tree with $n$ vertices, described by $n-1$ edges. A tree is a connected graph without cycles. The task is to choose a vertex as a root such that all vertices at the same distance from the root have the same...

CF 1200E - Compress Words

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

CF 1277D - Let's Play the Words?

CF 1277D - Let's Play the Words? Rating: 1900 Tags: data structures, hashing, implementation, math Solve time: 2m 3s Verified: no Solution Problem Understanding We are given a collection of binary strings, and we are allowed to optionally reverse some of them. After doing so, we want to arrange all strings in a single sequence such that every adjacent pair is compatible: the last character of a word must match...

2019-2020 ICPC, Asia Jakarta Regional Contest (Online Mirror, ICPC Rules, Teams Preferred)

2019-2020 ICPC, Asia Jakarta Regional Contest (Online Mirror, ICPC Rules, Teams Preferred) ICPC/IOI | 11 problems | 4/11 verified | Difficulty 1000-3000 | 31m # Problem Rating Tags Accepted Time ✓ A Copying Homework 1000 5,997 1m 50s ✓ B Cleaning Robots 2300 dp, trees 585 1m 58s ✓ C Even Path 1600 data-structures, implementation 3,982 1m 50s D Find String in a Grid 3000 data-structures, dp, strings 412 1m...

CF 1322C - Instant Noodles

CF 1322C - Instant Noodles Rating: 2300 Tags: graphs, hashing, math, number theory Solve time: 2m 42s Verified: no Solution Yes, the inequality $\nu(n) \le 2^{l(n) - \lambda(n)}$ holds for all positive integers $n$. Consider an addition chain of minimal length $l(n)$ and let $\lambda(n)$ be the length of a shortest chain consisting only of doubling steps. Each nondoubling step can at most double the number of ones in the...

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

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

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

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

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

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

CF 1394B - Boboniu Walks on Graph

CF 1394B - Boboniu Walks on Graph Rating: 2300 Tags: brute force, dfs and similar, graphs, hashing Solve time: 8m 53s Verified: no Solution Ah, now the bug is about the order in which the pairs are generated . The input is: 3 3 2 2 and the expected output is: 2 2 1 2 1 3 2 3 3 3 3 2 3 1 2 1 1 1 The...

Codeforces Global Round 7

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

CF 1418G - Three Occurrences

CF 1418G - Three Occurrences Rating: 2500 Tags: data structures, divide and conquer, hashing, two pointers Solve time: 28s Verified: no Solution Problem Understanding We are given an array of length $n$, and we want to count how many contiguous segments have the following property: every distinct value appearing inside that segment appears exactly three times. The condition is surprisingly restrictive. If a number appears once or twice inside the...

Codeforces Round 685 (Div. 2)

Codeforces Round 685 (Div. 2) Type: Div. 2 | Problems: 7 | Verified: 4/7 | Rating range: 800-2700 | Time: 16m 10s Problem Name Rating Tags Solve Time Verified A Subtract or Divide 800 greedy, math 2m 28s ✗ B Non-Substring Subsequence 900 dp, greedy, implementation 2m 30s ✓ C String Equality 1400 dp, greedy, hashing 1m 22s ✓ D Circle Game 1700 games, geometry, math 1m 5s ✓ E1...

CF 1451C - String Equality

CF 1451C - String Equality Rating: 1400 Tags: dp, greedy, hashing, implementation, strings Solve time: 1m 22s Verified: yes Solution Problem Understanding We are given two strings, a and b , of equal length n , along with an integer k . The goal is to determine whether we can transform a into b using two types of operations. The first operation allows swapping any adjacent characters in a ....

Codeforces Round 606 (Div. 2, based on Technocup 2020 Elimination Round 4)

Codeforces Round 606 (Div. 2, based on Technocup 2020 Elimination Round 4) Div. 2 | 3 problems | 1/3 verified | Difficulty 1000-1900 | 14m 28s # Problem Rating Tags Accepted Time ✓ A Happy Birthday, Polycarp! 1000 implementation 14,486 2m 35s B Make Them Odd 1200 greedy, number-theory 17,040 9m 50s ✓ D Let's Play the Words? 1900 data-structures, hashing, implementation 3,275 2m 3s

CF 1466G - Song of the Sirens

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

CF 1468F - Full Turn

CF 1468F - Full Turn Rating: 1700 Tags: geometry, hashing, number theory Solve time: 2m 1s Verified: yes Solution Problem Understanding We have a set of points on a plane, each representing a person, with each person initially looking at another point. Everyone rotates clockwise continuously, completing a full turn, and we are asked to count the number of distinct pairs of people who ever make “eye contact.” Eye contact...

CF 1469E - A Bit Similar

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

CF 1470B - Strange Definition

CF 1470B - Strange Definition Rating: 1900 Tags: bitmasks, graphs, hashing, math, number theory Solve time: 3m 7s Verified: yes Solution Problem Understanding We are given an array of integers. Define two values as adjacent when $$\frac{\operatorname{lcm}(x,y)}{\gcd(x,y)}$$ is a perfect square. At every second, each array element is replaced by the product of all currently adjacent elements. The quantity we care about is the beauty of the array, which is...

CF 1476G - Minimum Difference

CF 1476G - Minimum Difference Rating: 3100 Tags: data structures, hashing, sortings, two pointers Solve time: 1m 51s Verified: yes Solution Problem Understanding We are working with an array of integers where we need to handle two types of operations efficiently. The first operation asks, for a given subarray, to select exactly k distinct numbers whose frequencies are as balanced as possible, minimizing the largest difference between any two selected...

CF 1476E - Pattern Matching

CF 1476E - Pattern Matching Rating: 2300 Tags: bitmasks, data structures, dfs and similar, graphs, hashing, sortings, strings Solve time: 2m 53s Verified: no Solution I can't reliably diagnose this one from the sample alone because the sample input/output pair does not identify the problem. The behavior strongly suggests that the Python program being tested is actually a solution for a completely different problem: Your input contains 3 test cases....

CF 1493D - GCD of an Array

CF 1493D - GCD of an Array Rating: 2100 Tags: brute force, data structures, hashing, implementation, math, number theory, sortings, two pointers Solve time: 52s Verified: no Solution Problem Understanding We are given an array of integers, and we need to handle a sequence of queries where each query multiplies a specific element of the array by a given factor. After each query, we must compute the greatest common divisor...

CF 1494E - A-Z Graph

CF 1494E - A-Z Graph Rating: 2400 Tags: constructive algorithms, data structures, graphs, hashing Solve time: 2m 56s Verified: no Solution I can't reliably diagnose this one from the sample alone because the sample input/output pair does not identify the problem. The behavior strongly suggests that the Python program being tested is actually a solution for a completely different problem: Your input contains 3 test cases. The expected output is...

CF 1500A - Going Home

CF 1500A - Going Home Rating: 1800 Tags: brute force, hashing, implementation, math Solve time: 19m 39s Verified: no Solution Problem Understanding We are given an array of integers representing a gift from a friend to Nastya. She wants to find four distinct indices in the array such that the sum of the elements at the first two indices equals the sum of the elements at the other two indices....

Codeforces Round 707 (Div. 1, based on Moscow Open Olympiad in Informatics)

Codeforces Round 707 (Div. 1, based on Moscow Open Olympiad in Informatics) Type: Div. 1 | Problems: 6 | Verified: 1/6 | Rating range: 1800-3500 | Time: 26m 58s Problem Name Rating Tags Solve Time Verified A Going Home 1800 brute-force, hashing, implementation 19m 39s ✗ B Two chandeliers 2200 binary-search, brute-force, chinese-remainder-theorem 1m 3s ✗ C Matrix Sorting 2600 bitmasks, brute-force, constructive-algorithms 2m 46s ✗ D Tiles for Bathroom...

CF 1520D - Same Differences

CF 1520D - Same Differences Rating: 1200 Tags: data structures, hashing, math Solve time: 2m Verified: yes Solution Problem Understanding We are given an array and must count how many index pairs $(i, j)$ with $i < j$ satisfy a very specific relationship between their values and positions. The condition is: $$a_j - a_i = j - i$$ For every test case, we need to count all pairs that satisfy...

Codeforces Round 721 (Div. 2)

Codeforces Round 721 (Div. 2) Type: Div. 2 | Problems: 6 | Verified: 3/6 | Rating range: 800-2500 | Time: 15m 3s Problem Name Rating Tags Solve Time Verified A And Then There Were K 800 bitmasks 2m 39s ✗ B1 Palindrome Game (easy version) 1200 constructive-algorithms, games 2m 2s ✓ B2 Palindrome Game (hard version) 1900 constructive-algorithms, games 2m 14s ✓ C Sequence Pair Weight 1600 hashing, implementation, math...

CF 1527C - Sequence Pair Weight

CF 1527C - Sequence Pair Weight Rating: 1600 Tags: hashing, implementation, math Solve time: 1m 34s Verified: yes Solution Problem Understanding We are given several arrays, and for each array we consider every possible contiguous subarray. For each subarray, we define its “weight” as the number of pairs of positions inside it that contain the same value. In other words, inside a chosen segment, we look at all index pairs...

CF 1535F - String Distance

CF 1535F - String Distance Rating: 3000 Tags: binary search, brute force, data structures, hashing, implementation, strings Solve time: 6m 6s Verified: no Solution Problem Understanding We are given a collection of strings of equal length, and our task is to quantify how "sortable into each other" they are using a specific operation. This operation allows us to take any contiguous substring in one string and sort its characters in...

CF 1537E2 - Erase and Extend (Hard Version)

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

CF 1537E1 - Erase and Extend (Easy Version)

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

CF 1569F - Palindromic Hamiltonian Path

CF 1569F - Palindromic Hamiltonian Path Rating: 3000 Tags: brute force, dfs and similar, dp, graphs, hashing Solve time: 1m 18s Verified: yes Solution Problem Understanding We are given a small undirected graph with at most 12 vertices. We want to assign each vertex a letter from a fixed alphabet of size k . Every such assignment produces a labeled graph. The labeling is considered valid if there exists some...

CF 1569E - Playoff Restoration

CF 1569E - Playoff Restoration Rating: 2600 Tags: bitmasks, brute force, hashing, implementation, meet-in-the-middle Solve time: 2m 16s Verified: no Solution Problem Understanding We are given a single-elimination tournament with $2^k$ teams, where $k$ ranges from 1 to 5. The matches are structured in a fixed bracket: in the first round, consecutive teams play each other, and winners advance to the next round, pairing up according to the same rule...

CF 1574D - The Strongest Build

CF 1574D - The Strongest Build Rating: 2000 Tags: binary search, brute force, data structures, dfs and similar, graphs, greedy, hashing, implementation Solve time: 1m 21s Verified: yes Solution Problem Understanding In this problem, we are asked to help Ivan choose the strongest possible hero build from a set of equipment slots, each with multiple items of different strengths. Each slot has its own list of items, already sorted by...

CF 1598G - The Sum of Good Numbers

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

CF 1599F - Mars

CF 1599F - Mars Rating: 2700 Tags: hashing Solve time: 2m 23s Verified: no Solution Problem Understanding We are given a list of city positions on a circular Martian colony where cities are numbered modulo $10^9+7$. Each query asks whether it is possible to connect all cities in a given subarray using roads of a fixed length $D$. Connecting with a road of length $D$ means that, if you take...

CF 1608G - Alphabetic Tree

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

CF 1610G - AmShZ Wins a Bet

CF 1610G - AmShZ Wins a Bet Rating: 3300 Tags: data structures, greedy, hashing Solve time: 1m 54s Verified: no Solution Problem Understanding We are given a string of parentheses S that has been modified by repeatedly performing a wrapping operation. Each operation allows you to take any contiguous substring B and surround it with a pair of parentheses, inserting it back into its original place in the string. The...

CF 1621I - Two Sequences

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

CF 1622F - Quadratic Set

CF 1622F - Quadratic Set Rating: 2900 Tags: constructive algorithms, hashing, math, number theory Solve time: 1m 11s Verified: yes Solution Problem Understanding We are given the set of integers from 1 to n, and we are allowed to choose any subset of these numbers. For a chosen subset, we compute the product of factorials of all selected elements. A subset is considered valid when this product becomes a perfect...

CF 1624E - Masha-forgetful

CF 1624E - Masha-forgetful Rating: 2000 Tags: brute force, constructive algorithms, dp, hashing, implementation, strings Solve time: 1m 47s Verified: no Solution Problem Understanding We are given a target digit string s and a collection of known digit strings, all of the same length. The goal is to reconstruct s as a sequence of contiguous segments, where each segment must exactly match a substring taken from one of the known...

CF 1634F - Fibonacci Additions

CF 1634F - Fibonacci Additions Rating: 2700 Tags: brute force, data structures, hashing, implementation, math Solve time: 1m 23s Verified: yes Solution Problem Understanding We are asked to maintain two integer arrays, A and B , under a sequence of operations called Fibonacci additions. Each operation specifies a segment [l, r] and an array to update. The Fibonacci addition increases X_l by F_1 , X_{l+1} by F_2 , and so...

CF 1641D - Two Arrays

CF 1641D - Two Arrays Rating: 2700 Tags: bitmasks, brute force, combinatorics, greedy, hashing, math, two pointers Solve time: 1m 33s Verified: yes Solution Problem Understanding We are given a collection of small sets, each set contains exactly $m$ distinct integers and a weight attached to that set. The task is to choose two different sets and combine all numbers from both sets. The requirement is that after combining, no...

Codeforces Round 776 (Div. 3)

Codeforces Round 776 (Div. 3) Type: Div. 3 | Problems: 7 | Verified: 2/7 | Rating range: 800-2200 | Time: 15m 15s Problem Name Rating Tags Solve Time Verified A Deletions of Two Adjacent Letters 800 implementation, strings 3m 45s ✓ B DIV + MOD 900 math 1m 29s ✓ C Weight of the System of Nested Segments 1200 greedy, hashing, implementation 2m 35s ✗ D Twist the Permutation 1300...

CF 1650C - Weight of the System of Nested Segments

CF 1650C - Weight of the System of Nested Segments Rating: 1200 Tags: greedy, hashing, implementation, sortings Solve time: 2m 35s Verified: no Solution Problem Understanding We are given points on a number line. Every point has a coordinate and a weight. We want to choose exactly $2n$ of these points and use them as endpoints of $n$ segments. The segments must form a perfectly nested structure. If we sort...

CF 1671E - Preorder

CF 1671E - Preorder Rating: 2100 Tags: combinatorics, divide and conquer, dp, dsu, hashing, sortings, trees Solve time: 1m 26s Verified: yes Solution Problem Understanding We are given a complete binary tree of size $2^n - 1$, where every internal node has exactly two children and all leaves lie on the same level. Each node carries a label, either A or B. The structure is fixed, but before we read...

CF 1681D - Required Length

CF 1681D - Required Length Rating: 1700 Tags: brute force, dfs and similar, dp, hashing, shortest paths Solve time: 1m 25s Verified: yes Solution Problem Understanding We are given an integer x and a target length n . We can repeatedly choose any digit y from the current number x and multiply x by y . The goal is to make x have exactly n digits using the minimum number...

CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)

CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!) Type: Div. 1+2 | Problems: 9 | Verified: 0/9 | Rating range: 800-3500 | Time: 19m 33s Problem Name Rating Tags Solve Time Verified A Two 0-1 Sequences 800 constructive-algorithms, greedy 2m 42s ✗ B Luke is a Foodie 1000 brute-force, greedy, implementation 2m 33s ✗ C Virus 1200 greedy, implementation, sortings 2m 23s ✗ D Magical Array 1900 constructive-algorithms,...

CF 1704D - Magical Array

CF 1704D - Magical Array Rating: 1900 Tags: constructive algorithms, hashing, implementation, math Solve time: 2m 18s Verified: no Solution Problem Understanding We are given several arrays of equal length. All of them originate from the same hidden base array. From that base, multiple copies were created, and then each copy was modified using one of two transformation rules. Exactly one of these copies is special and uses a different...

CF 1729F - Kirei and the Linear Function

CF 1729F - Kirei and the Linear Function Rating: 1900 Tags: hashing, math Solve time: 1m 48s Verified: yes Solution Problem Understanding We are given a digit string. For every query, we look at one substring of the original string, namely s[l..r] , and compute its numeric value modulo 9 . Separately, we may choose any two different substrings of fixed length w . Let their starting positions be L1...

CF 1735D - Meta-set

CF 1735D - Meta-set Rating: 1700 Tags: brute force, combinatorics, data structures, hashing, math Solve time: 8m 55s Verified: yes Solution Problem Understanding We are given a variant of the card game "Set". Each card has $k$ features, each of which is 0, 1, or 2. A card is thus a length-$k$ vector over ${0,1,2}$. A "set" is any three cards where, for every feature, either all three values are...

CF 1743G - Antifibonacci Cut

CF 1743G - Antifibonacci Cut Rating: 3000 Tags: bitmasks, combinatorics, constructive algorithms, data structures, dp, hashing, math Solve time: 2m 32s Verified: no Solution Problem-Type Check This problem is Type A. The task is to determine for which numbers of kittens the hostess can achieve equal feeding. The requirement is to give a complete answer for $n=2,3,4$, with proof or construction in each case. The proposed solution attempts exactly this....

CF 1746F - Kazaee

CF 1746F - Kazaee Rating: 2800 Tags: data structures, hashing, probabilities Solve time: 1m 19s Verified: no Solution Producing a correct editorial for Codeforces 1746F requires reconstructing the intended probabilistic proof, the exact hashing scheme, the error analysis, and the implementation details used to achieve acceptance at $n,q \le 3\cdot 10^5$. I can see the problem statement and several secondary references, and they confirm the high level idea: assign random...

CF 1771F - Hossam and Range Minimum Query

CF 1771F - Hossam and Range Minimum Query Rating: 2500 Tags: binary search, bitmasks, data structures, hashing, probabilities, strings, trees Solve time: 2m 17s Verified: no Solution Problem-Type Check This is a Type B (prove inequality) problem, not Type C. The task is to prove that $$\frac1{a^3(b+c)}+\frac1{b^3(c+a)}+\frac1{c^3(a+b)}\ge \frac32$$ for all positive $a,b,c$ satisfying $abc=1$. A valid solution must establish the inequality for all admissible triples and correctly identify any equality...

CF 1780G - Delicious Dessert

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

CF 1792D - Fixed Prefix Permutations

CF 1792D - Fixed Prefix Permutations Rating: 1700 Tags: binary search, bitmasks, data structures, hashing, math, sortings Solve time: 2m 6s Verified: no Solution Problem Understanding We are given multiple permutations of length $m$. Each permutation contains all integers from 1 to $m$ exactly once. The "beauty" of a permutation is the length of its initial prefix that forms the identity sequence $1, 2, 3, \dots, k$. For example, the...

CF 1794E - Labeling the Tree with Distances

CF 1794E - Labeling the Tree with Distances Rating: 2400 Tags: data structures, dp, greedy, hashing, implementation, trees Solve time: 3m 9s Verified: yes Solution Problem Understanding We are given a tree with $n$ vertices and a multiset of $n-1$ integers. One vertex is special: it is not assigned any value from the list, while every other vertex must be assigned exactly one number from the list. After that, the...

CF 1800G - Symmetree

CF 1800G - Symmetree Rating: 2200 Tags: dfs and similar, hashing, implementation, trees Solve time: 1m 41s Verified: no Solution Problem Understanding We are given a rooted tree with vertices numbered from 1 to $n$, where vertex 1 is the root. Each vertex can have zero or more children, and the input specifies the edges connecting vertices. The task is to determine whether the tree is symmetrical. A tree is...

Codeforces Round 855 (Div. 3)

Codeforces Round 855 (Div. 3) Type: Div. 3 | Problems: 9 | Verified: 8/9 | Rating range: 800-2200 | Time: 18m 24s Problem Name Rating Tags Solve Time Verified A Is It a Cat? 800 implementation, strings 1m 47s ✓ B Count the Number of Pairs 1000 greedy, strings 2m 57s ✓ C1 Powering the Hero (easy version) 1000 data-structures, greedy 3m 50s ✓ C2 Powering the Hero (hard version)...

CF 1800F - Dasha and Nightmares

CF 1800F - Dasha and Nightmares Rating: 1900 Tags: bitmasks, hashing, meet-in-the-middle, strings Solve time: 1m 42s Verified: yes Solution Problem Understanding We are given a list of words and asked to count pairs of words whose concatenation satisfies several strict properties. Specifically, a "nightmare" is formed by concatenating two words, resulting in a string of odd length, containing exactly 25 distinct letters, and having each letter occur an odd...

CF 1800D - Remove Two Letters

CF 1800D - Remove Two Letters Rating: 1200 Tags: data structures, greedy, hashing, strings Solve time: 1m 41s Verified: yes Solution Problem Understanding We are given a string consisting of lowercase Latin letters, and the task is to count how many distinct strings can be formed by removing any two consecutive characters. Each test case consists of a string of length at least three. The output is simply the number...

CF 1801E - Gasoline prices

CF 1801E - Gasoline prices Rating: 3000 Tags: data structures, divide and conquer, dsu, hashing, trees Solve time: 1m 17s Verified: yes Solution Problem Understanding We are given a country, Berland, structured as a tree of cities rooted at city 1. Each city has a gas station with a price range $[l_i, r_i]$. Every year, the king’s two sons inspect gasoline prices along two paths of equal length. Each inspection...

CF 1827C - Palindrome Partition

CF 1827C - Palindrome Partition Rating: 2600 Tags: binary search, brute force, data structures, dp, hashing, strings Solve time: 1m 28s Verified: no Solution Problem Understanding We are given a string consisting of lowercase Latin letters, and we are asked to count its “beautiful” substrings. A substring is beautiful if it is an even palindrome or can be partitioned into smaller even palindromes. An even palindrome has even length and...

CF 1828E - Palindrome Partition

CF 1828E - Palindrome Partition Rating: 2600 Tags: data structures, dp, hashing, strings Solve time: 2m 5s Verified: no Solution Correctness The solution correctly generalizes the serial test from pairs to $k$-tuples by grouping the sequence into disjoint blocks of length $k$, ensuring independence under the null hypothesis. It correctly identifies that the counts of each possible $k$-tuple follow a multinomial distribution with $d^k$ categories and equal probabilities $1/d^k$ under...

CF 1831E - Hyperregular Bracket Strings

CF 1831E - Hyperregular Bracket Strings Rating: 2400 Tags: combinatorics, data structures, hashing, math, number theory, sortings, two pointers Solve time: 3m 20s Verified: no Solution Problem Understanding We are asked to count bracket sequences of length $n$ that are globally regular, while also being locally regular on certain specified subintervals. The input gives us the length $n$ and a list of $k$ intervals $[l_i, r_i]$. A globally regular bracket...

CF 1840E - Character Blocking

CF 1840E - Character Blocking Rating: 1600 Tags: data structures, hashing, implementation Solve time: 3m 6s Verified: no Solution Thanks for providing the input/output. From the symptoms, the actual bug is clear: the previous solution was just summing ASCII values of characters in the string ( ord(c) ), which produces numbers like 529 or 670 . The expected outputs ( 11088 , 10010 , etc.) indicate that the problem requires...

CF 1849C - Binary String Copying

CF 1849C - Binary String Copying Rating: 1600 Tags: binary search, brute force, data structures, hashing, strings Solve time: 1m 31s Verified: yes Solution Problem Understanding We are asked to analyze the effect of sorting substrings on multiple copies of a binary string. Each test case gives us a string consisting of zeros and ones, and a set of operations, one per copy. Each operation is defined by a range...

CF 2024E - C+K+S

CF 2024E - C+K+S Rating: 2400 Tags: constructive algorithms, graphs, hashing, strings Solve time: 3m 38s Verified: no Solution Problem Understanding We are given two directed graphs, each with the same number of vertices, and we are asked to add exactly one edge from each outgoing vertex to an incoming vertex in the other graph. Each original graph is strongly connected, and every cycle in the graph has a length...

Codeforces Round 841 (Div. 2) and Divide by Zero 2022

Codeforces Round 841 (Div. 2) and Divide by Zero 2022 Div. 2 | 6 problems | 5/6 verified | Difficulty 800-2500 | 26m 51s # Problem Rating Tags Accepted Time ✓ A Joey Takes Money 800 greedy, math 23,667 1m 54s ✓ B Kill Demodogs 1100 greedy, math 26,784 8m 50s C Even Subarrays 1700 bitmasks, brute-force, hashing 12,125 3m 54s ✓ D Valiant's New Map 1700 binary-search, brute-force, data-structures...

CF 1994H - Fortnite

CF 1994H - Fortnite Rating: 3500 Tags: combinatorics, constructive algorithms, games, greedy, hashing, interactive, math, number theory, strings Solve time: 2m 4s Verified: no Solution Exploration The first problem asks whether an infinite sequence of perfect squares $(a_n^2)$ can exist such that each term starting from the third satisfies the Fibonacci-type recurrence $a_n^2 = a_{n-1}^2 + a_{n-2}^2.$ Since squares grow faster than linearly and the recurrence is additive, the existence...

CF 1944D - Non-Palindromic Substring

CF 1944D - Non-Palindromic Substring Rating: 2000 Tags: hashing, implementation, strings Solve time: 1m 22s Verified: no Solution Problem Understanding We are given a string of lowercase English letters and a set of queries, each specifying a contiguous substring of the string. For each query, we are asked to compute the sum of all lengths $k$ for which there exists at least one substring of length $k$ that is not...

CF 1906B - Button Pressing

CF 1906B - Button Pressing Rating: 2600 Tags: bitmasks, constructive algorithms, hashing Solve time: 1m 46s Verified: no Solution Problem Understanding We have a line of lamps, each either on or off, and a line of buttons, one per lamp. Each button affects only the lamps immediately adjacent to it: pressing button $i$ toggles lamps $i-1$ and $i+1$, if they exist. The twist is that a button can only be...

CF 1867F - Most Different Tree

CF 1867F - Most Different Tree Rating: 2700 Tags: brute force, constructive algorithms, dfs and similar, greedy, hashing Solve time: 1m 7s Verified: yes Solution Problem Understanding We start with a rooted tree $G$ on $n$ vertices, rooted at vertex $1$. For every vertex $v$, we look at the “subtree of $v$” defined as all vertices whose path from the root passes through $v$. In other words, it is exactly...

CF 1887C - Minimum Array

CF 1887C - Minimum Array Rating: 2400 Tags: binary search, brute force, constructive algorithms, data structures, greedy, hashing, two pointers Solve time: 2m 2s Verified: no Solution Problem Understanding We are given an array of integers and a sequence of operations that increment segments of the array by a given value. Each operation specifies a contiguous subarray and an integer to add. The task is to determine which intermediate array-either...

Educational Codeforces Round 157 (Rated for Div. 2)

Educational Codeforces Round 157 (Rated for Div. 2) Type: Div. 2 | Problems: 7 | Verified: 4/7 | Rating range: 800-3100 | Time: 13m 43s Problem Name Rating Tags Solve Time Verified A Treasure Chest 800 math 1m 50s ✓ B Points and Minimum Distance 800 greedy, math, sortings 1m 38s ✗ C Torn Lucky Ticket 1400 brute-force, dp, hashing 1m 27s ✗ D XOR Construction 1900 bitmasks, constructive-algorithms, data-structures...

CF 1895C - Torn Lucky Ticket

CF 1895C - Torn Lucky Ticket Rating: 1400 Tags: brute force, dp, hashing, implementation, math Solve time: 1m 27s Verified: no Solution Problem Understanding We are given a collection of ticket fragments, each represented as a string of digits from 1 to 9. A lucky ticket is defined as a string of even length where the sum of digits in the first half equals the sum in the second half....

CF 1899D - Yarik and Musical Notes

CF 1899D - Yarik and Musical Notes Rating: 1300 Tags: hashing, math, number theory Solve time: 1m 41s Verified: yes Solution Problem Understanding We are given a sequence of integers a_1, a_2, ..., a_n , where each integer represents the exponent of 2 forming a musical note: b_i = 2^{a_i} . Yarik defines a combination of two notes (b_i, b_j) as b_i^{b_j} . He wants to count the number of...

CF 1909G - Pumping Lemma

CF 1909G - Pumping Lemma Rating: 3000 Tags: hashing, strings Solve time: 1m 22s Verified: yes Solution Problem Understanding We are given two strings, s of length n and t of length m , where n is strictly smaller than m . The task is to count the number of ways we can split s into three contiguous substrings x , y , z such that when we take x...

CF 1913F - Palindromic Problem

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

CF 1914G2 - Light Bulbs (Hard Version)

CF 1914G2 - Light Bulbs (Hard Version) Rating: 2300 Tags: combinatorics, data structures, dfs and similar, dp, graphs, hashing Solve time: 36s Verified: no Solution Problem Understanding We are given a row of $2n$ light bulbs, with each color from $1$ to $n$ appearing exactly twice. All bulbs start turned off. We are allowed to initially turn on any subset $S$ of bulbs. After that, we can apply two operations...

CF 1923F - Shrink-Reverse

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

Codeforces Round 1053 (Div. 1)

Codeforces Round 1053 (Div. 1) Div. 1 | 8 problems | 0/8 verified | Difficulty 1300-3500 | 15m 14s # Problem Rating Tags Accepted Time ✓ A Incremental Path 1300 data-structures, hashing, implementation 11,684 1m 41s B Grid Counting 1700 combinatorics, implementation, math 6,046 2m 32s C Limited Edition Shop 2100 data-structures, dp 2,653 1m 41s D Attraction Theory 2700 combinatorics, dp, math 752 1m 42s E1 Hidden Single (Version...

Codeforces Round 1050 (Div. 4)

Codeforces Round 1050 (Div. 4) Div. 4 | 7 problems | 4/7 verified | Difficulty 800-1900 | 12m 21s # Problem Rating Tags Accepted Time ✓ A Sublime Sequence 800 brute-force, hashing, math 47,386 1m 7s ✓ B Lasers 800 geometry 33,033 1m 11s ✓ C Pacer 900 greedy, math 25,326 1m 34s D Destruction of the Dandelion Fields 1000 constructive-algorithms, greedy, sortings 26,723 1m 33s ✓ E Split 1200...

CF 1969F - Card Pairing

CF 1969F - Card Pairing Rating: 3000 Tags: dp, greedy, hashing, implementation Solve time: 1m 47s Verified: yes Solution Problem Understanding We are given a sequence of cards arranged in a fixed order, each card having a type from a range of $k$ labels. The process starts by taking the first $k$ cards into our hand. After that, the game evolves in rounds where we repeatedly consume cards from the...

CF 1977D - XORificator

CF 1977D - XORificator Rating: 2300 Tags: bitmasks, brute force, greedy, hashing Solve time: 2m 8s Verified: no Solution Problem Understanding We are given a matrix of size $n \times m$ consisting only of 0s and 1s. We can “flip” any row using a XORificator, which changes every 0 to 1 and every 1 to 0 in that row. After performing any flips, we want to maximize the number of...

CF 1979D - Fixing a Binary String

CF 1979D - Fixing a Binary String Rating: 1800 Tags: bitmasks, brute force, constructive algorithms, dp, greedy, hashing, strings Solve time: 2m 23s Verified: no Solution Problem Understanding We are given a binary string of length n and a number k that divides n . The task is to perform exactly one special operation on the string to make it k -proper. A k -proper string starts with k identical...

CF 1980E - Permutation of Rows and Columns

CF 1980E - Permutation of Rows and Columns Rating: 1600 Tags: constructive algorithms, data structures, greedy, hashing, implementation, math, matrices, sortings Solve time: 1m 20s Verified: yes Solution Problem Understanding We are given two rectangular grids of numbers, both of size $n \times m$, and together they contain exactly the numbers from $1$ to $n \cdot m$, each appearing once. So each matrix is just a rearrangement of the same...

CF 1984D - ''a'' String Problem

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

CF 1986G2 - Permutation Problem (Hard Version)

CF 1986G2 - Permutation Problem (Hard Version) Rating: 2500 Tags: brute force, data structures, hashing, math, number theory Solve time: 3m 11s Verified: no Solution Problem Understanding We are given a permutation of integers from 1 to $n$, and we are asked to count how many pairs of indices $(i, j)$ satisfy $i < j$ and $p_i \cdot p_j$ divisible by $i \cdot j$. Conceptually, the permutation represents a reordering...

CF 1996G - Penacony

CF 1996G - Penacony Rating: 2200 Tags: brute force, data structures, graphs, greedy, hashing Solve time: 3m 49s Verified: yes Solution Problem Understanding The problem describes a circular town with n houses connected by roads that form a single cycle. Each house i connects to i+1 , and the last house n connects back to house 1 . Among these residents, there are m friendships, each linking two distinct houses....

CF 2002G - Lattice Optimizing

CF 2002G - Lattice Optimizing Rating: 3400 Tags: bitmasks, brute force, hashing, meet-in-the-middle Solve time: 39s Verified: no Solution Exploration The problem asks only for existence or nonexistence in three classes. For part (1), it suffices to exhibit a tetrahedron that tiles space by congruent copies. For part (2), we must decide whether a congruent tiling by equifacial tetrahedra exists. An equifacial tetrahedron is a disphenoid, that is, a tetrahedron...

CF 2002D2 - DFS Checker (Hard Version)

CF 2002D2 - DFS Checker (Hard Version) Rating: 2300 Tags: binary search, data structures, dfs and similar, graphs, hashing, trees Solve time: 2m 23s Verified: no Solution Problem Understanding We are given a rooted tree where vertex 1 is the root. Alongside the tree, we maintain a permutation stored in an array indexed by positions, and we repeatedly swap two positions in this array. After each swap, we must decide...

CF 2002D1 - DFS Checker (Easy Version)

CF 2002D1 - DFS Checker (Easy Version) Rating: 1900 Tags: brute force, data structures, dfs and similar, graphs, hashing, trees Solve time: 1m 30s Verified: yes Solution Problem Understanding We are given a perfect binary tree whose vertices are numbered in heap order. Vertex 1 is the root, and for every vertex i > 1 , its parent is i // 2 . A permutation p of all vertices is...

CF 2010C2 - Message Transmission Error (hard version)

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

Testing Round 19 (Div. 3)

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

CF 2014H - Robin Hood Archery

CF 2014H - Robin Hood Archery Rating: 1900 Tags: data structures, divide and conquer, greedy, hashing Solve time: 2m 2s Verified: yes Solution Problem Understanding For each query we look only at the subarray $a_l, a_{l+1}, \dots, a_r$. Robin moves first. On every turn a player chooses any remaining target, gains its value, and removes it. Since there are no restrictions on which target can be chosen, the game is...

CF 2020C - Bitwise Balancing

CF 2020C - Bitwise Balancing Rating: 1400 Tags: bitmasks, hashing, implementation, math, schedules, ternary search Solve time: 2m 10s Verified: no Solution Problem Understanding We are given three non-negative integers b , c , and d . We must construct a non-negative integer a such that $$(a \mid b) - (a & c) = d$$ where | is bitwise OR and & is bitwise AND. The task is not to...

CF 2023C - C+K+S

CF 2023C - C+K+S Rating: 2400 Tags: constructive algorithms, dfs and similar, graphs, greedy, hashing, implementation, strings Solve time: 1m 49s Verified: no Solution Problem Understanding We are given two directed graphs, each with the same number of vertices. Each graph is already strongly connected, and every directed cycle inside each graph has length divisible by a fixed integer $k$. This already imposes a hidden structure on both graphs: they...

CF 2034E - Permutations Harmony

CF 2034E - Permutations Harmony Rating: 2200 Tags: combinatorics, constructive algorithms, greedy, hashing, math Solve time: 2m 25s Verified: yes Solution Problem Understanding We need to construct $k$ distinct permutations of length $n$ such that if we look at any position $i$, the sum of the values appearing at that position across all $k$ permutations is the same for every position. If we denote the permutations by $p_1,p_2,\dots,p_k$, then for...

CF 2038I - Polyathlon

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

CF 2041I - Auto Complete

CF 2041I - Auto Complete Rating: 2300 Tags: binary search, data structures, hashing, implementation, sortings, strings, trees Solve time: 2m 10s Verified: yes Solution Problem Understanding We are asked to simulate an advanced text editor that supports four operations: adding patterns for auto-complete, deleting patterns, appending text to the current editor content, and deleting characters from the end of the current content. After each operation, the editor should suggest the...

CF 2053G - Naive String Splits

CF 2053G - Naive String Splits Rating: 3400 Tags: binary search, brute force, greedy, hashing, math, number theory, strings Solve time: 2m 11s Verified: yes Solution Problem Understanding We are given two strings for each test case: a string s of length n and a string t of length m . The task is to examine all ways to split s into a prefix x and a suffix y at...

CF 2055F - Cosmic Divide

CF 2055F - Cosmic Divide Rating: 3200 Tags: brute force, geometry, hashing, math, strings Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a polyomino described row by row. Each row contains a contiguous horizontal segment of filled unit cells, so the shape is a “staircase-like” union of intervals on integer rows. The shape is guaranteed to be convex in the sense that each row is a...

CF 2059E2 - Stop Gaming (Hard Version)

CF 2059E2 - Stop Gaming (Hard Version) Rating: 2900 Tags: brute force, constructive algorithms, data structures, hashing, strings Solve time: 1m 34s Verified: no Solution Problem Understanding We are given multiple arrays of equal length and we are asked to transform them into a target configuration using a very specific operation. The operation lets us pick an array, insert a number at the beginning, propagate the last element of that...

CF 2059E1 - Stop Gaming (Easy Version)

CF 2059E1 - Stop Gaming (Easy Version) Rating: 2500 Tags: brute force, constructive algorithms, greedy, hashing, strings Solve time: 1m 49s Verified: no Solution Problem Understanding We are given a sequence of arrays, each of length $m$, and we need to transform them into another target sequence of arrays using a special operation. The operation is a cascading insertion: we choose an array $i$ and a number $x$, insert $x$...

CF 2063F1 - Counting Is Not Fun (Easy Version)

CF 2063F1 - Counting Is Not Fun (Easy Version) Rating: 2400 Tags: combinatorics, data structures, dfs and similar, dp, dsu, graphs, hashing, implementation, math, trees Solve time: 1m 55s Verified: no Solution Problem Understanding The problem asks us to count balanced bracket sequences under incremental constraints. We are given a balanced sequence of 2n brackets, but we do not know its content. The sequence can be viewed as a set...

CF 2069D - Palindrome Shuffle

CF 2069D - Palindrome Shuffle Rating: 1800 Tags: binary search, greedy, hashing, strings, two pointers Solve time: 1m 36s Verified: yes Solution Problem Understanding We are given a string of even length, consisting only of lowercase letters. The allowed operation is to select any contiguous substring of the string and shuffle its characters arbitrarily. Our goal is to determine the minimum length of such a substring that, after shuffling, can...

CF 2110D - Fewer Batteries

CF 2110D - Fewer Batteries Rating: 1700 Tags: binary search, dfs and similar, dp, graphs, greedy, hashing Solve time: 1m 42s Verified: no Solution Problem Understanding We are asked to guide a robot through a series of checkpoints. Each checkpoint has a certain number of batteries that the robot can collect, and there are one-way passages connecting some checkpoints. Each passage requires the robot to carry at least a certain...

CF 2118F - Shifts and Swaps

CF 2118F - Shifts and Swaps Rating: 3100 Tags: data structures, graphs, hashing, trees Solve time: 1m 56s Verified: no Solution Problem Understanding We are asked whether one array of integers, a , can be transformed into another array, b , using two types of operations. The first operation is a cyclic left shift, which moves every element one position to the left and wraps the first element to the...

CF 2132G - Famous Choreographer

CF 2132G - Famous Choreographer Rating: 2600 Tags: hashing, implementation, strings Solve time: 1m 33s Verified: no Solution Problem Understanding We are given a rectangular grid of ballerinas, each performing one of 26 possible movements represented by lowercase English letters. Conceptually, each row is a string, and the entire grid is an array of strings. The choreographer wants to rotate the grid 180 degrees and have the final configuration match...

CF 2135F - To the Infinity

CF 2135F - To the Infinity Rating: 3500 Tags: data structures, hashing, math, trees Solve time: 1m 48s Verified: no Solution Problem Understanding We are given a rooted full binary tree where every node represents a function built recursively from its children. Leaves behave simply: their function is just the identity map $f_u(x) = x$. Internal nodes combine their two subtrees by exponentiation, so if a node has left child...

CF 2146E - Yet Another MEX Problem

CF 2146E - Yet Another MEX Problem Rating: 2300 Tags: brute force, constructive algorithms, data structures, divide and conquer, greedy, hashing Solve time: 1m 47s Verified: no Solution Problem Understanding We are given an array that grows one element at a time from left to right. After each new element is appended, we look at all subarrays that end exactly at this new position. Among those subarrays, we want the...

2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred)

2023-2024 ICPC, Asia Jakarta Regional Contest (Online Mirror, Unrated, ICPC Rules, Teams Preferred) Type: ICPC/IOI | Problems: 13 | Verified: 10/13 | Rating range: 1000-3000 | Time: 25m 58s Problem Name Rating Tags Solve Time Verified A Easy As ABC 1000 brute-force 1m 20s ✓ B Button Pressing 2600 bitmasks, constructive-algorithms, hashing 1m 46s ✗ C Cursed Game 3000 interactive 1m 18s ✓ D Spaceship Exploration 2800 binary-search, geometry 4m...

CF 2148A - Sublime Sequence

CF 2148A - Sublime Sequence Rating: 800 Tags: brute force, hashing, math Solve time: 1m 7s Verified: yes Solution Problem Understanding The problem gives us a number x and a length n and asks us to construct a sequence by alternating x and -x , starting with x . We are then asked to compute the sum of all elements in that sequence. Conceptually, this is like flipping the sign...

CF 2150A - Incremental Path

CF 2150A - Incremental Path Rating: 1300 Tags: data structures, hashing, implementation Solve time: 1m 41s Verified: no Solution Problem Understanding We are given a line of $10^9$ cells, each either black or white. Initially, a certain set of cells are black, and all others are white. Then, a series of commands is executed multiple times in a cumulative way: for the first command, we start at cell 1, follow...

CF 2172H - Shuffling Cards with Problem Solver 68!

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

CF 2178G - deCH OR Dations

CF 2178G - deCH OR Dations Rating: 2800 Tags: bitmasks, data structures, dp, hashing, probabilities Solve time: 2m 22s Verified: no Solution Problem Understanding We are given a circle with $2n$ points labeled from $1$ to $2n$. Santa draws $n$ chords connecting distinct pairs of points. Chords may intersect. For each prefix of chords $1$ through $\ell$, we are asked whether the chords are tight-knit . A set of chords...

CF 2201F2 - Monotone Monochrome Matrices (Hard Version)

CF 2201F2 - Monotone Monochrome Matrices (Hard Version) Rating: 2800 Tags: constructive algorithms, data structures, hashing, math Solve time: 1m 56s Verified: no Solution Problem Understanding We start with an $n \times n$ grid that is completely empty, and we gradually paint some cells black. After each paint operation, we must decide whether the current black-white pattern avoids a very specific forbidden configuration involving two rows and two columns. The...

CF 2201F1 - Monotone Monochrome Matrices (Medium Version)

CF 2201F1 - Monotone Monochrome Matrices (Medium Version) Rating: 2900 Tags: data structures, hashing Solve time: 1m 51s Verified: no Solution Problem Understanding We are maintaining an $n \times n$ grid that starts completely empty in the sense that every cell is white. Over time, we flip certain cells to black, one at a time, and after each flip we must decide whether the current black-white pattern satisfies a structural...

CF 2203F - Binary Search with One Swap

CF 2203F - Binary Search with One Swap Rating: 2600 Tags: binary search, divide and conquer, dp, hashing, math, two pointers Solve time: 2m 2s Verified: no Solution Problem Understanding We start with an array containing the numbers from 1 to n in increasing order. Then we pick two positions i and j and swap the elements at those positions, creating exactly one disturbance in an otherwise perfectly sorted sequence....

CF 2209E - A Trivial String Problem

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

Codeforces Round 1087 (Div. 2)

Codeforces Round 1087 (Div. 2) Div. 2 | 6 problems | 1/6 verified | Difficulty 800-2700 | 11m 5s # Problem Rating Tags Accepted Time ✓ A Flip Flops 800 greedy 21,430 2m 13s B Array 900 greedy 19,314 1m 27s ✓ C Find the Zero 1400 constructive-algorithms, interactive 10,597 2m D Ghostfires 1800 constructive-algorithms, greedy 5,306 1m 47s E A Trivial String Problem 2200 brute-force, dp, hashing 1,755 1m...

Codeforces Round 277 (Div. 2)

Codeforces Round 277 (Div. 2) Div. 2 | 5 problems | 5/5 verified | Difficulty 800-2200 | 9m 11s # Problem Rating Tags Accepted Time ✓ A Calculating Function 800 implementation, math 154,077 1m 34s ✓ B OR in Matrix 1300 greedy, hashing, implementation 19,167 1m 32s ✓ C Palindrome Transformation 1700 brute-force, greedy, implementation 12,370 1m 44s ✓ D Valid Sets 2100 dfs-and-similar, dp, math 4,380 1m 58s ✓...

CF 2225F - String Cutting

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

CF 1968G2 - Division + LCP (hard version)

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

CF 1968G1 - Division + LCP (easy version)

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

CF 1957F1 - Frequency Mismatch (Easy Version)

CF 1957F1 - Frequency Mismatch (Easy Version) Rating: 2600 Tags: binary search, data structures, divide and conquer, hashing, probabilities, trees Solve time: 2m 8s Verified: no Solution Problem Understanding We are working on a rooted tree where each node carries a small integer label. Each query gives us two paths in the tree. For each path, we can think of walking from one endpoint to the other and collecting the...

CF 1957F2 - Frequency Mismatch (Hard Version)

CF 1957F2 - Frequency Mismatch (Hard Version) Rating: 2700 Tags: binary search, data structures, dfs and similar, hashing, probabilities, trees Solve time: 1m 53s Verified: no Solution Problem Understanding We are given a tree with $n$ nodes, each node labeled with an integer value. The tree is unrooted, but conceptually we can root it anywhere for processing. For each query, we are asked to compare the multiset of values along...

CF 486E - LIS of Sequence

CF 486E - LIS of Sequence Rating: 2200 Tags: data structures, dp, greedy, hashing, math Solve time: 2m 23s Verified: yes Solution Problem Understanding We are given an array and we care about its longest increasing subsequences. An index belongs to a longest increasing subsequence if the value at that position is selected as one of the elements of that subsequence. The task is not to count LISs. Instead, for...

CF 486B - OR in Matrix

CF 486B - OR in Matrix Rating: 1300 Tags: greedy, hashing, implementation Solve time: 1m 32s Verified: yes Solution Problem Understanding We are given a matrix B of size m × n , where each element is either 0 or 1. This matrix was supposedly generated from some original matrix A of the same size using a specific rule: each element B[i][j] equals the logical OR of all elements in...

CF 452F - Permutation

CF 452F - Permutation Rating: 2700 Tags: data structures, divide and conquer, hashing Solve time: 2m 54s Verified: yes Solution Problem Understanding We are given a permutation of the numbers 1...n . For two distinct values a and b , their average is (a+b)/2 . Since the permutation contains every integer exactly once, this average is also present whenever a+b is even. The question is whether there exists a pair...

CF 407D - Largest Submatrix 3

CF 407D - Largest Submatrix 3 Rating: 2700 Tags: dp, hashing Solve time: 4m 44s Verified: no Solution Problem Understanding We are given an integer matrix of size n by m . Each cell contains a positive integer. The task is to find the largest rectangular submatrix where all the elements are distinct. The “largest” is measured by area, meaning the number of cells inside the rectangle. For example, a...

CF 350D - Looking for Owls

CF 350D - Looking for Owls Rating: 2400 Tags: binary search, data structures, geometry, hashing, sortings Solve time: 1m 55s Verified: no Solution Problem Understanding We are asked to count "owls" in a geometric picture composed of segments and circles. An owl is defined as a combination of two circles and a segment where the circles are reflections of each other across the segment, have identical radii, do not overlap,...

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

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

CF 316G1 - Good Substrings

CF 316G1 - Good Substrings Rating: 1700 Tags: hashing, strings Solve time: 1m 12s Verified: yes Solution Problem Understanding We are asked to count the number of distinct substrings of a string s that satisfy a set of occurrence-based rules. Each rule consists of a string p and a range [l, r] , and a substring t of s is considered good if the number of times it appears in...

CF 291E - Tree-String Problem

CF 291E - Tree-String Problem Rating: 2000 Tags: *special, dfs and similar, hashing, strings Solve time: 2m 57s Verified: no Solution Problem Understanding We are given a rooted tree with $n$ vertices, where each edge is labeled with a non-empty string. The root of the tree is vertex 1. Each non-root vertex $v$ has a parent $p_v$ and a string $s_v$ on the edge from $p_v$ to $v$. A "position"...

Codeforces Round 141 (Div. 2)

Codeforces Round 141 (Div. 2) Div. 2 | 5 problems | 4/5 verified | Difficulty 800-2100 | 8m 43s # Problem Rating Tags Accepted Time ✓ A Is your horseshoe on the other hoof? 800 implementation 139,744 1m 7s ✓ B Two Tables 1400 brute-force, implementation 3,636 1m 35s ✓ C Fractal Detector 2000 dp, hashing 549 2m 22s ✓ D Zigzag 2100 data-structures 438 1m 42s ✓ E The...

CF 228C - Fractal Detector

CF 228C - Fractal Detector Rating: 2000 Tags: dp, hashing Solve time: 2m 22s Verified: yes Solution Problem Understanding We are given an $n \times m$ grid where each cell is either white (".") or black ("*"). Vasya claims to have painted a fractal on some sub-squares of this grid. The fractal is built recursively from a $2 \times 2$ base pattern, where in each step, each white square is...

CF 196D - The Next Good String

CF 196D - The Next Good String Rating: 2800 Tags: data structures, greedy, hashing, strings Solve time: 2m 4s Verified: no Solution Problem Understanding We are asked to find the next string lexicographically larger than a given string s such that no substring of length d or more is a palindrome. A palindrome is a sequence that reads the same forwards and backwards. For example, in a string of lowercase...

CF 190E - Counter Attack

CF 190E - Counter Attack Rating: 2100 Tags: data structures, dsu, graphs, hashing, sortings Solve time: 1m 33s Verified: no Solution Problem Understanding We are given a set of cities, but the twist is that the input does not describe the real road system directly. Instead, it describes the complement of it. Every pair of cities that appears as connected in the input actually has no road between them in...

Codeforces Round 109 (Div. 1)

Codeforces Round 109 (Div. 1) Div. 1 | 5 problems | 1/5 verified | Difficulty 1600-3000 | 5m 36s # Problem Rating Tags Accepted Time ✓ A Hometask 1600 greedy 4,326 30s B Colliders 1600 math, number-theory 6,123 32s C Double Profiles 2300 graphs, hashing, sortings 3,317 1m 3s ✓ D Flatland Fencing 2400 games, math 487 1m 3s E Martian Colony 3000 geometry 112 2m 28s

Codeforces Beta Round 93 (Div. 1 Only)

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

CF 154C - Double Profiles

CF 154C - Double Profiles Rating: 2300 Tags: graphs, hashing, sortings Solve time: 1m 3s Verified: yes Solution Problem Understanding We are given an undirected graph representing a social network. Each vertex is a profile and each edge is a friendship. Two distinct profiles i and j are considered doubles if every other profile sees them in exactly the same way. For every vertex k ≠ i, j , either...

Codeforces Round 934 (Div. 1)

Codeforces Round 934 (Div. 1) Div. 1 | 8 problems | 1/8 verified | Difficulty 1300-3500 | 10m 17s # Problem Rating Tags Accepted Time ✓ A MEX Game 1 1300 games, greedy 21,471 1m 9s ✓ B Non-Palindromic Substring 2000 hashing, implementation, math 4,540 1m 20s C Tree Compass 2300 constructive-algorithms, dfs-and-similar, greedy 2,600 1m 16s D1 Counting Is Fun (Easy Version) 2400 brute-force, combinatorics, dp 1,950 1m 31s...

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

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

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

Codeforces Round 264 (Div. 2)

Codeforces Round 264 (Div. 2) Div. 2 | 5 problems | 5/5 verified | Difficulty 1100-2100 | 4m 50s # Problem Rating Tags Accepted Time ✓ A Caisa and Sugar 1200 brute-force, implementation 9,561 1m ✓ B Caisa and Pylons 1100 brute-force, implementation, math 29,962 59s ✓ C Gargari and Bishops 1900 greedy, hashing, implementation 9,179 1m 6s ✓ D Gargari and Permutations 1900 dfs-and-similar, dp, graphs 7,295 58s ✓...

CF 463C - Gargari and Bishops

CF 463C - Gargari and Bishops Rating: 1900 Tags: greedy, hashing, implementation Solve time: 1m 6s Verified: yes Solution Problem Understanding We have an $n \times n$ chessboard, and each cell has a non-negative integer representing money. The goal is to place exactly two bishops such that no cell is attacked by both bishops, and we maximize the total money collected from all cells that are attacked by at least...

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

Codeforces Round 254 (Div. 1)

Codeforces Round 254 (Div. 1) Div. 1 | 5 problems | 3/5 verified | Difficulty 1600-2700 | 15m 35s # Problem Rating Tags Accepted Time ✓ A DZY Loves Physics 1600 greedy, math 3,578 1m 32s ✓ B DZY Loves FFT 2300 probabilities 1,175 1m 51s ✓ C DZY Loves Colors 2400 data-structures 3,359 5m 19s D DZY Loves Strings 2500 binary-search, hashing, strings 862 1m 6s ✓ E DZY...

Codeforces Round 149 (Div. 2)

Codeforces Round 149 (Div. 2) Div. 2 | 5 problems | 3/5 verified | Difficulty 1100-2100 | 12m 58s # Problem Rating Tags Accepted Time ✓ A Heads or Tails 1100 brute-force, implementation 6,792 3m 26s ✓ B Big Segment 1100 implementation, sortings 17,356 1m 12s ✓ C King's Path 1800 dfs-and-similar, graphs, hashing 10,918 3m 11s D Dispute 2100 dfs-and-similar, graphs, greedy 2,032 1m 37s E XOR on Segment...

VK Cup 2012 Finals (unofficial online-version)

VK Cup 2012 Finals (unofficial online-version) Special | 5 problems | 1/5 verified | Difficulty 1500-3000 | 9m 48s # Problem Rating Tags Accepted Time ✓ A Privatization 3000 flows, graphs 228 2m 20s B Polycarpus is Looking for Good Substrings 2300 bitmasks, hashing, implementation 368 1m 54s ✓ C Cowboys 2100 combinatorics, dp, math 486 1m 28s D Cutting a Fence 2500 binary-search, data-structures, dsu 614 1m 8s E...

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

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

CF 425D - Sereja and Squares

CF 425D - Sereja and Squares Rating: 2300 Tags: binary search, data structures, hashing Solve time: 35s Verified: yes Solution Problem Understanding We are given a set of $n$ points on a 2D plane, each with integer coordinates, and all points are distinct. The task is to count how many axis-aligned squares exist whose four corners are all points from this set. An axis-aligned square is one where each side...

CF 212B - Polycarpus is Looking for Good Substrings

CF 212B - Polycarpus is Looking for Good Substrings Rating: 2300 Tags: bitmasks, hashing, implementation Solve time: 1m 54s Verified: yes Solution Problem Understanding We are given one long lowercase string s . For every query, we are also given a set of characters C . Among all substrings of s , we only care about those whose set of distinct characters is exactly C . From those substrings, we...

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

CF 242C - King's Path

CF 242C - King's Path Rating: 1800 Tags: dfs and similar, graphs, hashing, shortest paths Solve time: 3m 11s Verified: no Solution Problem Understanding We are given a huge implicit grid, up to $10^9 \times 10^9$, but only a small subset of cells are usable. Each usable region is given as a horizontal segment: a row number and a contiguous interval of columns. Taken together, these segments define a sparse...

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

Codeforces Beta Round 94 (Div. 1 Only)

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

Codeforces Beta Round 90

Codeforces Beta Round 90 Beta | 5 problems | 4/5 verified | Difficulty 800-2500 | 9m 34s # Problem Rating Tags Accepted Time ✓ A Epic Game 800 implementation 29,580 1m 29s ✓ B Before Exam 1900 constructive-algorithms, implementation, sortings 1,137 2m 2s ✓ C Education Reform 2000 dp 1,044 2m 59s D String Transformation 2500 hashing, strings 625 1m 34s ✓ E Alternative Reality 2400 geometry 123 1m 30s...

Codeforces Beta Round 86 (Div. 1 Only)

Codeforces Beta Round 86 (Div. 1 Only) Div. 1 | 5 problems | 5/5 verified | Difficulty 1600-2700 | 15m 15s # Problem Rating Tags Accepted Time ✓ A Grammar Lessons 1600 implementation, strings 2,603 4m 41s ✓ B Petr# 2000 brute-force, data-structures, hashing 3,241 3m 20s ✓ C Double Happiness 2200 brute-force, math, number-theory 1,450 3m 20s ✓ D Museum 2700 math, matrices, probabilities 817 1m 55s ✓ E...

Yandex.Algorithm 2011: Qualification 2

Yandex.Algorithm 2011: Qualification 2 Special | 5 problems | 4/5 verified | Difficulty 1100-2600 | 11m 32s # Problem Rating Tags Accepted Time ✓ A Double Cola 1100 implementation, math 32,231 1m 30s ✓ B Sets 1700 constructive-algorithms, hashing, implementation 2,336 2m 17s C General Mobilization 2000 data-structures, dfs-and-similar, sortings 871 2m 42s ✓ D Two out of Three 2000 dp 2,300 2m 57s ✓ E Corridor 2600 geometry 247...

Codeforces Beta Round 71

Codeforces Beta Round 71 Beta | 5 problems | 5/5 verified | Difficulty 1200-2900 | 7m 45s # Problem Rating Tags Accepted Time ✓ A Bus Game 1200 greedy 4,556 1m 20s ✓ B Colorful Field 1400 implementation, sortings 7,989 1m 19s ✓ C Beaver 1800 data-structures, dp, greedy 2,111 1m 27s ✓ D Password 2800 bitmasks, dp, shortest-paths 1,341 2m 11s ✓ E Security System 2900 math 160 1m...

Codeforces Beta Round 50

Codeforces Beta Round 50 Beta | 5 problems | 5/5 verified | Difficulty 1300-2700 | 8m 47s # Problem Rating Tags Accepted Time ✓ A Presents 1300 implementation 2,545 1m 19s ✓ B Cutting Jigsaw Puzzle 1800 hashing, implementation 909 1m 29s ✓ C First Digit Law 2000 dp, math, probabilities 1,639 1m 10s ✓ D Writing a Song 2100 brute-force, dp, strings 709 1m 3s ✓ E Vacuum \u0421leaner...

Codeforces Beta Round 19

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

Codeforces Beta Round 7

Codeforces Beta Round 7 Beta | 5 problems | 5/5 verified | Difficulty 1100-2600 | 5m 10s # Problem Rating Tags Accepted Time ✓ A Kalevitch and Chess 1100 brute-force, constructive-algorithms 8,023 1m 5s ✓ B Memory Manager 1600 implementation 2,956 1m 1s ✓ C Line 1800 math, number-theory 5,477 52s ✓ D Palindrome Degree 2200 hashing, strings 4,470 1m 5s ✓ E Defining Macros 2600 dp, expression-parsing, implementation 777...

Codeforces Beta Round 4 (Div. 2 Only)

Codeforces Beta Round 4 (Div. 2 Only) Div. 2 | 4 problems | 4/4 verified | Difficulty 800-1700 | 4m 57s # Problem Rating Tags Accepted Time ✓ A Watermelon 800 brute-force, math 687,420 46s ✓ B Before an Exam 1200 constructive-algorithms, greedy 29,461 1m 12s ✓ C Registration System 1300 data-structures, hashing, implementation 108,036 1m 42s ✓ D Mysterious Present 1700 dp, sortings 12,101 1m 17s ✓

Codeforces Beta Round 2

Codeforces Beta Round 2 Beta | 3 problems | 2/3 verified | Difficulty 1500-2600 | 5m 52s # Problem Rating Tags Accepted Time ✓ A Winner 1500 hashing, implementation 31,213 1m 9s ✓ B The least round way 2000 dp, math 12,942 3m 7s C Commentator problem 2600 geometry 2,023 1m 36s ✓

CF 4C - Registration System

CF 4C - Registration System Rating: 1300 Tags: data structures, hashing, implementation Solve time: 1m 42s Verified: yes Solution Problem Understanding We are building a username registration system. Every incoming request contains a desired username. If that username has never appeared before, registration succeeds immediately and we print OK . If the username is already taken, we must generate a new one by attaching the smallest positive integer suffix that...

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

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

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

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

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

CF 82B - Sets

CF 82B - Sets Rating: 1700 Tags: constructive algorithms, hashing, implementation Solve time: 2m 17s Verified: no Solution Problem Understanding We are given all pairwise unions of some hidden disjoint sets. The original sets themselves are not shown. Suppose the hidden sets are $S_1, S_2, \dots, S_n$. For every pair $i \neq j$, we are given the set $S_i \cup S_j$. These unions are shuffled, so we do not know...

CF 2A - Winner

Problem Understanding The game records a sequence of rounds. In each round, one player either gains or loses some number of points. At the end, the player with the highest total score should win. The tricky part appears when several players finish with the same highest score. In that situation, the winner is not chosen arbitrarily. Among all players whose final score equals the maximum value, we pick the one...

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

CF 54B - Cutting Jigsaw Puzzle

CF 54B - Cutting Jigsaw Puzzle Rating: 1800 Tags: hashing, implementation Solve time: 1m 29s Verified: yes Solution Problem Understanding We are given a rectangular picture represented as an A × B grid of letters. The task is to determine how many ways we can cut this picture into smaller rectangular pieces such that each piece is unique up to rotations, and to identify the smallest possible piece size among...

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

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

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

CF 65D - Harry Potter and the Sorting Hat

CF 65D - Harry Potter and the Sorting Hat Rating: 2200 Tags: brute force, dfs and similar, hashing Solve time: 1m 58s Verified: yes Solution Problem Understanding We process students one by one. Each student either has a fixed house, represented by one of the letters G , H , R , S , or has ambiguous ancestry, represented by ? . A fixed student always goes into that house....

CF 28D - Don't fear, DravDe is kind

CF 28D - Don't fear, DravDe is kind Rating: 2400 Tags: binary search, data structures, dp, hashing Solve time: 1m 40s Verified: yes Solution Problem Understanding We have a fixed sequence of trucks. For every truck we know its value, the number of people inside it, and two fear constraints. If a truck survives and enters the tunnel, then among all surviving trucks: the total number of people before it...

LeetCode 711: Number of Distinct Islands II

Problem Restatement We are given a binary grid. Value Meaning 1 Land 0 Water An island is a group of connected land cells using 4-directional movement: up down left right We need to count how many distinct island shapes exist. Two islands are considered the same if one can be transformed into the other using: Allowed Transformation Rotation Reflection Translation This means two islands are identical if we can rotate...

LeetCode 448: Find All Numbers Disappeared in an Array

Problem Restatement We are given an array nums of length n . Every value in the array is in the range: 1 <= nums[i] <= n We need to return all numbers from 1 to n that do not appear in nums . The official problem asks for all integers in [1, n] that are missing from the array. The constraints are n == nums.length , 1 <= n <=...

LeetCode 442: Find All Duplicates in an Array

Problem Restatement We are given an integer array nums . The array has length n . Every number satisfies: 1 <= nums[i] <= n Each integer appears either: Frequency Meaning Once Normal value Twice Duplicate value We need to return all numbers that appear exactly twice. The solution must use: Requirement Constraint Time O(n) Extra space O(1) excluding the answer list The official problem guarantees every integer appears once or...

3. Hashing and Table Search

3. Hashing and table search, 25 index slug name 56 hash-table-lookup Hash Table Lookup 57 separate-chaining-search Separate Chaining Search 58 linear-probing-search Linear Probing Search 59 quadratic-probing-search Quadratic Probing Search 60 double-hashing-search Double Hashing Search 61 cuckoo-hashing-lookup Cuckoo Hashing Lookup 62 hopscotch-hashing-lookup Hopscotch Hashing Lookup 63 robin-hood-hashing-lookup Robin Hood Hashing Lookup 64 perfect-hashing-lookup Perfect Hashing Lookup 65 minimal-perfect-hashing-lookup Minimal Perfect Hashing Lookup 66 bloom-filter-membership Bloom Filter Membership 67 counting-bloom-filter-membership Counting Bloom...

5.21 Consistent Performance Guarantees

5.21 Consistent Performance Guarantees Problem A hash-based structure may perform well on average but still fail in production due to unpredictable worst-case behavior. You need predictable performance bounds, not just good expected performance. This matters in systems where latency spikes are unacceptable: real-time services, interactive applications, databases, and network-facing APIs. Solution Control performance through a combination of design constraints: - bounded load factor - controlled collision handling - stable hash...

5.18 Attack Resistance

5.18 Attack Resistance Problem Hash tables usually provide expected constant time operations. That expectation depends on the assumption that keys are well distributed across buckets. When inputs are controlled by an adversary, this assumption may fail. You need a hash table strategy that remains safe when attackers can choose keys deliberately. Solution Use a keyed hash function or a collision-resistant table strategy for untrusted inputs. A keyed hash includes a...

5.23 Cache-Aware Hashing

5.23 Cache-Aware Hashing Problem Hash tables often fail to achieve their theoretical performance because memory access patterns dominate runtime. Even with good hashing and controlled load factor, repeated cache misses can make operations significantly slower than expected. You need a design that aligns hash table behavior with CPU cache structure. Solution Structure the hash table to maximize spatial locality and reduce pointer chasing. Core strategies: - use contiguous storage for...

5.24 Real-World Hash Table Design

5.24 Real-World Hash Table Design Problem You need to choose and implement a hash table that performs reliably under real workloads: mixed key types, uneven access patterns, deletions, resizing, and possible adversarial input. Pure theoretical designs often fail in production due to constant factors, memory layout, and edge cases. Solution Design the hash table as a layered system with explicit responsibilities: - hashing layer - indexing layer - collision handling...

5.15 Hash Joins

5.15 Hash Joins Problem You need to join two collections by matching keys. A nested loop join compares every item from the first collection with every item from the second collection. This is simple, but it costs O(nm) for collections of sizes n and m . A hash join reduces this cost by indexing one side in a hash map. Solution Build a hash map from the smaller collection, then...

5.20 Testing Hash Logic

5.20 Testing Hash Logic Problem You need confidence that a hash-based structure is correct, stable, and performs well under realistic inputs. Hash table bugs are often subtle. A map may pass small examples but fail after resizing. A set may work until keys collide. A deterministic hash may appear stable until another language, platform, or encoding rule is introduced. Solution Test both logical behavior and structural stress cases. Basic behavior:...

5.13 Count-Min Sketch

5.13 Count-Min Sketch Problem You need approximate frequency counts for a large stream of keys, and an exact counting map would use too much memory. A counting map stores one entry per distinct key. This is exact, but memory grows with the number of distinct keys. In a large log stream, network trace, search query stream, or telemetry pipeline, the number of distinct keys may be too large to store...

5.14 Consistent Hashing

5.14 Consistent Hashing Problem You need to distribute keys across a changing set of nodes so that when nodes are added or removed, only a small fraction of keys move. A standard hash table uses: index = hash(key) mod n When n changes, most keys are reassigned. This is unacceptable in systems like caches, distributed storage, or sharded services where moving data is expensive. Solution Map both keys and nodes...

5.19 Deterministic Hashing

5.19 Deterministic Hashing Problem You need hash values that remain stable across program runs, machines, builds, or language runtimes. Many hash tables deliberately use randomized hashing for attack resistance. This is good for public-facing in-memory maps, but it is wrong when the hash value becomes part of a persistent file, cache key, distributed partition rule, or reproducible build artifact. Solution Use a fixed, documented hash function with fixed parameters. deterministic_hash(key)...

5.25 Case Studies

5.25 Case Studies Problem You need to see how hash-based structures behave in complete systems rather than isolated operations. Real performance and correctness issues usually appear only when hashing interacts with full workflows: streaming data, graphs, caches, and distributed systems. This section consolidates patterns from previous recipes into concrete end-to-end designs. Case Study 1: Frequency Analysis Pipeline You need to compute frequencies over a large stream of events. Design Use...

5.17 Cache Behavior

5.17 Cache Behavior Problem Hash tables are expected constant time structures, but real performance often deviates from that expectation due to memory hierarchy effects. Poor cache locality can dominate runtime even when asymptotic complexity is optimal. You need to understand how hash table design interacts with CPU caches and memory access patterns. Solution Design hash-based structures to maximize spatial locality and minimize unpredictable memory access. Key principles: - Prefer contiguous...

5.22 Hybrid Hash Structures

5.22 Hybrid Hash Structures Problem Pure hash tables do not handle all workloads well. They are fast on average, but can degrade under collisions, skewed key distributions, or heavy deletion patterns. You need a design that preserves hash-table speed while adapting to pathological cases. Solution Combine multiple internal representations depending on bucket state or load conditions. A common hybrid design: bucket: if small: use array or list if medium: use...

5.16 Hash-Based Deduplication

5.16 Hash-Based Deduplication Problem You need to remove duplicates from a dataset or stream efficiently. A naive approach compares each element with all previously seen elements, which leads to quadratic time. For large inputs, this is impractical. Solution Use a hash set to track seen elements. deduplicate(items): seen = empty set output = empty list for item in items: if not contains(seen, item): insert(seen, item) append item to output return...

5.8 Counting Maps

5.8 Counting Maps Problem You need to count how many times each key appears in a dataset. A standard map stores one value per key. In counting problems, the value is a frequency. The task is to update counts efficiently while scanning input once. Solution Use a map from key to integer count. freq: Map<Key, Int> For each key, read the current count, then increment. count(items): freq = empty map...

5.9 Grouping Keys

5.9 Grouping Keys Problem You need to partition items into groups according to a derived key. A counting map records how many times each key appears. A grouping map records the actual items associated with each key. This is useful when the later algorithm needs to process each group separately. Solution Use a map from group key to list of items. groups: Map<Key, List<Item>> For each item, compute its group...

5.12 Bloom Filters

5.12 Bloom Filters Problem You need to test whether a key is in a set using very little memory, and you can tolerate occasional false positives but not false negatives. A standard hash set stores all keys explicitly. This gives exact answers but uses memory proportional to the number of keys. For large-scale or streaming data, this can be too expensive. Solution Use a Bloom filter. It is a bit...

5.7 Maps

5.7 Maps Problem You need to associate each key with a value and retrieve the value quickly by key. A set answers membership questions. A map answers lookup questions. It stores pairs of the form (key, value) and maintains the rule that each key appears at most once. Solution Implement the map as a hash table whose entries store both keys and values. Entry: key value HashMap: buckets: array of...

5.10 Composite Keys

5.10 Composite Keys Problem You need to use multiple fields together as a single key in a hash table. Examples include (user_id, timestamp) , (x, y) coordinates, (source, destination) , or (name, version) . Treating each field separately leads to incorrect grouping or lookup. Treating them together requires a consistent definition of equality and hashing. Solution Define a composite key type with equality and hashing over all relevant fields. Key:...

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

5.6 Sets

5.6 Sets Problem You need to store a collection of distinct keys and answer membership questions quickly. A set differs from a map because it stores only keys. There is no associated value. The main operations are insert , contains , and delete . Solution Implement the set as a hash table that stores keys directly. HashSet: buckets: array of bucket size: number of stored keys capacity: number of buckets...

Chapter 5. Hashing and Maps

Chapter 5. Hashing and Maps This chapter studies hashing as a practical mechanism for constant time access under realistic constraints. The focus is not on idealized O(1) claims, but on how hash tables behave under load, how collisions are handled, and how design choices affect predictability, memory locality, and adversarial robustness. A hash table implements a partial function from keys to values by mapping keys into a finite index space....

5.2 Hash Functions

5.2 Hash Functions Problem You need a function that turns a key into a hash code so that a hash table can place the key into a bucket. A hash table depends on two operations. First, it must decide whether two keys are equal. Second, it must compute a hash code for each key. These two operations must agree. Whenever two keys are equal, they must produce the same hash...

5.1 Hash Tables

5.1 Hash Tables Problem You need a data structure that supports fast insertion, lookup, and deletion by key. Arrays give fast access when the key is already a small integer index. A hash table generalizes that idea. It accepts keys such as strings, records, tuples, or large integers, converts each key into a table position, and stores the associated value there. Solution Use a hash function to convert each key...

5.5 Rehashing

5.5 Rehashing Problem A hash table must occasionally change its capacity or internal layout. When this happens, existing entries cannot remain in their current positions because bucket indexes depend on the table size and probing rules. You need a method to rebuild the table so that all operations remain correct and performance is restored. Solution Reinsert all existing entries into a new table using the current hash function and the...

5.4 Load Factor and Resizing

5.4 Load Factor and Resizing Problem As a hash table grows, collisions increase and operations slow down. If the table never expands, performance degrades toward linear time. If it expands too aggressively, memory is wasted and resizing costs dominate. You need a policy that keeps operations fast while controlling memory usage. Solution Track the load factor and resize the table when it crosses a threshold. load_factor = size / capacity...

5.3 Collision Handling

5.3 Collision Handling Problem Different keys can produce the same bucket index. A hash table must store and retrieve all such keys without losing correctness or degrading excessively in performance. Solution Use a collision resolution strategy. The two standard approaches are separate chaining and open addressing. Separate chaining Each bucket stores a small collection of entries. bucket[i] = list of (key, value) Lookup scans only the selected bucket. lookup(table, key):...

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

Rabin Karp Search

Rabin Karp Search Rabin Karp search is a string matching algorithm that uses a rolling hash to find candidate matches of a pattern in a text. It compares hash values first, then verifies equal-hash windows by direct character comparison. This separates fast candidate detection from exact verification. It is especially useful when searching for many patterns or when rolling hashes are reused in a larger text processing pipeline. Problem Given...

Robin Hood Hashing Lookup

Robin Hood Hashing Lookup Robin Hood hashing is an open addressing method that tries to reduce variance in probe lengths. During insertion, a key with a larger probe distance may displace a key with a smaller probe distance. This rule gives longer-searching keys priority and keeps lookup times more uniform. Lookup follows the same linear probe sequence as ordinary linear probing, but it can stop early when the current entry...

Linear Probing Search

Linear Probing Search Linear probing resolves collisions in an open addressing hash table by scanning forward one slot at a time. All keys are stored directly inside the table, and probing follows a contiguous sequence. You search by computing the hash index and walking forward until you either find the key or reach an empty slot. Problem Given a hash table using linear probing and a key $k$, return the...

Separate Chaining Search

Separate Chaining Search Separate chaining handles collisions in a hash table by storing all elements that hash to the same index in a bucket. Each bucket is typically a linked list, though dynamic arrays or trees are also used. You search by hashing the key and scanning only the corresponding bucket. Problem Given a hash table with chaining and a key $k$, find the associated value if it exists. Model...

Hash Table Lookup

Hash Table Lookup Hash table lookup retrieves a value associated with a key by computing a hash and using it to index into a table. It provides constant expected time for search under standard assumptions. You use it when fast membership or key value access is required, especially for repeated queries over large datasets. Problem Given a hash table storing key value pairs and a query key $k$, return the...

Hash Index Probe

Hash Index Probe Hash index probe retrieves records from a table using a hash index. The index maps key values to locations of rows, enabling fast equality lookups. You use it in databases and storage systems when queries involve exact key matches. Problem Given a table with a hash index on attribute $k$, and a query value $x$, retrieve all rows such that: $$ row.k = x $$ Model A...

Binary Fuse Filter Lookup

Binary Fuse Filter Lookup A binary fuse filter is a refined XOR-based approximate membership structure. It improves over standard XOR filters in construction success rate, speed, and memory layout. It remains static after construction and supports fast constant-time lookup with low false positive rates. You use it when you want a very compact, cache-friendly alternative to Bloom or XOR filters for static datasets. Problem Given a fixed set $S$ and...

Bloom Filter Membership

Bloom Filter Membership A Bloom filter is a compact probabilistic structure for membership testing. It can answer that a key is definitely absent or possibly present. It may report false positives, but it does not report false negatives when implemented correctly. You use it when memory is limited and exact storage of all keys is too expensive. Problem Given a set $S$ and a query key $k$, determine whether $k$...

Consistent Hashing Lookup

Consistent Hashing Lookup Consistent hashing maps keys to nodes in a dynamic set. Both keys and nodes are placed on a hash ring. A key is assigned to the first node encountered when moving clockwise from the key position. You use it in distributed systems where nodes are added or removed and minimal key movement is required. Problem Given a set of nodes and a key $k$, determine which node...

MinHash Similarity Search

MinHash Similarity Search MinHash similarity search estimates the similarity between sets and retrieves candidates that are likely similar to a query. It is widely used for near duplicate detection when items are represented as sets, such as document shingles. The key idea is that MinHash signatures preserve Jaccard similarity in expectation. Problem Given a collection of sets and a query set $Q$, find sets $S$ such that: $$ \operatorname{Jaccard}(Q, S)...

Hash Join Lookup

Hash Join Lookup Hash join lookup is the probe phase of a hash join. One relation is first scanned and stored in a hash table by join key. The other relation is then scanned, and each row probes the hash table to find matching rows. You use it when joining two datasets and the join key can be hashed efficiently. Problem Given two relations $R$ and $S$, find all pairs...

Rolling Hash Search

Rolling Hash Search Rolling hash search computes a hash over a fixed size window and updates it efficiently as the window moves. It allows substring search in linear time with low constant factors. You use it when scanning large text for patterns or when building string matching algorithms such as Rabin Karp. Problem Given a text $T$ of length $n$ and a pattern $P$ of length $m$, find all indices...

Double Hashing Search

Double Hashing Search Double hashing reduces clustering by using a second hash function to determine the step size between probes. Each key generates its own probe sequence, which distributes entries more uniformly than linear or quadratic probing. You search by following the same probe sequence defined by both hash functions. Problem Given a hash table using double hashing and a key $k$, return the associated value if it exists. Model...

XOR Filter Lookup

XOR Filter Lookup An XOR filter is a compact static approximate membership structure. It stores short fingerprints in an array. A query key is tested by hashing it to three array positions, XORing the three stored fingerprints, and comparing the result with the key fingerprint. Like Bloom filters, XOR filters may return false positives. They do not return false negatives after a successful construction. They are read only after construction,...

Cuckoo Filter Lookup

Cuckoo Filter Lookup A cuckoo filter is a compact approximate membership structure based on cuckoo hashing. Instead of storing full keys, it stores short fingerprints in buckets. Lookup checks a small fixed number of candidate buckets, so queries are fast and predictable. Like a Bloom filter, a cuckoo filter may return false positives. Unlike a standard Bloom filter, it supports deletion when fingerprints are stored with enough care. Problem Given...

Counting Bloom Filter Membership

Counting Bloom Filter Membership A counting Bloom filter extends the Bloom filter by replacing each bit with a small counter. This allows both insertion and deletion. Membership queries follow the same logic as a standard Bloom filter, but check that all counters are positive. You use it when you need approximate membership with support for removal. Problem Given a multiset-like structure supporting insert and delete, and a query key $k$,...

Rendezvous Hashing Lookup

Rendezvous Hashing Lookup Rendezvous hashing, also called highest random weight hashing, maps a key to the node with the highest score for that key. Each candidate node is scored together with the key, and the node with the maximum score is selected. You use it in distributed systems when keys must be assigned to changing sets of nodes with minimal movement and no shared hash ring. Problem Given a set...

Minimal Perfect Hashing Lookup

Minimal Perfect Hashing Lookup Minimal perfect hashing is a static dictionary technique. It builds a hash function for a fixed set of $n$ keys so that every stored key maps to a unique integer in the range $0$ to $n - 1$. Unlike ordinary perfect hashing, a minimal perfect hash uses exactly one table slot per key. Lookup computes the hash position, checks the stored key, and returns the associated...

Perfect Hashing Lookup

Perfect Hashing Lookup Perfect hashing uses a hash function that maps a fixed set of keys to distinct table positions. Because no two stored keys collide, lookup checks one computed position and compares the stored key with the query key. This method is useful for static dictionaries. The table is built once, then used for many fast lookups. Problem Given a static set of keys $S$ and a query key...

Cuckoo Hashing Lookup

Cuckoo Hashing Lookup Cuckoo hashing stores each key in one of several possible table positions. In the common two hash version, a key can live at either $h_1(k)$ or $h_2(k)$. Lookup is therefore simple: compute both positions and check them. The search operation is fast because it does not scan a bucket or probe a long sequence. The cost is moved mostly to insertion, where an existing key may be...

Locality Sensitive Hashing Search

Locality Sensitive Hashing Search Locality sensitive hashing, often abbreviated as LSH, is a search technique for approximate nearest neighbor queries. It uses hash functions that are designed so that similar objects are more likely to collide than dissimilar objects. You use it when exact nearest neighbor search is too expensive, especially in high dimensional spaces. Problem Given a dataset $D$ and a query object $q$, find items in $D$ that...

Quotient Filter Lookup

Quotient Filter Lookup A quotient filter is a compact approximate membership structure. Like a Bloom filter, it can return false positives but not false negatives when maintained correctly. Unlike a standard Bloom filter, it stores short hash remainders in a table and supports locality friendly lookup. You use it when approximate membership is required and the structure must support practical deletion, merging, or cache efficient scans. Problem Given a quotient...

Hopscotch Hashing Lookup

Hopscotch Hashing Lookup Hopscotch hashing maintains the invariant that each key resides within a small fixed distance from its home bucket. This distance is called the neighborhood size. Lookup only scans this bounded region, so it remains fast and cache friendly even at high load. You search by computing the home index and checking a compact neighborhood using a bitmap or mask that records which nearby slots are occupied by...

SimHash Near Duplicate Search

SimHash Near Duplicate Search SimHash near duplicate search uses compact bit fingerprints to detect items with similar weighted features. It is commonly used for near duplicate documents, pages, records, and text fragments. The main idea is to convert a high dimensional feature vector into a fixed width fingerprint, usually 64 bits. Similar inputs tend to produce fingerprints with small Hamming distance. Problem Given a collection of items and a query...

Quadratic Probing Search

Quadratic Probing Search Quadratic probing improves upon linear probing by spreading out probe sequences. Instead of stepping one slot at a time, it uses a quadratic function of the probe number. This reduces primary clustering and improves distribution under moderate load. You search by following the same quadratic probe sequence used during insertion. Problem Given a hash table using quadratic probing and a key $k$, return the associated value if...