Competitive Programming advices

Approaches.md

Some Standard Approaches for Competitive Programming

• Brute force

  • Will earn partial marks, as it is usually too slow
  • Do it if
    • The solution space is easy to define (easy to code)
    • You are out of time
    • You might as well do it to earn some quick marks before thinking of a more optimal solution
  • In a brute force solution, there is one level of nested loop for each solution space dimension
  • You may also want to check out itertools

• Graph Traversal: BFS/DFS

  • In BFS, you pop from the beginning of the queue, while pushing to the end of the queue
  • In DFS, you remove from the end of the container (in this case we call it a stack), but you also add to the container
  • DFS is faster, because removing/adding from the same end is fast. Having the ability to add from one end and removing from one end is always going to be slower. However, BFS allows you to get shortest path, which is why it is more used in competitive programming.
  • Essentially you visit nodes in different order, therefore achieving a different effect.
  • Usage
    • BFS

    visited = [start]
    queue = [start]
    while len(queue) > 0:
        current = queue.pop(0)
        process(current)
        if at_end(current):
            break
        for next in generate_nexts(current):
            if next not in visited:
                visited.add(next)
                queue.append(next)

    • DFS

    visited = {start}
    stack = [start]
     while len(queue) > 0:
        current = queue.pop()
        process(current)
        if at_end(current):
            break
        for next in generate_nexts(current):
            if next not in visited:
                visited.add(next)
                queue.append(next)

  • For common graph forms in competitive programming settings, you can check out my other tutorial: https://gist.github.com/Parihsz/afa1c89815031bf22690ff21417bca74

• Pathfinding

beginner advice.md

Know the Python language

• Especially the builtin’s

• Functions

  • https://docs.python.org/3/library/functions.html

• Data structures

  • Set, Frozen Set, Dictionary, List and Tuple

• Libraries

  • itertools, collection, bisect and heapq

• Try brute force solutions - will earn you some marks quickly

• Use recursion when the question defines itself recursively

  • When you see it, don’t shy away

• Graph algorithms are you friends for J4 and J5

• Brute force solutions using “itertools” is also your friend for J4 and J5

  • Really know the 4 functions
    • permutations
    • combinations
    • combinations_with_replacement
    • product

• Know the form of a solution

  • Graph solution form
  • Brute force via itertools solution form

• If there is a clever solution question, try brute force first

• There may not be one but you can identify by realizing both graph and itertools do not work