Competitive Programming

Methods to Solve (2000-present)

Use these filters to narrow down your next problem to solve:

OJ: , Topic: , Quality:

You can now sort these problems based on Distinct ACcepted Users (DACU) column.
Generally, problems with high DACU are the easier problems.
Note that we only update DACU column manually (not a live data).

As Kattis users, you can also sort these problems based Kattis points (usually correlated with DACU but not always).
Generally, problems with low Kattis points are the easier problems.
Note that we only update Point column manually (not a live data).

For Kattis and Google Chrome users, install Kattis Hint Giver created by one of my student Lin Si Jie that integrates this page directly with Kattis problems pages (Kattis has major UI/UX upgrade on early Jun 2022, Si Jie has updated this tool and added 'spoiler blur' so users can decide when to be spoiled; but Kattis changes its UI again by end 2023 so this feature is now broken again)
(Almost) all of the easiest 1004 problems (range: [1.1..3.3] points, average at 2.2 points) have hints and solving them all gives you 1004*~2.2 ≥ 2208.8 total Kattis points — The Lower Bound of Programming Contests in the 2020s year 2024.
Tips: You may want to occasionally 'Remove 'Kattis Hint Giver' from Chrome' and re-'Add it back to Chrome' to manually sync this Methods to Solve content with the local cache.

Kattis Problem Title CP4 Hint DACU Point
carrots carrots 1.4a, I/O + Sequences Only just print P 15155 1.3
hello hello 1.4a, I/O + Sequences Only just print "Hello World!" 39217 1.2
r2 r2 1.4a, I/O + Sequences Only just print 2*S-R1 14929 1.2
thelastproblem thelastproblem 1.4a, I/O + Sequences Only S can have space(s) 76 1.8
different different 1.4b, Repetition Only use abs function per test case 8964 2.3
qaly qaly 1.4b, Repetition Only trivial loop 5955 1.2
tarifa tarifa 1.4b, Repetition Only one pass; array not needed 9768 1.3
timeloop timeloop 1.4b, Repetition Only just print 'num Abracadabra' N times 17170 1.3
isithalloween isithalloween 1.4c, Selection Only if-else; 2 cases 3761 1.3
judgingmoose judgingmoose 1.4c, Selection Only if-else if-else; 3 cases 4516 1.4
moscowdream moscowdream 1.4c, Selection Only if-else; 2 cases; check n ≥ 3 443 1.7
onechicken onechicken 1.4c, Selection Only if-else if-else; 4 cases (piece vs pieces) 3014 1.6
provincesandgold provincesandgold 1.4c, Selection Only if-else if-else; 6 cases 1779 1.4
quadrant quadrant 1.4c, Selection Only if-else if-else; 4 cases 13625 1.3
temperature temperature 1.4c, Selection Only if-else if-else; 3 cases; derive formula 685 2.2
eligibility eligibility 1.4d, Multiple TC + Selection 3 cases 1741 1.6
helpaphd helpaphd 1.4d, Multiple TC + Selection 2 cases 2044 1.6
leftbeehind leftbeehind 1.4d, Multiple TC + Selection 4 cases 2014 1.6
oddities oddities 1.4d, Multiple TC + Selection 2 cases 11523 1.3
fizzbuzz fizzbuzz 1.4e, Control Flow actually just about easy divisibility properties 10274 1.3
licensetolaunch licensetolaunch 1.4e, Control Flow easy linear pass 1969 1.4
oddgnome oddgnome 1.4e, Control Flow linear pass 2388 1.6
statistics statistics 1.4e, Control Flow one pass; array not needed 2942 1.7
artichoke artichoke 1.4f, Function LA 7150 - WorldFinals Marrakech15; linear scan; probably one of the easiest WorldFinals problem; also available at UVa 0... 1390 2.8
digits digits 1.4f, Function direct simulation; also available at UVa 11687 - Digits 214 3.5
filip filip 1.4f, Function create a 'reverse string' function; then if-else check 6345 1.3
mia mia 1.4f, Function just if-else check 1136 2.1
acm acm 1.4g, 1D Array, Easier simple simulation; one pass 3526 1.5
cetiri cetiri 1.4g, 1D Array, Easier sort 3 number helps; 3 cases 1165 1.9
lineup lineup 1.4g, 1D Array, Easier sort ascending/descending and compare 3703 1.6
lostlineup lostlineup 1.4g, 1D Array, Easier simple 1D array manipulation 550 1.5
batterup batterup 1.4h, Easy easy one loop 4542 1.3
hangingout hangingout 1.4h, Easy simple loop 2218 1.3
hissingmicrophone hissingmicrophone 1.4h, Easy simple loop 7690 1.3
pokerhand pokerhand 1.4h, Easy frequency count; report max 2173 1.4
bossbattle bossbattle 1.4i, Still Easy trick question 1391 1.8
bubbletea bubbletea 1.4i, Still Easy simple simulation 806 2.2
peasoup peasoup 1.4i, Still Easy one linear pass 771 2.4
vote vote 1.4i, Still Easy follow the requirements 1584 2.2
basicprogramming1 basicprogramming1 1.4j, Medium a nice summative problem for programming examination of a basic programming methodology course 201 4.0
battlesimulation battlesimulation 1.4j, Medium one pass; special check on 3! = 6 possible combinations of 3 combo moves 900 2.8
bitsequalizer bitsequalizer 1.4j, Medium analyzing patterns; also available at UVa 12545 - Bits Equalizer 174 4.5
fastfood fastfood 1.4j, Medium eventually just one pass due to the constraints 330 2.2
bela bela 1.6a, Game (Card) simple card scoring problem 3731 1.3
memorymatch memorymatch 1.6a, Game (Card) interesting simulation game; many corner cases 161 4.0
shuffling shuffling 1.6a, Game (Card) simulate card shuffling operation 218 2.8
chess chess 1.6b, Game (Chess) bishop movements; either impossible, 0, 1, or 2 ways - one of this can be invalid; just use brute force 856 2.9
empleh empleh 1.6b, Game (Chess) the reverse problem of Kattis - helpme 245 1.8
helpme helpme 1.6b, Game (Chess) convert the given chess board into chess notation 302 2.4
connectthedots connectthedots 1.6c, Game (Others), Easier classic children game; output formatting 213 3.6
gamerank gamerank 1.6c, Game (Others), Easier simulate the ranking update process 732 3.9
guessinggame guessinggame 1.6c, Game (Others), Easier use a 1D flag array; also available at UVa 10530 - Guessing Game 684 2.7
battleship battleship 1.6d, Game (Others), Harder simulation; reading comprehension; many corner cases 120 5.4
rockpaperscissors rockpaperscissors 1.6d, Game (Others), Harder count wins and losses; output win average; also available at UVa 10903 - Rock-Paper-Scissors ... 820 3.7
tictactoe2 tictactoe2 1.6d, Game (Others), Harder check validity of Tic Tac Toe game; tricky; also available at UVa 10363 - Tic Tac Toe 167 5.3
turtlemaster turtlemaster 1.6d, Game (Others), Harder interesting board game to teach programming for children; simulation 323 2.9
chopin chopin 1.6e, Real Life, Easier you can learn a bit of music with this problem 823 1.8
compass compass 1.6e, Real Life, Easier your typical smartphone's compass function usually has this small feature 1529 2.0
trainpassengers trainpassengers 1.6e, Real Life, Easier create a verifier; be careful of corner cases 1807 2.1
wertyu wertyu 1.6e, Real Life, Easier use 2D mapper array to simplify the problem; also available at UVa 10082 - WERTYU 768 2.9
beatspread beatspread 1.6f, Real Life, Medium be careful with boundary cases!; also available at UVa 10812 - Beat the Spread 980 2.4
luhnchecksum luhnchecksum 1.6f, Real Life, Medium very similar (~95%) to UVa 11743 836 1.6
toilet toilet 1.6f, Real Life, Medium simulation; be careful of corner cases 1756 2.4
wordcloud wordcloud 1.6f, Real Life, Medium just a simulation; but be careful of corner cases 322 2.4
creditcard creditcard 1.6g, Real Life, Harder real life issue; precision error issue if we do not convert double (with just 2 digits after decimal point) into long lo... 123 6.3
touchscreenkeyboard touchscreenkeyboard 1.6g, Real Life, Harder follow the requirements; sort 636 1.9
workout workout 1.6g, Real Life, Harder gym simulation; use 1D arrays to help you simulate the time quickly 151 5.7
friday friday 1.6h, Time, Easier the answer depends on the start day of the month 1059 1.9
justaminute justaminute 1.6h, Time, Easier linear pass; total seconds/(total minutes*60) 1512 1.7
marswindow marswindow 1.6h, Time, Easier simple advancing of year and month by 26 months or 2 years+2 months each; direct formula exists 830 2.0
savingdaylight savingdaylight 1.6h, Time, Easier convert hh:mm to minute; compute difference of ending and starting; then convert minute to hh:mm again 986 2.1
bestbefore bestbefore 1.6i, Time, Harder tedious; 3! = 6 possibilities to check 148 4.0
birthdayboy birthdayboy 1.6i, Time, Harder convert mm-dd into [0..364]; use DAT; find largest gap via brute force 108 4.6
natrij natrij 1.6i, Time, Harder convert hh:mm:ss to seconds; make sure the second time is larger than the first time; corner case: 24:00:00 1136 2.6
timezones timezones 1.6i, Time, Harder follow the description, tedious; also available at UVa 10371 - Time Zones 67 5.3
rimski rimski 1.6j, Roman Numerals to Roman/to Decimal conversion problem; use next permutation to be sure 118 4.5
romanholidays romanholidays 1.6j, Roman Numerals generate and sort the first 1K Roman strings; ''M'' is at index 945; append prefix 'M' for numbers larger than 1K 92 3.6
conundrum conundrum 1.6k, Cipher, Easier simple cipher 5240 1.4
encodedmessage encodedmessage 1.6k, Cipher, Easier simple 2D grid cipher 2316 1.4
t9spelling t9spelling 1.6k, Cipher, Easier similar to (the reverse of) UVa 12896 2425 1.7
anewalphabet anewalphabet 1.6l, Cipher, Medium simple cipher; 26 characters 4154 1.8
piglatin piglatin 1.6l, Cipher, Medium simple; check the vowels that include 'y' and process it 916 2.1
secretmessage secretmessage 1.6l, Cipher, Medium just do as asked; use 2D grid 2866 1.7
tajna tajna 1.6l, Cipher, Medium simple 2D grid cipher 471 2.1
autori autori 1.6m, Input Parsing (Iter) simple string tokenizer problem 11602 1.2
pervasiveheartmonitor pervasiveheartmonitor 1.6m, Input Parsing (Iter) simple parsing; then finding average 950 1.7
timebomb timebomb 1.6m, Input Parsing (Iter) just a tedious input parsing problem; divisibility by 6 1174 1.8
display display 1.6n, Output Formatting, E unordered_map; map a digit -> enlarged 7x5 version 635 2.5
musicalnotation musicalnotation 1.6n, Output Formatting, E simple but tedious 421 2.0
skener skener 1.6n, Output Formatting, E enlarging 2D character array 2067 1.5
asciiaddition asciiaddition 1.6o, Time Waster, Easier a+b problem in text format; total gimmick; time waster 509 1.9
glitchbot glitchbot 1.6o, Time Waster, Easier time waster; O(n^2) simulation; do not output more than one possible answer 1036 2.0
pachydermpeanutpacking pachydermpeanutpacking 1.6o, Time Waster, Easier time waster; simple one loop simulation 322 1.9
printingcosts printingcosts 1.6o, Time Waster, Easier clear time waster; the hard part is in parsing the costs of each character in the problem description 705 2.2
froggie froggie 1.6p, Time Waster, Harder just a simulation; but many corner cases; S can be 0 296 6.8
functionalfun functionalfun 1.6p, Time Waster, Harder just follow the description; 5 cases; tedious parsing problem; requires a kind of mapper 487 1.9
windows windows 1.6p, Time Waster, Harder LA 7162 - WorldFinals Marrakech15; tedious simulation problem; also available at UVa 01721 - Window Manager 92 7.6
baloni baloni 2.2a, 1D Array, Medium clever use of 1D histogram array to decompose the shots as per requirement 689 3.5
downtime downtime 2.2a, 1D Array, Medium 1D array; use Fenwick Tree-like operation for Range Update Point Query 1068 3.2
greedilyincreasing greedilyincreasing 2.2a, 1D Array, Medium just 1D array manipulation; this is not the DP-LIS problem 1151 1.9
jollyjumpers jollyjumpers 2.2a, 1D Array, Medium 1D Boolean flags to check [1..n-1]; also available at UVa 10038 - Jolly Jumpers 413 3.4
divideby100 divideby100 2.2b, 1D Array, Harder big 1D character array processing; be careful 557 4.2
mastermind mastermind 2.2b, 1D Array, Harder 1D array manipulation to count r and s 446 2.4
pivot pivot 2.2b, 1D Array, Harder static range min/max query problem; special condition allows this problem to be solvable in O(n) using help of 1D arrays 1723 3.2
epigdanceoff epigdanceoff 2.2c, 2D Array, Easier count number of CCs on 2D grid; simpler solution exists: count the number of blank columns plus one 505 1.9
flowshop flowshop 2.2c, 2D Array, Easier interesting 2D array manipulation 392 2.5
imageprocessing imageprocessing 2.2c, 2D Array, Easier interesting 2D array manipulation 344 2.1
nineknights nineknights 2.2c, 2D Array, Easier 2D array checks; 8 directions 881 1.9
2048 2048 2.2d, 2D Array, Harder just a 2D array manipulation problem; utilize symmetry using 90 degrees rotation(s) to reduce 4 cases into 1 3150 2.1
flagquiz flagquiz 2.2d, 2D Array, Harder array of array of strings; be careful; duplicates may exists 167 3.7
funhouse funhouse 2.2d, 2D Array, Harder 2D array manipulation; note the direction update 700 2.0
rings2 rings2 2.2d, 2D Array, Harder more challenging 2D array manipulation; special output formatting style 385 3.8
basicprogramming2 basicprogramming2 2.2e, Sorting, Easier a nice problem about basic sorting applications 189 3.4
height height 2.2e, Sorting, Easier insertion sort simulation 899 2.0
mjehuric mjehuric 2.2e, Sorting, Easier a direct simulation of a bubble sort algorithm 1349 1.6
sidewayssorting sidewayssorting 2.2e, Sorting, Easier stable_sort or sort multi-fields of columns of a 2D array; ignore case 857 2.0
classy classy 2.2f, Sorting, Harder sort using modified comparison function; a bit of string parsing/tokenization 1633 4.5
dyslectionary dyslectionary 2.2f, Sorting, Harder sort the reverse of original string; output formatting 775 3.4
musicyourway musicyourway 2.2f, Sorting, Harder stable_sort; custom comparison function 404 2.4
sortofsorting sortofsorting 2.2f, Sorting, Harder stable_sort or sort multi-fields 2667 2.2
bread bread 2.2g, Special Sorting inversion index; hard to derive 249 5.0
mali mali 2.2g, Special Sorting Counting Sort two arrays; greedy matching largest+smallest at that point 97 5.1
bitbybit bitbybit 2.2h, Bit Manipulation be very careful with and + or corner cases 955 2.9
deathstar deathstar 2.2h, Bit Manipulation can be solved with bit manipulation 415 2.0
snapperhard snapperhard 2.2h, Bit Manipulation bit manipulation; find the pattern; the easier version is also available at Kattis - snappereasy 501 2.3
primaryarithmetic primaryarithmetic 2.2i, Big Integer not a Big Integer problem but a simulation of basic addition 399 2.7
simpleaddition simpleaddition 2.2i, Big Integer that A+B on BigInteger question 1913 1.9
wizardofodds wizardofodds 2.2i, Big Integer if K is bigger than 350, the answer is clear; else just check if 2^K ≥ N 488 2.6
evenup evenup 2.2j, Stack use stack to solve this problem 1273 2.7
pairingsocks pairingsocks 2.2j, Stack simulation using two stacks; just do as asked 556 3.0
restaurant restaurant 2.2j, Stack simulation with stack-based concept; drop plates at stack 2 (LIFO); use move 2-$gt;1 to reverse order; take from stack 1... 364 4.5
throwns throwns 2.2j, Stack use stack of egg positions to help with the undo operation; be careful of corner cases involving modulo operation 1091 2.6
bungeebuilder bungeebuilder 2.2k, Stack-based Problems clever usage of stack; linear pass; bracket (mountain) matching variant 83 3.3
circuitmath circuitmath 2.2k, Stack-based Problems postfix calculator problem 918 2.4
delimitersoup delimitersoup 2.2k, Stack-based Problems bracket matching; stack 382 1.9
integerlists integerlists 2.2l, List/Queue/Deque use deque for fast deletion from front (normal) & back (reversed list); use stack to reverse the final list if it is... 882 4.8
joinstrings joinstrings 2.2l, List/Queue/Deque all '+' operations must be O(1) 959 4.1
sim sim 2.2l, List/Queue/Deque use list and its iterator 99 2.0
teque teque 2.2l, List/Queue/Deque all operations must be O(1) 766 3.3
jugglingpatterns jugglingpatterns 2.3a, Priority Queue PQ simulation; reading comprehension 48 6.3
knigsoftheforest knigsoftheforest 2.3a, Priority Queue PQ simulation after sorting the entries by year 184 3.6
numbertree numbertree 2.3a, Priority Queue not a direct priority queue problem, but the indexing strategy is similar to binary heap indexing 1760 2.1
stockprices stockprices 2.3a, Priority Queue PQ simulation; both max and min PQ 109 3.7
alphabetspam alphabetspam 2.3b, DAT, ASCII count the frequencies of lowercase, uppercase, and whitespace characters 3902 1.4
quickbrownfox quickbrownfox 2.3b, DAT, ASCII pangram; frequency counting of 26 alphabets 4433 1.6
soundex soundex 2.3b, DAT, ASCII DAT for soundex A-Z code mapping; also available at UVa 10260 - Soundex 106 2.9
bookingaroom bookingaroom 2.3c, DAT, Others only 100 rooms; use 1D Boolean array 2849 1.7
busnumbers busnumbers 2.3c, DAT, Others only 1000 bus numbers; use 1D Boolean array 2776 2.4
freefood freefood 2.3c, DAT, Others only 365 days in a year 1965 1.5
princesspeach princesspeach 2.3c, DAT, Others DAT; linear pass 839 2.1
cd cd 2.3d, Hash Table (set) unordered_set is faster than set here; or use modified merge as the input is sorted; also available at UVa 11849 - CD 3176 5.3
esej esej 2.3d, Hash Table (set) use unordered_set to prevent duplicate 509 3.3
greetingcard greetingcard 2.3d, Hash Table (set) use unordered_set; good question; major hint: only 12 neighbors 607 4.9
shiritori shiritori 2.3d, Hash Table (set) linear pass; use unordered_set to keep track of words that have been called 295 2.9
competitivearcadebasketball competitivearcadebasketbal... 2.3e, Hash Table (map), E use unordered_map 209 2.8
conformity conformity 2.3e, Hash Table (map), E use unordered_map to count frequencies of the sorted permutations of 5 ids; also available at UVa 11286 - Conformity 1100 1.9
grandpabernie grandpabernie 2.3e, Hash Table (map), E use unordered_map plus (sorted) vector 1065 3.2
recount recount 2.3e, Hash Table (map), E use map; frequency counting 1163 2.0
addingwords addingwords 2.3f, Hash Table (map), H use unordered_map 1880 3.9
awkwardparty awkwardparty 2.3f, Hash Table (map), H use unordered_map to running max and running min; report the largest difference 611 3.0
basicinterpreter basicinterpreter 2.3f, Hash Table (map), H the harder version of Kattis - variablearithmetic; tedious; be careful; print string inside double quotes verbatim 152 6.7
bst bst 2.3g, Balanced BST (set) simulate special BST [1..N] insertions using set 449 7.3
candydivision candydivision 2.3g, Balanced BST (set) complete search from 1 to sqrt(N); insert all divisors into set for automatic sorting and elimination of duplicates 702 3.4
compoundwords compoundwords 2.3g, Balanced BST (set) use set extensively; iterator 1807 1.7
administrativeproblems administrativeproblems 2.3h, Balanced BST (map) use several maps as the output (of spy names) has to be sorted; be careful of corner cases 194 6.3
doctorkattis doctorkattis 2.3h, Balanced BST (map) Max Priority Queue with frequent (increaseKey) updates; use map 114 4.7
kattissquest kattissquest 2.3h, Balanced BST (map) use map of priority queues; other solutions exist 834 3.1
srednji srednji 2.3h, Balanced BST (map) go left and right of B; use fast data structure like map to help determine the result fast 164 4.1
babynames babynames 2.3i, Order Statistics Tree dynamic rank problem; use two pb_ds 87 5.5
continuousmedian continuousmedian 2.3i, Order Statistics Tree dynamic selection problem; specifically the median values; pb_ds helps 140 3.9
cookieselection cookieselection 2.3i, Order Statistics Tree map large integers to up to 600K integers; use pb_ds or Fenwick Tree and the select(median) operation of Fenwick Tree 923 4.3
gcpc gcpc 2.3i, Order Statistics Tree dynamic rank problem; pb_ds helps 876 5.3
abinitio abinitio 2.4a, Graph Data Structures combo: EL input, AM as working graph DS, AL output (in hash format); all operations must be O(V) or better 104 7.3
chopwood chopwood 2.4a, Graph Data Structures Prüfer sequence; use priority_queue 258 3.5
traveltheskies traveltheskies 2.4a, Graph Data Structures (graph) DS manipulation; an array of ALs (one per each day); simulate the number of people day by day 188 3.2
almostunionfind almostunionfind 2.4b, Union-Find new operation: move; idea: do not destroy the parent array structure; also available at UVa 11987 - Almost Union-Find 618 7.0
control control 2.4b, Union-Find LA 7480 - Singapore15; simulation of UFDS; size of set; number of disjoint sets 424 4.6
ladice ladice 2.4b, Union-Find size of set; decrement one per usage 615 2.8
unionfind unionfind 2.4b, Union-Find basic UFDS; similar to UVa 00793 1086 4.8
fenwick fenwick 2.4c, Tree-related DS basic Fenwick Tree; use long long 695 4.5
justforsidekicks justforsidekicks 2.4c, Tree-related DS use six Fenwick Trees, one for each gem type 359 3.8
moviecollection moviecollection 2.4c, Tree-related DS LA 5902 - NorthWesternEurope11; not a stack but a dynamic RSQ problem; also available at UVa 01513 - Movie collection 547 5.5
supercomputer supercomputer 2.4c, Tree-related DS easy problem if we use Fenwick Tree 760 3.8
cardtrick2 cardtrick2 3.2a, Pre-calculate-able n <= 13, we can simulate the process using queue and precalculate all 13 possible answers 869 1.6
foolingaround foolingaround 3.2a, Pre-calculate-able there are only 379 different values of N where Bob wins; pre-calculateable 117 5.8
sgcoin sgcoin 3.2a, Pre-calculate-able we can either brute force short string message; precompute all possible hash values; or come up with O(1) solution 271 2.4
blackfriday blackfriday 3.2b, Iterative (Two Loops) 2D nested loops; frequency counting 2384 2.2
closestsums closestsums 3.2b, Iterative (Two Loops) sort and then do O(n^2) pairings; also available at UVa 10487 - Closest Sums 1105 2.9
golombrulers golombrulers 3.2b, Iterative (Two Loops) 2D nested loops; additional 1D loops for checking 297 3.2
cudoviste cudoviste 3.2c, Three+ Nested Loops, E 4 nested loops; the inner loops is just 2x2; 5 possibilities of crushed cars; skip 2x2 area that contains building 1194 1.4
npuzzle npuzzle 3.2c, Three+ Nested Loops, E 4 nested loops; easy 683 2.2
set set 3.2c, Three+ Nested Loops, E 4 nested loops; easy 364 1.8
calculatingdartscores calculatingdartscores 3.2d, Three+ Nested Loops, H 6 nested loops but easy; see if a*i +b*j + c*k == n 752 2.8
lektira lektira 3.2d, Three+ Nested Loops, H 2 nested loops to try all 2 cutting points plus 1 more loop to actually do the reversing of sub words 376 3.2
tautology tautology 3.2d, Three+ Nested Loops, H try all 2^5 = 32 values with pruning; also available at UVa 11108 - Tautology 160 3.4
dancerecital dancerecital 3.2e, Iterative (Permutation) try all R! permutations; compare adjacent routines 274 4.2
dreamer dreamer 3.2e, Iterative (Permutation) try all 8! permutations of digits; check if the date is valid; output earliest valid date 406 2.0
veci veci 3.2e, Iterative (Permutation) try all permutations; get the one that is larger than X 1193 1.8
geppetto geppetto 3.2f, Iterative (Combination) try all 2^N subsets of ingredients 305 3.3
squaredeal squaredeal 3.2f, Iterative (Combination) try all 3! permutations of rectangles and try all 2^3 combinations of rectangle orientations; test figure 1.a and 1.b co... 232 4.6
zagrade zagrade 3.2f, Iterative (Combination) try all subsets of bracket pairs to be removed 298 3.1
communication communication 3.2g, Try All Answers try all possible bytes; apply the bitmask formula 764 2.0
flexible flexible 3.2g, Try All Answers try all possible answers 2354 1.7
islands islands 3.2g, Try All Answers try all possible subsets; prune the non-contiguous ones (only 55 valid bitmasks between [0..1023]); check the 'island' p... 443 2.6
walls walls 3.2g, Try All Answers try whether the answer is 1/2/3/4; or Impossible; use up to 4 nested loops 513 4.0
easiest easiest 3.2h, Math Simulation, Easier complete search; sum of digit 3991 1.6
growlinggears growlinggears 3.2h, Math Simulation, Easier physics of parabola; derivation; try all gears 496 2.4
trollhunt trollhunt 3.2h, Math Simulation, Easier brute force; simple 976 2.6
videospeedup videospeedup 3.2h, Math Simulation, Easier brute force; simple for loop; do as asked 298 2.0
crackingrsa crackingrsa 3.2i, Math Simulation, Harder a bit number theory; solvable with complete search 258 2.3
falling falling 3.2i, Math Simulation, Harder rework the formula; complete search up to sqrt(D) 588 3.1
thanosthehero thanosthehero 3.2i, Math Simulation, Harder for-loop from backwards 320 3.9
eenymeeny eenymeeny 3.2j, Josephus Problem Josephus problem; small n; just simulate 492 1.7
musicalchairs musicalchairs 3.2j, Josephus Problem Josephus variant; brute force 139 4.0
toys toys 3.2j, Josephus Problem use general case Josephus recurrence 142 4.5
goodmorning goodmorning 3.2k, Backtracking (Easier) we can use backtracking to generate all possible (small) numbers that can be pressed according to the constraints 347 2.7
natjecanje natjecanje 3.2k, Backtracking (Easier) 4 options for each team with kayak: do nothing, pass to left (if damaged), keep to self (if damaged), pass to right (if ... 701 2.5
paintings paintings 3.2k, Backtracking (Easier) try all possible paintings based on Catherine's preference; skip hideous color pairs 162 3.6
dobra dobra 3.2l, Backtracking (Harder) try all possible 3^n changes of '_' (to a vowel, an 'L', or other consonant not 'L'); prune invalid states; count valid ... 44 3.9
fruitbaskets fruitbaskets 3.2l, Backtracking (Harder) interesting backtracking problem; compute the small numbers < 200; output all minus this value computed via backtrack... 493 4.1
pagelayout pagelayout 3.2l, Backtracking (Harder) a bit of geometry; O(2^n imes n^2 iterative bitmask will TLE; need to use recursive backtracking with pruning 84 5.1
firefly firefly 3.3a, Binary Search sort stalactites vs stalagmites separately; brute force height; binary search the obstacles hit 323 4.0
outofsorts outofsorts 3.3a, Binary Search do O(log n) binary searches on unsorted array n times 107 3.7
roompainting roompainting 3.3a, Binary Search sort the cans at shop (can be used more than once); use lower_bound for what Joe needs at shop 416 3.8
carefulascent carefulascent 3.3b, Bisection and BSTA, E BSTA + Physics simulation 558 1.8
freeweights freeweights 3.3b, Bisection and BSTA, E BSTA + simulation; Mathematical observation 356 4.5
monk monk 3.3b, Bisection and BSTA, E BSTA + simulation; cool 86 3.3
suspensionbridges suspensionbridges 3.3b, Bisection and BSTA, E BSTA + Maths; be careful of precision error 409 4.6
a1paper a1paper 3.3c, Ternary Search & Others division of A1 paper is a kind of DnC principle 1212 3.9
ceiling ceiling 3.3c, Ternary Search & Others LA 7578 - WorldFinals Phuket16; BST insertion then tree equality check; also available at UVa 01738 - Ceiling Function 1871 1.9
goingtoseed goingtoseed 3.3c, Ternary Search & Others divide to search into four regions; extension of binary/ternary search concept 156 6.2
classrooms classrooms 3.4a, Greedy (Classical) variant of interval covering; multiple rooms 229 5.9
froshweek2 froshweek2 3.4a, Greedy (Classical) greedy; sort first; similar to Dragon of Loowater; greedy matching 489 2.3
squarepegs squarepegs 3.4a, Greedy (Classical) convert square to circular; sort; greedy matching 265 3.1
icpcteamselection icpcteamselection 3.4b, Involving Sorting, E greedy; sorting 586 3.0
minimumscalar minimumscalar 3.4b, Involving Sorting, E greedy; sorting 1202 2.3
shopaholic shopaholic 3.4b, Involving Sorting, E greedy; sorting 959 2.4
airconditioned airconditioned 3.4c, Involving Sorting, H greedy; sorting 1116 3.9
birds birds 3.4c, Involving Sorting, H greedy; sorting 566 3.5
delivery delivery 3.4c, Involving Sorting, H greedy; sorting 253 3.3
ballotboxes ballotboxes 3.4d, Involving PQ greedy; priority queue 776 4.4
canvas canvas 3.4d, Involving PQ greedy; priority queue 214 3.5
vegetables vegetables 3.4d, Involving PQ greedy; priority queue 347 3.4
workstations workstations 3.4d, Involving PQ greedy; priority queue 1110 3.6
ants ants 3.4e, Non Classical, Easier greedy; also available at UVa 10714 - Ants 1145 2.5
bank bank 3.4e, Non Classical, Easier greedy 2389 2.6
marblestree marblestree 3.4e, Non Classical, Easier greedy; also available at UVa 10672 - Marbles on a tree 258 3.0
dvds dvds 3.4f, Non Classical, Harder greedy 731 2.9
stockbroker stockbroker 3.4f, Non Classical, Harder greedy 578 3.4
virus virus 3.4f, Non Classical, Harder greedy 753 3.6
commercials commercials 3.5a, Max 1D/2D Range Sum transform each input by -P; Kadane's algorithm 1570 2.0
prozor prozor 3.5a, Max 1D/2D Range Sum 2D range sum with fix range; output formatting 558 1.6
sellingspatulas sellingspatulas 3.5a, Max 1D/2D Range Sum -8 per time slot initially; read sale data; 1D range sum; complete search 109 8.0
increasingsubsequence increasingsubsequence 3.5b, LIS LIS; n ≤ 200$; print lexicographically smallest solution, 99% similar to 'longincsubseq' 352 4.1
nesteddolls nesteddolls 3.5b, LIS sort in one dimension; Dilworth's theorem; LIS in the other; also available at UVa 11368 - Nested Dolls 115 7.1
trainsorting trainsorting 3.5b, LIS max(LIS(i)+LDS(i)-1), ∀i ∈ [0...n-1]; also available at UVa 11456 522 5.4
knapsack knapsack 3.5c, 0-1 KNAPSACK basic DP KNAPSACK; print the solution 687 4.8
orders orders 3.5c, 0-1 KNAPSACK interesting KNAPSACK variant; print the solution 713 4.5
presidentialelections presidentialelections 3.5c, 0-1 KNAPSACK pre-process the input to discard non winnable states; be careful of negative total voters; then standard DP KNAPSACK 116 5.7
bagoftiles bagoftiles 3.5d, COIN-CHANGE count number of ways to do COIN-CHANGE; meet in the middle; DP combinatorics (n choose k) to find the answer for a+b 102 6.5
canonical canonical 3.5d, COIN-CHANGE complete search possible range of counter examples; do both greedy COIN-CHANGE and DP COIN-CHANGE 502 5.7
exactchange2 exactchange2 3.5d, COIN-CHANGE a variation to the Coin-Change problem; also available at UVa 11517 - Exact Change 708 5.4
beepers beepers 3.5e, TSP DP or recursive backtracking with sufficient pruning; also available at UVa 10496 - Collecting Beepers 196 4.6
bustour bustour 3.5e, TSP LA 6028 - WorldFinals Warsaw12; DP TSP variant; also available at UVa 01281 - Bus Tour 124 6.1
cycleseasy cycleseasy 3.5e, TSP Count number of HAMILTONIAN-TOURs 108 4.1
errands errands 3.5e, TSP map location names to integer indices; DP TSP 51 7.0
nikola nikola 3.5f, DP level 1 s: (pos, last_jump); t: jump forward or backward 295 3.6
spiderman spiderman 3.5f, DP level 1 simple DP; go up or down; print solution 1010 3.9
ticketpricing ticketpricing 3.5f, DP level 1 LA 6867 - Rocky Mountain15; similar with UVa 11450 discussed in this book; real life problem; print (the first) part of ... 138 4.9
kutevi kutevi 3.5g, DP level 2 s: (360 integer degrees) 170 2.6
tight tight 3.5g, DP level 2 s: (i, j); #tight words of length i that end in digit j divided by #words: (k+1)^n; also available at UVa 10081 - Tight ... 100 3.5
walrusweights walrusweights 3.5g, DP level 2 backtracking with memoization 570 3.8
dominoes2 dominoes2 4.2a, Finding CCs unlike UVa 11504, we treat SCCs as CCs; also available at UVa 11518 - Dominos 2 599 3.3
reachableroads reachableroads 4.2a, Finding CCs report number of CC-1 892 2.1
terraces terraces 4.2a, Finding CCs group cells with similar height together; if it cannot flow to any other component with lower height, add the size of th... 339 3.6
wheresmyinternet wheresmyinternet 4.2a, Finding CCs check connectivity to vertex 1 1716 3.7
amoebas amoebas 4.2b, Flood Fill, Easier easy floodfill 1079 1.8
countingstars countingstars 4.2b, Flood Fill, Easier basic flood fill problem; count CCs 1494 2.7
gold gold 4.2b, Flood Fill, Easier flood fill with extra blocking constraint; also available at UVa 11561 - Getting Gold 735 2.2
10kindsofpeople 10kindsofpeople 4.2c, Flood Fill, Harder intelligent flood fill; just run once to avoid TLE as there are many queries 2380 3.9
coast coast 4.2c, Flood Fill, Harder intelligent flood fill; just run once to avoid TLE as there are many queries 1339 3.2
islands3 islands3 4.2c, Flood Fill, Harder optimistic flood fill; assume all Cs are Ls 936 2.1
brexit brexit 4.2d, Topological Sort toposort; chain reaction; modified Kahn's algorithm 826 3.6
builddeps builddeps 4.2d, Topological Sort the graph is acyclic; toposort with DFS from the changed file 626 4.7
conservation conservation 4.2d, Topological Sort modified Kahn's algorithm; greedily process all steps in a certain lab before alternating to the other lab 133 4.2
pickupsticks pickupsticks 4.2d, Topological Sort cycle check + toposort if DAG; also available at item UVa 11686 - Pick up sticks 373 4.7
hoppers hoppers 4.2e, Graph Properties Check the answer is number of CC-1 if there is at least one non-bipartite component in the graph; or number of CC otherwise 234 3.9
molekule molekule 4.2e, Graph Properties Check undirected tree is also Bipartite/bi-colorable; bi-color it with 0 and 1; direct all edges from 0 to 1 (or vice versa) 175 3.5
runningmom runningmom 4.2e, Graph Properties Check find a cycle in a directed graph 591 3.8
torn2pieces torn2pieces 4.2e, Graph Properties Check construct graph from strings; traversal from source to target; reachability check; print path 1115 3.6
birthday birthday 4.2f, Cut Vertices/Bridges check if the input graph contains any bridge; N is small though so weaker solution can still be accepted 323 4.3
caveexploration caveexploration 4.2f, Cut Vertices/Bridges find size of bi-connected components that contains vertex 0; identify the bridges 306 3.4
intercept intercept 4.2f, Cut Vertices/Bridges Articulation Points in SSSP Spanning DAG; clever modification of Dijkstra's 112 6.6
cantinaofbabel cantinaofbabel 4.2g, Finding SCCs build directed graph 'can_speak'; compute the largest SCC of 'can_speak'; keep this largest SCC 379 3.5
dominos dominos 4.2g, Finding SCCs count the number of SCCs without incoming edge from a vertex outside that SCC; also available at UVa 11504 - Dominos 248 6.2
equivalences equivalences 4.2g, Finding SCCs contract input directed graph into SCCs; count SCCs that have in-/out-degrees = 0; report the max 281 5.4
faultyrobot faultyrobot 4.2h, Really Ad Hoc interesting graph traversal variant 182 4.5
promotions promotions 4.2h, Really Ad Hoc modified DFS; special graph; DAG; also available at UVa 13015 - Promotions 129 5.5
succession succession 4.2h, Really Ad Hoc (upwards) traversal of family DAG; use unordered_maps; make the founder has very large starting blood to avoid fraction 165 3.1
cats cats 4.3a, MST, Standard standard MST 456 4.1
islandhopping islandhopping 4.3a, MST, Standard MST on small complete graph 440 3.0
lostmap lostmap 4.3a, MST, Standard actually just a standard MST problem 782 2.1
minspantree minspantree 4.3a, MST, Standard very standard MST problem; check if a spanning tree is formed; also output the edges in any spanning tree in lexicograph... 862 4.0
millionairemadness millionairemadness 4.3b, MST, Variants MiniMax path problem 649 2.4
muddyhike muddyhike 4.3b, MST, Variants MiniMax path problem 209 3.9
naturereserve naturereserve 4.3b, MST, Variants Prim's algorithm from multiple sources 180 4.6
buttonbashing buttonbashing 4.4a, SSSP, BFS, Easier very similar to UVa 12160 728 3.4
grid grid 4.4a, SSSP, BFS, Easier modified BFS with step size multiplier 1026 2.8
horror horror 4.4a, SSSP, BFS, Easier SSSP from all sources = horror movies; report lowest ID with the highest unweighted SSSP distance 500 3.3
fire2 fire2 4.4b, SSSP, BFS, Harder very similar to UVa 11624 395 4.2
lost lost 4.4b, SSSP, BFS, Harder interesting twist of BFS/SSSP spanning tree 269 4.7
mallmania mallmania 4.4b, SSSP, BFS, Harder multi-sources BFS from m1; get minimum at border of m2; also available at UVa 11101 - Mall Mania 48 4.9
oceancurrents oceancurrents 4.4b, SSSP, BFS, Harder 0/1-weighted SSSP; BFS+deque; also available at UVa 11573 - Ocean Currents 118 5.4
grasshopper grasshopper 4.4c, Knight Moves BFS on implicit Knight jump graph 136 4.0
hidingplaces hidingplaces 4.4c, Knight Moves SSSP from (r, c); find cells with max distance; print 607 1.9
flowerytrails flowerytrails 4.4d, SSSP, Dijkstra, Easier Dijkstra's; record predecessor graph as there can be multiple shortest paths; also available at UVa 12878 - Flowery Trai... 305 3.9
shortestpath1 shortestpath1 4.4d, SSSP, Dijkstra, Easier very standard Dijkstra's problem 1470 3.5
shortestpath2 shortestpath2 4.4d, SSSP, Dijkstra, Easier Dijkstra's with modification; edges only available periodically; be careful with P = 0 case 423 3.9
texassummers texassummers 4.4d, SSSP, Dijkstra, Easier Dijkstra's; complete weighted graph; print path 97 4.0
blockcrusher blockcrusher 4.4e, SSSP, Dijkstra, Harder Dijkstra's from top row to bottom row (or vice versa); print path 257 5.1
emptyingbaltic emptyingbaltic 4.4e, SSSP, Dijkstra, Harder Dijkstra's variant; grow spanning tree from drain/source 287 5.4
invasion invasion 4.4e, SSSP, Dijkstra, Harder SSSP with multiple and successive sources; multiple calls of Dijkstra's (gets lighter each time if pruned properly) 46 4.3
visualgo visualgo 4.4e, SSSP, Dijkstra, Harder Dijkstra's produces SSSP spanning DAG if there are multiple shortest paths from s to t; counting paths on DAG 496 3.4
hauntedgraveyard hauntedgraveyard 4.4f, SSSP, -ve weight Bellman-Ford; negative cycle check needed 95 8.2
shortestpath3 shortestpath3 4.4f, SSSP, -ve weight Bellman-Ford; do DFS/BFS from vertices that are part of any negative cycle 524 5.1
xyzzy xyzzy 4.4f, SSSP, -ve weight check 'positive' cycle; check connectedness; also available at UVa 10557 152 6.7
allpairspath allpairspath 4.5a, APSP, Standard basic Floyd-Warshall; tricky negative cycle checks 772 5.5
importspaghetti importspaghetti 4.5a, APSP, Standard smallest cycle; print path by breaking the self-loop into i - other vertex j - i 292 5.1
transportationplanning transportationplanning 4.5a, APSP, Standard APSP; FW; for each unused edge, use it and see how much distance is reduced; get minimum; O(n^4) 65 3.9
arbitrage arbitrage 4.5b, APSP, Variants arbitrage problem; similar to UVa 00104 and 00436 324 3.3
kastenlauf kastenlauf 4.5b, APSP, Variants n ≤ 100; Warshall's transitive closure problem 713 3.8
secretchamber secretchamber 4.5b, APSP, Variants LA 8047 - WorldFinals RapidCity17; Warshall's transitive closure; also available at UVa 01757 - Secret Chamber ... 1187 2.2
fibtour fibtour 4.6a, S/Longest Paths on DAG only ~90 Fibonacci numbers not more than 10^18; LONGEST-PATH on DAG problem; special case for first two Fibonacci number... 105 6.4
mravi mravi 4.6a, S/Longest Paths on DAG reverse edge directions to change the input tree into a DAG; find longest path from leaf that contains ant to root 197 2.7
safepassage safepassage 4.6a, S/Longest Paths on DAG SSSP; implicit DAG; s: (cloak_pos, bitmask); try all ways to go back and forth between gate and dorm; report minimum 387 4.9
robotsonagrid robotsonagrid 4.6b, Counting Paths, Easier counting paths in grid (implicit DAG); DP 147 4.3
runningsteps runningsteps 4.6b, Counting Paths, Easier LA 7360 - Greater NY15; s: (leg, l2, r2, l1, r1); t: left/right leg 1/2 steps; use unordered_map as memo table; use prun... 168 2.6
scenes scenes 4.6b, Counting Paths, Easier s: (pos, ribbon_left); t: try all possible heights; ignore the flat scenes first and subtract those cases at the end 407 3.6
cardmagic cardmagic 4.6c, Conversion to DAG s: (deck, tgt_left); t: val 1 to K ≤ tgt_left 133 3.9
drinkresponsibly drinkresponsibly 4.6c, Conversion to DAG s: (cur_drink, money_left, u_left); be careful with precision errors; print solution 98 4.2
maximizingwinnings maximizingwinnings 4.6c, Conversion to DAG separate the maximizing and minimizing problem; s: (cur_room, turns_left); t: go to other room or stay 193 3.9
adjoin adjoin 4.6d, Tree the key parts are finding tree diameter and its center (along that diameter); also see UVa 11695 373 5.3
flight flight 4.6d, Tree cut the worst edge along the tree diameter; link two centers; also available at UVa 11695 - Flight Planning 46 6.3
tourists tourists 4.6d, Tree APSP on Tree (special requirements); LCA 431 3.8
bookclub bookclub 4.6e, Bipartite Graph check if perfect MCBM is possible 307 4.5
escapeplan escapeplan 4.6e, Bipartite Graph left set: robots; right set: holes; 3 version of similar bipartite graphs; MCBM 98 5.7
flippingcards flippingcards 4.6e, Bipartite Graph left set: n card numbers; right set: 2*n picture numbers; possible if MCBM = n; need fast algorithm 169 7.0
catenyms catenyms 4.6f, Eulerian Graph Euler graph property check; 26 vertices; directed non simple graph; printing the Euler tour in lexicographic order 67 7.1
eulerianpath eulerianpath 4.6f, Eulerian Graph Euler graph property check; directed graph; printing the Euler tour 219 5.6
railroad2 railroad2 4.6f, Eulerian Graph x-shaped level junctions have even degrees - ignore X; y-shaped switches have degree 3 - Y has to be even 2188 1.4
averageshard averageshard 5.2a, Finding Formula, Easier find O(n) formula; also see Kattis - averageseasy 605 2.6
bishops bishops 5.2a, Finding Formula, Easier chess pattern involving bishops; from IPSC 2004 1185 2.2
crne crne 5.2a, Finding Formula, Easier simulate cutting process on small numbers; get formula 477 2.5
twostones twostones 5.2a, Finding Formula, Easier just check odd or even 15317 1.3
mortgage mortgage 5.2b, Finding Formula, Harder geometric progression; divergent but finite; special case when r = 1.0 (no interest) 51 7.9
neighborhoodwatch neighborhoodwatch 5.2b, Finding Formula, Harder sum of AP; inclusion-exclusion 319 3.1
nine nine 5.2b, Finding Formula, Harder find the required formula 681 3.2
allaboutthatbase allaboutthatbase 5.2c, Base Number Conversion check base 1 to 36; base 1 is special; Big Integer 927 2.9
arithmetic arithmetic 5.2c, Base Number Conversion conversion of octal (per 4 bits) to hexa (per 3 bits); be careful with leading zeroes 726 3.9
basicremains basicremains 5.2c, Base Number Conversion also involving Big Integer modulo; also available at UVa 10551 - Basic Remains 174 3.4
oktalni oktalni 5.2c, Base Number Conversion convert each 3-bits of binary strings to octal; Big Integer 634 1.8
aliennumbers aliennumbers 5.2d, Base Number Variants source base to decimal; decimal to target base 1050 2.1
ignore ignore 5.2d, Base Number Variants actually a base 7 conversion problem as only 7 digits are meaningful when rotated 268 3.2
mixedbasearithmetic mixedbasearithmetic 5.2d, Base Number Variants mix of base 10 and two versions of base 26 54 5.9
candlebox candlebox 5.2e, Number Systems/Seqs sum of arithmetic series [1..N]; -6 for Rita or -3 for Theo; brute force Rita's age; also available at UVa 13161 - Candl... 448 2.6
collatz collatz 5.2e, Number Systems/Seqs similar to UVa 00694; just do as asked 757 3.7
permutedarithmeticsequence permutedarithmeticsequence 5.2e, Number Systems/Seqs sort differences of adjacent items 1262 2.0
rationalsequence rationalsequence 5.2e, Number Systems/Seqs pattern finding; tree traversal on a special tree 458 4.6
cokolada cokolada 5.2f, Log, Exp, Pow the answers involve powers of two and a simulation 605 2.2
factstone factstone 5.2f, Log, Exp, Pow use logarithm; power; also available at UVa 10916 - Factstone Benchmark 200 3.6
thebackslashproblem thebackslashproblem 5.2f, Log, Exp, Pow actually power of two 349 2.2
beehouseperimeter beehouseperimeter 5.2g, Grid transform the hexagonal grid like Kattis - honeyheist; flood fill from outside Alice's house; count #walls touched 155 4.0
honeyheist honeyheist 5.2g, Grid transform the hexagonal grid input into 2D grid first; then run SSSP on unweighted graph; BFS 135 3.8
maptiles2 maptiles2 5.2g, Grid simple conversion between two grid indexing systems 1338 1.6
ada ada 5.2h, Polynomial polynomial problem; apply the given procedure recursively 346 2.8
curvyblocks curvyblocks 5.2h, Polynomial differentiate degree 3 to degree 2 polynomial; get roots of quadratic equation; the two blocks will touch at either root... 89 4.3
plot plot 5.2h, Polynomial analyze the given pseudocode; the required pattern involves Binomial Coefficients 210 2.5
deadfraction deadfraction 5.2i, Fractions try every single possible repeating decimals; also available at UVa 10555 - Dead Fraction 153 4.9
fraction fraction 5.2i, Fractions continued fraction to normal fraction and vice versa 154 3.8
mixedfractions mixedfractions 5.2i, Fractions convert fraction to mixed fraction 5154 1.5
thermostat thermostat 5.2i, Fractions convert one temperature to another; use fraction; use Java BigInteger; gcd 81 3.4
matrix matrix 5.2j, Really Ad Hoc use simple linear algebra; one special case when c = 0 784 3.1
trip trip 5.2j, Really Ad Hoc be careful with precision error; also available at UVa 10137 - The Trip 103 5.5
yoda yoda 5.2j, Really Ad Hoc ad hoc; 9 digits comparison 1607 2.1
enlarginghashtables enlarginghashtables 5.3a, Prime Numbers use sieve up to 40 000; prime test numbers greater than 2n; check primality of n itself 448 3.4
primesieve primesieve 5.3a, Prime Numbers use sieve up to 10^8; it is fast enough 865 4.5
reseto reseto 5.3a, Prime Numbers sieve of Eratosthenes until the k-th crossing 460 2.7
flowergarden flowergarden 5.3b, (Prob) Prime Testing Euclidean dist; small prime check; use isProbablePrime; simulation; faster solutions exist 317 4.4
goldbach2 goldbach2 5.3b, (Prob) Prime Testing simple brute force problem; use isProbablePrime; faster solutions exist 1219 2.7
primes2 primes2 5.3b, (Prob) Prime Testing convert input to either base 2/8/10/16; skip those that cause NumberFormatException error; use isProbablePrime test and ... 289 4.7
pseudoprime pseudoprime 5.3b, (Prob) Prime Testing yes if !isPrime(p) && a.modPow(p, p) = a; Big Integer; also available at UVa 11287 - Pseudoprime Numbers 347 3.5
pascal pascal 5.3c, Finding Prime Factors find lowest prime factor of N; special case: N = 1 351 3.8
primalrepresentation primalrepresentation 5.3c, Finding Prime Factors factorization problem; use sieve to avoid TLE; use long long; 231-1 is a prime 258 5.4
primereduction primereduction 5.3c, Finding Prime Factors factorization problem 465 3.9
almostperfect almostperfect 5.3d, Prime Factors Functions sumDiv(N)-N; minor variation 1507 3.2
divisors divisors 5.3d, Prime Factors Functions return numDiv(nCk); but do not compute nCk directly; work with its prime factors 208 5.2
relatives relatives 5.3d, Prime Factors Functions EulerPhi(N); also available at UVa 10299 - Relatives 231 3.8
data data 5.3e, Modified Sieve numDiffPF(V) for V up to N x 1000; Brute force combination/all subsets; DP Subset 68 5.9
farey farey 5.3e, Modified Sieve pre-calculate EulerPhi(N); do prefix sum (1D RSQ) of EulerPhi(N) from 1 to each N; the answer is related to this value 257 3.6
nonprimefactors nonprimefactors 5.3e, Modified Sieve numDiv(i) - numDiffPF(i) ∀i in the range; the I/O files are large so Buffered I/O speed is needed 389 5.6
jackpot jackpot 5.3f, GCD and/or LCM similar to Kattis - smallestmultiple; use Java BigInteger or other faster solutions 379 3.2
prsteni prsteni 5.3f, GCD and/or LCM GCD of first circle radius with subsequent circle radiuses 993 1.6
smallestmultiple smallestmultiple 5.3f, GCD and/or LCM simple LCMs of all numbers; use Java BigInteger to be safe 335 3.5
inversefactorial inversefactorial 5.3g, Factorial good problem; number of digits in factorial 1059 5.3
loworderzeros loworderzeros 5.3g, Factorial last non zero digit of factorial; classic 288 4.2
namethatpermutation namethatpermutation 5.3g, Factorial permutation number; involving factorial 154 4.8
tutorial tutorial 5.3g, Factorial factorial is just part of the problem; pruning 1249 2.8
consecutivesums consecutivesums 5.3h, Working with PFs work with factor; sum of Arithmetic Progression series 239 5.2
factovisors factovisors 5.3h, Working with PFs factorize m; see if it has support in n!; Legendre's formula; also available at UVa 10139 - Factovisors 373 6.4
fundamentalneighbors fundamentalneighbors 5.3h, Working with PFs reverse prime power notation 237 4.5
iks iks 5.3h, Working with PFs sieve of Eratosthenes; prime factorize each number; spread the factors around to maximize final GCD/minimize total opera... 115 3.0
anothercandies anothercandies 5.3i, Modular Arithmetic simple modular arithmetic 1843 2.7
ones ones 5.3i, Modular Arithmetic no factor of 2 and 5 implies that there is no trailing zero; also available at UVa 10127 - Ones 567 4.6
threedigits threedigits 5.3i, Modular Arithmetic simulate factorial computation; remove trailing zeroes; keep many last few non-zero digits using modulo 289 5.9
candydistribution candydistribution 5.3j, Extended Euclid the problem boils down to finding C-1 (mod K); be careful when the answer is "IMPOSSIBLE" or ≤ K 199 4.9
modulararithmetic modulararithmetic 5.3j, Extended Euclid the division operation requires modular inverse; use Extended Euclidean algorithm 333 2.9
soyoulikeyourfoodhot soyoulikeyourfoodhot 5.3j, Extended Euclid Linear Diophantine Equation; still solvable with brute force 103 5.2
divisible divisible 5.3k, Divisibility Test divisibility; linear pass algorithm 327 4.3
meowfactor meowfactor 5.3k, Divisibility Test divisibility test of 9^ans; small range of ans 310 3.5
thinkingofanumber thinkingofanumber 5.3k, Divisibility Test simple range; use min/max properly; then small divisibility tests 379 3.8
anti11 anti11 5.4a, Fibonacci Numbers this problem degenerates into a modified Fibonacci numbers 518 2.7
batmanacci batmanacci 5.4a, Fibonacci Numbers Fibonacci; observation on N; Divide and Conquer 331 3.8
rijeci rijeci 5.4a, Fibonacci Numbers simple simulation with a single loop; Fibonacci 2478 1.5
election election 5.4b, Binomial Coefficients compute the answers with help of binomial coefficients 213 6.2
lockedtreasure lockedtreasure 5.4b, Binomial Coefficients the answer is nCm-1 321 2.8
oddbinom oddbinom 5.4b, Binomial Coefficients OEIS A006046 245 3.5
catalan catalan 5.4c, Catalan Numbers basic Catalan Numbers 521 3.6
catalansquare catalansquare 5.4c, Catalan Numbers Catalan Numbers++; follow the description 507 3.5
fiat fiat 5.4c, Catalan Numbers N-th Catalan Number; use Fermat's little theorem 75 6.7
character character 5.4d, Others, Easier OEIS A000295 841 2.4
honey honey 5.4d, Others, Easier OEIS A002898 415 2.4
integerdivision integerdivision 5.4d, Others, Easier count frequencies of each remainder of [0..d-1]; add C(freq, 2) per such remainder 242 3.3
anagramcounting anagramcounting 5.4e, Others, Harder use Big Integer 1117 3.1
incognito incognito 5.4e, Others, Harder count frequencies; combinatorics; minus one 791 2.7
tritiling tritiling 5.4e, Others, Harder there are two related recurrences here; also available at UVa 10918 - Tri Tiling 465 2.1
bobby bobby 5.5a, Probability, Easier computation of expected value 618 2.8
dicebetting dicebetting 5.5a, Probability, Easier s: (dice_left, distinct_numbers_so_far); each throw can increase distinct_numbers_so_far or not 261 3.3
odds odds 5.5a, Probability, Easier complete search; simple probability 142 2.5
anthony anthony 5.5b, Probability, Harder DP probability; need to drop one parameter (N or M) and recover it from the other one 203 5.2
goodcoalition goodcoalition 5.5b, Probability, Harder DP probability; like KNAPSACK 276 3.4
lostinthewoods lostinthewoods 5.5b, Probability, Harder simulate random walks of various lengths and distribute the probabilities per iteration; the answer will converge eventu... 77 3.1
fibonaccicycles fibonaccicycles 5.6a, Cycle Finding detect cycle of fib(n)%k using fast data structure 118 3.2
rats rats 5.6a, Cycle Finding string processing plus cycle-finding; unordered_set 92 6.3
bachetsgame bachetsgame 5.7a, Game Theory (Basic) 2 players game; Dynamic Programming; also available at UVa 10404 - Bachet's Game 724 2.1
blockgame2 blockgame2 5.7a, Game Theory (Basic) observe the pattern; 2 winnable cases if N == M and N%M == 0; only 1 move if M < N < 2M; we can always win if N &g... 314 3.2
euclidsgame euclidsgame 5.7a, Game Theory (Basic) minimax; backtracking; also available at UVa 10368 - Euclid's Game 199 4.8
linije linije 5.7a, Game Theory (Basic) game theory; check conditions on how Mirko can win and when Slavko can win; involves MCBM 39 7.9
checkingforcorrectness checkingforcorrectness 5.8a, Matrix Power Java Big Integer; one subtask uses modPow 244 4.1
porpoises porpoises 5.8a, Matrix Power Fibonacci; matrix power; modulo 268 2.9
squawk squawk 5.8a, Matrix Power count the number of paths of length L in an undirected graph after t steps that are reachable from source s 409 3.5
crackingthecode crackingthecode 6.2a, Cipher, Harder one corner case involving the 25th to 26th character determination 48 6.4
itsasecret itsasecret 6.2a, Cipher, Harder playfair cipher; 2D array; quite tedious 81 5.9
playfair playfair 6.2a, Cipher, Harder follow the description; a bit tedious; also available at UVa 11697 - Playfair Cipher 156 2.5
progressivescramble progressivescramble 6.2a, Cipher, Harder the encode part is trivial; the decode part requires a bit of thinking 977 2.1
textencryption textencryption 6.2a, Cipher, Harder convert input alphabets to UPPERCASEs; loop 305 3.2
calculator calculator 6.2b, Input Parsing (Rec) recursive parser and evaluator 351 3.3
otpor otpor 6.2b, Input Parsing (Rec) parallel vs series evaluation; write a recursive parser; or use linear pass with stack 94 4.3
polish polish 6.2b, Input Parsing (Rec) recursive parser 224 3.3
subexpression subexpression 6.2b, Input Parsing (Rec) recursive parsing; use DP; similar to https://visualgo.net/en/recursion tree versus DAG 44 5.9
apaxiaaans apaxiaaans 6.2c, Regular Expression solvable with regex 6751 1.4
hidden hidden 6.2c, Regular Expression just a careful 1D array manipulation; we can also use regex 1100 2.3
lindenmayorsystem lindenmayorsystem 6.2c, Regular Expression DAT; map char to string; simulation; max answer ≤ 30*5^5; we can also use regex 302 2.5
asciifigurerotation asciifigurerotation 6.2d, Output Formatting, H rotate the input 90 degrees clockwise; remove trailing whitespaces; tedious 521 3.5
imagedecoding imagedecoding 6.2d, Output Formatting, H simple Run-Length Encoding 321 3.4
juryjeopardy juryjeopardy 6.2d, Output Formatting, H tedious problem 309 2.3
nizovi nizovi 6.2d, Output Formatting, H formatting with indentation; not that trivial but sample input/output helps 199 3.8
phonelist phonelist 6.2e, String Comparison sort the numbers; see if num i is a prefix of num i+1 1955 4.3
rhyming rhyming 6.2e, String Comparison compare suffix of a common word with the list of other given words 296 2.5
smartphone smartphone 6.2e, String Comparison compare prefix so far with the target string and the 3 suggestions; output 1 of 4 options with shortest number of keypre... 354 2.6
irepeatmyself irepeatmyself 6.2f, Really Ad Hoc string period; complete search 380 2.4
periodicstrings periodicstrings 6.2f, Really Ad Hoc brute force; skip non divisor 299 3.0
raggedright raggedright 6.2f, Really Ad Hoc just simulate the requirement 1708 1.8
zipfslaw zipfslaw 6.2f, Really Ad Hoc sort the words to simplify this problem; also available at UVa 10126 - Zipf's Law 157 5.7
inflagrantedelicto inflagrantedelicto 6.3a, DP String, Classic k_p is always 2 (read the problem description); k_r is the LCS of the two permutations plus one; O(n log k) solution 75 4.8
pandachess pandachess 6.3a, DP String, Classic LCS of 2 permutations → LIS; O(n log k) solution; also see UVa 10635 267 6.0
princeandprincess princeandprincess 6.3a, DP String, Classic find LCS of two permutations; also available at UVa 10635 - Prince and Princess 140 6.7
exam exam 6.3b, DP String, Non Classic s: (pos, correct_left); t: either your friend is wrong or your friend is right, process accordingly; easier solution exi... 891 1.9
heritage heritage 6.3b, DP String, Non Classic s: (cur_pos); t: try all N words in dictionary; final answer modulo prime 348 5.2
hillnumbers hillnumbers 6.3b, DP String, Non Classic digit DP; s: (prev_digit, pos, is_rising, is_lower); try digit by digit 84 6.7
stringfactoring stringfactoring 6.3b, DP String, Non Classic s: the min weight of substring [i..j]; also available at UVa 11022 - String Factoring 57 5.1
geneticsearch geneticsearch 6.4a, String Matching multiple string matchings 346 2.1
powerstrings powerstrings 6.4a, String Matching find s in s+s; similar with UVa 00455; also available at UVa 10298 - Power Strings 451 5.2
quiteaproblem quiteaproblem 6.4a, String Matching trivial string matching per line 1212 2.1
scrollingsign scrollingsign 6.4a, String Matching modified string matching; complete search; also available at UVa 11576 - Scrolling Sign 238 3.1
boggle boggle 6.4b, String Matching, 2D 2D grid; backtracking 323 3.8
kinarow kinarow 6.4b, String Matching, 2D brute the top left point of each possible x or o row, then straight-line (horizontal, vertical) or two diagonals 2D stri... 107 4.6
knightsearch knightsearch 6.4b, String Matching, 2D 2D grid; backtracking or DP 425 3.2
automatictrading automatictrading 6.5a, Suffix Trie/Tree/Array Suffix Array; LCP of a range; use Sparse Table 160 5.2
buzzwords buzzwords 6.5a, Suffix Trie/Tree/Array Longest Repeated Substring that appears X times (2 ≤ X < N); also available at UVa 11855 - Buzzwords 141 5.0
suffixarrayreconstruction suffixarrayreconstruction 6.5a, Suffix Trie/Tree/Array clever creative problem involving Suffix Array concept; be careful that '*' can be more than one character 125 4.1
suffixsorting suffixsorting 6.5a, Suffix Trie/Tree/Array basic Suffix Array construction problem; be careful with terminating symbol 201 5.7
hashing hashing 6.6a, String Hashing the problem description is very clear; good rolling hash practice; or use Suffix Array+Sparse Table 142 7.3
stringmatching stringmatching 6.6a, String Hashing try Rabin-Karp or KMP 719 4.5
multigram multigram 6.7a, Anagram brute force lengths that is divisor of the original length of the string; test 221 2.8
kaleidoscopicpalindromes kaleidoscopicpalindromes 6.7b, Palindrome (Checking) test all; when you try enlarging k, the answers are actually 'small' 233 3.2
palindromesubstring palindromesubstring 6.7b, Palindrome (Checking) try all pairs of O(n^2) substrings with at least 2 characters; keep the ones that are palindrome (use DP) in a sorted se... 298 4.2
peragrams peragrams 6.7b, Palindrome (Checking) only one odd frequency character can be in the center of palindrome once; the rest need to have even frequency 1692 1.7
evilstraw evilstraw 6.7c, Palindrome (Generating) greedily match leftmost char s[0]/rightmost char s[n-1] with rightmost/leftmost matching s[i], respectively 137 3.8
names names 6.7c, Palindrome (Generating) add a letter or change a letter; complete search 368 4.0
browniepoints browniepoints 7.2a, Points points and quadrants; simple; also available at UVa 10865 - Brownie Points 154 2.3
cursethedarkness cursethedarkness 7.2a, Points Euclidean dist 596 2.2
imperfectgps imperfectgps 7.2a, Points Euclidean dist; simulation 487 4.2
hurricanedanger hurricanedanger 7.2b, Lines distance from point to line (not vector); be careful of precision error; work with integers 114 5.9
logo2 logo2 7.2b, Lines n vectors that sum to 0; given n-1 vectors, find the unknown vector; also available at UVa 11519 - Logo 2 114 5.6
platforme platforme 7.2b, Lines line segment intersection tests; N ≤ 100; complete search 210 2.7
unlockpattern unlockpattern 7.2b, Lines complete search; Euclidean dist 902 1.7
amsterdamdistance amsterdamdistance 7.2c, Circles arcs of circles; no need to model this as an SSSP problem/Dijkstra's 571 2.9
biggest biggest 7.2c, Circles find biggest area of sector using simulation; use array (not that larget) to avoid precision error 147 6.6
estimatingtheareaofacircle estimatingtheareaofacircle 7.2c, Circles PI estimation experiment 2084 1.6
ornaments ornaments 7.2c, Circles arch length plus two times tangent lengths 236 2.2
alldifferentdirections alldifferentdirections 7.2d, Triangles (Trig) use trigonometry to compute x and y displacement 446 2.6
billiard billiard 7.2d, Triangles (Trig) enlarge the billiard table; then this is solvable with atan2 856 1.6
egypt egypt 7.2d, Triangles (Trig) Pythagorean theorem/triple; also available at UVa 11854 - Egypt 862 1.9
mountainbiking mountainbiking 7.2d, Triangles (Trig) up to 4 line segments; simple trigonometry; simple Physics/Kinematic equation 216 2.8
cropeasy cropeasy 7.2e, Triangles + Circles complete search 3 points/tree; check if the center is integer 178 3.0
stickysituation stickysituation 7.2e, Triangles + Circles see if 3 sides form a triangle; see UVa 11579 675 2.7
trilemma trilemma 7.2e, Triangles + Circles triangle properties; sort the 3 sides first 225 3.6
cetvrta cetvrta 7.2f, Quadrilaterals sort the x and y points, then you will know the 4th point 4727 1.3
officespace officespace 7.2f, Quadrilaterals rectangles; small numbers; 2D Boolean arrays 143 5.5
rectanglesurrounding rectanglesurrounding 7.2f, Quadrilaterals rectangles; small; 2D Boolean arrays 187 3.8
roundedbuttons roundedbuttons 7.2f, Quadrilaterals in-rectangle/in-square test; in-4-circles tests 176 2.9
convexhull convexhull 7.3a, Polygon, Easier basic convex hull problem; be careful with duplicate points and collinear points 644 4.8
convexpolygonarea convexpolygonarea 7.3a, Polygon, Easier even more basic problem about area of polygon than Kattis - polygonarea 703 1.9
cuttingcorners cuttingcorners 7.3a, Polygon, Easier simulation of angle checks 95 3.5
robotprotection robotprotection 7.3a, Polygon, Easier simply find the area of convex hull 236 2.4
convex convex 7.3b, Polygon, Harder must understand the concept of convex polygon; a bit of mathematical insights: GCD; sort 132 6.4
pointinpolygon pointinpolygon 7.3b, Polygon, Harder in/out and on polygon 311 5.5
roberthood roberthood 7.3b, Polygon, Harder the classic furthest pair problem; use convex hull and then rotating caliper 376 4.6
airlinehub airlinehub 7.4a, 3D Geometry gcDistance; also available at UVa 10316 - Airline Hub 211 6.6
beavergnaw beavergnaw 7.4a, 3D Geometry volumes of cylinders and cones; inclusion-exclusion; also available at UVa 10297 - Beavergnaw 1210 1.4
bottles bottles 7.4a, 3D Geometry LA 6027 - WorldFinals Warsaw12; BSTA+geometric formula; also available at UVa 01280 - Curvy Little Bottles 217 3.0
flowers flowers 7.4a, 3D Geometry the key part of this problem is integration 63 4.4
movingday movingday 7.4a, 3D Geometry output volume of the largest cuboid - V 261 2.1
committeeassignment committeeassignment 8.2a, Harder Backtracking backtracking; pruning; add a member to existing committee or create a new committee; TLE with DP bitmask 68 7.4
greatswercporto greatswercporto 8.2a, Harder Backtracking use backtracking with pruning; testing up to 10! possible permutations possibly TLE 120 4.1
holeynqueensbatman holeynqueensbatman 8.2a, Harder Backtracking similar with UVa 11195 527 2.2
ecoins ecoins 8.2b, State-Space, BFS, E s: (conventional-value, infotechnological-value); BFS; also available at UVa 10306 - e-Coins 169 4.6
flipfive flipfive 8.2b, State-Space, BFS, E s: (bitmask); only 2^9 = 512 grid configurations; BFS 621 2.7
safe safe 8.2b, State-Space, BFS, E s: (convert 3x3 grid into a base 4 integer); BFS 181 3.0
keyboard keyboard 8.2c, State-Space, BFS, H LA 7155 - WorldFinals Marrakech15; s: (row, col, char_typed); also available at UVa 01714 - Keyboarding 258 5.0
robotmaze robotmaze 8.2c, State-Space, BFS, H s: (r, c, dir, steps); be careful of corner cases 87 5.7
robotturtles robotturtles 8.2c, State-Space, BFS, H s: (r, c, dir, bitmask_ice_castles); print solution; very tedious 114 4.5
bumped bumped 8.2d, State-Space, Dijkstra s: (city, has_use_free_ticket); use Dijkstra's 545 4.4
destinationunknown destinationunknown 8.2d, State-Space, Dijkstra use Dijkstra's twice; one normally; one with s: (point, has_edge_g_h_used); compare the results 101 5.6
justpassingthrough justpassingthrough 8.2d, State-Space, Dijkstra s: (r, c, n_left); Dijkstra's/SSSP on DAG 92 5.1
aspenavenue aspenavenue 8.3a, DP level 3 sort; compute tree positions; s: (l_left, r_left), t: put next tree on the left/right; also available at UVa 11555 - Asp... 223 5.8
busticket busticket 8.3a, DP level 3 s: (day_i); t: either buy daily ticket or jump to end of period ticket (use binary search to avoid TLE) 186 4.4
coke coke 8.3b, DP level 4 drop parameter n1; recover it from b (number of coke bought), n5, and n10; also available at UVa 10626 - Buying Coke 304 5.6
companypicnic companypicnic 8.3b, DP level 4 s: (name, has_been_matched); DP weighted matching (both cardinality and weight) on Tree 200 5.0
rollercoasterfun rollercoasterfun 8.3b, DP level 4 s: (T); split DPs when b = 0 and when b != 0 101 7.7
countcircuits countcircuits 8.3c, Counting Paths, Harder s: (id, cur_x, cur_y); t: skip or use this vector; use offset technique to avoid negative indices 278 5.8
favourable favourable 8.3c, Counting Paths, Harder s: (cur_page); t: jump to one of the 3 sections 304 4.5
pachinkoprobability pachinkoprobability 8.3c, Counting Paths, Harder s: (pos); DAG modeling; long long 113 5.8
hidingchickens hidingchickens 8.3d, DP with Bitmask weighted MCM; small complete weighted graph; make fox goes back to the killing spot first after hiding one or two chicke... 89 5.7
narrowartgallery narrowartgallery 8.3d, DP with Bitmask interesting DP; s: (row, state_of_prev_row, k_left) 1417 2.8
pebblesolitaire2 pebblesolitaire2 8.3d, DP with Bitmask backtracking suffices for Kattis - pebblesolitair; but this version needs extra memoization 400 3.6
maxflow maxflow 8.4a, Network Flow, Standard standard max flow problem for practice; print edges used in the max flow 531 6.3
mazemovement mazemovement 8.4a, Network Flow, Standard use gcd for all pairs of vertices to construct the flow graph; then it is just a standard max flow problem 135 4.4
mincut mincut 8.4a, Network Flow, Standard standard min cut problem for practice; print vertices reachable from source s after max flow 293 4.1
avoidingtheapocalypse avoidingtheapocalypse 8.4b, Network Flow, Variants interesting max flow modeling; blow the vertices based on time 191 4.4
thekingofthenorth thekingofthenorth 8.4b, Network Flow, Variants interesting min cut problem 193 5.0
transportation transportation 8.4b, Network Flow, Variants max flow with vertex capacities 165 5.6
equalsumseasy equalsumseasy 8.6a, NP-hard/C, small, E PARTITION; generate all possible subsets with bitmask; use set to record which sums have been computed 474 2.3
flowfree flowfree 8.6a, NP-hard/C, small, E brute force combination 3^10 or 4^8; then LONGEST-PATH problem on non DAG between two end points of the same color 109 4.4
font font 8.6a, NP-hard/C, small, E count number of possible SET-COVERs; use 2^N backtracking; but use bitmask to represent small set of covered letters 199 4.2
socialadvertising socialadvertising 8.6a, NP-hard/C, small, E MIN-DOMINATING-SET/MIN-SET-COVER; n ≤ 20; use compact Adjacency Matrix technique 59 5.1
beanbag beanbag 8.6b, NP-hard/C, small, H SET-COVER problem; T farmers can collude to give Jack the hardest possible subset of beans to be given freely to Jack 119 4.9
busplanning busplanning 8.6b, NP-hard/C, small, H MIN-CLIQUE-COVER; DP bitmask over sets 91 5.4
programmingteamselection programmingteamselection 8.6b, NP-hard/C, small, H PARTITION-INTO-TRIANGLES; prune if #students % 3 != 0; generate up to m/3 teams; backtracking with memo 64 7.2
bilateral bilateral 8.6c, NP-hard/C, special, E MIN-VERTEX-COVER on Bipartite Graph; MCBM; Konig's theorem that can handle the 1009 case correctly 43 6.5
europeantrip europeantrip 8.6c, NP-hard/C, special, E STEINER-TREE with 3 terminal vertices and up to 1 Steiner point; we can use two ternary searches 297 3.3
reactivity reactivity 8.6c, NP-hard/C, special, E verify if a HAMILTONIAN-PATH exists in the DAG; find one topological sort of the DAG; verify if it is the only one in li... 280 4.0
jailbreak jailbreak 8.6d, NP-hard/C, special, H STEINER-TREE; grid; BFS from 3 vertices: 'outside' and 2 prisoners (open doors independently or meet a Steiner point fir... 130 4.8
ridofcoins ridofcoins 8.6d, NP-hard/C, special, H not the minimizing COIN-CHANGE problem; but the maximizing one; greedy pruning; complete search on much smaller instance 94 7.9
wedding wedding 8.6d, NP-hard/C, special, H can be modeled as a 2-SAT problem; also available at UVa 11294 - Wedding 36 6.7
arrivingontime arrivingontime 8.7a, BSTA+Other, Easier BSTA: the latest starting time; use Dijkstra's to compute whether we can still arrive at meeting point on time 79 6.3
charlesincharge charlesincharge 8.7a, BSTA+Other, Easier BSTA: max edge that Charles can use; SSSP from 1 to $N$ passing through edges that do not exceed that; is it OK? 149 4.8
programmingtutors programmingtutors 8.7a, BSTA+Other, Easier +perfect MCBM 161 3.7
catandmice catandmice 8.7b, BSTA+Other, Harder BSTA: the initial velocity of Cartesian Cat; DP TSP to verify if the cat can catch all mice in the shortest possible tim... 141 6.8
enemyterritory enemyterritory 8.7b, BSTA+Other, Harder MSSP from all enemy vertices; BSTA, run BFS from (xi, yi) to (xr, yr) avoiding vertices that are too close to any enemy 66 4.2
gravamen gravamen 8.7b, BSTA+Other, Harder BSTA + max flow 45 6.1
wifi wifi 8.7b, BSTA+Other, Harder +greedy; also available at UVa 11516 - WiFi 214 4.3
bing bing 8.7c, Fast DS+Other, Easier map all prefixes to frequencies using Hash Table; or use Trie 1061 3.6
busnumbers2 busnumbers2 8.7c, Fast DS+Other, Easier complete search; use unordered_map 377 3.0
selfsimilarstrings selfsimilarstrings 8.7c, Fast DS+Other, Easier complete search as the string is short; frequency counting; use unordered_map; repetition 181 3.5
undetected undetected 8.7c, Fast DS+Other, Easier brute force; simple geometry; UFDS 274 3.9
dictionaryattack dictionaryattack 8.7d, Fast DS+Other, Harder time limit is generous; you can generate all possible password with just 3 swaps; store in sets 101 7.0
doublets doublets 8.7d, Fast DS+Other, Harder s: (string); BFS; use trie to quickly identify neighbor that is one Hamming distance away; also available at UVa 10150 -... 56 8.3
magicallights magicallights 8.7d, Fast DS+Other, Harder LA 7487 - Singapore15; flatten the tree with DFS; use Fenwick Tree for Range Odd Query; use long long 309 5.4
sparklesseven sparklesseven 8.7d, Fast DS+Other, Harder seven nested loops with fast DS 52 5.7
collidingtraffic collidingtraffic 8.7e, Geometry+CS try all pairs of boats; 0.0 if one pair collide; or, use a quadratic equation; also available at UVa 11574 - Colliding T... 48 5.0
cranes cranes 8.7e, Geometry+CS circle-circle intersection; backtracking or brute force subsets with bitmask; also available at UVa 11515 - Cranes 137 3.8
doggopher doggopher 8.7e, Geometry+CS complete search; Euclidean distance dist; also available at UVa 10310 - Dog and Gopher 119 2.5
findinglines findinglines 8.7f, Geometry+Other randomly pick two points; there is a good chance that 20% or more points are on that line defined by those two points 209 6.3
humancannonball humancannonball 8.7f, Geometry+Other build the travel time graph with Euclidean distance computations; use Floyd-Warshall 757 2.2
walkway walkway 8.7f, Geometry+Other we can build the graph and compute area of trapezoid using simple geometry; SSSP on weighted graph; Dijkstra's 190 3.4
crowdcontrol crowdcontrol 8.7g, Graph+Other maximin path problem; MST; DFS from train station to BAPC; block unused edges 100 3.8
gears2 gears2 8.7g, Graph+Other graph reachability test; cycle with equal ratio is actually OK; math fraction 95 3.7
gridmst gridmst 8.7g, Graph+Other Singapore15 preliminary; rectilinear MST problem; small 2D grid; multi-sources BFS to construct short edges; Kruskal's t... 245 7.4
emergency emergency 8.7h, Mathematics+Other the problem is posed as an SSSP problem on special graph; but turns out a simple formula solves the problem; Big Integer 319 3.7
industrialspy industrialspy 8.7h, Mathematics+Other brute force recursive bitmask with prime check; also available at UVa 12218 - An Industrial Spy 556 3.3
megainversions megainversions 8.7h, Mathematics+Other a bit of combinatorics; use Fenwick Tree to compute smaller/larger numbers quickly 333 5.0
ontrack ontrack 8.7h, Mathematics+Other DFS on Tree; the input is a tree, we can try all possible junctions as the critical junction 156 4.1
treasurediving treasurediving 8.7i, Graph+DP SSSP from source and all idol positions; TSP-like but there is a knapsack style parameter 'air_left'; use backtracking 87 7.3
walkforest walkforest 8.7i, Graph+DP counting paths in DAG; build the DAG; Dijkstra's from 'home'; also available at UVa 10917 - A Walk Through the Forest 245 4.4
centsavings centsavings 8.7j, Other+DP 1D RSQ/RMQ 1D RSQ DP for sum of prices from [i..j]; round up/down; s: (idx, d_left); t: try all positioning of the next divider 531 4.6
dvoniz dvoniz 8.7j, Other+DP 1D RSQ/RMQ involving 1D RSQ DP; binary search the answer 47 7.1
program program 8.7j, Other+DP 1D RSQ/RMQ somewhat like Sieve of Eratosthenes initially and 1D RSQ DP speedup at the end 89 7.7
beeproblem beeproblem 8.7k, Three++ Components, E transform bee grid into 2D grid; compute size of each CCs; sort; greedy 156 4.9
gettingthrough gettingthrough 8.7k, Three++ Components, E BSTA+graph connectivity; Union-Find; similar to UVa 00295 51 7.2
researchproductivityindex researchproductivityindex 8.7k, Three++ Components, E sort papers by decreasing probability; brute force k and greedily submit k best papers; DP probability; keep max 358 3.2
carpool carpool 8.7l, Three++ Components, H Floyd-Warshall/APSP; iterative brute force subset and permutation; DP; also available at UVa 11288 - Carpool 40 6.4
clockpictures clockpictures 8.7l, Three++ Components, H sort angles; compute 'string' of differences of adjacent angles (use modulo); min lexicographic rotation; use SA or KMP 463 5.5
guessthenumbers guessthenumbers 8.7l, Three++ Components, H brute force permute up to 5!; recursive string parsing (simple BNF); also available at UVa 12392 - Guess the Numbers 64 8.5
joggingtrails joggingtrails 9.chi1, Chinese Postman basic Chinese Postman Problem; also available at UVa 10296 - Jogging Trails 75 5.0
chineseremainder chineseremainder 9.chi2, Chinese Remainder basic CRT; 2 linear congruences; Big Integer 343 5.4
generalchineseremainder generalchineseremainder 9.chi2, Chinese Remainder general CRT; 2 linear congruences 362 3.7
granica granica 9.chi2, Chinese Remainder CRT; GCD of all N differences of 2 numbers 95 6.2
heliocentric heliocentric 9.chi2, Chinese Remainder CRT or brute force 1030 1.8
remainderreminder remainderreminder 9.chi2, Chinese Remainder a bit of brute force + sorting; generalized CRT 124 5.2
closestpair1 closestpair1 9.clos, Closest Pair classic closest pair problem - the easier one 269 5.7
base2palindrome base2palindrome 9.cons, Construction construct all possible base 2 palindromes; put into a set to remove duplicates and maintain order; output the M-th one 385 4.4
espressobucks espressobucks 9.cons, Construction easy brute force construction; small nxm; not about Min-Vertex-Cover 159 2.4
exofficio exofficio 9.cons, Construction we can use BFS spanning tree from center of the grid; be careful of corner cases 41 7.5
plowking plowking 9.cons, Construction greedy construction; reverse MST problem 92 3.2
poplava poplava 9.cons, Construction actually there is a rather simple construction algorithm to achieve the required requirement 105 3.4
batteries batteries 9.eggd, Egg Dropping Puzzle Egg dropping puzzle with just 2 batteries; special case 146 3.6
powereggs powereggs 9.eggd, Egg Dropping Puzzle Egg dropping puzzle; similar to UVa 10934 92 5.2
golfbot golfbot 9.fast, Fast Fourier Trans count frequencies dist of each reachable distance in one shot; use FFT to multiply dist*dist; count distances reachable ... 133 6.1
polymul2 polymul2 9.fast, Fast Fourier Trans basic polynomial multiplication problem that needs an O(n log n) algorithm; also see Kattis - polymul1 227 6.8
houseofcards houseofcards 9.form, Formulas/Theorems number of cards for certain height h is h * (3*h + 1) / 2; use Python to handle Big Integer 432 3.4
janitortroubles janitortroubles 9.form, Formulas/Theorems Brahmagupta's formula 745 1.5
sjecista sjecista 9.form, Formulas/Theorems number of intersections of diagonals in a convex polygon 581 1.9
seti seti 9.gaus, Gauss Elimination n equations and n unknowns; but there are division under modulo, so use Gaussian elimination with modular multiplicative... 52 3.1
pizza pizza 9.grad, Gradient Descent gradient descent 252 4.5
amazing amazing 9.inte, Interactive Problem run DFS and react based on the output of the program 215 5.2
askmarilyn askmarilyn 9.inte, Interactive Problem the famous Monty hall problem in interactive format 135 4.2
blackout blackout 9.inte, Interactive Problem interactive game theory; block one row; mirror jury's move 129 3.1
crusaders crusaders 9.inte, Interactive Problem another nice interactive problem about binary search 34 7.4
guess guess 9.inte, Interactive Problem interactive problem; binary search 1682 2.7
aqueducts aqueducts 9.kuhn, Kuhn-Munkres build bipartite graph; weighted MCBM; Hungarian 51 6.0
engaging engaging 9.kuhn, Kuhn-Munkres LA 8437 - HoChiMinhCity17; Hungarian; print solution 135 5.8
cheeseifyouplease cheeseifyouplease 9.line, Linear Programming simple Linear Programming problem; use Simplex 51 3.3
maximumrent maximumrent 9.line, Linear Programming basic Linear Programming problem with integer output; we can use simplex algorithm or another simpler solution 241 3.1
chewbacca chewbacca 9.lowe, Lowest Common Anc complete short k-ary tree; binary heap indexing; LCA 186 3.6
catering catering 9.minc, Min Cost (Max) Flow LA 7152 - WorldFinals Marrakech15; MCMF modeling 246 3.9
mincostmaxflow mincostmaxflow 9.minc, Min Cost (Max) Flow very basic MCMF problem; good starting point 232 5.3
ragingriver ragingriver 9.minc, Min Cost (Max) Flow MCMF; unit capacity and unit cost 96 7.1
sound sound 9.slid, Sliding Window sliding window variant 4; max and min; similar to Kattis - treeshopping 104 5.3
subseqhard subseqhard 9.slid, Sliding Window interesting sliding window variant 1119 3.9
cardboardcontainer cardboardcontainer 9.sqrt, Square Root Decomp two out of L, W, and H must be ≤ sqrt(V); brute force L and W in sqrt(V)*sqrt(V) and test if V is divisible by (L*W) 141 2.5
modulodatastructures modulodatastructures 9.sqrt, Square Root Decomp basic problem that can be solved with Square Root Decomposition technique 277 4.6

Buy Now!

Partner Links

© 2000-2024 Steven Halim

Share this page in Facebook