The Inclusion-Exclusion Principle

Problems

• SPOJ: EASYMATH
• SPOJ: KPRIMESB
• SPOJ: NGM2
• SPOJ: SQFREE (Hint: Use Mobius function)
• SPOJ: SUBSET
• SPOJ: IITKWPCH
• SPOJ: MSKYCODE

Resources

• CP-Algorithms - Inclusion Inclusion-Exclusion Principle

Divide and Conquer DP

Problems

• SPOJ: LARMY
• KATTIS: money

Resources

• CP-Algorithms - Divide and Conquer DP

Connected components, bridges, articulations points

Definitions (that may not be accurate)

• In a connected undirected graph, a bridge is an edge that if removed the graph becomes disconnected.
• In a connected undirected graph, an articulation point or a cut vertex is a node that if removed the graph becomes disconnected.
• A strongly connected component is a graph where every two nodes are reachable from each others.

Problems

• Leetcode: Critical Connections in a Network (Finding Bridges Offline)
• Codeforces: Round 377 - Div2 F - Tourist Reform (Strong Orientation)

Resources

• CP-Algorithms - Finding Bridge Offline
• CP-Algorithms - Strong Orientation

RMQ

Problems

• Spoj: THRBL (Simple - Sparse Table)
• Codeforces: Round 475 - Div2 D - CGCDSSQ (Binary Search + Sparse Table)