Skip to content

Instantly share code, notes, and snippets.

View xennygrimmato's full-sized avatar

Vaibhav Tulsyan xennygrimmato

View GitHub Profile
@xennygrimmato
xennygrimmato / spoj_pt07x.py
Last active April 20, 2018 14:03
SPOJ - PT07X
# http://www.spoj.com/problems/PT07X/
from functools import lru_cache
d = {}
@lru_cache(maxsize=None)
def f(u, taken, parent):
s0, s1 = 0, 0
for v in d[u]:
if taken and v!=parent: s0 += min(f(v, 1, u), f(v, 0, u))
elif v!=parent: s1 += f(v, 1, u)
if taken: return 1 + s0
@xennygrimmato
xennygrimmato / TheLotteryBothDivs
Last active March 18, 2018 11:48
Topcoder SRM 502 - Div2 500
# https://community.topcoder.com/stat?c=problem_statement&pm=11359
class TheLotteryBothDivs:
def find(self, goodSuffixes):
s = goodSuffixes
s = sorted(s, key=lambda x: len(x))
st = set()
for t in s:
for i in xrange(len(t)):
if t[i:] in st:
@xennygrimmato
xennygrimmato / russian_dolls_ways.py
Last active March 15, 2018 03:21
CSAcademy - #73 - Russian Dolls Ways
fact, n, d = [1] + [j for j in [1] for i in xrange(1, 10**5+2) for j in [(j * i) % (10**9+7)]], raw_input(), __import__('collections').Counter(map(int, raw_input().split())).most_common();print (reduce(lambda x, y: (x * fact[d[0][1]] * pow(fact[d[0][1] - y[1]], (10**9+7) - 2, (10**9+7))) % (10**9+7), d, 1) * pow(fact[d[0][1]], 10**9+5, 10**9+7)) % (10**9+7)
@xennygrimmato
xennygrimmato / russian_dolls_ways.py
Last active March 15, 2018 03:20
CSAcademy - #73 - Russian Dolls Ways
from collections import Counter
MOD, N = 10**9 + 7, 10**5 + 2
fact = [1] + [j for j in [1] for i in xrange(1, N) for j in [(j * i) % MOD]]
inv = [pow(fact[i], MOD - 2, MOD) for i in xrange(N)]
def C(h, k): return (fact[h] * inv[k] * inv[h - k]) % MOD
n, d = raw_input(), Counter(map(int, raw_input().split())).most_common()
print (reduce(lambda x, y: (x * C(d[0][1], y[1]) * fact[y[1]]) % MOD, d, 1) * inv[d[0][1]]) % MOD
@xennygrimmato
xennygrimmato / NAJKRACI.cpp
Created March 12, 2018 18:48
SPOJ - NAJKRACI
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
const int N = 6502;
const int INF = 1000000000;
const int MOD = 1000000007;
typedef vector<int> vi;
export OCAMLFIND_CONF="$(pwd)/_build/ocamlfind/lib/findlib.conf" && export PATH="/Users/vaibhavtulsyan/learn-reason/ExampleProject/node_modules/nopam:$PATH" && export opam_bin="$(pwd)/./_build/ocamlfind/bin" && export opam_doc="$(pwd)/./_build/ocamlfind/doc" && export opam_lib="$(pwd)/./_build/ocamlfind/lib" && export opam_man="$(pwd)/./_build/ocamlfind/man" && export opam_prefix="$(pwd)/./_build/ocamlfind" && export opam_sbin="$(pwd)/./_build/ocamlfind/sbin" && export PATH="/Users/vaibhavtulsyan/learn-reason/ExampleProject/node_modules/opam-installer-bin/_build/ocamlfind/bin:$PATH" && export CHECK_IF_PREINSTALLED="false" && export OCAMLLIB="/Users/vaibhavtulsyan/learn-reason/ExampleProject/node_modules/ocaml/lib/ocaml" && export OCAMLPARAM="_,g=1" && export OCAML_TOPLEVEL_PATH="/Users/vaibhavtulsyan/learn-reason/ExampleProject/node_modules/ocaml/lib/ocaml" && export OCAML__SOME_VAR="see how this must be prefixed by OCAML__ because the package name is ocaml, and this wasnt marked global:true" && export PATH="
=========== ./BANANAGLEE/BANANAUSURPER/BG2200_UPGRADE/UPGRADE/BUSURPER-2211-611.exe ===========
00000000 l df *ABS* 00000000 upgrade_pix.c
00000000 l df *ABS* 00000000 change_page_permission.c
00000000 l df *ABS* 00000000 osVersionChecking.c
=========== ./BANANAGLEE/BANANAUSURPER/BG2200_UPGRADE/UPGRADE/BUSURPER-2211-614.exe ===========
00000000 l df *ABS* 00000000 upgrade_pix.c
00000000 l df *ABS* 00000000 change_page_permission.c
00000000 l df *ABS* 00000000 osVersionChecking.c
=========== ./BANANAGLEE/BANANAUSURPER/BG2200_UPGRADE/UPGRADE/BUSURPER-2211-622.exe ===========
00000000 l df *ABS* 00000000 upgrade_pix.c
@xennygrimmato
xennygrimmato / catchChecker.ml
Last active August 16, 2016 01:18
Expression to check whether a certain instruction is within a catch block
open! Utils
module F = Format
module L = Logging
module Domain = struct (* implementation of join, widen, <=, pp *)
type astate = { in_catch : bool ; seen_call : bool; }
let is_bottom _ = false
let initial = { in_catch = false; seen_call = false; }
let (<=) ~lhs ~rhs = lhs == rhs
open! Utils
module F = Format
module L = Logging
(** backward analysis for computing set of maybe-live variables at each program point *)
module Domain = AbstractDomain.FiniteSet(Var.Set)
(* compilers 101-style backward transfer functions for liveness analysis. gen a variable when it is
@xennygrimmato
xennygrimmato / Mod.java
Created August 9, 2016 08:01
Java code in which modulo 1 operation is being performed
public class Mod {
public int modulo_one(int x) {
int rem = x % 1;
return rem;
}
}