Triples shows time limit exceedes

Dev Skill archived problems can be discussed here.

Triples shows time limit exceedes

by arabin » Thu Oct 27, 2016 6:43 pm

my solution shows timelimit exceedes. how can i improve my solution. please suggest me anyone. thanks

Code: Select all
#include <stdio.h>

#define ASIZE 5000
#define MAXVAL 1000
#define MINVAL 0
#define TESTCASE 20
#define TRUE 1
#define FALSE 0
#define ASIZEMIN 3

int main(){
   
    int answer[TESTCASE],a[ASIZE];
    int test;
   
    scanf("%d",&test);
    int checking = (test>0&&test<=TESTCASE);
    if (checking!=0) {

        for (int i=0; i<test; i++) {
            int count =0;
           
            int number;
            scanf("%d",&number);
            checking = (number>=ASIZEMIN&&number<=ASIZE);
            if (checking!=0) {
                for (int i=0; i<number; i++) {
                    int val;
                    scanf("%d",&val);
                    a[i] = val;
                }
               
               
               
                for (int p=0; p<number; p++) {
                    for (int q=p+1; q<number; q++) {
                        for (int r=q+1; r<number; r++) {
                            checking = (a[p]>a[r]||a[q]>a[r]);
                            int value = a[p]+a[q]-a[r];
                            if ((value==0)&&(checking==0)) {
                                count++;
                            }
                        }
                    }
                }
                for (int p=number-1; p>=0; p--) {
                    for (int q=p-1; q>=0; q--) {
                        for (int r=q-1; r>=0; r--) {
                            checking = (a[p]>a[r]||a[q]>a[r]);
                            int value = a[p]+a[q]-a[r];
                            if ((value==0)&&(checking==0)) {
                                count++;
                            }
                        }
                    }
                }
                answer[i] = count;
            }
        }
       
        for (int i=0; i<test; i++) {
            printf("Case %d: %d\n",(i+1),answer[i]);
        }
       
    }
   
    return 0;
}

 
Posts: 28
Joined: Sat Aug 06, 2016 11:02 pm

Re: Triples shows time limit exceedes

by ahqmrf » Thu Oct 27, 2016 8:50 pm

Did you see the constraints carefully? It said-
Here T ≤ 20, 3 ≤ N ≤ 5000, 0 ≤ A[i] ≤ 1000


The value of N can be upto 5000. Your code seems like an O(N^3) solution which, in the worst case, will cause 5000^3 operations which is very bad algorithm for the time limit 1 sec. Even, an O(N^2 Log N) approach also might not pass for such big value of N. So, try to make an O(N^2) algorithm for this problem and also watch out the constraints carefully. The constraints sometimes help to identify some technical issues. Hope it helps.
 
Posts: 3
Joined: Wed Oct 26, 2016 12:50 am

Re: Triples shows time limit exceedes

by arabin » Fri Oct 28, 2016 7:29 pm

yes got it thank you so much
 
Posts: 28
Joined: Sat Aug 06, 2016 11:02 pm


Who is online
Users browsing this forum: No registered users and 1 guest
cron