Solution to the Flea Circus problem. It uses a range minimum query segment tree to compute the lowest common ancestor between two nodes in the tree, thus the distance from one node in a tree to another can be computed in O(log n)
time, and the tree can be built in O(log(n) n)
time. This allows the entire problem to be solved in O(log(n) n)
time.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
$ ps -o rss,command | grep ./omg | grep -v grep | |
488 ./omg | |
$ ps -o rss,command | grep ./omg | grep -v grep | |
10268 ./omg |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
var fs = require("fs"); | |
input_lines = fs.readFileSync('/dev/stdin').toString().split('\n').map(function(s) { | |
return s.trim(); | |
}); | |
nums = input_lines[0].split(' ').map(Number) | |
console.log(nums[0] + nums[1]) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
--- | |
BUNDLE_PATH: ./vendor/bundle | |
BUNDLE_DISABLE_SHARED_GEMS: '1' | |
BUNDLE_JOBS: 3 |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package segment_tree | |
import "fmt" | |
const sizeMultiplier int = 3 | |
type Comparator func(int, int) int | |
type Node struct { | |
set bool |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include<iostream> | |
#include<gmpxx.h> | |
#include<gmp.h> | |
#include<vector> | |
#include<string> | |
#include<cstdio> | |
using namespace std; | |
void set_prime(mpz_t rop) | |
{ |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'lastfm' | |
LASTFM_API_KEY = "" | |
LASTFM_SECRET = "" | |
SIRUPSEN = "f6b7ffe9b0c87fe8a341eb7a474f4574" | |
def get_token | |
lastfm = Lastfm.new(LASTFM_API_KEY, LASTFM_SECRET) | |
token = lastfm.auth.get_token |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class RedisQueue | |
include Enumerable | |
def initialize(queue) | |
@queue = queue | |
end | |
def each(&block) | |
while element = redis.lpop(@queue) | |
block.call(*JSON.parse(element)) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* | |
* This is a simple example of using memory mapped I/O with a data structure. | |
* The data structure used is a minimum query segment tree. This data structure | |
* can answer queries of which value in some interval from i..j is the minimum | |
* in O(log(n)) time. Updates are also O(log(n)). | |
* | |
* The data structure is persisted to the file passed as the first argument to | |
* the compiled program. Memory mapped I/O is nice because: | |
* | |
* 1. You get the speed and convenience of accessing memory. |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'benchmark' | |
class SlowTrie | |
attr_accessor :word, :nodes | |
def initialize | |
@word, @nodes = false, {} | |
end | |
def <<(word) |