Strange Docs

Unbounded Knapsack : Given a knapsack weight W and a set of N items with certain value Vi and weight W i , we need to calculate minimum amount that could make up this quantity exactly. To have a more clear understanding of this problem, see SPOJ-PIGBANK Sample Problem : We're given a box which can hold maximum W weight. There are N various coins each of value Vi and Weight Wi. We need to fill the box with total W weight with any number of coins of any value. Note that coins are unlimited.  100 ----- W 2 ------- N 1 1 ----- vi,wi 30 50 --- vi,wi Answer of the problem above is, 60. If we take 2 coins of value 30, weight 50, we'll get exactly weight 100 with a minimum value of 60. Algorithm : This is a DP solution. To get the solution for W=100, we'll solve subproblems first. Let dp[W+1]  be an array which will store the subproblems solutions. In the end, dp[W] will give us the minimum amount. Subproblems soultion will be the minimum of taking the coin Vk ...

You’re given a non-empty string made in its entirety from opening and closing braces. Your task is to find the minimum number of “operations” needed to make the string stable. The definition of being stable is as follows: An empty string is stable. If S is stable, then {S} is also stable. If S and T are both stable, then ST (the concatenation of the two) is also stable. All of these strings are stable: {}, {}{}, and {{}{}}; But none of these: }{, {{}{, nor {}{. The only operation allowed on the string is to replace an opening brace with a closing brace, or visa-versa. Solution Heuristics: Traverse the string. When the number of opening braces( { ) matches the number of closing braces ( } ), the string is balanced. Else it's not balanced. So count both of them. Make a list. Insert only opening braces. If a closing brace is found delete one brace( if the size of the list is > 0 ) from the list. Because they would make a pair. If the list is empty then we'll conve...

Given an arbitrary series, we've to calculate the maximum sum confined to only one restriction- If we choose any number a [ i ] to calculate the sum, we can't choose a [ i+1 ] Let's take a series: a[ ]= {1,2,3,4,5,9} Linear Solution: Take two variable inc and exl . inc will store value if we choose a [ i ] to calculate the sum & exl will store value if we do not choose a [ i ], for any 0 ≤ i ≤ n. Now for every step, we have to calculate inc and exl . After iteration ends, max( inc,exl ) is the maximum non-contiguous sum. Roughly- Why inc = exl + a [ i ] ? because the already calculated exl is from i-2 . So if we choosed inc=  inc + a [ i ] , that would be a contiguous sum . exl is maximum of inc & exl right until   i-1 . Top Down solution( DP ): If you're familiar with dynamic programming, you know that, we need to calculate dp[n] - the maximum non contiguous sum at nth index. Now we can have two possible state, we'll select the maximum ...

Imagine a climber trying to climb on top of a wall.  A wall is constructed out of square blocks of equal size. From each block, the climber can reach three blocks of the row right above: one right on top, one to the right and one to the left ( unless right or left not available because that is end of the wall ). Find the least costly path from bottom to top where cost is the summation of costs of the blocks used on the path. Problem Representation: An NxM size grid where each cell has a positive cost C(i,j) associated with it. There exists three possible moves from a cell (i,j) - i+1,j-1     [ diagonally left ] i+1. j       [ above ] i+1.j+1     [ diagonally right ] Take an array dp[ n ][ m ] that will hold the cost for all cells. Initiate dp[ 0 ][ i ] = C(0,i)  for 0 ≤ i ≤ m . There are three cases to the recurrence: a cell might be in the middle (horizontally), on the leftmost or  on ...

Problem Statement: http://www.spoj.com/problems/AGGRCOW/ Solution:  

Given a number, we have to find the next smallest palindrome which is larger than this number.  The input can be large. We'll store the input in an array. e.g. if input is  1259, array will be, int k[]= {1,2,5,9} To find the next smallest palindrome, we have to generalize the input. There can be three types of input.    All digits are 9. e.g. 999 Input is not a palindrome. e.g 12942 The input itself a palindrome number. e.g. 1221 Algorithm for the first type is easy. Expand the array length by one and put boundary digits as 1 & all other digits will be 0.  Input :    999 Output : 1001   Left half & Right half : Using example, left half of 522665 is, 522 & left half of 52123 is 52 . Right half of 522665 is 665 & right half of 52123 is 23 .   Iteration: We'll compare between left half and right half, starting from middle. For example, two variable i and j will indicate to 2 & 4 respecti...

Find the number of trailing zeroes in 122! ?  That's a big number right? The solution is pretty simple. Ask yourself when does any multiplication results in a trailing zero? The answer is (2x5) = 10, leaves one zero behind. The factorial of 122 is a multiplication which you already know. The expansion is, 98750442008336013624115798714482080125644041369 78359605958470050267671457205014364903379642774 50422940710230505796264047365129395968426948958 2137821062001338805474721479524352 0000000000000 000000000000000 So, we have to find the number of multiples of 5 from the expansion and they are 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120. So there are 24 multiples of 5. then again, 25= 5 x 5 , which has another extra factor of  5 to count. So how many multiples of 25 from 1 to 122? (122 / 25) = 4 (taking the only integer) So, add that 4 to the earlier count. 24 + 4 = 28 , so we have 28 trailing zero in 122! Let's take a num...

Sieve of Eratosthenes is explained HERE Bitwise sieve is an optimized implementation of  Sieve of Eratosthenes. It does the same thing but more memory efficient because it uses logic operations( &,|,>>,<< ) on binary numbers. In normal implementation, we use an array as flag to check if a number is prime or not.we know index of an array ( i.e  myarray[n]  ) is 32 bit long. If an array is 10 index long, that it has 32x10(=320) bits.  We use bits of that array as flag. that way we can flag numbers upto 320 as prime or not prime. i.e, how to check the flag status of 51 in myarray[ n ] ? We'll divide 5 by 32, that will give us the index number of the certain bit, then we'll mod 5 by 32, that will give us the certain bit position to check for 0 or 1. Remember bit positions are defined from right to left, starting from 0. Meaning LST = 0 and MST = 31. So we need to define two functions, one to set that certain bit as 0 or 1, another to check if...