ANNOUNCEMENT

-
I moved all the posts from Codrspace, another blogging platform. Here is the link to my Codrspace blog (now no longer updated.) So don't think I wrote all these posts in a single day. Thank you.

😌

Comments

Post a Comment

Popular posts from this blog

USACO Training "hamming": Hamming Codes

-
USACOT "hamming": Hamming Code Problem Statement Given N, B, and D: Find a set of N codewords (1 <= N <= 64), each of length B bits (1 <= B <= 8), such that each of the codewords is at least Hamming distance of D (1 <= D <= 7) away from each of the other codewords. The Hamming distance between a pair of codewords is the number of binary bits that differ in their binary notation. Consider the two codewords 0x554 and 0x234 and their differences (0x554 means the hexadecimal number with hex digits 5, 5, and 4):         0x554 = 0101 0101 0100         0x234 = 0010 0011 0100 Bit differences: xxx  xx Since five bits were different, the Hamming distance is 5. PROGRAM NAME: hamming INPUT FORMAT N, B, D on a single line SAMPLE INPUT (file hamming.in) 16 7 3 OUTPUT FORMAT N codewords, sorted, in decimal, ten per line. In the case of multiple solutions, your program should output the solution which, if interpreted a...
Read more

POJ 1088: Skiing

-
POJ 1088: Skiing Original Problem Statement Michael喜欢滑雪百这并不奇怪， 因为滑雪的确很刺激。可是为了获得速度，滑的区域必须向下倾斜，而且当你滑到坡底，你不得不再次走上坡或者等待升降机来载你。Michael想知道载一个区域中最长底滑坡。区域由一个二维数组给出。数组的每个数字代表点的高度。下面是一个例子 1 2 3 4 5 16 17 18 19 6 15 24 25 20 7 14 23 22 21 8 13 12 11 10 9 一个人可以从某个点滑向上下左右相邻四个点之一，当且仅当高度减小。在上面的例子中，一条可滑行的滑坡为24-17-16-1。当然25-24-23-...-3-2-1更长。事实上，这是最长的一条。 Translation On a 2D array, find the longest sequence of entries such that the sequence satisfies the following: For every entry i in the sequence (excluding the last), the entry after it, j, is less than i. For every entry i in the sequence (excluding the last), it is adjacent to the entry after it, j, on the 2D array. How You Should Think Of This Problem Find the longest decreasing subsequence in a 2D array. How To Solve It Instead of thinking how to implement LIS for a 2D array, think about how to convert it into a problem already seen before - well, 1D LIS. Let's store the data in an 1D array and include i...
Read more

OpenJudge 1768: Kadane's Algorithm on 2D Arrays

-
OpenJudge 1768: Kadane's Algorithm on 2-D Arrays Simple Version Given a 2-D matrix of integers, find the sub-matrix of this whose sum is maximized, and find that sum. The size of the matrix is no larger than 100 by 100. Analysis O(N^4) - Works, but naive     That's true, an naive O(N^4) version would work. We simply need to calculate (two dimensional!) prefix sums first. A quick review to what 2-D prefix sums are:     The 2-D prefix sum of two coordinates, X and Y, is the sum of all elements that have X-coordinate less than or equal to X, and Y coordinate less than or equal to Y.     It can be calculated through tabulation by removing overlapping areas.     Let P be the prefix sum array and V be the array of values, so the formula is as follows:     P[x, y] = V[x, y] - P[x-1, y] - P[x, y-1] + P[x-1, y-1].     We need to add the P[x-1, y-1] at the end since subtracting P[x-1, y] and P[x, y-1]...
Read more