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
Just make sure to give question link as well, that will make things extremely convenient for answerers. Thanks!
Sure! There you go:
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;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}
Binary search does in LogN, while other method works in N/1000 time. You can read about it in square root decomposition method.
Any help with the code??