Here’s a proof that, in the absence of the anomalous jumps mentioned by harold in the comments, the “start small” algorithm is optimal: First, let’s establish that “start small” always produces a feasible solution — that is, one that doesn’t contain any short encoding of a too-long jump. The algorithm essentially amounts to repeatedly asking … Read more
One option would be the following: Using a linear-time selection algorithm like median-of-medians or introsort, find the kth largest element and rearrange the elements so that all elements from the kth element forward are greater than the kth element. Sort all elements from the kth forward using a fast sorting algorithm like heapsort or quicksort. … Read more
I’ve been tinkering with an approach that (1) multiplies a and b with the school algorithm on 21-bit limbs (2) proceeds to do long division by c, with an unusual representation of the residual a*b – c*q that uses a double to store the high-order bits and a long to store the low-order bits. I … Read more
In case you want the sample to follow a uniform distribution, the problem reduces to generate N random numbers with sum = 1. This, in turn, is a special case of the Dirichlet distribution but can also be computed more easily using the Exponential distribution. Here is how: Take a uniform sample v1 … vN … Read more
The source code from the Fhourstones Benchmark from John Tromp uses a fascinating algorithm for testing a connect four game for a win. The algorithm uses following bitboard representation of the game: . . . . . . . TOP 5 12 19 26 33 40 47 4 11 18 25 32 39 46 3 … Read more
To answer the question of “Why does Hoare partitioning work?”: Let’s simplify the values in the array to just three kinds: L values (those less than the pivot value), E values (those equal to the pivot value), and G value (those larger than the pivot value). We’ll also give a special name to one location … Read more
Here is the example of GNU Policy-Based STL MAP implemented as order statistic tree (tested on Linux gcc 4.6.1): #include <iostream> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; typedef tree< int, int, less<int>, rb_tree_tag, tree_order_statistics_node_update> map_t; int main() { map_t s; s.insert(make_pair(12, 1012)); s.insert(make_pair(505, 1505)); s.insert(make_pair(30, 1030)); cout << s.find_by_order(1)->second << ‘\n’; … Read more
There is a better algorithm, which needs at most 6 iterations to converge to maximum precision for double numbers: #include <math.h> double sqrt(double x) { if (x <= 0) return 0; // if negative number throw an exception? int exp = 0; x = frexp(x, &exp); // extract binary exponent from x if (exp & … Read more
I’ll first give you the code and then explain it a bit: // direction vectors const int dx[] = {+1, 0, -1, 0}; const int dy[] = {0, +1, 0, -1}; // matrix dimensions int row_count; int col_count; // the input matrix int m[MAX][MAX]; // the labels, 0 means unlabeled int label[MAX][MAX]; void dfs(int x, … Read more
if n is not far from r then using the recursive definition of combination is probably better, since xC0 == 1 you will only have a few iterations: The relevant recursive definition here is: nCr = (n-1)C(r-1) * n/r This can be nicely computed using tail recursion with the following list: [(n – r, 0), … Read more