# Triples shows time limit exceedes

Dev Skill archived problems can be discussed here.

### Triples shows time limit exceedes

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 3int 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

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

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 