This is the problem: CodeChef: Practical coding for everyone
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
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