Competitive programming and exercises

These are my C++ solutions of some competitive programming problems and various exercises. Similar problems are solved using different algorithms and data structures — sometimes using those provided by the standard library, sometimes using my own ones.

Most solutions are in C+11 due to ex-UVa online-judge limitation. Some of them after successful submission were modified to use C++14/17 features.

ex-UVa OJ problems

Problems source

ID	Title	Categories
001 08	Maximum sum	Linear search, maximum sum subarray, Kadane’s algorithm
001 09	Scud busters	Convex hull
001 12	Tree summing	Binary tree
001 20	Stacks of flapjacks	Stack, pancake sorting
001 22	Trees on the level	Binary tree, level-order traversal, breadth-first search
001 40	Bandwidth	Permutations, backtracking
001 47	Dollars	Dynamic programming, coin change
001 64	String computer	Dynamic programming, edit distance
002 00	Rare order	Topological sorting, depth-first search
002 16	Getting in line	Dynamic programming, Hamiltonian path, bit masks
002 18	Moth eradication	Convex hull
002 22	Budget travel
002 40	Variable radix Huffman encoding	Huffman tree, depth-first search
002 59	Software allocation
002 64	Count on cantor
002 70	Lining up
002 94	Divisors
003 34	Identifying concurrent events
003 48	Optimal array mult. sequence	Dynamic programming, matrix-chain multiplication
003 50	Pseudo random numbers
003 53	Pesky palindromes	Polynomial rolling hash, string processing
003 57	Count the ways
003 61	Cops and robbers
003 72	WhatFix notation	Binary tree, pre-/in-/post-order traversals conversion
003 74	Big mod	Binary exponentiation, modular exponentiation
004 29	Word transformation
004 37	Tower of Babylon
004 39	Knight moves	Breadth-first search
004 54	Anagrams
004 55	Periodic strings	Strings, Knuth–Morris–Pratt algorithm
004 59	Graph connectivity	Disjoint-set/union-find, graph connected components
004 69	Wetlands of Florida
004 81	What goes up	Longest increasing subsequence, binary search
004 82	Permutations arrays
005 01	Black box	AVL tree, binary tree iterator
005 07	Jill rides again	Linear search, maximum sum subarray, Kadane’s algorithm
005 16	Prime land
005 26	String distance	Dynamic programming, edit distance
005 36	Tree recovery	Binary tree, pre-/in-/post-order traversals conversion
005 40	Team queue
005 43	Goldbach conjecture	Prime numbers
005 48	Tree
005 51	Nesting bunch of brackets
005 58	Wormholes
005 62	Dividing coins
005 68	Just the facts	Factorial, recurrence relation
005 74	Sum it up
005 82	Randomly wired neural nets	Depth-first search, graph biconnected component
005 83	Prime factors
006 12	DNA sorting	Merge sort, inversions counting
006 23	500!	Factorial, big integer
006 30	Anagrams
006 39	Don’t get rooked
006 74	Coin change
006 79	Dropping balls
006 84	Integral determinant	Gaussian elimination, Euclidean algorithm
006 86	Goldbach conjecture II	Prime numbers
007 01	The archeologists’ dilemma	Logarithm
007 14	Copying books	Linear partitioning, implicit binary search
007 19	Glass beads	Lexicographically minimal rotation, Duvan’s algorithm
007 27	Equation	Expression parsing, shunting yard algorithm
007 29	The Hamming distance problem	Backtracking
007 50	Eight queens chess problem	Backtracking
007 87	Maximum sub-sequence product	Maximum product subarray, big integer
007 93	Network connections
007 96	Critical links	Depth-first search, graph bridge
008 20	Internet bandwidth
008 33	Water falls
008 68	Numerical maze	Backtracking
008 72	Ordering
009 08	Reconnecting computer sites
009 29	Number maze
009 42	Cyclic numbers	Rational number, decimal fraction, hash table
009 90	Diving for gold
009 91	Safe salutations	Combinatorics, recurrence relation, Catalan numbers
011 21	Subsequence	Sliding window
011 75	Ladies’ choice	Stable matching problem, Gale-Shapley algorithm
012 10	Sum of consecutive prime numbers	Prime numbers
012 52	Twenty questions
012 60	Sales
012 93	Symbolic derivation	Expression parsing, shunting yard algorithm, symbolic eval.
013 72	Log jumping
016 50	Number string	Combinatorics, recurrence relation
100 03	Cutting sticks
100 04	Bicoloring
100 18	Reverse and add	Integers, 196-algorithm
100 61	How many zeros and digits?	Factorial, prime numbers, factorization, logarithm
100 79	Pizza cutting	Combinatorics, central polygonal numbers
101 07	What is the median	Priority queue, online algorithms
101 71	Meeting prof. Miguel
101 93	All you need is love	Greatest common divisor
102 20	I love big numbers!	Factorial, big integer
102 23	How many nodes	Combinatorics, recurrence relation, Catalan numbers
102 29	Modular Fibonacci	Fibonacci numbers, modular exponentiation
102 45	The closest pair problem	2D closest pair of points
102 68	498-bis	Horner’s rule
102 82	Babelfish	Hash table
102 98	Power strings
103 05	Ordering tasks
103 11	Goldbach and Euler	Prime numbers
103 19	Manhattan
103 27	Flip sort	AVL tree
103 41	Solve it	Numerics, Newton’s method
103 64	Square	Backtracking, bit masks
103 82	Watering grass	Greedy, interval covering
104 28	The roots	Root finding, bisection method
104 54	Trexpression	Expression parsing, shunting yard algorithm, Catalan numbers
104 96	Collecting beepers
105 33	Digit primes
105 67	Helping Fill Bates
105 70	Meeting with aliens	Permutation, swaps counting, cycles counting
105 76	Y2K accounting bug
105 86	Polynomial remains
106 00	ACM contest and blackout
106 04	Chemical reaction
106 51	Pebble solitaire
106 55	Contemplation! Algebra	Recurrence relation, modular exponentiation
106 64	Luggage
106 84	Jackpot
106 99	Count the factors	Prime numbers, prime decomposition
107 23	Cyborg genes
107 38	Riemann vs Mertens	Prime numbers, Möbius function, Mertens function
108 01	Lift hopping
108 10	Ultra quicksort	Merge/insertion sort, inversions counting
108 55	Rotated squares	Matrix rotation, matrix transposition
108 70	Recurrences
109 20	Spiral Tap	Analytic expression
109 31	Parity
109 34	Dropping water balloons
109 35	Throwing cards away	Queue, singly-linked list
109 38	Flea circus
109 54	Add all	Heap
109 57	Su Doku checker	Backtracking, bit mask
109 94	Simple addition	Analytic expression
110 57	Exact sum
110 60	Beverages
110 77	Find the permutations	Combinatorics, recurrence relation, Stirling numbers
111 37	Ingenuous cubrency
111 51	Longest palindrome	Dynamic programming, string processing
111 71	SMS	Dynamic programming, string processing, trie
111 95	Another N-queen problem	Backtracking, bit mask
112 27	The silver bullet
112 35	Frequent values
112 36	Grocery store
112 57	New marketing plan	Polygon, inscribed circle radius, priority queue
112 58	String partition	Dynamic programming
112 60	Odd root sum	Analytic expression, impl. binary search, modular arithmetic
112 71	Lattice of resistors	Recurrence relation, asymptotic expansion
112 83	Playing Boggle	Backtracking
112 97	Census	2D sqrt decomposition
113 62	Phone list	Trie, prefix matching
114 13	Fill the containers
114 20	Chest of drawers	Combinatorics, recurrence relation
114 56	Trainsorting
114 61	Square numbers	Implicit binary search
114 62	Age sort	Count sort
114 63	Commandos
114 75	Extend to palindrome
115 17	Exact change
115 36	Smallest sub-array	Sliding window
115 72	Unique snowflakes	Linear search, hash table
115 84	Partitioning by palindromes
116 21	Small factors	Logarithm
116 34	Generate random numbers
116 36	Hello, world!	Analytic expression, logarithm
116 58	Best coalitions
116 86	Pick up sticks
116 91	Allergy test
117 03	Sqrt, log, sin	Recurrence relation
117 14	Blind sorting	Order statistics (2nd largest)
117 33	Airports
119 02	Dominator
119 91	Easy problem from Rujia Liu?	Sorting, binary search
119 97	K smallest sums
120 86	Potentiometers	Fenwick tree
121 05	Bigger is better (1)
121 05	Bigger is better (2)
121 92	Grapevine	Binary search
122 38	Ants colony
123 47	Binary search tree	Binary search tree, pre/post-order traversal
124 55	Bars	Complete search, backtracking
124 58	Oh, my trees!
124 62	Rectangle	Linear search, stack, bit mask
124 94	Distinct substring	Lex. minimal rotation, Duvan’s algorithm, hash table
125 04	Updating a dictionary	Quick sort
126 40	Largest sum game	Linear search, maximum sum subarray, Kadane’s algorithm
126 97	Minimal subarray length	Linear search, maximum sum subarray, Kadane’s algorithm
127 02	Dilation	Binary morphology, binary image dilation
129 11	Subset sum	Subset sum, complete search, meet-in-the-middle
130 50	Discovering paths	Combinatorics, recurrence relation
132 82	Cakey McCakeFace (1)	Sorting, linear search
132 82	Cakey McCakeFace (2)	Bit mask, bucketing

International high performance computing contest

Problems source

ID	Title	Categories
C2	Get the image	Fractal, Mandelbrot set, MPI, std::thread

Other problems and exercises

Miscellaneous problems from different online sources.

Title	Categories
Array to binary search tree	Binary search tree
Array with unit adj. difference search	Linear search
Binary sorted array transition point	Binary search
Binary tree diameter	Binary tree, depth-first traversal
Binary tree top view	Binary tree, breadth-first traversal
Bitonic array search	Binary search
Common elements in three array	Linear search
Connection point in Y-shaped linked lists	Singly-linked list
Count anagram substrings	Hash table, sliding window
Count smaller elements on the right	AVL tree
Count squares in postal codes	Analytic expression
Count the triplets	Linear search, pair sum search
Divisibility in a binary stream	Modular arithmetic, divisibility
Equilibrium point	Linear search
Generate parentheses (1)	Combinatorics, backtracking
Has a subset with a sum	Dynamic programming
Is a linked list a palindrome	Singly-linked list
Is a subtree (1)	Binary tree, depth-first traversal
K-th element in row-column sorted matrix	Heap
Largest number with k swaps	Backtracking
Largest rectangle in a histogram	Linear search, stack
Largest square a boolean matrix	Dynamic programming, largest square submatrix
Last two digits of Fibonacci	Fibonacci numbers, modular arithmetic, binary exponentiation
List merge	Singly-linked list
List merge sort	Singly-linked list, merge sort
Longest distinct-character substring	Linear search
Longest palindromic sum substring	Linear search
Majority element	Boyer–Moore majority vote algorithm
Make array strictly increasing	Longest increasing subsequence, binary search
Matrix rotation	Matrix rotation, matrix transposition
Maximum distance between sorted elements	Linear search
Maximum numerical value in a string	Linear search, lexicographic comparison
Maximum of each subarray (1)	Sliding window, balanced binary tree
Maximum of each subarray (1)	Sliding window, deque
Maximum product of 3 elements	Linear search
Min-stack	Stack
Minimum element in sorted rotated array	Binary search
Minimum number of jumps (1)	Dynamic programming
Minimum number of jumps (2)	Linear search
Nearly sorted	Heap sort, insertion sort
Next greater element	Linear search, stack
Nodes at distance k in binary tree	Binary tree, depth-first traversal
Number of paths in a grid	Combinatorics
Partition even and odd nodes	Singly-linked list
Queue as two stacks	Queue, stack
Remove duplicate nodes	Singly-linked list
Remove middle node	Singly-linked list
Restore an alphabet from a dictionary	Topological sorting, Kahn’s algorithm
Reverse a singly-linked list	Singly-linked list
Reverse words in a string	Linear search
Rotate a singly-linked list	Singly-linked list
Rotated array search	Binary search, linear search
Second largest	Order statistics, second largest element, binary counter
Set row and column if	Linear search
Smallest number in a permutation	Linear search
Sorted subsequence of size 3	Linear search
Sorted subsequence of size 4	Linear search
Square root	Implicit binary search
Subarray with given sum	Linear search
Three way partition	Array partitioning
Two elements with the given sum	Linear search, hash table
Unordered equal arrays	Sequence, hash table
XOR linked list	Doubly-linked list
Zero-sum subarray	Linear search, hash table