How could I not get TLE (ZCO13003)

This is the problem: https://www.codechef.com/ZCOPRAC/problems/ZCO13003

This is my solution: https://ideone.com/cz06mj

I seem to pass all test cases except one, the last one!

Sorry if I seem to be asking every question on the forum, but getting to know the fault in the codes will help me be an ace in ZCO. I appreciate all the help provided by the forum.
Thanks for all the help!

Regards,
Arnav

I think the intended solution is of complexity O(NLogN), and involves sorting the array.

After sorting, for each chewgum’s hardness, arr[i], we binary search for exact value/upper bound/lower bound of K-arr[i] [Hint: Read about lower_bound and upper_bound functions]

I will update once I solve the problem.

Here, the algorithm passes the TC-

    int n,k;
	cin>>n>>k;
	int arr[n],i;
	for(i=0;i<n;i++)cin>>arr[i];
	sort(arr,arr+n);
	long long ans=0;
	for(i=0;i<n && arr[i]<=k;i++)
	{
	    int pos=lower_bound(arr+i,arr+n,k-arr[i])-arr;//Read about lower bound function
	    ans+=pos-i; //Pair all elements from [i,pos] with arr[i]. Let j be an element in [i,pos]. Pair is (arr[i],arr[j])
	    if(pos>i)ans--; //To exclude the pair (arr[i],arr[i])
	}
	cout<<ans<<endl;
1 Like

Just make sure to give question link as well, that will make things extremely convenient for answerers. Thanks!

1 Like

Sure! There you go:

I tried to implement a similar technique.

I sorted the array in ascending order.

What I did is, that I run a loop for every i such that arr[i] was less than K. Then, I ran a loop for every i+1 till n-1, until arr[i+1]+arr[n’]>K

Any trick to shorten this up? Probably like counting the inverse cases and subtracting from total??

You are checking each element from i+1 to n-1 in second loop. But since array is sorted in ascending order, we know that if “hardness of arr[j] +arr[i]<=K, then since array is sorted in ascending order, hardness of arr[k]+arr[i]<=K as well where K is in range [i+1,j].”

Hence no need to check for all values if we can directly arrive at this critical point j. Binary search is a possible option, but implementation must be carefully done to avoid WA.

Alternate- Instead of traversing 1 by 1 in your 2nd loop, check "if (arr[j+1000]+arr[i]<=K) j+=1000 else {1 by 1 search in this range}

1 Like

Binary search does in LogN, while other method works in N/1000 time. You can read about it in square root decomposition method.

1 Like

Any help with the code??