Category: Algorithm

UVa 713. Adding Reversed Numbers

UVa 713: Adding Reversed Numbers is a straight-forward problem that can be solved using an ad-hoc algorithm. We have discussed a similar problem in a previous blog-post. However, this problem imposes following additional constraint—numbers will be at most 200 characters long–which necessitates the use of BigInteger. Following Java code shows such an ad-hoc algorithm that solves this problem by considering the stated constraints.

import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Scanner;
class Main {
private final Scanner in;
private final PrintWriter out;
public Main(){
in = new Scanner(System.in);
out = new PrintWriter(System.out, true);
}
public Main(Scanner in, PrintWriter out){
this.in = in;
this.out = out;
}
private static BigInteger bigIntAfterRemovingTrailingZeros(String num){
int nonZeroIndex=num.length()-1;
for (; nonZeroIndex>=0; nonZeroIndex--){
if (num.charAt(nonZeroIndex) != '0'){
break;
}
}
return new BigInteger(num.substring(0, nonZeroIndex+1));
}
private static BigInteger[] readLineAsBigInts(String input){
String [] ints = input.trim().split(" ");
BigInteger [] rets = new BigInteger[2];
rets[0] = bigIntAfterRemovingTrailingZeros(ints[0]);
rets[1] = bigIntAfterRemovingTrailingZeros(ints[1]);
return rets;
}
private static BigInteger reversedBigInt(BigInteger num1){
BigInteger reversedNum = BigInteger.ZERO;
final int _REM = 1;
final int _QUOTIENT = 0;
while (num1.compareTo(BigInteger.ZERO)>0){
BigInteger [] results = num1.divideAndRemainder(BigInteger.TEN);
reversedNum = reversedNum.add(results[_REM]);
if(num1.compareTo(BigInteger.TEN)>=0)
reversedNum =reversedNum.multiply(BigInteger.TEN);
num1 = results[_QUOTIENT];
}
return reversedNum;
}
private static BigInteger getAddRevNumbers(BigInteger num1, BigInteger num2){
return reversedBigInt(reversedBigInt(num1).add(reversedBigInt(num2)));
}
public void run(){
final int T = Integer.parseInt(in.nextLine().trim()); // no of test cases
BigInteger [] numbers;
for (int testCase = 0 ; testCase< T ; testCase++){
numbers = readLineAsBigInts(in.nextLine());// read input
out.println(getAddRevNumbers(numbers[0], numbers[1]));// print result
}
}
public static void main(String[] args) {
Main uva713Solver = new Main();
uva713Solver.run();
}
}
view raw uva713.java hosted with ❤ by GitHub

Please leave a comment if you have any question. Thanks.

See Also

see Party Schedule postSPOJ 42. Adding Reversed Numbers (ADDREV) with F#.

UVa 10664. Luggage

The UVa 10664: Luggage is a typical example of the problems that can be solved using dynamic programming (DP) technique. In fact, after further analysis, this problem can be realized as a special case of Subset-Sum problem, which we have discussed in a recent post.

The following Java code snippet outlines an algorithm using dynamic programming to solve this problem. Notice that the function solveLuggageProblem applies a bottom-up DP to construct dpTable. The boolean value of each dpTable[i][j] implies that whether it is possible to achieve weight j from the weights of 1..i suitcases. In this way, it determines whether halfWeight — the half of the total weights (of the suitcases)– can be derived from using 1..n suitcases, i.e., whether the weights of suitcases can be distributed equally into the boots of two cars.

import java.io.PrintWriter;
import java.util.Scanner;
class Main {
private final Scanner in;
private final PrintWriter out;
public Main(){
in = new Scanner(System.in);
out = new PrintWriter(System.out, true);
}
public Main(Scanner in, PrintWriter out){
this.in = in;
this.out = out;
}
private static int[] readLineAsIntegers(String input){
String [] ints = input.trim().split(" ");
int [] rets = new int[ints.length];
for (int i = 0 ;i < ints.length; i++)
rets[i] = Integer.parseInt(ints[i]);
return rets;
}
private String solveLuggageProblem(int[] weights){
final String _TRUE = "YES";
final String _FALSE = "NO";
int totalWeight = getTotalWeight(weights);
if (totalWeight%2 != 0)
return _FALSE;
int n = weights.length+1;
int halfWeight = totalWeight/2;
boolean [][] dpTable = new boolean [n][halfWeight+1];
// Base case 1: weights = 0 for all n --> True
for(int i = 0;i<n;i++)
dpTable[i][0] = true;
// Base case 2: weights !=0 for all n=0 --> False
for(int i = 1;i<halfWeight+1;i++)
dpTable[0][i] = false;
for (int i = 1; i< n; i++ ){
for (int j = 1; j< halfWeight+1; j++){
int w_i = weights[i-1]; // weight of ith item
if(j<w_i) // this item can't be included since its over the limit:j
dpTable[i][j] = dpTable[i-1][j];
else
dpTable[i][j] = dpTable[i-1][j] || dpTable[i-1][j-w_i];
}
}
return dpTable[n-1][halfWeight]==true?_TRUE:_FALSE;
}
private int getTotalWeight(int[] weights) {
int totalWeight = 0;
// compute total weight of the bags
for(int indx =0;indx< weights.length;indx++){
totalWeight += weights[indx];
}
return totalWeight;
}
public void run(){
final int T = Integer.parseInt(in.nextLine().trim()); // no of test cases
for (int i = 0 ; i< T ; i++){
int [] weights = readLineAsIntegers(in.nextLine());
// result:
out.println(solveLuggageProblem(weights));
}
}
public static void main(String[] args) {
Main solveLuggageProblem = new Main();
solveLuggageProblem.run();
}
}
view raw uva10664.java hosted with ❤ by GitHub

Please leave a comment if you have any question regarding this problem or implementation. Thanks.

See Also

see SPOJ 97. Party Schedule (PARTY) with F#SPOJ 97. Party Schedule (PARTY) with F#.
see SPOJ 8545. Subset Sum (Main72) with Dynamic Programming and F#SPOJ 8545. Subset Sum (Main72) with Dynamic Programming and F#.

UVa 102. Ecological Bin Packing | with Brute-force search

The UVa 102: Ecological Bin Packing can be solved using brute-force search, as outlined in the following Java code snippet. Note that, the primary function getOPTConfiguration iterates over all possible bin arrangements, and determines the arrangement that requires minimum bottle moves for a given problem instance.

import java.io.PrintWriter;
import java.util.Scanner;
class Main {
private Scanner in = new Scanner(System.in);
private PrintWriter out = new PrintWriter(System.out, true);
private char[] types;
private int[][] permutations;
private static final int _NO_OF_BINS = 3;
private static final int _BOTTLE_TYPES = 3;
private int optMoveCount;
private String optPermutation;
public Main(){
types = new char[]{'B','G','C'};
permutations = new int[][] {
{0,1,2},
{0,2,1},
{1,0,2},
{1,2,0},
{2,0,1},
{2,1,0}
};
}
private String permutationString(int permutationIndex){
String retString = "";
for(int i = 0;i<_NO_OF_BINS;i++){
retString += types[permutations[permutationIndex][i]];
}
return retString;
}
private void initState(){
optMoveCount = -1;
optPermutation = "";
}
/**
* A brute-force algorithm to determine a bin
* configuration that yield
* optimal (minimum) bin movements.
* @param input
* @return a String that represents OPT bin
* configuration that yields minimum movement.
*/
String getOPTConfiguration(int[][] input){
initState();
for (int pi = 0;pi<permutations.length;pi++){
int currentMoveCount = 0;
for (int bno=0;bno<_NO_OF_BINS;bno++){
int allowedType = permutations[pi][bno];
for(int btype = 0; btype<_BOTTLE_TYPES;btype++){
if (allowedType!=btype){
currentMoveCount += input[bno][btype];
}
}
}
String currentPermutation = permutationString(pi);
if ((this.optMoveCount == -1) ||
(currentMoveCount < optMoveCount) ||
((currentMoveCount == optMoveCount) && (currentPermutation.compareTo(optPermutation)<0))){
this.optMoveCount = currentMoveCount;
this.optPermutation = currentPermutation;
}
}
return optPermutation+" "+optMoveCount;
}
public void solve(){
int[][] inputBottles = new int[_NO_OF_BINS][_BOTTLE_TYPES];
while (in.hasNextInt()){
for(int i = 0;i<_NO_OF_BINS;i++){
for (int j=0;j<_BOTTLE_TYPES;j++){
inputBottles[i][j] = in.nextInt();
}
}
out.println(getOPTConfiguration(inputBottles));
}
}
public static void main(String[] args) {
Main binPackingSolver = new Main();
binPackingSolver.solve();
}
}
view raw uva102.java hosted with ❤ by GitHub

Please leave a comment if you have any question/comment. Happy coding!

SPOJ 8545. Subset Sum (Main72) with Dynamic Programming and F#

The Subset Sum (Main72) problem, officially published in SPOJ, is about computing the sum of all integers that can be obtained from the summations over any subset of the given set (of integers). A naïve solution would be to derive all the subsets of the given set, which unfortunately would result in  time complexity, given that is the number of elements in the set.

This post outlines a more efficient (pseudo-polynomial) solution to this problem using Dynamic Programming and F#. Additionally, we post C# code of the solution.

see Party Schedule postNote that we have solved a similar problem in Party Schedule (PARTY) with F# blog-post.

Interpretation

This problem provides a set of integers , and specifies the following constraints–

noun_project_6403 (1) The size of the given set, i.e., , where the value of is bounded by: .
noun_project_6403 (1) , the following condition holds: .

Given this input, we would like to find all the integers: and is the sum of the items of any subset over . Afterward, we sum all these integers, and return it as the result to the problem instance.

In essence, we reduce this problem as follows: Given  , can we express it using any subset over ? If yes, we include it in the solution set for summation. Interestingly, we  realize that the stated problem is a special case of a more general problem called Subset Sum, given that the sum is .

Algorithm

What would be the maximum possible value for ? Indeed, is not practical at all, as can be bounded by the following upper limit: , i.e., the summation of all the items in . This observation effectively reduces the search space to , for a given .

It implies that a naïve algorithm would require to iterate all the subsets over and verify whether their sum is within . Recall that, due to its exponential time complexity, it is quite impractical .

Using dynamic programming technique, a pseudo-polynomial algorithm can be derived, as the problem has an inherent optimal substructure property. That is, a solution of an instance of the problem can be expressed as the solutions of its subproblems, as described next.

We define as the function that determines whether the summation over any subset can result in the integer . So, it yields if sum can be derived over any subset, otherwise, . Also, note that,  and .

To define the recurrence, we describe in terms of its smaller subproblems as follows.

image

In Eq. (1), the first case refers to the fact that is larger than . Consequently,  can not be included in the subset to derive . Then, the case 2 of Eq. (1) expresses the problem into two subproblems as follows: we can either ignore though , or we can include it. Using any case stated in Eq. (1), if we can derive   i.e. = true, we can include it in the solution set.

As we can see overlapping subproblems, we realize that we can effectively solve them using a bottom-up dynamic programming approach. What about the base cases?

image

Using a table– dp, we can implement the stated algorithm as follows.

let computeSubsetSum (set:int array, n:int, sum:int):int =
// dp[i,j] = True, if subset of [0..i-1] sum
// equals to :
// j-set[i] => ith item is included
// or
// j => ith item is not included
let dp:bool[,] = Array2D.zeroCreate (n+1) (sum+1)
// This dp tries answer folloowing question, given a sum
// j, whether we can derive it by summing any subset of
// [0..i]. It computes this answer in bottom up manner,
// hence, if starting from (i,j) if it can reach (i,0), the
// answer is yes. Otherwise, if sum<>0 but i=0, then answer is
// no due to the fact that, using any subsets, the sum cannot be
// computed.
// Therefore.
// base case 1 : given sum = 0, answer is true
// sum is zero with the provided set of items.
// Hence, storing it as 0
for i = 0 to n do
dp.[i,0] <- true
// base case 2 : sum <> 0 but OPT = empty -->
// answer is false
for j=1 to sum do
dp.[0,j] <- false
for i = 1 to n do
let v_i = set.[i-1]
for j = 1 to sum do
dp.[i,j] <-
if j - v_i < 0 then
// we can't include i th item in OPT
dp.[i-1,j]
else
dp.[i-1,j]||dp.[i-1,j-v_i]
let mutable result = 0
for j=1 to sum do
result <- result+
( if dp.[n,j] = true then
j
else
0
)
result
view raw SPOJ_MAIN72.fsx hosted with ❤ by GitHub

In essence, the Nth row in the table provides the set of integers that can be derived by summing over any subset . Thereby, we compute the summation of all these integers that satisfies subsum(N,j) = true, and returns it as the result.

Conclusion

Full source code of the solution can be downloaded from this gist. For C# source code, please visit following gist. Please leave a comment if you have any question/suggestion regarding this post.

Enough said… now, it’s time for a 34-coffee and a new problem. See you soon; till then, happy problem-solving!

See Also

see SPOJ 97. Party Schedule (PARTY) with F#SPOJ 97. Party Schedule (PARTY) with F#.
see UVa 10664. LuggageUVa 10664. Luggage.

SPOJ 346. Bytelandian Gold Coins (COINS) with Dynamic Programming and F#

The Bytelandian Gold Coins problem, officially published in SPOJ, concerns computing the maximum dollars that can be exchanged for a Bytelandian gold coin. In this post, we outline a solution to this problem with memoization and F#.

Interpretation

The problem definition enforces following rules to perform the exchange. Consider, a Bytelandian gold coin —

noun_project_8551 It can be exchanged to three other coins, i.e., coins. Thus,  coin  yields value in bytelandian gold coins.
noun_project_8551 Alternatively, coin can be exchanged for dollars.

Our objective is to derive an algorithm that maximizes the dollars exchanged from the gold coin .

Algorithm

From the above interpretation, it is evident that the maximum achievable dollars, (from the exchange of coin ) can be computed  as follows.

image

It effectively demonstrates an optimal substructure and therefore, hints to a dynamic programming (DP) technique to solve it. That is, for a coin , the optimal value of dollar is given by the following function.

image

We employ a top-down DP approach, as it seems more efficient than a bottom-up approach in this context. It is due to the fact that a bottom-up approach generally requires an OPT table to persist results of smaller subproblems. As in this case, the value of can be very large (i.e., , a bottom-up DP would require a very large array, and performs more computations.  Hence, for the overlapping subproblems, we employ memoization.

let computeMaxDollars (n:int) (memo:Dictionary<int64,int64>)=
let rec computeMaxDollars' (ni:int64) =
if ni = 0L || ni = 1L then // base case
ni
else
match memo|> Memo.tryFind ni with
| Some (nx) -> nx // found in memo. Returning Result.
| None ->
let f = computeMaxDollars'
let nx =
(ni/2L, ni/3L, ni/4L)
|> (fun (x,y,z) -> (f x) + (f y) + (f z))
|> (fun nx -> Math.Max(ni,nx))
memo|> Memo.add ni nx |> ignore // storing the result in memo
nx
computeMaxDollars' (n|>int64)
view raw spoj_COINS.fsx hosted with ❤ by GitHub

The following code snippet outlines the implementation of Memo.

module Memo =
let empty () = new Dictionary<int64,int64>()
let add k v (memo:Dictionary<int64,int64>) =
memo.[k] <- v; memo
let tryFind k (memo:Dictionary<int64,int64>) =
match memo.TryGetValue(k) with
| true, v -> Some(v)
| false,_ -> None
view raw spoj_COINS.fsx hosted with ❤ by GitHub

Full source code of the solution can be downloaded from this gist. Please leave a comment if you have any question/suggestion regarding this post.
Happy problem-solving! noun_project_6324