cho.sh

Problems

Pick a problem and write your solution in the built-in editor. The judge runs it against real test cases while you watch, and the wider archive is open to read whenever you like.

Total results457 problems
TitleLevelTopicsSolvedTime limitMemory limitJudge
Transforming CometsGiven two cyclic sequences of integer points, decide whether one is a rotation, uniform positive scaling, and translation of the other, and report the matching cyclic offset.Hard8String matchingGeometry+2No attempts yet5s512 MBJudgeable
Ransom NoteGiven a target note and a newspaper text, find the minimum number of contiguous clips (letters and spaces only, case-insensitive, reusable) needed to paste the note.Hard8Dynamic programmingString+2No attempts yet1s128 MBJudgeable
Word CountingGiven a rooted tree whose edges carry letter strings, count distinct occurrences of a query word along all paths from the root to the leaves, identifying each occurrence by its start and end position.Hard8String matchingTrie+2No attempts yet1s128 MBJudgeable
Similar PolygonsDecide whether two polygons are similar, and if so print the square of the similarity factor as a reduced fraction and the matching vertex index in the second polygon.Hard8GeometryString matching+2No attempts yet1s1024 MBJudgeable
Similar PolygonsDecide whether two polygons are similar under rotation, reflection, translation, and scaling, then output the exact squared similarity ratio and the smallest matching vertex index.Hard8GeometryString matching+2No attempts yet1s1024 MBJudgeable
Automatic TradingGiven a string and pairs of positions, for each query find the length of the longest common prefix of the two suffixes starting at those positions.Hard8StringString matching+2No attempts yet5s128 MBJudgeable
Address MatchingMatch each student address to a distinct teacher address with minimum total weighted edit distance, and among optimal matchings output the lexicographically smallest index sequence.Hard8Dynamic programmingGreedy+2No attempts yet3s1024 MBJudgeable
Word EncodingGiven up to 1000 forbidden substrings of length 1 to 3, rank valid words by length then alphabetically; answer queries converting a word to its index and an index to its word.Hard8Dynamic programmingString matching+2No attempts yet1s128 MBJudgeable
Morphing is funGiven color mutation rules, decide whether every fixed-height cell eventually stops changing color over the nights.Hard8GraphDFS+2No attempts yet1s512 MBJudgeable
NecklacesDecide whether two run-length compressed string descriptions encode the same circular necklace up to rotation.Hard8StringString matching+2No attempts yet1s128 MBJudgeable
BeadsSplit the bead string into blocks of size k (leftover dropped) and find the k that maximizes the count of distinct blocks, where a block and its reversal are the same.Hard8StringHash map+2No attempts yet1s128 MBJudgeable
AntisymmetryCount how many contiguous substrings of a binary string are antisymmetric, meaning each character differs from its mirror-position partner.Hard8StringHash map+2No attempts yet3s512 MBJudgeable
A Horrible PoemGiven a string and substring queries, find the length of the shortest full period of each substring, where a full period divides the substring into equal repeats.Hard8StringNumber theory+2No attempts yet8s128 MBJudgeable
PrefixuffixGiven a string t, find the maximum length L, at most n/2, such that the length-L prefix and the length-L suffix of t are cyclic rotations of each other.Hard8StringString matching+2No attempts yet3s512 MBJudgeable
The Shortest PeriodDelete exactly one letter from a string to minimize the length of the shortest period of the resulting word.Hard8StringString matching+2No attempts yet5s128 MBJudgeable
TurnsFor each starting position, find how many turns must be observed before the position on the map becomes uniquely determined.Hard8StringString matching+2No attempts yet1s128 MBJudgeable
Almost ConjugatesDecide whether two length-n words are almost conjugates and, if so, list every rotation of the first that differs from the second in exactly one position.Hard8StringString matching+2No attempts yet1s128 MBJudgeable
Cyclic NumbersFind the smallest B >= n that is a multiple m*A (1<=m<=k) of some k-digit number A whose multiples 1..k are all cyclic rotations.Hard8String matchingMath+2No attempts yet1s128 MBJudgeable
Folding the MapDecide whether an n by m map with convex or concave creases folds to one square.Hard8SimulationDivide and conquer+1No attempts yet1s128 MBJudgeable
The Fibonacci GameDetermine whether the first player wins a game that erases Fibonacci words only from the right end of a given a/b string.Hard8String matchingDynamic programming+2No attempts yet1s128 MBJudgeable
MutationsAnswer many queries whether a fragment of the second array matches a fragment of the first after changing all copies of one value.Hard8String matchingHash map+1No attempts yet1s128 MBJudgeable
TrainSum over all n! orders of the wagon strings the number of occurrences of their concatenation in t.Hard8Dynamic programmingString matching+1No attempts yet1s128 MBJudgeable
DrzewaFor each node of a labeled rooted tree, find the leaf below it whose downward label string is lexicographically largest, breaking ties by smaller leaf number.Hard8TreeGreedy+2No attempts yet1s128 MBJudgeable
Text AlgorithmsMove a pawn from the bottom-right to the top-left of a grid where left and up steps cost 1 and diagonal steps are free when row and column colors match.Hard8Dynamic programmingString matchingNo attempts yet1s128 MBJudgeable
Rotate and RewriteDecide whether two rotatable integer sequences can be reduced to a common sequence by substring rewrite rules and report the greatest such length.Hard8Dynamic programmingString matching+1No attempts yet15s128 MBJudgeable
Fragment ReassemblyArrange the given text fragments so neighbors share an exact overlap and print the joined text in lines of at most 72 characters.Hard8BacktrackingString matching+1No attempts yet1s128 MBJudgeable
Fine Dining RestaurantFor each banned serial number, count the digit comparisons the described naive left-to-right substring search performs against the concatenated string A.Hard8String matchingTrie+1No attempts yet3s128 MBJudgeable
Correcting CuriosityGiven two strings, find the length of the shortest substitution command that rewrites the first into the second.Hard8String matchingString+1No attempts yet2s256 MBJudgeable
PasswordsFind the longest prefix length and suffix length from two distinct set strings whose repetitions coincide.Hard8String matchingStringNo attempts yet7s128 MBJudgeable
Tandem RepeatsCount substrings of even length whose first half equals the second half in each DNA string.Hard8String matchingDivide and conquerNo attempts yet1s128 MBJudgeable
KkunglishFor each query range, the program reports the case-insensitive occurrence of T with the most case differences, or -1 if none, then flips the case of the range.Hard8Segment treeString matchingNo attempts yet2s128 MBJudgeable
DictionaryGiven up to 50 short words, find the fewest vertices of an edge-labeled tree whose downward paths contain every word.Hard8TrieString matching+2No attempts yet1s128 MBJudgeable
C(O|W|A*RD*|S)* CROSSWORD PuzzleFill a 2 to 4 by 2 to 4 grid with capital letters so each row and column matches its regex clue, and report the unique solution, none, or ambiguous.Hard8BacktrackingString matchingNo attempts yet10s128 MBJudgeable
CriminalsFind every house where two given color sequences appear as subsequences on the left and right with both walkers sharing one home color outside.Hard8String matchingGreedy+1No attempts yet2s256 MBJudgeable
Hari MerdekaChoose a string over priced letters with total cost within the budget to maximize the summed scores of all occurrences of the given words.Hard8Dynamic programmingString matchingNo attempts yet3s256 MBJudgeable
Out of contextFor each text line, print the longest substring the given grammar generates, breaking ties by earliest position, or NONE.Hard8Dynamic programmingString matchingNo attempts yet10s256 MBJudgeable
Virus synthesisBuild each DNA string over A, C, G, and T from empty using single-letter attachments or mirrored duplication in the fewest operations.Hard8Dynamic programmingString matchingNo attempts yet20s256 MBJudgeable
Integer in IntegerCount how many times C appears as a (possibly overlapping) substring in the decimal writings of all integers from A to B, modulo 1000000007.Hard8Dynamic programmingString matching+1No attempts yet10s128 MBJudgeable
Revenge of the ants 2Labeled ants walk both ways on a circular rail and bounce on collision; compute when each ant is back at its start with its initial direction.Hard8String matchingSorting+2No attempts yet5s256 MBJudgeable
Evolution in ParallelDecide whether every fossil sequence fits into one of two chains in which each sequence is a subsequence of the next one and of the living species sequence.Hard8GraphBFS+1No attempts yet2s256 MBJudgeable
Bracket StringsFor each queried length L, count bracket strings that match the incorrect or aperiodic filters chosen by flags p and q, modulo m.Hard8CombinatoricsNumber theory+2No attempts yet10s512 MBJudgeable
Finding a Grayscale ImageCount the R by C windows of A that equal B after a linear brightness change of the form p times A plus q.Hard8String matchingMatrix+1No attempts yet10s512 MBJudgeable
Text ProcessorCount the distinct substrings inside each fixed-width window of a lowercase string for many queries.Hard8String matchingSliding window+1No attempts yet1s256 MBJudgeable
Counting palindromesCount the palindromic substrings fully contained in each query interval of a lowercase string.Hard8String matchingSegment tree+2No attempts yet2s64 MBJudgeable
Swapping the StonesMove stones along empty arcs of a circular shore so black and white stones exchange position sets with minimum total carry distance, or report impossibility.Hard8GreedyString matching+1No attempts yet2s32 MBJudgeable
Alphabet Blocks and PasswordsArrange A to Z into the lexicographically smallest permutation with none of the given passwords appearing as a contiguous block.Hard8BacktrackingString matching+1No attempts yet5s512 MBJudgeable
Wildcard (Large)Given two filenames A and B, find the shortest star pattern that matches A but not B, breaking ties by fewer stars then lexicographic order.Hard8Dynamic programmingString matching+1No attempts yet5s512 MBJudgeable
The Great Mixing Song FestivalPartition the given songs into groups of exactly c songs each within a year span of m, maximizing the total length of the longest common substring in each group.Hard8Dynamic programmingBit manipulation+2No attempts yet5s128 MBJudgeable
Shades of the townGiven several integer patterns and one shade array, count every occurrence where a contiguous block equals a pattern scaled by a positive real factor.Hard8String matchingMathNo attempts yet1s1024 MBJudgeable
Hongjun Likes StringsFor each of up to 100000 queries, find the shortest substring of a fixed string S that contains both given short patterns A and B, allowing overlap.Hard8StringString matching+2No attempts yet2s512 MBJudgeable
Maximum substring costGiven a string T, find the maximum of length times number of occurrences over all substrings S of T.Hard8StringSorting+2No attempts yet2s512 MBJudgeable
Substring CountCount length-L lowercase strings that contain exactly C of N given words (N at most 6, L at most 50) as substrings, modulo 1,000,000,009.Hard8Dynamic programmingString matching+2No attempts yet2s512 MBJudgeable
PasswordGiven a length-N string, collect all distinct substrings meeting four counts (length, digits, specials, uppercase), sort them lexicographically, and print the middle one.Hard8StringSorting+2No attempts yet4s512 MBJudgeable
Pseudo PalindromeGiven a string w and a rational theta, split w into the fewest substrings that are each a theta-palindrome (form uvu^R with enough border), or report 0.Hard8Dynamic programmingString matching+1No attempts yet2s512 MBJudgeable
Good SubstringsCount how many distinct substrings of a binary string appear twice at non-overlapping positions.Hard8StringString matching+2No attempts yet2s512 MBJudgeable
Palindromes and QueriesSupport range character assignments and count palindromic substrings of length at most K inside a queried range.Hard8Segment treeString+2No attempts yet2s512 MBJudgeable
Revenge of the Champernowne ConstantGiven a digit string S of length up to 100, find the 1-indexed position of its first occurrence in the Champernowne constant 0.123456789101112...Hard8StringMath+2No attempts yet8s512 MBJudgeable
Favorite musicGiven n note strings and q pairs, find the shortest string containing both given fragments as contiguous substrings, allowing overlap.Hard8String matchingTrie+2No attempts yet1s256 MBJudgeable
ExamGiven each student's fixed semester points and a distribution of exam points, find the probability that the grade string avoids all forbidden substrings.Hard8Dynamic programmingString matching+2No attempts yet1.5s512 MBJudgeable
Game of MatchingsCount substrings of S that match pattern P under a bijective letter-to-number mapping, where distinct numbers must get distinct letters.Hard8String matchingString+2No attempts yet2s512 MBJudgeable
PasswordsCount length A to B alphanumeric passwords with mixed case and a digit that avoid blacklist substrings, where digits can stand in for similar letters.Hard8Dynamic programmingString matching+2No attempts yet2s512 MBJudgeable
Kids Designing KidsGiven three grid pictures, find the translation of the second that makes the XOR of the first two match the third, up to translation.Hard8ImplementationString matching+2No attempts yet2s512 MBJudgeable
Substring appearing twiceGiven a string and at most K letter replacements, maximize the length of the longest substring that occurs at two different starting positions, allowing overlap.Hard8StringBinary search+2No attempts yet6s128 MBJudgeable
Permutations that contain a wordCount distinct permutations of A that contain B as a contiguous substring, modulo 10007.Hard8Dynamic programmingCombinatorics+2No attempts yet2s128 MBJudgeable
OsmosmjerkaGiven a letter block tiled infinitely in all directions, pick a random start square and one of 8 directions twice, and report the probability that the two read words of length K match, as a reduced fraction.Hard8MathString matching+2No attempts yet4s256 MBJudgeable
String arrayCount strings S of length 1 to W such that the repeated periodic filling of X matches the given patch F at the fixed offset.Hard8String matchingNumber theory+1No attempts yet2s512 MBJudgeable
f(X) = A + X + B + X + CCount occurrences of pattern F in the K-fold string expansion f(X)=A+X+B+X+C applied to S, modulo 1e9+7.Hard8String matchingDynamic programming+2No attempts yet2s512 MBJudgeable
PianoGiven N equally likely piano tones, find the expected number of presses until a fixed M-tone sequence appears, for every prefix of it.Hard8String matchingDynamic programming+2No attempts yet1s64 MBJudgeable
Palindromes and Queries 2Given a string and queries, each query asks how many palindromic substrings start at a given index with length at least a given value.Hard8StringString matching+2No attempts yet2s512 MBJudgeable
Period of a Slot MachineGiven a sequence of n outcomes, find k and p minimizing k+p (ties by smaller p) such that T[i+p]=T[i] for all i>k with i+p<=n.Hard8String matchingImplementation+1No attempts yet2s512 MBJudgeable
Flipping OutCount the strings that, added to the given patterns, make the flip rule reproduce the given flip sequence, or -1 if infinitely many work.Hard8StringDynamic programming+2No attempts yet2s512 MBJudgeable
Calendar FragmentGiven a small rectangular fragment cut from a fixed-format yearly calendar, list all years from 1900 to 2100 whose calendar could contain that fragment.Hard8ImplementationSimulation+2No attempts yet1s512 MBJudgeable
MarsFor each query substring, find the minimum number of bit flips that make it match no substring of the DNA, or report Impossible.Hard8String matchingDynamic programming+1No attempts yet2s512 MBJudgeable
Vera and the BanquetGiven a circular string S, count the number of distinct substrings appearing in any contiguous block read in either direction around the circle.Hard8StringString matching+2No attempts yet2s512 MBJudgeable
Standing Out from the HerdFor each name in the herd, count its substrings that occur in no other name.Hard8StringString matching+2No attempts yet2s512 MBJudgeable
Longest Common Palindromic SubstringGiven up to 50 strings with total length 1,000,000, find the length of the longest palindrome that occurs as a substring in every one of them.Hard8StringString matching+2No attempts yet1s512 MBJudgeable
Split and MergeGiven two tilings of a 1xL board by 1x1 and 1x2 pieces, find the minimum number of split/merge operations to transform one into the other and count the ways.Hard8Dynamic programmingCombinatorics+2No attempts yet1s512 MBJudgeable
LotteryFor each of n-l+1 length-l windows and each query threshold k, count how many other windows differ from it in at most k positions.Hard8String matchingHash map+2No attempts yet2s32 MBJudgeable
Willy Feels GuiltyBuy, throw, or swap products so the delivered sequence realizes a fixed menu at minimum total cost.Hard8String matchingGreedy+1No attempts yet2s512 MBJudgeable
Hiding MerlinDecompose a digit string into concatenated perfect squares, each at most 10 digits and starting with 1 to 9, and report the smallest possible total sum.Hard8String matchingDynamic programming+2No attempts yet4s512 MBJudgeable
Binary Tree and SequenceFind the smallest tree depth where one concatenated leaf sequence occurs at least K times under a periodic leaf pattern.Hard8String matchingHash map+2No attempts yet3s256 MBJudgeable
Suffix-FreenessGiven a DFA with n at most 2000 states and f final states, decide whether some accepted string is a proper suffix of another accepted string, and answer 1 or 0.Hard8String matchingGraph+2No attempts yet2s512 MBJudgeable
Isomorphic InversionSplit a digit string into the largest number of contiguous pieces whose sequence of pieces reads the same forward and backward.Hard8GreedyString matching+2No attempts yet1s512 MBJudgeable
Locker RoomPick length-K substrings from a cyclic string covering every position and minimize their lexicographic maximum.Hard8StringGreedy+2No attempts yet6s512 MBJudgeable
Numbers GeneratorGiven up to ten H/T patterns of the same length, compute the expected number of fair coin flips until one pattern first appears contiguous.Hard8String matchingHash map+2No attempts yet2s512 MBJudgeable
Repeated SubstringsFind the longest substring with at least two overlapping occurrences in a string of up to 10^5 letters, breaking ties by the smallest in lexicographic order.Hard8String matchingString+2No attempts yet2s512 MBJudgeable
A Sequence That Matches Front and BackChoose how many elements to cut from the array's front so that, if the rest is a k-front-back sequence, k is as large as possible or no k exists. Return k and the cut count.Hard8ArrayString matching+1No attempts yet2s128 MBJudgeable
Bad KemingFill every gap in the spaced copy of S with chosen letters to make the longest prefix of S a contiguous substring, and find that prefix length.Hard8String matchingString+2No attempts yet2s512 MBJudgeable
Distinct SubstringsGiven a period string p and length n, count distinct substrings of the string formed by repeating p and cutting to n. n may be 1e9.Hard8String matchingMath+1No attempts yet3s512 MBJudgeable
The ABCD MurdererFind the fewest word occurrences needed to cover a target text exactly when cut-outs may overlap on matching text, or report -1 if impossible.Hard8String matchingArray+2No attempts yet2s512 MBJudgeable
Prefix Suffix SearchGiven N words and Q prefix/suffix pairs, report for each query how many words match both prefix and suffix. Total input length is up to 2.5 million.Hard8String matchingTrie+2No attempts yet3s512 MBJudgeable
Naming the ComputerGiven a string S and integer K, find the shortest string that contains S as a substring at least K times, and output its length.Hard8String matchingDynamic programming+2No attempts yet2s512 MBJudgeable
Distinct Substring Queries 2Process a stream of append-character and count-distinct-substrings queries on a growing string, answering each count query online.Hard8StringString matching+2No attempts yet1s512 MBJudgeable
Substring ReplacementReplace each question mark in S with a lowercase letter so that T appears as a substring as many times as possible, and report that maximum count.Hard8Dynamic programmingString matching+2No attempts yet2s512 MBJudgeable
String DecorationGiven a string S and N pattern strings, find the length of the shortest substring of S that contains every pattern as a substring.Hard8StringSliding window+2No attempts yet2s512 MBJudgeable
ZooGiven a string, count for each prefix the non-overlapping prefix-suffix matches and output the product of (count+1) modulo 1e9+7.Hard8StringString matching+2No attempts yet1s512 MBJudgeable
Ali's TypewriterGiven a keypress sequence that builds strings in a buffer and prints them, answer queries counting how often printed string x occurs inside printed string y.Hard8StringTrie+2No attempts yet1s512 MBJudgeable
AbbreviationCount the ways to split a query string into pieces, where each piece is a prefix of some dictionary word, with duplicates counted as distinct.Hard8Dynamic programmingString matching+2No attempts yet2.5s1024 MBJudgeable
Fox QuizGiven answer strings S and T over O/X, answer range queries and point flips: for a range, choose positions to mark F to maximize A times correct answers plus B times occurrences of the consecutive pattern F,O,X.Hard8Segment treeDynamic programming+2No attempts yet3s1024 MBJudgeable
Copy and PasteGiven a string of up to 200,000 lowercase letters, find the length of the longest substring that appears at least twice at disjoint positions, or -1 if none exists.Hard8StringBinary search+2No attempts yet2s512 MBJudgeable