ChrisVilches/Algorithms

Solutions for competitive programming problems in various online judges such as Kattis, SPOJ, URI Online Judge, etc.

Algorithms

Index

Note: This index is not exhaustive.

Strings

Trie

• kattis/bing.cpp
• kattis/phonelist.cpp
• uva/12506-shortest_names.cpp
• uva/12526-cellphone_typing.cpp

Suffix Array

• kattis/stringmultimatching.cpp
• urionlinejudge/3018-gluing_pictures.cpp

Suffix Automaton

• spoj/DISUBSTR-distinct_substrings.cpp
• spoj/LCS-longest_common_substring.cpp
• urionlinejudge/3018-gluing_pictures_suffix_automaton.cpp
• uva/10679-i_love_strings.cpp

KMP

• spoj/NAJPF-pattern_find.cpp

Segment Tree, Fenwick Tree

Segment Tree

• atcoder/D-flat_subsequence.cpp
• codeforces/domino_principle.cpp
• codeforces/pillars.cpp
• cses/hotel_queries.cpp
• kattis/antimatterrain.cpp
• kattis/mountainouslandscape.cpp
• kattis/supercomputer.cpp
• leetcode/container-with-most-water.cpp
• leetcode/jump-game.cpp
• leetcode/maximum-earnings-from-taxi.cpp
• spoj/FREQUENT-frequent_values.cpp
• spoj/HORRIBLE-horrible_queries.cpp
• spoj/RMQSQ-range_minimum_query.cpp
• urionlinejudge/1477-man_elephant_and_mouse.cpp
• urionlinejudge/1496-go_up_the_ultras.cpp
• urionlinejudge/1969-generations.cpp
• urionlinejudge/2010-keep_it_energized.cpp
• urionlinejudge/2010-keep_it_energized_2.cpp
• urionlinejudge/2531-shopping_in_fdi.cpp
• urionlinejudge/2655-dangerous_trail.cpp
• urionlinejudge/2700-fundraising.cpp
• urionlinejudge/3014-cut_inequality_down_online.cpp
• urionlinejudge/3021-jumping_grasshopper.cpp
• uva/12532-interval_product.cpp

Segment Tree + Lazy Propagation

• cses/polynomial_queries.cpp
• cses/range_updates_and_sums.cpp
• dmoj/IOI14-wall.cpp
• kattis/queryonarray.cpp
• leetcode/falling-squares.cpp
• spoj/HORRIBLE-horrible_queries.cpp
• urionlinejudge/1477-man_elephant_and_mouse.cpp

BIT (Fenwick Tree)

• acmicpc.net/17703-dragon_2.cpp
• codechef/FLYMODE.cpp
• codechef/LAZER.cpp
• codeforces/excellent_views.cpp
• cses/intersection_points.cpp
• kattis/bridgebuilding.cpp
• spoj/ADARAINB-ada_and_rain_ii.cpp
• spoj/HAYBALE-haybale_stacking.cpp
• spoj/HORRIBLE-horrible_queries_BIT.cpp
• urionlinejudge/1856-aryas_death_list.cpp
• urionlinejudge/2007-fence_the_vegetables_fail.cpp
• urionlinejudge/2792-golnaldinho.cpp
• urionlinejudge/3359-ancient_towers.cpp

Merge Sort Tree

• spoj/KQUERY-kquery.cpp

2D Segment Tree

• cses/forest_queries_ii.cpp
• urionlinejudge/1863-ramsays_counterattack.cpp

Geometry

Radial Sweep (and Polar Sort)

• acmicpc.net/17703-dragon_2.cpp
• codechef/CNVX4HUL.cpp
• codechef/REDBLUE.cpp
• kattis/fancy.cpp
• kattis/leylines.cpp
• kattis/maxcolinear.cpp
• kattis/oil2.cpp
• kattis/oldschooldays.cpp
• kattis/single.cpp
• kattis/spin.cpp
• leetcode/max-points-on-a-line.cpp
• leetcode/maximum-number-of-visible-points.cpp
• spoj/ADAKOHL-ada_and_kohlrabi.cpp
• spoj/ADAPICK-ada_and_cucumber.cpp
• spoj/BLMIRANA-mayonnaise_arrow.cpp
• spoj/IOIBOUND-boundary_2003.cpp
• spoj/SPOINTS-separate_points.cpp
• spoj/TAP2013F-flowers_of_babylon.cpp
• szkopul/2018-stone.cpp
• urionlinejudge/1108-towers_for_mobile_telephony.cpp
• urionlinejudge/1268-mission_impossible.cpp
• urionlinejudge/1336-garden_fence.cpp
• urionlinejudge/1497-hide_and_seek_2.cpp
• urionlinejudge/1613-goemon_is_in_trouble.cpp
• urionlinejudge/3013-build_the_perfect_house.cpp
• urionlinejudge/3015-dazzling_stars.cpp
• urionlinejudge/3359-ancient_towers.cpp

Convex Hull

• kattis/convexhull.cpp
• kattis/fasterthanlight.cpp
• kattis/fence.cpp
• kattis/forestofcelery.cpp
• kattis/largesttriangle.cpp
• kattis/mountainouslandscape.cpp
• spoj/BSHEEP-build_the_fence.cpp
• urionlinejudge/1315-not_too_convex_hull_2.cpp
• urionlinejudge/1464-onion_layers.cpp
• urionlinejudge/2541-ingrest.cpp
• urionlinejudge/3015-dazzling_stars_2.cpp
• uva/12307-smallest_enclosing_rectangle.cpp

Sweep Line

• codechef/LAZER.cpp
• codechef/TOWCNT.cpp
• cses/intersection_points.cpp
• kattis/antimatterrain.cpp
• kattis/arable.cpp
• kattis/directingrainfall.cpp
• kattis/pinball.cpp
• kattis/polygon.cpp
• kattis/rectilinear.cpp
• kattis/visual.cpp
• leetcode/perfect-rectangle.cpp
• leetcode/the-skyline-problem.cpp
• spoj/ADARAINB-ada_and_rain_ii.cpp
• spoj/RAIN1-november_rain.cpp
• urionlinejudge/1468-balloon.cpp
• urionlinejudge/1748-fence_the_vegetables.cpp
• urionlinejudge/2007-fence_the_vegetables_fail.cpp
• urionlinejudge/2043-high_mountains.cpp
• urionlinejudge/2043-high_mountains_faster.cpp

Quadrilaterals

• codechef/CNVX4HUL.cpp
• kattis/oldschooldays.cpp
• urionlinejudge/3359-ancient_towers.cpp

Segment to Segment Distance

• urionlinejudge/1223-toboggan_of_marbles.cpp
• urionlinejudge/1844-the_deathly_hallows.cpp

Circle & Segment Intersection

• codeforces/cornering_at_poles.cpp

Tangents & Arcs

• codeforces/cornering_at_poles.cpp
• kattis/fruitslicer.cpp
• spoj/BLMIRINA-archery_training.cpp
• urionlinejudge/1268-mission_impossible.cpp
• urionlinejudge/1646-forest.cpp
• urionlinejudge/3013-build_the_perfect_house.cpp

Polygon Tangents

• kattis/spin.cpp

Geometry with Dynamic Programming

• codeforces/impenetrable_wall.cpp
• kattis/beautifulbridges.cpp
• kattis/fancy.cpp
• kattis/trimmingpolygons.cpp
• spoj/MPOLY-polygon.cpp
• urionlinejudge/1315-not_too_convex_hull_2.cpp
• urionlinejudge/2665-hipercampo.cpp
• urionlinejudge/2695-arranging_tiles.cpp
• urionlinejudge/3064-elastico.cpp

Convex Polygons + Two-Pointers

• atcoder/B-longest_segment.cpp
• codeforces/new_year_and_cake.cpp
• codeforces/very_simple_problem.cpp
• kattis/fancy.cpp
• kattis/fasterthanlight.cpp
• kattis/forestofcelery.cpp
• kattis/largesttriangle.cpp
• urionlinejudge/2015-cake_cut.cpp
• urionlinejudge/2695-arranging_tiles.cpp
• urionlinejudge/2904-building_a_field.go
• urionlinejudge/2907-escape_polygon_2.cpp
• uva/12307-smallest_enclosing_rectangle.cpp

Concave Polygons

• kattis/airport.cpp
• kattis/arable.cpp
• kattis/biometrics.cpp
• kattis/crane.cpp
• kattis/cuttingpolygon.cpp
• kattis/floatingpoints.cpp
• kattis/forest.cpp
• kattis/maptiles.cpp
• kattis/pollution.cpp
• kattis/polygonarea.cpp
• kattis/problematicpolygons.cpp
• kattis/puzzle2.cpp
• urionlinejudge/2007-fence_the_vegetables_fail.cpp
• urionlinejudge/3361-cyclists_versus_clouds.cpp

Point Inside Polygon

• kattis/domes.cpp
• kattis/icefloes.cpp
• kattis/maptiles.cpp
• kattis/pointinpolygon.cpp
• kattis/problematicpolygons.cpp
• kattis/spin.cpp
• spoj/INOROUT-inside_or_outside.cpp
• urionlinejudge/2007-fence_the_vegetables_fail.cpp

Polygon Intersection

• kattis/asteroids.cpp
• kattis/domes.cpp
• kattis/forest.cpp
• kattis/hiddencamera.cpp
• kattis/puzzle2.cpp
• uva/137-polygons.cpp

Half-Planes Intersection (Finite Area)

• aizu/1267-how_i_mathematician_wonder_what_you_are.cpp
• codechef/CHN02.cpp
• kattis/artappreciation.cpp
• kattis/domes.cpp

Rectangle-Rectangle Intersection

• kattis/visual.cpp

Simple Polygon Detection

• kattis/polygon.cpp

Misc

• codechef/count_the_squares.cpp
• kattis/artur.cpp
• kattis/cheese_2.cpp
• kattis/countingtriangles.cpp
• kattis/dormroomdivide.cpp
• kattis/money.cpp
• kattis/segmentintersection.cpp
• kattis/undetected.cpp
• matcomgrader/O-polygon.cpp
• spoj/AXIS-axis_of_symmetry.cpp
• spoj/PIR-pyramids.cpp
• urionlinejudge/1102-deadly_atack.cpp
• urionlinejudge/1124-elevator.cpp
• urionlinejudge/1295-the_closest_pair_problem.cpp
• urionlinejudge/1378-isosceles_triangles.cpp
• urionlinejudge/1455-icpc_finals.cpp
• urionlinejudge/1665-decorate_the_wall.cpp
• urionlinejudge/1991-factory_of_bridges.cpp
• urionlinejudge/2083-on_the_side_of_the_road.cpp
• urionlinejudge/2840-balloon++.cpp
• uva/858-berry_picking.cpp

Graphs

BFS, DFS

• codeforces/maze_in_bolt.cpp
• kattis/fontan.cpp
• kattis/keyboard.cpp
• kattis/robotmaze.cpp
• kattis/secretchamber.cpp
• kattis/wheresmywaterfall.cpp
• leetcode/balanced-binary-tree.js
• leetcode/detonate-the-maximum-bombs.cpp
• leetcode/dungeon-game.cpp
• leetcode/escape-the-spreading-fire.cpp
• leetcode/jump-game-iii.cpp
• leetcode/jump-game-iv.cpp
• leetcode/max-area-of-island.cpp
• leetcode/minimum-moves-to-move-a-box-to-their-target-location.cpp
• leetcode/number-of-provinces.cpp
• leetcode/shortest-path-in-a-grid-with-obstacles-elimination.cpp
• leetcode/symmetric-tree.rs
• leetcode/trapping-rain-water-ii.cpp
• spoj/BITMAP-bitmap.cpp
• spoj/BUGLIFE-a_bugs_life.cpp
• spoj/CLEANRBT-cleaning_robot.cpp
• spoj/CTOI09_1-ioi2009_mecho.cpp
• spoj/MAKEMAZE-validate_the_maze.cpp
• urionlinejudge/1082-connected_components.cpp
• urionlinejudge/1100-knight_moves.cpp
• urionlinejudge/3361-cyclists_versus_clouds.cpp
• urionlinejudge/3364-fields_division.cpp
• uva/1103-ancient_messages.cpp
• uva/13011-height_map.cpp

Bipartite Matching, Max Flow, Min-Cut

• codeforces/halting_wolf.cpp
• codeforces/halting_wolf_dinic.cpp
• kattis/bookclub.cpp
• kattis/escapeplan.cpp
• kattis/jupiter.cpp
• kattis/maxflow.cpp
• kattis/maxflow_dinic.cpp
• kattis/mincut.cpp
• kattis/piano.cpp
• urionlinejudge/1299-game_of_tiles.cpp
• urionlinejudge/1362-my_tshirt_suits_me.cpp
• urionlinejudge/1362-my_tshirt_suits_me_dinic.cpp
• urionlinejudge/1490-attacking_rooks.cpp
• urionlinejudge/2014-blood_groups.cpp
• urionlinejudge/2705-keep_it_covered.cpp
• urionlinejudge/2705-keep_it_covered_2.cpp
• urionlinejudge/2705-keep_it_covered_dinic.cpp
• urionlinejudge/3012-algorithm_teaching.cpp
• urionlinejudge/3012-algorithm_teaching_hopcroft_karp.cpp
• uva/10330-power_transmission.cpp
• uva/11167-monkeys_in_the_emei_mountain.cpp

Minimum Cost Flow

• cses/parcel_delivery.cpp
• cses/task_assignment.cpp
• kattis/catering.cpp
• kattis/mincostmaxflow.cpp

Dijkstra

• codeforces/cornering_at_poles_dijkstra.cpp
• kattis/millionairemadness.cpp
• kattis/shortestpath1.cpp
• urionlinejudge/1370-regatta_of_scientists.cpp
• uva/10986-sending_email.cpp
• uva/11833-route_change.cpp
• uva/13010-galactic_taxes.cpp

Bellman-Ford

• uva/558-wormholes.cpp

Topological Sort

• kattis/artur.cpp
• kattis/pickupsticks.cpp

Minimum Dominating Set

• kattis/socialadvertising.cpp

Hungarian Algorithm for Assignment Problem

• urionlinejudge/3366-hamilton_the_musical.cpp

Dynamic Programming

Counting, Combinatorics, Math

• codeforces/impenetrable_wall.cpp
• codeforces/keylogger.cpp
• kattis/gigcombinatorics.cpp
• kattis/permutationdescent.cpp
• kattis/tritiling.cpp
• matcomgrader/H-round_table.cpp
• spoj/BADXOR-bad_xor.cpp
• urionlinejudge/1319-hyperactive_girl.cpp
• urionlinejudge/1493-disjoint_water_supply.cpp
• urionlinejudge/2009-just_a_bit_sorted.cpp
• urionlinejudge/3017-fabricating_sculptures.cpp
• urionlinejudge/3020-improve_spam.cpp

Maximization, Minimization

• aizu/1164-tighten_up.cpp
• atcoder/A-frog_1.cpp
• atcoder/D-flat_subsequence.cpp
• codeforces/boredom.cpp
• codeforces/domino_principle.cpp
• codeforces/pillars.cpp
• google/controlled_inflation.cpp
• google/moons_and_umbrellas.cpp
• google/plates.cpp
• kattis/3dprinter.go
• kattis/beautifulbridges.cpp
• kattis/centsavings.cpp
• kattis/coke.cpp
• kattis/fancy.cpp
• kattis/intervalcover.cpp
• kattis/narrowartgallery.cpp
• kattis/nikola.cpp
• kattis/speedrun.cpp
• kattis/stol.cpp
• leetcode/jump-game-ii.cpp
• leetcode/jump-game-v.cpp
• leetcode/jump-game-vi.cpp
• leetcode/maximum-earnings-from-taxi.cpp
• spoj/BORW-black_or_white.cpp
• spoj/COINS-bytelandian_gold_coins.cpp
• spoj/KNAPSACK-the_knapsack_problem.cpp
• spoj/MPOLY-polygon.cpp
• spoj/ROCK-sweet_and_sour_rock.cpp
• spoj/THREECOL-threecoloring_of_binary_trees.cpp
• urionlinejudge/1315-not_too_convex_hull_2.cpp
• urionlinejudge/1863-ramsays_counterattack.cpp
• urionlinejudge/2008-exposing_corruption.cpp
• urionlinejudge/2010-keep_it_energized.cpp
• urionlinejudge/2010-keep_it_energized_2.cpp
• urionlinejudge/2665-hipercampo.cpp
• urionlinejudge/3023-leverage_mdt.cpp
• urionlinejudge/3064-elastico.cpp

Probability

• kattis/bachetsgame.cpp
• spoj/AE2A-dice.cpp
• urionlinejudge/3019-hold_or_continue.cpp

Binary Search, Ternary Search

Binary Search

• atcoder/D-flat_subsequence.cpp
• codeforces/domino_principle.cpp
• codeforces/keylogger.cpp
• codeforces/pillars.cpp
• kattis/bridgebuilding.cpp
• kattis/cheese_2.cpp
• kattis/dormroomdivide.cpp
• kattis/messenger.cpp
• kattis/monk.cpp
• kattis/mountainouslandscape.cpp
• kattis/rangers.cpp
• kattis/speed.cpp
• kattis/stringmultimatching.cpp
• leetcode/dungeon-game.cpp
• leetcode/find-first-and-last-position-of-element-in-sorted-array.cpp
• leetcode/median-of-two-sorted-arrays.cpp
• leetcode/search-in-rotated-sorted-array.cpp
• spoj/AGGRCOW-aggressive_cows.kt
• spoj/BBIN-busqueda_binaria.cpp
• spoj/BBIN2-busqueda_binaria_2.cpp
• spoj/MATHLOVE-math_is_love.cpp
• spoj/TAP2013F-flowers_of_babylon.cpp
• urionlinejudge/1108-towers_for_mobile_telephony.cpp
• urionlinejudge/1549-splitting_the_coke.cpp
• urionlinejudge/1646-forest.cpp
• urionlinejudge/2010-keep_it_energized.cpp
• urionlinejudge/2010-keep_it_energized_2.cpp
• urionlinejudge/2014-blood_groups.cpp
• urionlinejudge/2104-lasers.cpp
• urionlinejudge/2695-arranging_tiles.cpp
• urionlinejudge/3013-build_the_perfect_house.cpp
• urionlinejudge/3018-gluing_pictures.cpp
• uva/11935-through_the_desert.cpp

Ternary Search

• kattis/asteroids.cpp
• kattis/euclideantsp.cpp
• kattis/messenger.cpp
• urionlinejudge/1294-the_largest_and_smallest_box.cpp
• urionlinejudge/1991-factory_of_bridges.cpp
• urionlinejudge/2015-cake_cut_2.cpp
• urionlinejudge/2517-pogro_challenge.cpp
• uva/13010-galactic_taxes.cpp

Trees

Tree Problems

• google/chain_reactions.cpp
• kattis/ceiling.cpp
• kattis/floatingpoints.cpp
• kattis/kitten.cpp
• spoj/PT07Y-is_it_a_tree.cpp
• spoj/PT07Z-longest_path_in_a_tree.cpp
• spoj/THREECOL-threecoloring_of_binary_trees.cpp
• urionlinejudge/1135-ants_colony.cpp
• urionlinejudge/1195-binary_search_tree.cpp
• urionlinejudge/1200-bst_operations_i.cpp
• urionlinejudge/1493-disjoint_water_supply.cpp
• urionlinejudge/3020-improve_spam.cpp

Cycle Detection

• kattis/pickupsticks.cpp

Other Data Structures & Algorithms

Fast Fourier Transform

• spoj/POLYMUL-polynomial_multiplication.cpp

Union Find (+ Minimum Spanning Tree)

• kattis/almostunionfind.cpp
• kattis/cats.cpp
• kattis/icefloes.cpp
• kattis/islandhopping.cpp
• kattis/rangers.cpp
• kattis/rectilinear.cpp
• kattis/treehouses.cpp
• kattis/undetected.cpp
• kattis/unionfind.cpp
• kattis/wheresmyinternet.cpp
• spoj/ANTTT-the_ant.cpp
• urionlinejudge/1152-dark_roads.cpp
• urionlinejudge/1268-mission_impossible.cpp
• urionlinejudge/1298-fix_the_maze.cpp
• urionlinejudge/1468-balloon.cpp
• urionlinejudge/1844-the_deathly_hallows.cpp
• urionlinejudge/3014-cut_inequality_down.cpp

Sparse Table

• kattis/forestofcelery.cpp
• leetcode/jump-game-v.cpp
• spoj/RMQSQ-range_minimum_query_sparse_table.cpp
• urionlinejudge/1496-go_up_the_ultras_sparse_table.cpp
• urionlinejudge/3014-cut_inequality_down_online.cpp

Prefix Sum

• codeforces/keylogger.cpp
• codeforces/new_year_and_cake.cpp
• cses/polynomial_queries.cpp
• kattis/bridgebuilding.cpp
• kattis/centsavings.cpp
• kattis/oldschooldays.cpp
• kattis/queryonarray.cpp
• spoj/CSUMQ-cumulative_sum_query.cpp
• spoj/RANGESUM-range_sum.cpp
• urionlinejudge/2010-keep_it_energized.cpp
• urionlinejudge/2010-keep_it_energized_2.cpp
• urionlinejudge/2015-cake_cut_2.cpp
• urionlinejudge/3014-cut_inequality_down_online.cpp
• uva/10324-zeros_and_ones.cpp
• uva/11833-route_change.cpp

Lowest Common Ancestor

• matcomgrader/O-polygon.cpp
• urionlinejudge/1135-ants_colony.cpp

Coordinate (or Arrays in General) Compression

• codechef/FLYMODE.cpp
• codechef/LAZER.cpp
• cses/intersection_points.cpp
• kattis/antimatterrain.cpp
• urionlinejudge/2007-fence_the_vegetables_fail.cpp
• urionlinejudge/2700-fundraising.cpp

Rope

• kattis/joinstrings.cpp

Ordered Set

• kattis/gcpc.cpp
• urionlinejudge/3359-ancient_towers_2.cpp

Fast Exponentiation, Fast Fibonacci, Etc

• spoj/MPOW-power_of_matrix.cpp
• urionlinejudge/1151-easy_fibonacci.cpp
• urionlinejudge/1969-generations.cpp

Modular Division

• codechef/CNVX4HUL.cpp
• codeforces/cqxym_count_permutations.cpp
• kattis/chineseremainder.rb
• matcomgrader/H-round_table.cpp

Simpson's Integration

• kattis/bottles.cpp
• kattis/flowers.cpp
• urionlinejudge/1297-environment_protection.cpp

Kadane's Algorithm (Maximum Subarray Problem)

• kattis/purplerain.cpp
• leetcode/maximum-subarray.cpp
• spoj/MAXSUMSU-maximum_subset_sum.cpp