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

×

Not a Triangle:Wrong answer

In the problem Not a Triangle , i have used c language and followed the algo :

1.Sort the array using merge sort in ascending order.
2.find the smallest index of array such that it is a[index] >a[i]+a[j] so chosen using binary search.

here is the code :

#include<stdio.h>

void sort(int a[] ,int start1 ,int end1 ,int start2 ,int end2)//part of merge sort
{

        int temp[end1-start1 +1 + end2-start2+1 ];
        int i=start1,j=start2,count=0;

        while(i<=end1 && j<=end2)
        {
                if(a[i]<=a[j])
                    temp[count++]=a[i++];
                else
                    temp[count++]=a[j++];


        }

        for(;i<=end1;++i)
            temp[count++]=a[i];

        for(;j<=end2;++j)
            temp[count++]=a[j];

        for(i=0;i<count;++i)
            a[i+start1]=temp[i];


}

void mergesort(int a[] ,int start,int end)
{
        if(start==end)
            return;

        int middle =(start+end)/2;

        mergesort(a,start,middle);
        mergesort(a,middle+1,end);
        sort(a,start,middle,middle+1,end);

}

int binarysearch(int a[] ,int start ,int end ,int key)
{

        int middle;

        while(start<=end)
        {
            middle=(start+end)/2;

            if(a[middle]==key)
                return middle;

            if(a[middle]<key)
                start=middle+1;

            if(a[middle]>key)
                end=middle-1;


        }

        return start;//this gives the index where the number > key starts as key is not present in array



}

int main()
{
        int n,i,j,count;

        scanf("%d",&n);

        while(n!=0)
        {
            int a[n];
            count=0;

            for(i=0;i<n;++i)
                scanf("%d",&a[i]);

            mergesort(a,0,n-1);


            /******** In case you want to print the sorted array************
            printf("\n");
            for(i=0;i<n;++i)
                printf("%d, ",a[i]);
            printf("\n");

            ****************************************************************/

            for(i=0;i<n;++i)
                for(j=i+1;j<n;++j)
                   count=count+n-binarysearch(a,j+1,n-1,a[i]+a[j]+1); // one more than a[i]+a[j] as that will contradict as the set as triangle

            printf("%d\n",count);
            scanf("%d",&n);

        }

        return 0;
}

asked 16 May '14, 18:28

empty_life's gravatar image

2★empty_life
355819
accept rate: 20%

edited 16 May '14, 18:30


Binary search wont work if you have repeated values.

e.g.

6

1 2 4 4 4 4

correct ans is 4 but your code gives 3

link

answered 16 May '14, 19:47

abbas's gravatar image

4★abbas
4118
accept rate: 28%

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:

×3,820
×558
×11

question asked: 16 May '14, 18:28

question was seen: 816 times

last updated: 16 May '14, 19:47