Skip to content

Instantly share code, notes, and snippets.

@jakab922
jakab922 / sol.cc
Created February 5, 2019 07:59
Sliding window median
#include <map>
#include <utility>
#include <vector>
#include <algorithm>
#include <iostream>
#include <iomanip>
using namespace std;
typedef long long ll;
@jakab922
jakab922 / segment_intersection.go
Created January 9, 2019 11:12
Intersection of 2 segments in 2 dimension. The method also finds an arbitrary intersection point if there is any.
package main
import (
"bufio"
"fmt"
"log"
"math"
"strconv"
"strings"
)
@jakab922
jakab922 / stuff.json
Created July 10, 2018 12:00
Aggregated elastic query
{
"size": 0,
"query": {
"bool": {
"must": [
{ "exists": {"field": "status" } },
{ "exists": {"field": "class_name" } },
{ "exists": {"field": "test_name" } }
]
}
@jakab922
jakab922 / circle_check.py
Created June 24, 2018 21:12
Circle check in a weighted directed graph
def circle_check(graph):
n = len(graph)
graph = [list(node.keys()) for node in graph]
indexes = [0] * n
stack = [0]
visited = [False] * n
visited[0] = True
while stack:
curr = stack[-1]
@jakab922
jakab922 / palindromic_subsets_brute_sol.py
Created June 13, 2018 21:09
Palindromic subsets brute solution
MOD = 10 ** 9 + 7
def modpow(x, y, mod):
elems = []
while y:
elems.append(y % 2)
y >>= 1
el = len(elems)
x_pows = [x for _ in xrange(el)]
@jakab922
jakab922 / palindromic_subsets.py
Created June 13, 2018 21:03
Palindromic subsets
MOD = 10 ** 9 + 7
LEFT, RIGHT = range(2)
def modpow(x, y, mod):
elems = []
while y:
elems.append(y % 2)
y >>= 1
el = len(elems)
@jakab922
jakab922 / beaming_with_joy.py
Created May 14, 2018 16:15
Code Jam 17/2/3
from collections import defaultdict as dd
from itertools import product
# 2SAT linear solver START
def strongly_connected(graph):
""" From Cormen: Strongly connected components chapter. """
l = len(graph)
normal = [list(graph[i]) for i in xrange(l)]
reverse = [[] for _ in xrange(l)]
from collections import defaultdict as dd
# 2SAT linear solver START
def strongly_connected(graph):
""" From Cormen: Strongly connected components chapter. """
l = len(graph)
normal = [list(graph[i]) for i in xrange(l)]
reverse = [[] for _ in xrange(l)]
for fr, tos in enumerate(normal):
from collections import defaultdict as dd
def fill(distances, was, backlinks, top, curr, dist):
distances[curr] = dist
was[curr] = True
while dist > 0:
distances[curr] = dist
was[curr] = True
curr = backlinks[curr][0]
@jakab922
jakab922 / lollipop.py
Created May 5, 2018 11:39
Google Code Jam 18 / 1C / Lollipop shop
from random import choice
import sys
t = int(raw_input().strip())
LOW, HIGH = 0.005, 0.1
def calc(p, count, curr, left):
return pow(p, count) * pow(1.0 - p, curr - count) * pow(1.0 - p, left)
for case in xrange(1, t + 1):