# Competitive Programming

Information on this page is taken from Competitive Programmer's Handbook and Elements of Programming Interviews. These tricks are also applicable to interview questions (e.g. LeetCode).

## Plan of Attack   meta

1. Understand the problem.
• Work on concrete examples.
• Apply patterns.
• Find a good data structure (e.g. priority queue, graph)
• See if the problem fits an algorithmic technique (e.g. sort, divide-and-conquer, recursion, dynamic programming).
2. Develop a simple brute-force solution.
3. Analyze the brute-force solution and write a more efficient algorithm.
4. Test the program on concrete input.
5. Analyze time and space complexity.

## Primitive Types   topic

• Use bitwise operators.
• Be comfortable with XOR.
• Understand integer storage (see information storage).
• Understand unsigned vs. signed and two's complement.

## Arrays   topic

• Take advantage of both ends of the array.
• For example, suppose we'd like to place the even entries of an array first. Easy with $$O(n)$$ space. Two indices can solve this problem without additional storage. We would partition the array into three subarrays: even, unclassified, and odd, appearing in that order.

### Random Subset

Trick is to reuse the given array.

import random

def sample(count, array):
for i in range(count):
r = random.randint(i, len(A) - 1)
array[i], array[r] = array[r], array[i]

### Transpose Matrix

def transpose(matrix):
"""Calculate A^T on a 2D array."""
list(zip(*matrix))

### Rotate Matrix 90 Degrees

def rotate_clockwise(matrix):
"""Rotate a matrix 90 degrees with flip(A)^T."""
return list(zip(*matrix[::-1]))

def rotate_anticlockwise(matrix):
"""Rotate a matrix -90 degrees with flip(A^T)."""
return list(zip(*matrix))[::-1]

## Strings   topic

### Palindromic

Solution without using extra space:

def is_palindromic(s):
return all(s[i] == s[-(i + 1)] for i in range(len(s) // 2))

### Base Conversion

Use multiplication and division to convert to base-10. For example, $$1101 = 1*2^3 + 1*2^2 + 0*2^1 + 1*2^0 = 13$$.

from functools import reduce
from string import hexdigits

def to_decimal(number: str, base: int):
return reduce(lambda total, d: total * base + hexdigits.index(d), number, 0)

Use modulus and division to convert base-10 to another base. We find the next digit with number % base (e.g. 321 % 10 = 1). The number without that digit is number // base (e.g. 321 // 10 = 32).

from string import hexdigits

def to_base(number: int, base: int):
if number:
digit = hexdigits[number % base]
else:
return ''

### Inserting Values

Inserting into a array without using additional memory requires two passes: (1) find the final size, (2) work backwards moving characters to the end.

import reduce from functools

def insert_dd(s, size):
"""Replace 'a' with 'dd'. Assume the string has room."""
final_size = size + s.count('a')
write_index = final_size - 1
for letter in s:
if letter = 'a':
s[write_index - 1:write_index + 1] = 'dd'
write_index -= 2
else:
s[write_index] = letter
write_index -= 1
return final_size

### Deleting Values

Deleting from an array without using additional memory requires two indices.

def remove_b(s, size):
"""Remove 'b' from a string."""
write_index = 0
for letter in s:
if letter != 'b':
nums[write_index] = num
write_index += 1

See Linked Lists and the examples on that page.

## Stacks and Queues   topic

### Queue with Stacks

def Queue:

def __init__(self):
self.first = []
self.second = []

def enqueue(self, value):
self.first.append(value)

def dequeue(self):
while self.first:
self.second.append(self.first.pop())
return self.second.pop()

## Binary Trees   topic

Consider left- and right-skewed trees when doing complexity analysis. Note that $$O(h)$$ complexity, where $$h$$ is the tree height, translates into $$O(log n)$$ complexity for balanced trees, but $$O(n)$$ complexity for skewed trees.

## Heaps   topic

See Heaps for information and examples.

## Searching   topic

Binary search is an effective search tool. It is applicable to more than just searching in sorted arrays, e.g., it can be used to search an interval of real numbers or integers.

Also see selection.

## Sorting   topic

### Intervals

Given a list of intervals ((start_time, end_time)), determine the maximum number of events that take place concurrently. The trick is to focus on the endpoints. This algorithm is $$O(n\logn)$$ (dominated by the sort).

from collections import namedtuple

Endpoint = namedtuple("Endpoint", ["time", "is_start"])

def find_max_simultaneous(intervals):
endpoints = [endpoint
for start, end in intervals
for endpoint in [Endpoint(start, True), Endpoint(end, False)]]
# Sort by time, break ties by putting start times before end times.
endpoint.sort(key=lambda endpoint: (endpoint.time, not endpoint.is_start))

max_simultaneous, current_simultaneous = 0, 0
for endpoint in endpoints:
if endpoint.is_start:
current_simultaneous += 1
max_simultaneous = max(max_simultaneous, current_simultaneous)
else:
current_simultaneous -= 1
return max_simultaneous

Another interval problem that benefits from sorting is computing the union of intervals. First sort the intervals by their start date. Then traverse the i]ntervals joining when the current interval's start is before the previous interval's end.

## Recursion   topic

Recursion is especially suitable when the input is expressed using recursive rules (e.g. recurrence relation). Consider recursion in search, enumeration, and divide-and-conquer.

Two key ingredients to a successful use of recursion are identifying the base cases, which are to be solved directly, and ensuring process, that is the recursion converges to the solution.

Backtracking is a useful technique for combinatorial search that uses recursion.

See Graphs.

## Parallel Computing

The two primary models for parallel computation are the shared memory model, in which each processor can access any location in memory, and the distributed memory model, in which a processor must explicitly send a message to another processor to access its memory. The former is more appropriate in the multicore setting and the latter is more accurate for a cluster.

Challenges in parallel computing include

• Races: two concurrent instruction sequences access the same address in memory and at least one of them writes to that address.
• Starvation: a processor needs a resource but never gets it.
• Deadlock: thread A acquires lock 1 and thread B acquires lock 2, following which A tries to acquire 2 and B tries to acquire 1.
• Livelock: a processor keeps retrying an operation that always fails.

A semaphore is a very powerful synchronization construct. Conceptually, a semaphore maintains a set of permits. A thread calling acquire() on a semaphore waits, if necessary, until a permit is available, and then takes it. A thread calling release() on a semaphore adds a permit and notifies threads waiting on that semaphore potentially releasing a blocking acquirer.

### Concurrency Tips

• Start with an algorithm that locks aggressively and is easily seen to be correct. Then add back concurrency, while ensuring the critical parts are locked.
• Try to work at a higher level of abstraction. Know the concurrency libraries.