SAMER08D – DNA Sequences – SPOJ

September 26, 2017

Given two string, find the longest subsequence matching substrings of at least k sizes. Read the rest of this entry »


Square Brackets – SPOJ

September 24, 2017

Given n integers and k values <= 2n. Find the number of proper bracket expressions (proper starting and ending brackets) with “[” enforced in each p[k] positions. Read the rest of this entry »

Create all possible combinations

September 24, 2017

This was an attempt to solve SPOJ – SQRBR, but gives TLE. It explores all the options recursively, and without the use of dynamic programming. This technique can be used to generate all the combination of certain values.  Read the rest of this entry »

Mixtures – SPOJ

September 23, 2017

Given mixtures in a row. When they are mixed with each other, the result is modulus 100 of the sum. This replaces the mixing color. During mixing the process some smoke is generated (as by product), the quantity of which is the result of multiplication of two mixtures. Minimize the smoke generated when mixing two mixture. Read the rest of this entry »

Matrix Chain Multiplication (MCM)

September 23, 2017

Given the dimensions of matrices next to each other, find the best way to parenthesize (multiply the matrices) that minimized the number of multiplication. Read the rest of this entry »

Martian – SPOJ

September 19, 2017

Given a grid that contains two types of minerals B and Y. If the refinery to B are at top and Y are at left and the corresponding minerals gets collected if there is a straight path from that grid location all the way to the refinery. Maximize the total amount of mineral mined. Read the rest of this entry »

Minimum number of coins

September 18, 2017

Given some denomination of coins (you can use any coins of one type), find the minimum no. of coins that can be used to get sum S. Read the rest of this entry »

Longest common substring

September 18, 2017

Given two strings, find the longest common substring between them. Read the rest of this entry »

Longest common subsequence

September 17, 2017

Given two sequence of elements (e.g. characters) find the longest common subsequence. Read the rest of this entry »

0/1 Knapsack

September 17, 2017

Given some weights and corresponding values associated with each weight, maximize the value while keeping the weight below a given weight. Also, each weight can be picked only once. Read the rest of this entry »