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\$ Commented Jul 9, 2014 at 19:45

1 Answer 1

Reset to default
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\$ Commented Jul 10, 2014 at 5:53

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.