Skip to content

Instantly share code, notes, and snippets.

Avatar

Izan Beltran izanbf1803

View GitHub Profile
View keybase.md

Keybase proof

I hereby claim:

  • I am izanbf1803 on github.
  • I am izanbf (https://keybase.io/izanbf) on keybase.
  • I have a public key ASCMeN20EyeipWshitqPFu-yVZZSPv6gnqJvm3cmo5GKago

To claim this, I am signing this object:

@izanbf1803
izanbf1803 / simulate.py
Last active Dec 13, 2020 — forked from fraret/simulate.py
Simula N partides del joc de la asignatura d'algorismia de la FME
View simulate.py
# Exemple per executar:
# python simulate.py Stonks Stonks Stonks2 Stonks2 100
import subprocess
import random
import os
import sys
from multiprocessing import Pool, Lock, current_process, Value
from collections import defaultdict
@izanbf1803
izanbf1803 / simulate.py
Last active Dec 2, 2020
Simula N partides del joc de la asignatura d'algorismia de la FME
View simulate.py
# Exemple per executar:
# python simulate.py Stonks Stonks Stonks2 Stonks2
# Sortida:
# Stonks won with seeds: 43913 70491 41637 65191
#
# Stonks2 won with seeds: 39428 20517 29384 42524 24253 54463
#
# Stonks won 4 times 40.00%
# Stonks2 won 6 times 60.00%
@izanbf1803
izanbf1803 / vec.h
Created Sep 17, 2019
Simple math vector class in C++
View vec.h
#ifndef __VEC_HPP__
#define __VEC_HPP__
#include <iostream>
#include <cmath>
namespace vec
{
typedef long double ld;
@izanbf1803
izanbf1803 / khun.cc
Created Sep 17, 2019
Khun algorithm
View khun.cc
#include <bits/stdc++.h>
using namespace std;
// Khun algorithm, computes maximum bipartite matching in O(|V|^3)
bool tryKhun(int n, const vector<vector<int>>& adj, vector<bool>& used, vector<int>& M, int v)
{
if (used[v]) return false;
used[v] = true;
for (int u : adj[v]) {
@izanbf1803
izanbf1803 / fast_popcount.cc
Last active Jun 24, 2019
Fast popcount method.
View fast_popcount.cc
typedef unsigned int uint;
uint popcount_short[0xffff];
void popcount_setup()
{
popcount_short[0] = 0;
for (uint mask = 1; mask < 0xffff; ++mask) {
popcount_short[mask] = (mask&1) + popcount_short[mask>>1];
}
@izanbf1803
izanbf1803 / discrete_log.cc
Created May 30, 2019
Discrete logarithm solver.
View discrete_log.cc
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// This implementation uses cast to __int128 for products because
// of big input (0 < q < 5*10^10).
ll mpow(ll x, ll n, ll m)
{
@izanbf1803
izanbf1803 / fibo.py
Created May 6, 2019
Fast O(log n) computation of n-th fibonacci number.
View fibo.py
import numpy as np
n = int(input())
M = np.matrix([[1,1],[1,0]], dtype="object")
ans = (M**n)[0,0]
print(ans)
@izanbf1803
izanbf1803 / suffix_array.cc
Last active Apr 5, 2019
Suffix Array Construction
View suffix_array.cc
struct Suffix {
int idx, rank0, rank1;
};
bool suffix_lt(Suffix& a, Suffix& b)
{
if (a.rank0 == b.rank0) return a.rank1 < b.rank1;
return a.rank0 < b.rank0;
}
@izanbf1803
izanbf1803 / karatsuba.cc
Created Apr 2, 2019
Simple C++ Karatsuba implementation.
View karatsuba.cc
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<typename T> using V = vector<T>;
string bigint_to_str(const V<char>& c)
{
string s = "";
for (int i = c.size()-1; i >= 0; --i) {
s += c[i] + '0';