sharmaeklavya2

Competitive Programming Syllabus

Geometry

• Graham Scan algorithm for Convex Hull O(n * log(n))
• Online construction of 3-D convex hull in O(n^2)
• Bentley Ottmann algorithm to list all intersection points of n line segments in O((n + I) * logn)
  • Suggested Reading - http://softsurfer.com/Archive/algorithm_0108/algorithm_0108.htm
• Rotating Calipers Technique
  • Suggested Reading - http://cgm.cs.mcgill.ca/~orm/rotcal.html

• Problems - Refer the article for a list of problems which can be solved using Rotating Calipers technique.

sharmaeklavya2

#!/usr/bin/env python3

"""
Uses code2dtree (https://github.com/sharmaeklavya2/code2dtree) to find
the tight approximation factor of the LPT algorithm for makespan minimization
for a given number of jobs and machines.

Specifically, for every possible scenario, we find out the maximum load
a machine in the LPT schedule can have if the optimal makespan is at most 1.

sharmaeklavya2

// See codechef FLIPCOIN for an example
#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <vector>

/*
Output of segment tree range queries are modelled as elements of a monoid.
Updates on the segment tree are functions on the monoid.

sharmaeklavya2

#!/usr/bin/env python3

"""
Visualize how a quantity varies with time.
Reads a CSV file where first column is timestamp.
Plots the data points and a weighted average of a sliding window.
"""

import csv
import math

sharmaeklavya2

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<array>
	<dict>
		<key>phrase</key>
		<string>₋</string>
		<key>shortcut</key>
		<string>_-</string>
	</dict>

sharmaeklavya2

LOLCODE

LOLCODE is an esoteric programming language inspired by lolcat memes on the internet. The language was created in 2007 by Adam Lindsay, researcher at Lancaster University's Computing Department.

Here I have explained basics of LOLCODE with complete examples. However, you may have questions even after reading them because I have not included all details. For an exhaustive reference, read the official documentation.

Hello World

HAI 1.2
BTW This is the famous 'Hello World' program

sharmaeklavya2

Starting out with Competitive Programming

(This guide is meant for beginners. If you have solved 100+ problems and are looking for guidance on how to solve problems involving algorithms and data structures, this document is not for you.)

Competitive Programming is an interesting activity which mixes problem solving with programming. It is not only enjoyable but also very demanded in placements. Competitive programming will make you very good at writing efficient programs quickly.

sharmaeklavya2

#!/usr/bin/env python3

"""
Takes a CSV file as input and performs linear regression on the data.
"""

import sys
import ast
import argparse
import numpy as np

sharmaeklavya2

#!/usr/bin/env python3

"""
Convert a float to the nearest fraction.
"""

import math
import ast
import argparse
from fractions import Fraction as F

sharmaeklavya2

#!/usr/bin/env python3

"""Downloads style/class files necessary to compile a LaTeX paper."""

import sys
import os
from os.path import join as pjoin
import argparse
from urllib.request import urlopen
from zipfile import ZipFile