You are not logged in. Please login at www.codechef.com to post your questions!

×

Getting 'Time limit exceeded' for the problem NOTATRI. Please help. What's wrong with my code?

include <iostream>

using namespace std;

int main() { unsigned long int i, x, y, z, counter = 1, a, b, c, ans=0;

int n;

cin >> n;

while(n>0)
{

    unsigned long int arr[n];

    for(i=0;i<n;i++)
    {
        cin >> arr[i];
    }

    for(x=0;x<=(n-3);x++)
    {
        for(y=(x+1);y<=(n-2);y++)
        {
            for(z=(y+1);z<=(n-1);z++)
            {

            a = arr[x];
            b = arr[y];
            c = arr[z];

            while(counter <= 3)
            {
                if((a+b)<c)
                {
                    ans++;
                }

                x = a;

                a = b;

                b = c;

                c = x;

                counter++;
            }

            counter = 1;
        }
    }
}

cout << ans << endl;

ans = 0;

cin >> n;

}

return 0;

}

asked 05 Mar '13, 19:23

harsha_badass's gravatar image

2★harsha_badass
-3113
accept rate: 0%


The 3 nested FOR loops are giving you complexity of n^3.You can eliminate the third loop by using the binary search to find the smallest element greater than arr[x]+arr[y].

link for binary search...its much more than searching an element in the array

http://www.quora.com/Binary-Search/What-is-binary-search

link

answered 23 Jun '13, 17:20

re_hash's gravatar image

4★re_hash
8493815
accept rate: 3%

edited 23 Jun '13, 17:21

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×1,840
×530
×248

question asked: 05 Mar '13, 19:23

question was seen: 922 times

last updated: 23 Jun '13, 17:21