Can't figure out what the generic name of this algorithm is called?

Question

I just did a Top Coder SRM where there was a question I had problem solving. I am trying to searching online for details of the algorithm but I can't seem to find it.

The question went around the lines of: You have an array, for example [12, 10, 4]

Each round, you can apply any permutation of 9,3,1 to subtract from [12,10,4]

Return the minimum amount of permutations needed to be applied to get to 0 for all numbers in the array.

Any help?

Edit: Let me be somewhat more descriptive so that the question can be understood better.

One question would be
input: [12 10 4]
output: 2 (minimum rounds)

How it would work:
[12 10 4] - [9 3 1] = [3 7 3]
[12 10 4] - [9 1 3] = [3 9 1]
[12 10 4] - [3 9 1] = ..
[12 10 4] - [3 1 9] = ..
[12 10 4] - [1 3 9] =
[12 10 4] - [1 9 3] =

[3 7 3] - [3 9 1] = ...

..
[9 1 3] - [9 1 3] = [0 0 0] <-- achieved with only two permutation subtractions

Edit2:

Here is the topcoder question: http://community.topcoder.com/stat?c=problem_statement&pm=13782

Edit3: Can anyone also explain the Overlapping Subproblem and Optimal Substructure if they believe a solution is with dynamic programming?

Answer 1

EDIT :

after seeing the original question, here is the solution which gave correct output for every testcase provided in above question link, if u want give input {60} , u shud give as {60,0,0} .

Basic idea is , u need to get all of them less than or equal to zero atlast , so if number is divisible by 3 , u can get zero by subtracting 9 or 3 and if not divisible, subtract by 1 to make it divisible by 3

first , sort the given triplet , then

• check the largest number is divisible by 3, if so, subtract 9 and the number still can be divisible by 3
• now check the next largest number , if it is divisible by 3, subtract 3 else subtract 1
• if largest number is not divisible by 3, subtract 1 so that it may be divisible by 3
• now subtract next largest number by 9 and the other one by 3

here is the implementation

#include <iostream>
#include <algorithm>
#include<cmath>
using namespace std;
int f(int* a,int k){
sort(a,a+3);
if(a[2]<=0 )
{cout << k<< endl ;
return 0;}

if(a[1]<=0){
cout << k+ceil((double)a[2]/9) << endl;
return 0;

}
if(a[2]%3==0 ){
a[2]=a[2]-9;
if(a[1]%3==0 )
{
    a[1] = a[1] -3;
    a[0] = a[0] -1;
}
else{
    if(a[2]%2==0 && (a[1]-1)%2==0  && a[1]!=0){
        a[2]=a[2] +9 -3;
        a[1] = a[1] -9;
        a[0] = a[0]-1;
    }
    else{
    a[1] = a[1] -1;
    a[0] = a[0] - 3;}
}
return f(a,++k);
}
else{
a[2] = a[2] -1;

    a[1] = a[1] -9;
    a[0]=a[0] -3;
return f(a,++k);

}
}
int main() {

int a[] = {54,18,6};
f(a,0);
return 0;
}

hope this is helpful

Example: input is [12,4,10]

sort it [12,4,10] -> [12,10,4]

now check if largest number is divisible by 3, here Yes

so [12-9,10,4] -> [3,10,4] now check next largest number divisible by 3, here N0

so [3,10-1,4-3] ->[3,9,1]

now increment count and pass this to function (recursive)

input -> [3,9,1]

sort [3,9,1] -> [9,3,1]

now check if largest number is divisible by 3, here Yes

so [9-9,3,1] -> [0,3,1]

now check next largest number divisible by 3, here Yes

so [0,3-3,1-1] -> [0,0,0]

now increment the count and pass the array

as largest element is 0 , we will print count and that is 2

Answer 2

It can be solved using dynamic programming. If you look at common solutions to dynamic programming problems, they follow the same general structure. We use an array to store the minimum number of permutations needed to reach each value, and update each value in turn using nested loops. The answer will end up in d[0][0][0] which is the number of permutations required to get to [0, 0, 0].

public static int count(int a, int b, int c) {
    int[][] permutations = {{9, 3, 1}, {9, 1, 3}, {1, 9, 3}, {1, 3, 9}, {3, 9, 1}, {3, 1, 9}};

    int[][][] d = new int[a + 1][b + 1][c + 1];

    // Set initial values to high value to represent no solution.
    for(int x = 0; x <= a; x++) {
        for(int y = 0; y <= b; y++) {
            for(int z = 0; z <= c; z++) {
                d[x][y][z] = Integer.MAX_VALUE / 2;
            }
        }
    }

    // Set number of permutations for initial value to 0.
    d[a][b][c] = 0;

    // Update all values.
    for(int x = a; x >= 0; x--) {
        for(int y = b; y >= 0; y--) {
            for(int z = c; z >= 0; z--) {
                for(int[] p:permutations) {
                    // Update count from [x, y, z] -> [nx, ny, nz] using permutation p.
                    int nx = x - p[0];
                    int ny = y - p[1];
                    int nz = z - p[2];
                    if(nx >= 0 && ny >= 0 && nz >= 0) {
                        d[nx][ny][nz] = Math.min(d[nx][ny][nz], d[x][y][z] + 1);
                    }
                }
            }
        }
    }

    // Return final answer.
    return d[0][0][0];
}

Answer 3

Let the number of elements be n, let p₁ to p_n! be the permutations of the array you want to subtract, and let A be your original array. Then you want the natural numbers solutions of the linear system

A - k₁*p₁ - ... - k_n!*p_n! = 0

which is equivalent to

A = k₁*p₁ + ... + k_n!*p_n!

where 0 is the n-item array with all zeroes. You can't figure that out using the obvious linear algebra solution since ℕ^n is not an ℕ-vector space; actually, finding solutions to linear systems over natural numbers in general is NP-complete by a reduction from subset sum. I couldn't adapt the reduction to your version of the problem ad hoc, so maybe think about that for a bit. It should remain NP-hard, at least that's what I would expect.