4
\$\begingroup\$

I am solving ROCK problem on SPOJ. I have used bottom up dynamic programming approach for this problem. Time complexity for this is \$O(n^3)\$.

#include<stdio.h>
#include<string.h>
#include<math.h>
#define MAX 210
#define NEG_INFINITY -1000

int sellable(int a[MAX], int i, int j)
{
    int index,sweet=0,sour=0;
    for(index=i;index<=j;index++)
    {
        if(a[index])
            sweet++;
        else
            sour++;
    }
    if(sweet>sour)
        return 1;
    return 0;
}
int main()
{
    int test_cases,i,j,k,length,l;
    int number,cost;
    int a[MAX];
    int m[MAX][MAX];
    char buffer[MAX];

    for(scanf("%d",&test_cases);test_cases>0;test_cases--)
    {       

        scanf("%d",&number);
        for(i=0;i<number;i++)
            for(j=0;j<number;j++)
                m[i][j]=NEG_INFINITY;
        scanf("%s",&buffer);
        for(i=0;i<number;i++)
        {
            a[i]=buffer[i]-'0';
            m[i][i]=a[i];
        }
        for(l=2;l<=number;l++)
        {       
            for(i=0;i<number-l+1;i++)
            {
                j=i+l-1;
                for(k=i;k<j;k++)
                {
                    if(sellable(a,i,j))
                        cost=j-i+1;
                    else
                        cost=m[i][k]+m[k+1][j];
                    if(cost>m[i][j])
                    {
                        m[i][j]=cost;
                    }
                }
            }
        }
        printf("%d\n",m[0][number-1]);
    }
    return 0;
} 

Can you please suggest an alternative approach for this problem, or if any changes can be made in my code?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ The constraints scream \$O(n^3)\$, so I would look into potential constant optimizations. \$\endgroup\$
    – Niklas B.
    Jul 9, 2014 at 19:45

1 Answer 1

3
\$\begingroup\$

The way you call sellable may amount to a 4-th degree complexity. The very smart compiler may notice that it is a pure function, and optimize it out of the inner loop, but I wouldn't rely on it. So, one obvious optimization is to rephrase it as

if (sellable(a, i, j)) {
    cost = j - i + 1;
} else {
    cost = m[i][j];
    for (k = i; k < j; k++) {
        cost = max(cost, m[i][k] + m[k+1][j]);
}
m[i][j] = max(m[i][j], cost);

Still, sellable contributes to the cubic complexity. With a one-time linear investment you can make it into a constant time. Collect accumulated sums [0, i) of the input array; then sellable becomes just

return (a[j] - a[i]) * 2 > (j - i);

The mandatory CR note on the variable names: one letter identifiers make it really hard to follow the code, even as simple as this. I would recommend to use length, seg_start, seg_end instead of l, i, j respectively. number is just meaningless; size sounds better.

Then, I'd highly recommend to interpret length as length (not length + 1 as your code does).

Finally, please don't be shy on spaces.

\$\endgroup\$
1
  • \$\begingroup\$ Only the first change itself lowered my running time by multitudes. Now I understand how I had put forth order just by messing up the order of execution. Thanks a lot for such precise answer. I have lot to learn. \$\endgroup\$
    – Naman
    Jul 10, 2014 at 5:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.