The problem is in the step where you say to find the true median of the medians. In your example, you had these medians: 50 45 40 35 30 25 20 15 10 The true median of this data set is 30, not 15. You don’t find this median by splitting the groups into blocks … Read more
This is a pretty clever solution — it exploits the fact that there is a pattern of results in the running XORs. The f() function calculates the XOR total run from [0, a]. Take a look at this table for 4-bit numbers: 0000 <- 0 [a] 0001 <- 1 [1] 0010 <- 3 [a+1] 0011 … Read more
What you are talking about is lifetime dependency chaining, that one thing is dependent on another which can be modified outside of it’s control. If you have an idempotent function from a, b to c where, if a and b are the same then c is the same but the cost of checking b is … Read more
The simplest approach is as follows: Sort the list: O(n lg n) The sorted list is the first permutation Repeatedly generate the “next” permutation from the previous one: O(n! * <complexity of finding next permutaion>) Step 3 can be accomplished by defining the next permutation as the one that would appear directly after the current … Read more
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
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
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 you read the documentation it is mentioned this function implements the algorithm of: Suzuki, S. and Abe, K., Topological Structural Analysis of Digitized Binary Images by Border Following. CVGIP 30 1, pp 32-46 (1985) OpenCV is open source if you want to see how this is implemented just need to read the code: https://github.com/opencv/opencv/blob/master/modules/imgproc/src/contours.cpp#L1655 … Read more
MergeSort time Complexity is O(nlgn) which is a fundamental knowledge. Merge Sort space complexity will always be O(n) including with arrays. If you draw the space tree out, it will seem as though the space complexity is O(nlgn). However, as the code is a Depth First code, you will always only be expanding along one … Read more