aleksmitov’s gists

aleksmitov / Test.java

Created June 14, 2015 21:39

Implementations of the Fisher–Yates shuffle algorithm and Quickselect

	import java.util.ArrayList;
	import java.util.Random;
	public class Test {
	/*
	* Implementation of the Fisher–Yates shuffle algorithm with O(N) time complexity
	*/
	public static <T> void shuffle(ArrayList<T> items)
	{
	if(items == null) throw new NullPointerException();
	Random numberGenerator = new Random();

aleksmitov / solution.cpp

Created March 18, 2015 21:11

Facebook Programming Challenges: Bar problem

	//Complexity for each case: O(N^2 * logN)
	#include <iostream>
	#include <utility>
	#include <vector>
	#include <algorithm>
	using namespace std;
	typedef pair<int, int> ii;
	const int MAXN = 1000;
	int N, K;
	int atWhichPosMin[MAXN];

aleksmitov / MaxFlowEdmondKarp.cpp

Created September 28, 2014 20:15

Решение на задачата "КОТКИ" от националния кръг на НОИ, 2013г. Използвана е имплементация на Edmond-Karp за Максимален поток в граф

	#include <iostream>
	#include <vector>
	#include <string>
	#include <utility>
	#include <queue>
	#include <algorithm>
	#include <cstring>
	using namespace std;
	typedef pair<int, int > ii;
	struct Edge {

aleksmitov / MST.cpp

Created August 13, 2014 11:45

Implementation of Kruskal's Minimum Spanning tree(MST) algorithm for UVa problem "11228 - Transportation system"

	#include <iostream>
	#include <vector>
	#include <cstring>
	#include <string>
	#include <algorithm>
	#include <queue>
	#include <cstdio>
	#include <stack>
	#include <utility>
	#include <fstream>

aleksmitov / TarjanSCC.cpp

Created August 11, 2014 00:20

Implementation of Tarjan's Strongly connected components algorithm with O(|V| + |E|) time complexity for UVA problem "247 - Calling Circles". I also use hash table with open addressing and linear probing

	#include <iostream>
	#include <vector>
	#include <cstring>
	#include <string>
	#include <algorithm>
	#include <queue>
	#include <cstdio>
	#include <stack>
	#include <utility>
	using namespace std;

aleksmitov / BipartiteGraphCkeck.cpp

Created August 9, 2014 18:50

Bipartite graph check for UVa problem "11080 - Place the Guards"

	#include <iostream>
	#include <vector>
	#include <cstring>
	#include <string>
	#include <algorithm>
	#include <queue>
	#include <cstdio>
	#include <utility>
	using namespace std;
	int N, M;

aleksmitov / articulationPoints.cpp

Created August 9, 2014 18:31

Finding the Articulation points (cut vertexes) in a graph using Tarjan's algorithm with O(|V| + |E|). I also implement string hashing for the UVa problem "10199 - Tourist Guide"

	#include <iostream>
	#include <vector>
	#include <cstring>
	#include <string>
	#include <algorithm>
	#include <queue>
	#include <cstdio>
	#include <utility>
	using namespace std;
	const int TABLE_SIZE = 10000;

aleksmitov / 3D_range_sum.cpp

Last active August 29, 2015 14:04

Finding 3D range sum with O(N^5 complexity) using 1D & 2D range sums(Kadane's algorithm). Sample problem: UVA "Garbage Heap"

	#include <iostream>
	#include <cstring>
	#include <algorithm>
	using namespace std;
	typedef long long int i64;
	void read()
	{
	int A, B, C;
	i64 matrix[30][30][30];
	i64 maxSum = -(1LL << 60);

aleksmitov / bisection.cpp

Last active August 29, 2015 14:04

Example of using the Bisection method, page 86 of "Competitive programming 3" by Steven & Felix Halim

	#include <iostream>
	#include <iomanip>
	#include <algorithm>
	using namespace std;
	const double EPS = 1e-10;
	double f(double d, int m, int v, double i)
	{
	double loanLeft = v;
	for(int j = 0; j < m; ++j)
	{

aleksmitov / IntervalTree.cpp

Last active August 29, 2015 14:03

Implementation of Interval Tree with recursive Binary search

	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <cstdlib>
	using namespace std;

	struct IntervalTree
	{
	vector<int> data, tree;
	int N;

Aleksandar Mitov aleksmitov