My biggest mistake with this project is not knownig how long each problem took me to complete. but maybe from my commits someone can figure it out?
Someone please create a an application to calculate the time it took me to solve each problem in this git repo.
Can probably use commit times of problem and solution.
This repository is a bunch of Algorithms and Data Structures problems and solutions.
My goal is to go through all the must try problems of the book Competitive Programming 3 by Steven Halim and Felix Halim. So this is a sort of solution manual.
The core directive in Competitive Programming is
Given well-known Computer Science (CS) problems, solve them as quickly as possible!
------------------------------------------
Data Structures
------------------------------------------
1D Array Manipulation ----
UVa 10038 Jolly Jumper - [Done]
UVa 11340 Newspaper - [Done]
2D Array Manipulation ----
UVa 10855 Rotated squares - [Done]
UVa 10920 Spiral Tap - [Done]
UVa 11581 Grid Successors --- [Done]
Java Collections ##
UVa 00146 ID Codes - [Done]
UVa 10107 What is the Median - [Done]
UVa 10258 Contest Scoreboard - [Done]
Bit Manipulation ---
UVa 11926 Multitasking - [Done]
UVa 11933 Splitting Numbers - [Done]
Java LinkedList ----
UVa 11988 Broken Keyboard - [Done]
Java Stack ----
UVa 00514 Rails - [Done]
UVa 00732 Anagram by Stack [Done w/ TLE]
Java Queue and Deque ----
UVa 10172 The Lonesome Cargo [Skipped]
UVa 10901 Ferry Loading III - [Done]
UVa 11034 Ferry Loading IV - [Done]
Java TreeMap ----
UVa 10226 - Hardwood Species - [Done]
UVa 11286 - Conformity - [Done]
Java TreeSet ----
UVa 00978 - Lemmings Battle (use multiset) - [DONE]
UVa 11136 - Hoax or what (use multiset) - [DONE]
UVa 11849 - CD (set or hashing) -[DONE]
Java PriorityQueue ----
UVa 01203 - Argus - [DONE]
UVa 10954 - Add all - [DONE]
UVa 11995 - I can Guess...[RTE]
Graph Data Structures ----
UVa 00599 - The Forrest for the Trees [DONE]
UVa 10895 - Matrix Tranpose [DONE]
UVa 11991 - Easy Problem from...[DONE]
Union-Find Disjoint Sets ----
UVa 00793 - Network Connections* [DONE]
UVa 10507 - Waking up brain* [DONE]
UVa 11503 - Virtual Friends* [DONE]
Tree-related Data Structures ----
UVa 11235 - Frequent Values* (Sparse Table)[DONE]
UVa 11402 - Ahoy, Pirates (SegmentTree) [SKIP]
------------------------------------------
Complete Search
------------------------------------------
Iterative (One Loop, Linear Scan) ----
UVa 00927 - Integer Sequence From ... [DONE]
UVa 01237 - Expert Enough - [DONE]
UVa 10976 - Fractions Again? -[ DONE]
Iterative (Two Nested Loops) ----
UVa 01260 - Sales * [DONE]
UVa 10487 - Closest Sums * [DONE]
UVa 11242 - Tour de France *[DONE]
Iterative (Three or More Nested Loops, Easier) ----
UVa 00441 - Lotto *[DONE]
UVa 00725 - Dart-a-Mania*[DONE]
UVa 10102 - The Path in the ...*[DONE]
Iterative (Three-or-More Nested Loops, Harder) ----
UVa 10660 - Citizen attention ... * [DONE]
UVa 11565 - Simple Equations *[DONE]
Fancy Techniques ----
UVa 11553 - Grid Game *[DONE]
Recursive Backtracking (Easy) ----
UVa 00624 - CD * [DONE]
UVa 10576 - Y2K Accounting Bug [DONE]
UVa 11085 - Back to the 8-Queens [DONE]
Recursive Backtracking (Medium) ----
UVa 00524 - Prime Ring Problem [ORDER WRONG]
UVa 00574 - Sum It Up [DONE]
UVa 10503 - The dominoes soliaire [DONE]
Recursive Backtracking (hard) ----
UVa 00193 - Graph Coloring - [DONE]
UVa 00416 - LED Test - [DONE]
------------------------------------------
Dynamic Programming
------------------------------------------
UVa 00787 - Maximum Sub - [DONE]"
UVa 10684 - The Jackpot - [DONE]"
UVa 00108 - Maximum Sum - [DONE]"
UVa 10827 - Maximum Sum on..[DONE]"
UVa 00481 - What Goes up? [TLE]"
UVa 11456 - Trainsorting - [DONE]"
UVa 11790 - Murcia's Skyline - [DONE]"
Knapsack (Subset Sum) --- "
UVa 10616 - Divisible Group Sum [Come back to this ]"
UVa 10819 - Trouble of 13-Dots - [DONE]"
Coin Change (CC) --- "
UVa 00357 - Let Me Count The ways - [DONE]"
UVa 10306 - e-Coins [RETURN TO ME !!!****!!!!!]"
UVa 11517 - Exact Change"
Traveling Salesman Problem (TSP) ---
UVa 00216 - Getting in Line - C++ DONE
UVa 10496 - Collecting Beepers - C++ DONE
UVa 11284 - Shopping Trip"
Non Classical --- "
UVa 10337 - Flight Planner"
UVa 10721 - Bar Codes"
UVa 10943 - How do you add?"
------------------------------------------
Graph
------------------------------------------
# Just Graph Traversal (161)
UVa 11831 - Sticker Collector - [DONE]
UVa 11906 - Knight in a War Grid
# Flood Fill/ Finding Connected Components
UVa 11094 - Continents"
UVa 11953 - Battleships"
# Topological Sort
# Bipartite Graph Check
# Finding Articulation Points/Bridges
# Finding Strongly Connected Components
# Minimum Spanning Tree
# Single-Source Shortest Paths
------------------------------------------
Mathematics
------------------------------------------
------------------------------------------
String Processing
------------------------------------------
# Cipher/Encode/Encrypt/Decode/Decrypt, Easier
UVa 10878 - Decode the Tape - [DONE] C++
UVa 10851 - 2D Hieroglyphs ... [DONE] C++
UVa 11278 - One-Handed Typist * [DONE] C++
# Cipher/Encode/Encrypt/Decode/Decrypt, Harder
UVa 11385 - Da Vinci Code [DONE] C++
UVa 11697 - Playfair Cipher [DONE] C++ (Wrong Answer but passing all known test cases)
# Frequency Counting
UVa 00902 - Password Search * (read char by char; count word freq) [DONE] C++
UVa 10252 - Common Permutation * (count freq of each alphabet) [DONE] C++
UVa 11203 - Can you decide it ... * (convoluted, but its actually easy) [DONE] C++
# Input Parsing (Non Recursive)
UVa 11878 - Homework Checker * (mathematical expression parsing) [DONE] C++
# Input Parsing (Recursive)
UVa 00622 - Grammar Evaluation * (recursive BNF grammar check/evaluation) [DONE] C++
UVa 10854 - Number of Paths * (recursive parsing plus counting) [DONE] C++
# Solvable with Java String/Pattern class (Regular Expression)
UVa 00325 - Identifying Legal ... * (see the Java solution above) [DONE] C++
UVa 00494 - Kindergarten Counting ... * (see the Java solution above) [DONE] C++
UVa 10058 - Jimmi’s Riddles * (solvable with Java regular expression [DONE] C++
# Output Formatting
UVa 00488 - Triangle Wave * (use several loops) [DONE] C++
UVa 10800 - Not That Kind of Graph * (tedious problem) [DONE] C++
# String Comparison
UVa 00644 - Immediate Decodability * (use brute force) [DONE] C++
UVa 11048 - Automatic Correction ... * (flexible string comparison with respect to dictionary) [DONE] C++
UVa 11056 - Formula 1 * (sorting, case-insensitive string comparison) [DONE] C++
# Just Ad Hoc
UVa 00941 - Permutations * (formula to get the n-th permutation) - C++ [DONE]
UVa 10393 - The One-Handed Typist * (follow problem description) - C++ [DONE]
UVa 11452 - Dancing the Cheeky ... * (string period, small input, BF) - C++ [DONE]
# String Matching Standard
UVa 10298 - Power Strings * (find s in s + s, similar to UVa 455) C++ [DONE]
UVa 11475 - Extend to Palindromes * (‘border’ of KMP) C++ [DONE]
UVa 11576 - Scrolling Sign * (modified string matching; complete search) C++ [DONE]
# String Matching In 2D Grid
UVa 00422 - Word Search Wonder * (2D grid, backtracking)
UVa 10010 - Where’s Waldorf ? * (discussed in this section)
UVa 11283 - Playing Boggle * (2D grid, backtracking, do not count twice)
# String Processing with DP
UVa 00526 - Edit Distance * (String Alignment/Edit Distance)
UVa 10192 - Vacation * (Longest Common Subsequence)
UVa 10635 - Prince and Princess * (find LCS of two permutations)
UVa 11151 - Longest Palindrome * (discussed in this section)
UVa 11258 - String Partition * (discussed in this section)
# Suffix Trie/Tree/Array
UVa 00760 - DNA Sequencing * (Longest Common Substring of two strings)
UVa 11107 - Life Forms * (Longest Common Substring of 1/2 of the strings)
UVa 11512 - GATTACA * (Longest Repeated Substring)
------------------------------------------
Geometry
------------------------------------------
Points and Lines
UVa 00920 - Sunny Mountains * (Euclidean distance dist)
UVa 10263 - Railway * (use distToLineSegment)
UVa 10927 - Bright Lights * (sort points by gradient, Euclidean distance)
https://cses.fi/book/book.pdf https://github.com/AhmadElsagheer/UVa-Solutions/blob/master/v112/OneHandedTypist_UVa11278.java