which algorithm ?

This is a discussion on which algorithm ? within the C Programming forums, part of the General Programming Boards category; 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 ...

  1. #1
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    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

  2. #2
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    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.
    Last edited by Snafuist; 02-14-2009 at 09:44 AM.

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    I would vote for Snafuist. Nice one.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    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

  5. #5
    Registered User
    Join Date
    Jan 2009
    Posts
    71

    thanks

    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

  6. #6
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by jack_carver View Post
    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

  7. #7
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    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.
    Last edited by abachler; 02-15-2009 at 10:38 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,739
    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.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Malum in se abachler's Avatar
    Join Date
    Apr 2007
    Posts
    3,189
    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;
       }
    Last edited by abachler; 02-15-2009 at 10:43 AM.
    Until you can build a working general purpose reprogrammable computer out of basic components from radio shack, you are not fit to call yourself a programmer in my presence. This is cwhizard, signing off.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 01:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 06:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21