# SPOJ is giving TLE for this solution of ROCK

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?

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

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.

• 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. Jul 10, 2014 at 5:53