Skip to content

UVA Problem: 1152 (4 Values whose Sum is 0)

October 5, 2011

Problem Statement

Problem Explanation:

The main concern of this problem is to develop a fast algorithm. The O(n^4) or O(n^3) algorithm is not enough to pass the time limit. So we need a O((n^2)lg(n)) algorithm.

Ok, Here is my O(n^2lg(n)) algorithm-

Suppose there is four array A[], B[], C[], D[]. we want to find the number of way A[i]+B[j]+C[k]+D[l] = 0 can be made where 0 <= i,j,k,l < n.

So sum up all possible arrangement of A[] and B[] and place them in another array E[] that contain n*n number of element.

int k=0; for(i=0;i<n;i++) { for(j=0;j<n;j++) { E[k++]=A[i]+B[j]; } } 

The complexity of above code is O(n^2).

Do the same thing for C[] and D[].

int l=0; for(i=0;i<n;i++) { for(j=0;j<n;j++) { AUX[l++]=C[i]+D[j]; } } 

The complexity of above code is O(n^2).

Now sort AUX[] so that you can find the number of occurrence of unique element in AUX[] easily.

Sorting complexity of AUX[] is O(n^2 lg(n^2)).

now declare a structure-

struct myHash { int value; int valueOccuredNumberOfTimes; }F[]; 

Now in structure F[] place the unique element of AUX[] and number of time they appeared.

It’s complexity is O(n^2)


Now for each item of E[], do the following

for(i=0;i<k;i++) { x=E[i]; find -x in structure F[] using binary search. if(found in j'th position) { possibleQuardtupple+=number of occurrences of -x in F[j]; } } For loop i ,total n^2 number of iteration is performed and in each iteration for binary search lg(n^2)
comparison is done. So Here complexity is O(n^2 lg(n^2)) which is mathmatically  O(n^2 lg(n)).

And the overall complexity of above program is O(n^2 lg(n)). You can speed up program run time by some
modification. But the overall complexity is remain same.

Now you can use stl map/ binary search. But stl map is slow, so its better to use binary search.

Hope my explanation is clear enough to understand.

2 Comments leave one →
  1. May 6, 2012 2:59 am

    please post sample code?

    • May 9, 2012 9:33 am

      I think it will be not wise to post full source code here. You saw i already provided most part of the code in the post. You just need to combine 4 array to 2 array and then just do binary search.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: