CODEWITHSUNDEEP
algorithmdynamic-programming
Alok Tripathy
Alok Tripathy

Reputation: 11

Dynamic programming based zigzag puzzle

I found this interesting dynamic programming problem where it's required to re-order a sequence of integers in order to maximize the output.

Steve has got N liquor bottles. Alcohol quantity of ith bottle is given by A[i]. Now he wants to have one drink from each of the bottles, in such a way that the total hangover is maximised. Total hangover is calculated as follow (Assume the 'alcohol quantity' array uses 1-based indexing) :

int hangover=0 ;
for( int i=2 ; i<=N ; i++ ){
    hangover += i * abs(A[i] - A[i-1]) ;
}

So, obviously the order in which he drinks from each bottle changes the Total hangover. He can drink the liquors in any order but not more than one drink from each bottle. Also once he starts drinking a liquor he will finish that drink before moving to some other liquor.

Steve is confused about the order in which he should drink so that the hangover is maximized. Help him find the maximum hangover he can have, if he can drink the liquors in any order.

Input Format : First line contain number of test cases T. First line of each test case contains N, denoting the number of fruits. Next line contain N space separated integers denoting the sweetness of each fruit.

2
7
83 133 410 637 665 744 986
4
1 5 9 11

I tried everything that I could but I wasn't able to achieve a O(n^2) solution. By simply calculating the total hangover over all the permutations has a O(n!) time complexity. Can this problem be solved more efficiently?

Thanks!

Upvotes: 1

Views: 169

Answers (1)

user3235832
user3235832

Reputation:

My hunch: use a sort of "greedy chaining algorithm" instead of DP.

1) find the pair with the greatest difference (O(n^2))

2) starting from either, find successively the next element with the greatest difference, forming a sort of "chain" (2 x O(n^2))

3) once you've done it for both you'll have two "sums". Return the largest one as your optimal answer.

This greedy strategy should work because the nature of the problem itself is greedy: choose the largest difference for the last bottle, because this has the largest index, so the result will always be larger than some "compromising" alternative (one that distributes smaller but roughly uniform differences to the indices).

Complexity: O(3n^2). Can prob. reduce it to O(3/2 n^2) if you use linked lists instead of a static array + boolean flag array.

Pseudo-ish code:

int hang_recurse(int* A, int N, int I, int K, bool* F)
{
    int sum = 0;
    for (int j = 2; j <= N; j++, I--)
    {
        int maxdiff = 0, maxidx;
        for (int i = 1; i <= N; i++)
        {
            if (F[i] == false)
            {
                int diff = abs(F[K] - F[i]);
                if (diff > maxdiff)
                {
                    maxdiff = diff;
                    maxidx = i;
                }
            }
        }
        K = maxidx;
        F[K] = true;
        sum += maxdiff * I;
    }
    return sum;
}

int hangover(int* A, int N)
{
    bool* F = new bool[N];
    int maxdiff = 0;
    int maxidx_i, maxidx_j;
    for (int j = 2; j <= N; j++, I--)
    {
        for (int i = 1; i <= N; i++)
        {
            int diff = abs(F[j] - F[i]);
            if (diff > maxdiff)
            {
                maxdiff = diff;
                maxidx_i = i;
                maxidx_j = j;
            }
        }
    }
    F[maxidx_i] = F[maxidx_j] = true;
    int maxsum = max(hang_recurse(A, N, N - 1, maxidx_i, F),
                     hang_recurse(A, N, N - 1, maxidx_j, F));
    delete [] F;
    return maxdiff * N + maxsum;
}

Upvotes: 1

Related Questions