TopCoder Cookbook

1. Algorithm Competition

 

1.1. Getting Started

Registering

Understanding SRM competition format (mart0258, Nickolas)

Submitting Your Solution (mingshun)

Setting up your environment for an SRM vijay03

Writing Template

Using and Understanding C++ Macros (Eryx & Eryx)

Using Prewritten Code (it4.kp, Nickolas)

Understanding Your Rating and Why It Changes (bmerry)

 

1.2 Approaching the Problem

Dissecting Problem Statement (antimatter, Nickolas)

Planning an Approach to the Problem

Recognizing Problem Types StevieT

Solving Problems Using Alternative Bruteforce Solution (Nickolas)

Practicing & Improving Your Style  (momtchil)

Choosing Best Programming Language

 

1.3. Finding and Avoiding Mistakes

Understanding the Importance of Testing

Avoiding Common Coding Mistakes

Testing for Correctness (Nickolas)

Testing for Efficiency V1, V2, V3

Choosing Correct Data Types (dttri, Nickolas)

Using Rational Arithmetic to Avoid Floating Point Imprecision (Nemui, Nickolas)

Testing Using Alternative Brute-Force Solution (it4.kp, Nickolas)

Finding Common Challenge Opportunities

 

2. Common Algorithmic Problems

 

2.1. Main Data Types, Data Structures and Related Problems

Working with Numbers

Working with Strings

Working with Fixed-length Arrays

Working with Variable-length Arrays (Vectors)

Working with Maps and Sets

Representing Sets with Bitfields

Converting between Numbers and Strings (Nickolas)

Parsing String Input (Nickolas)

Iterating Over All Subsets of a Set  (dimkadimon)

Iterating Over All Permutations of an Array (quimey, Ferlon)

STL Basic

 

2.2. Math and Geometry

Performing Calculations Modulo p

Handling Prime Numbers

Using Euclid’s Algorithm

Understanding Combinatorics

Using Inclusion-Exclusion Principle

Using Recurrent Relations for Calculations started by Ferlon

Defining Probabilities

Using Vector Operations

Working with Lines and Segments

Working with Polygon

Convex Hull

Geometry with Complex Number

 

2.3. Graphs

Recognizing and Representing a Graph

Representing State

Understanding Properties of Graphs

Handling Grid-Represented Graphs eraserhd

Searching a Graph Breadth-First

Searching a Graph Depth-First 1, 2, 3

Finding the Best Path Using Dijkstra’s Algorithm V1, V2, V3, V4, V5

Finding the Best Path Using Bellman-Ford Algorithm

Finding all Best Paths Using Floyd-Warshall Algorithm

Choosing Shortest Path algorithm

Finding Maximum Flow Using Ford-Fulkerson Algorithm

Solving Minimum Cost Flow Problem V1, V2

Solving Maximum Bipartite Matching Problem V1, V2

Recognizing the Algorithm to Use

Minimal Spanning Tree

Graph with Probabilities

 

2.4. Recursive Problems

Recognizing Recursive Problems

Solving Recursive Problems

Optimizing Recursive Solution

Solving Two-Person Games with Perfect Information

Introducing Dynamic Programming V1, V2

Commonly used DP state domains

DP Under Memory Constraint

Optimizing DP Solution

 

2.5. Miscellaneous Problems

Using Greedy Algorithms

Using Binary Search

Using Ternary Search

Using Backtracking

Using Linesweep Algorithm

Constructing Combinatorial Objects

Finding the lexicographically K-th combinatorial object (rrpai, Ferlon)

Using Regular Expressions

 

3. Marathon Competition

 

3.1. Getting Started

Understanding Marathon Competition Format

Understanding Two Kinds of Marathon Problems

Dissecting Problem Statement

Submitting Your Solution

Understanding Absolute and Relative Scoring Systems V0

Understanding Specific Marathon Matches

 

3.2. Working on the Problem

Measuring Time V1

Running Visualizer with Your Solution V0 V1

Setting Up Your Environment/Keeping Track of Your Progress V0

Rewriting the Visualizer

Implementing the Limitations Locally

Comparing Solutions

Deciding How to Improve Your Solution V0 V2

Improving Your Solution in the Home Stretch

Fine-tuning Your Solution

Using Precompute data in your solution

Choosing Best Programming Language

 

3.3. Methods of Solving the Problem

Identifying Principal Types of Problems

Generating Ideas for Your Solution

Approaching Single-Player Game-Based Problems V0

Using Hill Climbing Techniques V0

Using Simulated Annealing Techniques

Using Genetic Algorithms

Using SSE not started

Generating random numbers with C++ TR1

Books

Advertisement