10
\$\begingroup\$

I have a N*N upper triangular matrix with property such that, all its diagonal elements are a1,a2,a3,...,aN. I want that a[i][j] (for all j>i) should be

(a[i][j-1] + a[i+1][j]) / 2.

I have many test cases, and I have to apply this property every time to calculate the answer. What is the most optimal way to do this, so that for all test cases the overall running time is less? Test cases: Inputs are N and a1,a2,...,aN.

To calculate the answer, I need to do:

a[0][0] + a[0][2] + ... + a[0][n-1] + a[2][n-1] + a[4][n-1] + ... + a[n-1][n-1].

My solution (which keeps getting timed out):

#include<stdio.h>
double a[2000][2000];
int main(){
int test;
scanf("%d",&test);
//int arr[2000];
while(test--){
    int n,i,j;
    //scanf("%d",&n);
    scanf("%d",&n);
    for(i=0;i<n;i++){
         int num;
         scanf("%d",&num);
         if(n!=1)
            a[i][i] = num*0.5;
         else
            a[i][i] = num;
     }
    for(j=1;j<n;j++){
         int k=j;
         for(i=0;i<n-j;i++,k++){
             if(i==0 && k==n-1)
                 a[i][k] = (a[i+1][k]+a[i][k-1]);
             else
                 a[i][k] = (a[i+1][k]+a[i][k-1])*0.5;
         }
     }
     float sum=0.0;
     for(i=0;i<n;i+=2){
         if( i != n-1 )
         sum+=a[0][i]+a[n-1-i][n-1];
         else
         sum+=a[0][i];
     }
    printf("%.3f\n",sum);
}
getch();
}

Please provide some hints how to optimize the above code.

\$\endgroup\$
6
\$\begingroup\$

I suggest dropping the floating point and doing it fixed point. To do this I would make a[][] of type int or short (depending upon the input constraints) and instead of storing values x and x * 0.5, store 2x and x respectively. At the end of the summation you can then divide by 2 to get the true result.

The only issue this raises is that of integer overflow. You don't state any numerical constraints but the fixed size arrays (2000x2000) suggest overflow will not occur with long long. Alternatively the summation itself could be floating point while the array values remain integers. I notice that your current summation uses float which might well be slower than double.

Another minor point where you can improve the speed is in the input loop. You have the conditional

if(n!=1)
    a[i][i] = num*0.5;
else
    a[i][i] = num;

As the loop variable i goes from 0 to n, if n is 1 then the loop only fills a[0][0] and so this conditional can be removed from the loop. But if n is small this will make little difference.

\$\endgroup\$
6
\$\begingroup\$

@WilliamMorris had some good points on improving your code. I have a few things to add though.

There is an implicit declaration of function getch() in your code, which is invalid in C99.

#include <conio.h> // on Linux
#include <curses.h> // on Mac

getch() is (technically) deprecated. It is still okay to use it, but I prefer getchar() instead. You also get rid of a dependency, which means your code will work on more systems (with getch(), your code would not work on my computer, but with getchar() it did).


You don't check if your input is actually an int. That could lead to invalid input, and since your program isn't built to handle that it is considered a security flaw.

if (!isdigit(n))
{
    printf("Invalid input.\n");
    return -1; // returning is kind of drastic.
               // It's better to let the user re-enter valid input in a loop.  
               // I'll let you implement that in your code though if you deem it necessary
}

With the addition of isdigit(), we will have to add a header.

#include <ctype.h>

Many systems support <ctype.h>, so while it is a dependency, it is minor and necessary.


Everything feels very squished in your code with lack of whitespace. Let's add some space to let your code breathe and make it more readable. Don't take this too far though, because too much whitespace can also make your code unreadable. The place where I see this is needed the most is the adding of matrices.

sum+=a[0][i]+a[n-1-i][n-1]; // Takes a bit to read and understand
sum += a[0][i] + a[n-1-i][n-1]; // Eases the reading and understanding process a bit.

Your variable names make this program a bit obfuscated in it's current stance. The variable names are somewhat acceptable in this case though, since you are dealing which the indexes of matrices, which are hard to give proper names.


Final code:

#include <stdio.h>
#include <ctype.h>

double a[2000][2000];
int main()
{
    int test;
    scanf("%d", &test);
    if (!isdigit(test))
    {
        printf("Invalid input.\n");
        return -1;
    }
    while (test--)
    {
        int n, i, j;
        scanf("%d", &n);
        if (!isdigit(n))
        {
            printf("Invalid input.\n");
            return -1;
        }
        for (i=0; i<n; i++)
        {
            int num;
            scanf("%d", &num);
            if (!isdigit(num))
            {
                printf("Invalid input.\n");
                return -1;
            }
            if (n !=1 ) a[i][i] = num * 0.5;
            else a[i][i] = num;
        }
        for (j=1; j<n; j++)
        {
            int k = j;
            for(i=0; i < n-j; i++, k++)
            {
                if(i == 0 && k == n-1) a[i][k] = (a[i+1][k] + a[i][k-1]);
                else a[i][k] = (a[i+1][k] + a[i][k-1])*0.5;
            }
        }
        float sum = 0.0;
        for (i=0; i<n; i+=2)
        {
            if( i != n-1 ) sum += a[0][i] + a[n-1-i][n-1];
            else sum += a[0][i];
        }
        printf("%.3f\n", sum);
        getchar();
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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