current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 5 down vote favorite

I wrote following code for a Dynamic Programming problem but the online judge gives me a 'Time Limit Exceeded' error. I wonder how can I optimize this code more efficiently, especially the part of initializing the DP array to 0.0(I am using memset() right now.) Any pointers to the 'inefficient' lines of the code are welcome.

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
using namespace std;
#define max  2000
int main(){
    int T;
    double **dp = new double*[max];
    for(int i=0; i<max; ++i)
            dp[i] = new double[max];
    cin >> T;
    while(T--){
            int N;
            cin >> N;
            int V[N];
            for(int i=0; i<N; ++i)
                    cin >> V[i] ;
            for(int i=0; i<N; ++i)
                    memset(dp[i], 0.0, sizeof(dp[0][0])*N);
            for(int i=0; i<N; ++i)
                    dp[i][i] = V[i];
            for(int j=1; j<N; ++j)
                    for(int i=j-1; i>=0; --i){
                            dp[j][i] = 0.5 * ( dp[i][i] + dp[j][j] + dp[j-1][i+1] );
                            if( (i+2)<N )
                                    dp[j][i] += (0.250 * dp[j][i+2]);
                            if( (j-2)>=0 )
                                    dp[j][i] += (0.250 * dp[j-2][i]);
                    }
            cout << setprecision (5) << dp[N-1][0] << endl;
    }
    for(int i=0; i<max; ++i)
            delete[] dp[i];
    delete dp;
    return 0;
}

Thanks in advance,

EDIT:
The given problem is as following:
1. There are N values in an array. Two players take turn by turn to play the game.
2. Player1, with 50% probability can pick the left most value or the right most value.
3.If there is only one value left in the array, the player, having no more choice, will just pick up that value.
4. Question is to calculate the expected sum of values that First player can obtain.

Edit 2:
T<=500 and N<=2000
Updated code.
Now using dp array on stack instead of heap(as suggested by dasblinkenlight).

#include<iostream>
#include<iomanip>
#include<cstring>
#define max  2000
int main(){
    int T;
    std::cin >> T;
    while(T--){
            int N;
            std::cin >> N;
            int V[N];
            for(int i=0; i<N; ++i)
                    std::cin >> V[i];
            int r = N < 3 ? N : 3;
            double dp[r][N];
            for(int i=0; i<r; ++i)
                    dp[i][i] = V[i];
            for(int j=1; j<N; ++j)
                    for(int i=j-1; i>=0; --i){
                            dp[j%3][i] = 0.5 * ( V[i] + V[j] + dp[(j-1)%3][i+1] );
                            dp[j%3][i] += (0.250 * dp[(j-2)%3][i]);
                            if( (i+2)<N )
                                    dp[j%3][i] += (0.250 * dp[j%3][i+2]);
                    }
            std::cout << std::setprecision (5) << dp[(N-1)%3][0] << std::endl;
    }
    return 0;
}

This still gives me a 'Time Limit Exceeded' error.
I wonder if there is any better approach to solve this problem?

share|improve this question
    
Is there a public url that you could point us to for information on the problem? –  Glenn Rogers Oct 3 '12 at 12:15
    
Glenn: I've updated the Question. –  srbh.kmr Oct 3 '12 at 13:39
    
What is the time limit? Do you have any idea how much you're failing it by? That should help indicate if another approach is required. –  Glenn Rogers Oct 3 '12 at 18:04
    
sadly, I don't get to know the time when my code gets interuppted but for this question they give 4sec on their servers for K<=500 and N<=2000. I too guess theres' nothing much left to optimize so I've to come up with something better than O(N^2). like- O(NlogN) or O(N). Thanks for all your help guys. –  srbh.kmr Oct 3 '12 at 18:34
add comment

2 Answers

up vote 2 down vote

It looks like the nested loops of your algorithm are using only three rows of the dp matrix:

dp[j]
dp[j-1]
dp[j-2]

You can use this observation to transform your solution from one requiring O(N^2) space to one requiring O(N) space by changing

double **dp = new double*[max];

to

double dp[3][max]; // Now your matrix has a chance of fitting on the stack

and adding %3 to all operations that touch the first index of the dp matrix.

This may or may not eliminate the timeout, but it will make your program better by reducing the amount of resources that it needs to operate.

share|improve this answer
    
Thanks for suggesting a memory efficient approach. I've updated my code but it still goes over the allowed Time Limit! –  srbh.kmr Oct 3 '12 at 17:09
    
@srbh.kmr Does it produce the correct output? Can you switch from double to float? –  dasblinkenlight Oct 3 '12 at 17:11
    
I think so. Yes, it never gives me a 'Wrong answer' just runs out of time when submitted. and yes, I can change double to float but what difference would it make specifically? i wonder. –  srbh.kmr Oct 3 '12 at 17:15
    
@srbh.kmr Changing doubles to floats will reduce the amount of data needed for computation in half, improving the chance of hitting the cache more often. –  dasblinkenlight Oct 3 '12 at 17:26
    
Oh. Right. I was under the wrong impression that both double and float are 4Bytes. –  srbh.kmr Oct 3 '12 at 17:33
show 1 more comment
up vote 2 down vote

There are some things that I can think of:

  1. Is it quicker to deal with one blob of size max*max, and replacing dp[i][j] with dp[i+j*N]?
  2. Are you sure that your values are doubles, or could they be 32, 16, or even 8-bit integers? - less space to alloc/memset. Similarly, is your 2000 limit a specified one or one "large enough"?
  3. I'm not convinced that you actually need memset at all (You'll need to guard the dp[j-1][i+1] term which reaches below the diagonal for the first cells)! Because you're always refering to values to the 'bottom left' of the current cell, you never access values generated by the previous run...
  4. Also, because you "shouldn't" access values below the diagonal, all the dp[i] lines are actually (N - i) in length, so less to alloc/zero. You will though need to make other changes to the indices in the loops (and especially guard the dp[j-1][i+1] term).

And although it won't actually save any time, you can 'squash' a couple of loops together.

for(int i=0; i<N; ++i) {
    int V;
    cin >> V;
    memset( dp[i], 0, sizeof(dp[0][0])*N );
    dp[i][i] = V;
}

And don't forget that the final delete should be delete[] dp;!

share|improve this answer
    
Thanks for your review. Points noted but yes, result has to be a double. and T<=500 and N<=2000 is specified. and I need to do memset in order to zero out the dp[][] array for every new testcases. I know I'm allocating almost twice as many elements as I need to, but please take a look at my updated code. It still gives me 'Time Limit Exceeded' error! –  srbh.kmr Oct 3 '12 at 17:12
    
Actually, yes I can see I don't need that memset at all. Thanks, –  srbh.kmr Oct 3 '12 at 17:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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