Strange Docs

In simple terms, Modular Arithmetic calculates the remainder of anything divided by anything. The later is called modulus. e.g. ( 15 / 7 ) Quotient: 2, Remainder 1.  In greater sense,  modular arithmetic  is a system of  arithmetic  for  integers , where numbers "wrap around" upon reaching a certain value—the  modulus ( src: Wikipedia ). Take a look at hour clock. After 12:59 pm, we say 1:00 pm, because we modulo the hours by 12. 13 pm % 12 is 1 pm. (%) represents modulus operator. Examples: 5 % 2 = 1, 14458948 % 25 = 23 a≡b (mod n) This says that a  A is  congruent  to b modulo n. It means both a and b has same remainder when divided by n. e.g. 38 ≡14 (mod 12) Commonly Used Properties: Reflexivity:  a  ≡  a  (mod  n ) Symmetry:   a  ≡  b  (mod  n )   if and only if   b  ≡  a  (mod  n ) Transitivity: If   a  ≡  b  (mod  n )   and   b  ≡  c  (mod  n ) , then   a  ≡  c  (mod  n ) If   a 1  ≡  b 1  (mod  n )   and   a 2  ≡  b 2  (mod  n ),   or if   a

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

Problem Statement: ANARC09A - Seinfeld Explanation: Minimum moves for balancing brackets

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

Problem Statement: ENIGMATH - PLAY WITH MATH Heuristic: Ax - By = 0   has two possible cases:   a can divide b or if b can divide a  and you can figure out the rest.  a or b cannot divide the other so it will be A B - B A = 0, but we still have to find the minimum x & y.

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