Help in ZCO15002 & ZCO13001

general
, , ,
1

I have written this code for ZCO15002: https://ideone.com/AiNy7P

I also used the same approach for ZCO13001, with this code: https://ideone.com/3HmAfR

They seem to execute fine for small inputs, but show TLE for large ones.
Any comments on how could I optimize the code, or change the approach for large test cases?
Thanks in advance!

2

I am not able to view your code since it is a live contest. You should upload it on ideone and provide the link.

1 Like
3

@dhruvsomani I changed the code link to IDEONE. :slight_smile:

4

Please answer the question…

5

Hey @arnavvarshney

I just read the question ZCO15002. Your solution is of time complexity O(N^2). You can solve the problem by reducing the time complexity to O(N*log(N)).

Hint 1:

Click to view

Try sorting the array and then solve the problem.

Hint 2:

Click to view

Instead of calculating the number of pairs with difference greater than k, we can calculate the number of pairs with difference less than k.

1 Like
6

My accepted solution also has a worst case complexity of O(N^2) but sorting did help me improve my solution and pass all the test cases.

1 Like
7

Some help with the code would be appreciated :smiley:

8

I switched over to C++14 after seeing that the execution times were less.
I also implemented the SORTING algorithm and finally have written this code, but it’s still getting TLE. Where am I wrong?

https://ideone.com/9kj9Ou

9

Regarding your question ZCO13001 ,you can do the following-

  1. Sort the array
  2. Find out the difference between last and second last element. Add it to answer.
  3. Now find difference between third last and second last element. Now, can we deduce the difference between third last and last element on basis of this? Yes, number of terms with which we have to calculate difference (=end index-start index-1)=(n-1-(n-3)-1)=1. And we know that Difference b/w 3rd last and last term= Diff b/w 3rd last and 2nd last+ Difference b/w 2nd last and 3rd last.
  4. Now think in terms of calculating the difference with just knowledge of number of elements, and difference between i and (i+1)'th term. Lets take an example array to highlight it.

Let arr={3,3,5,7,10}. Now, difference between last and 2nd last term= 10-7 =3. Thats the answer had the array been just {7,10}.

Now, consider {5,7,10}. The answer is (2+5)+(3)=10. Can we find a relation between previous answer and this answer? Yes we can!

We know that difference between 5 and 7 is 2. We also know that answer of array {7,10} is 3. Now, the new terms added are nothing but (7-5) and (10-5) to the answer.

Now see this, difference between 7 and 5 is 2. Also, number of terms, excluding 7, is 1. We know that difference of all such terms = 2+difference of that term with 7. Can we make a formula out of it?

Lets say you are at i’th term. We know the difference between i and (i+1)'th term. We also know the number of terms in interval (i+1,n]. We also know answer upto (i+1) from end, or sum of difference of terms in [i+1,n].

Now I claim that, using this, I can say that-

Newly added terms in ans= (arr[i+1]-arr[i])+(arr[i+2]-arr[i])…(arr[n-1]-arr[i])
and-
difference = arr[i+1]-arr[i].
==>arr[i]=arr[i+1]-difference.

Proceed further with substitution and find relation between previous and new answer. The code snippet is given to cross check and must be seen only after you give an attempt.

int i,j,k;
for(i=0;i<n;i++)cin>>arr[i];
sort(arr,arr+n);
long long int ans=0,add=0,diff=0;
for(i=n-2;i>=0;i--)
{
    if(arr[i]!=arr[i+1])
    {
        diff=arr[i+1]-arr[i];
        add+=(n-1-i)*(arr[i+1]-arr[i]);
    }
    ans+=add;
    //cout<<"diff="<<diff<<" ans="<<ans<<" add="<<add<<endl;
}
cout<<ans<<endl;
1 Like
10

Hey @arnavvarshney

You can have a look at my


[1].

**Explanation:** I just calculated number of pairs which have absolute difference less than k and then subtracted it from the total number of pairs possible.

Your approach is also correct and it will perform more efficiently if there are lesser number of pairs with absolute difference greater than or equal to k. But if we have higher number of such pairs then the above solution works efficiently as loop runs comparatively lesser number of times to find the pairs with difference less than k. The worst case complexity of both the cases is O(N^2) only. Its just a matter of trade-off for a particular approach and the given testcases.

PS: Had to create a new answer because of the exceeded character limit in the comments section.


  [1]: https://ideone.com/38yGGk
1 Like
11

Completed it finally! Thanks a lot!!!

12

Glad I could help :slight_smile: