hashing | brain

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

CF 2225F - String Cutting

CF 2225F - String Cutting Rating: - Tags: binary search, brute force, greedy, hashing, string suffix structures, strings Solve time: 2m 54s Verified: no Solution Problem Understanding A string $s$ must be split into several contiguous pieces. Each piece has length at least $l$, and the total number of pieces is at least $k$. After cutting, all pieces are sorted lexicographically, and the piece in position $k$ of this sorted...

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

CF 486B - OR in Matrix

CF 486B - OR in Matrix Rating: 1300 Tags: greedy, hashing, implementation Solve time: 5m 23s Verified: no Solution

Practice › Codeforces Solutions ›

Codeforces Round 934 (Div. 1)

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

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

CF 1943B - Non-Palindromic Substring

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

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

CF 486E - LIS of Sequence

CF 486E - LIS of Sequence Rating: 2200 Tags: data structures, dp, greedy, hashing, math Solve time: 5m 17s Verified: no Solution

Practice › Codeforces Solutions ›

Codeforces Round 277 (Div. 2)

Codeforces Round 277 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 0/4 | Rating range: 800-2200 | Time: 26m 47s Problem Name Rating Tags Solve Time Verified A Calculating Function 800 implementation, math 10m 49s ✗ B OR in Matrix 1300 greedy, hashing, implementation 5m 23s ✗ D Valid Sets 2100 dfs-and-similar, dp, math 5m 18s ✗ E LIS of Sequence 2200 data-structures, dp, greedy 5m 17s ✗

Practice › Codeforces Solutions › Codeforces Global Round 25 ›

CF 1951E - No Palindromes

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

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

CF 1950G - Shuffling Songs

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

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

CF 452F - Permutation

CF 452F - Permutation Rating: 2700 Tags: data structures, divide and conquer, hashing Solve time: 2m 37s Verified: no Solution Problem Understanding The permutation contains every value from 1 to n exactly once. We need to determine whether there exist two distinct values a and b such that their arithmetic mean $$\frac{a+b}{2}$$ appears somewhere between them in the permutation order. Since the mean must itself be an integer in the...

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

CF 467D - Fedor and Essay

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

Practice › Codeforces Solutions ›

Codeforces Round 264 (Div. 2)

Codeforces Round 264 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 5/5 | Rating range: 1100-2100 | Time: 4m 50s Problem Name Rating Tags Solve Time Verified A Caisa and Sugar 1200 brute-force, implementation 1m ✓ B Caisa and Pylons 1100 brute-force, implementation, math 59s ✓ C Gargari and Bishops 1900 greedy, hashing, implementation 1m 6s ✓ D Gargari and Permutations 1900 dfs-and-similar, dp, graphs 58s ✓ E...

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

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

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

CF 407D - Largest Submatrix 3

CF 407D - Largest Submatrix 3 Rating: 2700 Tags: dp, hashing Solve time: 4m 21s Verified: no Solution Problem Understanding We are given a 2D integer matrix with n rows and m columns. The task is to find a rectangular submatrix where all elements are distinct and whose area (number of elements) is maximized. A submatrix is defined by choosing a top-left corner (i1, j1) and a bottom-right corner (i2,...

Practice › Codeforces Solutions ›

VK Cup 2012 Finals (unofficial online-version)

VK Cup 2012 Finals (unofficial online-version) Type: Special | Problems: 5 | Verified: 1/5 | Rating range: 1500-3000 | Time: 9m 48s Problem Name Rating Tags Solve Time Verified A Privatization 3000 flows, graphs 2m 20s ✗ B Polycarpus is Looking for Good Substrings 2300 bitmasks, hashing, implementation 1m 54s ✓ C Cowboys 2100 combinatorics, dp, math 1m 28s ✗ D Cutting a Fence 2500 binary-search, data-structures, dsu 1m 8s...

Practice › Codeforces Solutions › VK Cup 2012 Finals (unofficial online-version) ›

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

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

CF 213E - Two Permutations

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

Practice › Codeforces Solutions › ABBYY Cup 3.0 ›

CF 316G1 - Good Substrings

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

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

CF 444D - DZY Loves Strings

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

Practice › Codeforces Solutions ›

Croc Champ 2013 - Qualification Round

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

Practice › Codeforces Solutions ›

Codeforces Round 149 (Div. 2)

Codeforces Round 149 (Div. 2) Type: Div. 2 | Problems: 5 | Verified: 3/5 | Rating range: 1100-2100 | Time: 12m 58s Problem Name Rating Tags Solve Time Verified A Heads or Tails 1100 brute-force, implementation 3m 26s ✓ B Big Segment 1100 implementation, sortings 1m 12s ✓ C King's Path 1800 dfs-and-similar, graphs, hashing 3m 11s ✗ D Dispute 2100 dfs-and-similar, graphs, greedy 1m 37s ✗ E XOR on...

Practice › Codeforces Solutions ›

Codeforces Round 254 (Div. 1)

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

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

CF 245H - Queries for Number of Palindromes

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

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

CF 154C - Double Profiles

CF 154C - Double Profiles Rating: 2300 Tags: graphs, hashing, sortings Solve time: 1m 37s Verified: yes Solution Problem Understanding We are working with an undirected graph where each vertex represents a social network profile. Two profiles are considered "doubles" if every other profile sees them identically. For any third vertex k , either both i and j are connected to k , or neither is connected to k ....

Practice › Codeforces Solutions ›

Codeforces Round 109 (Div. 1)

Codeforces Round 109 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 4/4 | Rating range: 1600-2400 | Time: 6m 30s Problem Name Rating Tags Solve Time Verified A Hometask 1600 greedy 1m 15s ✓ B Colliders 1600 math, number-theory 2m 4s ✓ C Double Profiles 2300 graphs, hashing, sortings 1m 37s ✓ D Flatland Fencing 2400 games, math 1m 34s ✓

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

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

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

CF 291E - Tree-String Problem

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

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

CF 182D - Common Divisors

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

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

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

Practice › Codeforces Solutions ›

Codeforces Round 239 (Div. 1)

Codeforces Round 239 (Div. 1) Type: Div. 1 | Problems: 4 | Verified: 0/4 | Rating range: 1600-3100 | Time: 10m 34s Problem Name Rating Tags Solve Time Verified B Long Path 1600 dp, implementation 1m 3s ✗ C Curious Array 2500 brute-force, combinatorics, implementation 34s ✗ D Largest Submatrix 3 2700 dp, hashing 4m 21s ✗ E k-d-sequence 3100 data-structures 4m 36s ✗

Practice › Codeforces Solutions ›

Codeforces Round 243 (Div. 1)

Codeforces Round 243 (Div. 1) Type: Div. 1 | Problems: 3 | Verified: 1/3 | Rating range: 2300-2500 | Time: 10m 7s Problem Name Rating Tags Solve Time Verified C Sereja and Two Sequences 2300 data-structures, dp 6m 43s ✗ D Sereja and Squares 2300 binary-search, data-structures, hashing 35s ✓ E Sereja and Sets 2500 dp 2m 49s ✗

Practice › Codeforces Solutions › Codeforces Beta Round 60 ›

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

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

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

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

CF 39J - Spelling Check

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 19

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

Practice › Codeforces Solutions ›

Yandex.Algorithm 2011: Qualification 2

Yandex.Algorithm 2011: Qualification 2 Type: Special | Problems: 5 | Verified: 4/5 | Rating range: 1100-2600 | Time: 11m 32s Problem Name Rating Tags Solve Time Verified A Double Cola 1100 implementation, math 1m 30s ✓ B Sets 1700 constructive-algorithms, hashing, implementation 2m 17s ✗ C General Mobilization 2000 data-structures, dfs-and-similar, sortings 2m 42s ✓ D Two out of Three 2000 dp 2m 57s ✓ E Corridor 2600 geometry 2m...

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

CF 126B - Password

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

Practice › Codeforces Solutions › Codeforces Beta Round 50 ›

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

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

CF 25E - Test

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

Practice › Codeforces Solutions › Codeforces Beta Round 90 ›

CF 119D - String Transformation

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

Practice › Codeforces Solutions › Codeforces Beta Round 7 ›

CF 7D - Palindrome Degree

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

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

CF 30E - Tricky and Clever Password

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

Practice › Codeforces Solutions › Codeforces Beta Round 71 ›

CF 79C - Beaver

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 94 (Div. 1 Only)

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

Practice › Codeforces Solutions › Codeforces Beta Round 2 ›

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

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

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 50

Codeforces Beta Round 50 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1300-2700 | Time: 8m 47s Problem Name Rating Tags Solve Time Verified A Presents 1300 implementation 1m 19s ✓ B Cutting Jigsaw Puzzle 1800 hashing, implementation 1m 29s ✓ C First Digit Law 2000 dp, math, probabilities 1m 10s ✓ D Writing a Song 2100 brute-force, dp, strings 1m 3s ✓ E Vacuum \u0421leaner 2700...

Practice › Codeforces Solutions ›

Codeforces Beta Round 71

Codeforces Beta Round 71 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1200-2900 | Time: 7m 45s Problem Name Rating Tags Solve Time Verified A Bus Game 1200 greedy 1m 20s ✓ B Colorful Field 1400 implementation, sortings 1m 19s ✓ C Beaver 1800 data-structures, dp, greedy 1m 27s ✓ D Password 2800 bitmasks, dp, shortest-paths 2m 11s ✓ E Security System 2900 math 1m 28s ✓

Practice › Codeforces Solutions ›

Codeforces Beta Round 93 (Div. 1 Only)

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

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

CF 113B - Petr#

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 2

Codeforces Beta Round 2 Type: Beta | Problems: 3 | Verified: 2/3 | Rating range: 1500-2600 | Time: 5m 52s Problem Name Rating Tags Solve Time Verified A Winner 1500 hashing, implementation 1m 9s ✓ B The least round way 2000 dp, math 3m 7s ✗ C Commentator problem 2600 geometry 1m 36s ✓

Practice › Codeforces Solutions ›

Codeforces Beta Round 7

Codeforces Beta Round 7 Type: Beta | Problems: 5 | Verified: 5/5 | Rating range: 1100-2600 | Time: 5m 10s Problem Name Rating Tags Solve Time Verified A Kalevitch and Chess 1100 brute-force, constructive-algorithms 1m 5s ✓ B Memory Manager 1600 implementation 1m 1s ✓ C Line 1800 math, number-theory 52s ✓ D Palindrome Degree 2200 hashing, strings 1m 5s ✓ E Defining Macros 2600 dp, expression-parsing, implementation 1m 7s...

Practice › Codeforces Solutions ›

Codeforces Beta Round 86 (Div. 1 Only)

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 90

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

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

CF 128B - String

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

Practice › Codeforces Solutions ›

Codeforces Beta Round 4 (Div. 2 Only)

Codeforces Beta Round 4 (Div. 2 Only) Type: Div. 2 | Problems: 4 | Verified: 4/4 | Rating range: 800-1700 | Time: 4m 57s Problem Name Rating Tags Solve Time Verified A Watermelon 800 brute-force, math 46s ✓ B Before an Exam 1200 constructive-algorithms, greedy 1m 12s ✓ C Registration System 1300 data-structures, hashing, implementation 1m 42s ✓ D Mysterious Present 1700 dp, sortings 1m 17s ✓

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

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

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

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

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

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

Practice › LeetCode › LeetCode (archived) › LeetCode 04xx ›

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

Wiki › Algorithms › 01. Searching and Sorting ›

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.11 Rolling Hashes

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Programming › Algorithm Cookbook ›

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

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

2.17 Rolling Hashes

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

Wiki › Algorithms › 01. Searching and Sorting › 3. Hashing and Table Search ›

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

#hashing

CF 2225F - String Cutting

CF 486B - OR in Matrix

Codeforces Round 934 (Div. 1)

CF 1943B - Non-Palindromic Substring

CF 486E - LIS of Sequence

Codeforces Round 277 (Div. 2)

CF 1951E - No Palindromes

CF 1950G - Shuffling Songs

CF 452F - Permutation

CF 467D - Fedor and Essay

Codeforces Round 264 (Div. 2)

CF 463C - Gargari and Bishops

CF 407D - Largest Submatrix 3

VK Cup 2012 Finals (unofficial online-version)

CF 212B - Polycarpus is Looking for Good Substrings

CF 213E - Two Permutations

CF 316G1 - Good Substrings

CF 444D - DZY Loves Strings

Croc Champ 2013 - Qualification Round

Codeforces Round 149 (Div. 2)

Codeforces Round 254 (Div. 1)

CF 245H - Queries for Number of Palindromes

CF 154C - Double Profiles

Codeforces Round 109 (Div. 1)

CF 242C - King's Path

CF 291E - Tree-String Problem

CF 182D - Common Divisors

CF 425D - Sereja and Squares

Codeforces Round 239 (Div. 1)

Codeforces Round 243 (Div. 1)

CF 65D - Harry Potter and the Sorting Hat

CF 82B - Sets

CF 39J - Spelling Check

Codeforces Beta Round 19

Yandex.Algorithm 2011: Qualification 2

CF 126B - Password

CF 54B - Cutting Jigsaw Puzzle

CF 25E - Test

CF 119D - String Transformation

CF 7D - Palindrome Degree

CF 30E - Tricky and Clever Password

CF 79C - Beaver

Codeforces Beta Round 94 (Div. 1 Only)

CF 2A - Winner

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

Codeforces Beta Round 50

Codeforces Beta Round 71

Codeforces Beta Round 93 (Div. 1 Only)

CF 113B - Petr#

Codeforces Beta Round 2

Codeforces Beta Round 7

Codeforces Beta Round 86 (Div. 1 Only)

Codeforces Beta Round 90

CF 128B - String

Codeforces Beta Round 4 (Div. 2 Only)

CF 4C - Registration System

LeetCode 711: Number of Distinct Islands II

LeetCode 448: Find All Numbers Disappeared in an Array

LeetCode 442: Find All Duplicates in an Array

3. Hashing and Table Search

5.23 Cache-Aware Hashing

5.17 Cache Behavior

5.25 Case Studies

5.24 Real-World Hash Table Design

5.13 Count-Min Sketch

5.14 Consistent Hashing

5.21 Consistent Performance Guarantees

5.18 Attack Resistance

5.16 Hash-Based Deduplication

5.20 Testing Hash Logic

5.22 Hybrid Hash Structures

5.19 Deterministic Hashing

5.15 Hash Joins

5.9 Grouping Keys

5.10 Composite Keys

5.6 Sets

5.11 Rolling Hashes

5.8 Counting Maps

5.7 Maps