which algorithm ?

Hi,
can any 1 help me solve this problem:

http://www.spoj.pl/problems/NOTATRI/

my code exceedes the timelimit..
i used this

1.sorted the data using quicksort
2.then used bruteforce

here is my code: (wont compile becoz i omitted the procedure for quicksort)

Code:

---

#include<stdio.h>
int main()
{
        int i=0,j=0,k=0,n,ans=0,sum;
        int arr[2001];
       
        while(1)
        {
                scanf("%d",&n);
               
                if(n==0) break;
               
                for(i=0;i<n;i++)
                        scanf("%d",&arr[i]);
               
                quicksort(arr,0,n-1);
                               
                for(i=0;i<n-2;i++)
                {
                        for(j=i+1;j<n-1;j++)
                        {
                                sum=arr[i]+arr[j];
                               
                                for(k=j+1;k<n;k++)
                                {
                                        if(sum<arr[k])
                                        {
                                                ans=ans+(n-k);
                                                break;
                                        }
                                       
                                }
                        }
                }
                printf("%d\n",ans);
                ans=0;
        }
return 0;
}

---

thanks

Hello,

you can partition your sorted set of sticks into subsets of sticks. Check for each triple of consecutive sticks whether they form a triangle or not. If they do, put partition boundaries around the triple.

Example: consider the following set:
1 2 3 7 10 23 27 31 59 100


1 2 3 forms a triangle, so add boundaries:
| 1 2 3 | 7 10 23 27 31 59 100

2 3 7 doesn't, do nothing.

3 7 10 does, add boundaries:
| 1 2 | 3 | 7 10 | 23 27 31 59 100

7 10 23 doesn't, do nothing.

and so on...


Once you're done, you end up with the following partitioning:
| 1 2 | 3 | 7 10 | 23 27 31 | 59 100

The first thing we notice is that 59 and 100 don't have partition boundaries around it, so we can completely skip them. Next, a partition contains at most three sticks. Next, we observe that sticks in partition X can only form a triangle with sticks from itself and/or with sticks from at most one of the neighboring partitions. Hence the algorithm continues as follows:

Start with the first and second partition, use brute force to determine the number of triangles we can form. Do the same for the 2nd and 3rd, 3rd and 4th and so on...


This will vastly improve your runtime. Determining partition boundaries works in linear time. Using brute force sounds evil, but as the size of two partitions is at most 6, this is actually a constant time task.

Thus, you need to traverse the array exactly two times, only performing constant time operations. Hence, your overall runtime is linear.

Note that I pulled this stuff out of my ass. I believe it to be correct, but I have not proven it. I'd be glad to hear whether it worked or not.

Greets,
Philip


EDIT: I forgot to mention that you can ignore partitions of size > 3, because there's no way to form a triangle with the sticks from such a partition.
EDIT: Oh, and in order to get the correct output, compute the total number of ways to choose three sticks and subtract the number of ways to form a triangle (which is what the algorithm is actually supposed to do, although I didn't mention to keep track of it).
EDIT: one last remark: if this algorithm is correct, then it is optimal.

I would vote for Snafuist. Nice one.

Sadly, my approach doesn't work. Consider the following set: 1 2 3 ... 98 99 100

The subset 2 98 99 forms a triangle, but my algorithm won't detect it. I have another approach in mind, but I just came from a party and now it's 3:24am over here, so I think I'll post it tomorrow.

Greets,
Philip

thanks fr trying....

all the ppl used an O(n^2lgn) algorithm n optimised it to O(n^2)

i used binary search and got accepted :)

if u find a better method plz do post


thank u
abhijith

Quote:

---

Originally Posted by jack_carver

all the ppl used an O(n^2lgn) algorithm n optimised it to O(n^2)

---

Yep, O(n^2lg(n)) would've been my new guess regarding the optimal runtime: For each pair (a,b) in the array (O(n^2)), use binary search (O(lg(n)) to find the largest stick smaller than a+b. There is room to improve this by some sort of marking strategy in order to avoid searching c for (a,b) if you have already checked (a,c) or (b,c).

You can still use my method to rule out regions where the partition size exceeds a size of 3. This won't change the asymptotic runtime, but depending on the dataset it may vastly improve the actual execution speed.

Just out of curiosity, how did they manage to get O(n^2)?

Greets,
Philip

hmm, I wouldnt put too much stock in that sites judging, My submission for teh test problem (TEST) had a runtime error

Code:

---

#include <stdio.h>

int Input[] = { 1 , 2 , 88 , 42 , 99 };

int main(void){
  int Index = 0;
  while(Input[Index] != 42){
      printf("%d\n" , Input[Index]);
      Index++;
      }
  return;
  }

---

when it should have given a compile time error

correctly returning 0 led to a 'wrong result'

It seems there are several unspoken points in the contests which are not immediately apparent, one is that all input i actually given through the console, so that you have to use cin or scanf(). While that one was a simple thing to figure out, it makes me wonder if there are other such hidden requirements that may cause correct submissions to be labelled as incorrect for some reason.

You did not actually put everything on one line, did you? Besides, I think you are supposed to read from stdin rather than define the input yourself.

Yes, after i figured out that they are supplyign the input via stdin, it was a simple fix and the solution was accepted, but it woudl have been nice if thye had actually specified, althoguh they may do that in some FAQ somewhere, admittedly I never read FAQ's, because usually the Q's I A arent all that F.

and no I didnt put it all on one line, that was an artifact of cut adn pasting the code I submitted. I corrected it so its readable.

BTW the one that was accepted was -

Code:

---

#include <stdio.h>

int main(void){
  int Input = 0;
  scanf("%d",&Input);
  while(Input != 42){
      printf("%d\n" , Input);
      scanf("%d",&Input);
      }
  return 0;
  }

---