Archive for September, 2017

AIBOHP – SPOJ

September 28, 2017

Find the minimum number of characters that needs to be added to a string to make is palindrome. (more…)

Advertisements

ACMAKER – SPOJ

September 28, 2017

Given a line that starts with acronym and has bunch of insignificant words. How many ways the acronym can be formed using significant (not insignificant) words so that each word has at least one char contributing to the acronym. (more…)

SAMER08D – DNA Sequences – SPOJ

September 26, 2017

Given two string, find the longest subsequence matching substrings of at least k sizes. (more…)

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. (more…)

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.  (more…)

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. (more…)

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. (more…)

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. (more…)

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. (more…)

Longest common substring

September 18, 2017

Given two strings, find the longest common substring between them. (more…)