Some Interesting Programming Problems

Adhoc:

1. Chocolate Feast
2. Balloons
3. Aladdin and the Optimal Invitation [O(n) adhoc solution exists, also solvable in nlogn using binary search]
4. Stacks of Flapjacks
5. Pole Position

Angular Sweeping:

1. Photo Shoot 

Backtracking

1. Turn the Lights Off  [Explanation]
2. Another n-Queen Problem
3. The Sultan's Successors [straightforward] 

Basic Data Structure:

1. Flip It! [stack / vector]
2. Wedding of Sultan [stack] [Editorial]
3. Fence Repair [priority queue in reverse order]
4. A and B and Interesting Substrings [map, pair]
5. Parentheses Balance [stack]

Binary Search:

1. Energetic Pandas [vector+lower bound, counting] 
2. Haircut

Binary Indexed Tree:

1. Cows

Binary Tree:

1. Tree Summing [input to binary tree making]

Bitmask DP:

1. Histogram

Bellman Ford:

1. Travel Company

BFS:

1. Number Transformation [i solved with dp]
2. Chef and Digit Jumps [tricky bfs variant] 
3. Prime Path

BigMod:

1. One Unit Machine [Mod Inverse]

Bipartite Matching:

1. Kamehameha [Editorial] 

Bridge:

1. Street Directions

Brute Force:

1. Be Efficient
2. TheMatrix

Combinatorics:

1. Colorful Board
2. A Careful Approach (next permutation + binary search)

Computational Geometry:

1. Laser Shot

Connected Component:

1. Dominos 2 [undirected]
2. Dominos [directed]

Counting:

1. How Many Zeroes? [iterative and dp both solution exists]

Dijkstra:

1. Not the best (2nd / kth)
2. Almost Shortest Path (path track)

DFS:

1. The Queue [dfs with combinatorics]
2. Friends [straightforward dfs, wrong second sample output]

DP:

1. Maximum Square
2. nth Permutation
3. Jogging Trails [Warshall+bitmask, Chinese Postman Problem]
4. Chest of Drawers [basic]
5. Dividing up [iterative dp with a little trick]
6. Breaking Strings [Knuth's optimization, similar to Cutting Sticks with higher n]
7. Antimatter
8. Candy [0/1 knapsack, tricky]
9. Lighted Panels [bitmask]

Floyd Warshall:

1. Heavy Cargo (similar: The Tourist Guide, modified warshall)

Game Theory:

1. Euclid's Game [ nim with a tricky observation]

Geometry:

1. The Kissing Circles [solution]

Greedy:

1. Sum the Square 

Histogram:

1. Largest Rectangle in a Histogram

Implementation:

1. Vitaly and Strings
2. Arm Wrestling Tournament

Inclusion/Exclusion:

1. 1144 - Ray Gun

KMP:

1. Period [failure function only]

LCS:

1. Vacation [straightforward lcs]
2. 
   

Math:

1. Answering Queries
2. Points in Figures: Rectangles, Circles, and Triangles [basic, tricks, precision check]
3. Feynman 

Meet In The Middle:

1. Coin Change (IV)
2. 4 values whose sum is 0 (binary search / upper_bound, lower_bound)

Number Theory:

1. Square-Free Numbers (factor power)
2. How Many Points? (gcd)
3. Garden Game (bigmod, prime factor)
4. Big Number (log10)
5. Divisors (number of divisors)
6. Prime Factors [straightforward] 

Probability and Expected value:

1. Game on Tree [+dfs]

Segment Tree:

1. Meteor
2. Sereja and Brackets
3. Interval Product

Sieve:

1. Help Hanzo [Segmented Sieve ]
2. Printing some primes [bit seive]

Simulation:

1. Basketball Game (queue)
2. Billiard Balls

Sliding Window / Line Sweeping:

1. Christmas Play [straightforward] [editorial]
2. Broken Keyboard
3. Sliding Window [classic, with explanation, beginner, deque]

Strongly Connected Components

1. Proving Equivalences

Structure

1. Wooden Sticks [STL pair]

Strongly Connected Component:

1. Efficient Traffic System
2. Forwarding Email

Trie

1. XOR Sum ( cummulative XOR property: xor (L to R) = xor (1 to R) ^ xor (1 to L-1)

Union Find:

1. Dish Owner