CDVA1603 - Editorial

ad-hoc
binary-search
cdva16
cdva1603
editorial

#1

PROBLEM LINK:

Practice

Contest

Author: Suraj Prakash

Tester: Aditya Kumar

Editorialist: Suraj Prakash

DIFFICULTY:

Easy

PREREQUISITES:

Ad-hoc, Binary Search

PROBLEM

Compute the count of elements (floating point decimals) greater than K, if the list of non repeating elements was sorted.

EXPLANATION

To find the number of elements greater than K, what we can do is to simply iterate through the array and count the number of elements greater than K, this is an approach which will run in time for smaller constraints. This will lead to a complexity of \mathcal{O}(N * Q)

For better efficiency this can be done using binary search in \mathcal{O}(\log (N) * Q), since we need to count the number of elements greater than K.

		int find(vector<double> &v, int l, int h, double f){
			int low = l, high = h, mid;
			while (low < = high){
				mid = (low + high) >> 1;
				if (v[mid] == f) 
					return (h - mid);
				else if (v[mid] > f) 
					high = mid - 1;
				else 
					low = mid + 1;
			}
			return h - low + 1;
		}

STL offers inbuilt binary search which can be used to solve this problem using a line of code.

N - (upper_bound(arr, arr + N, K) - arr)

OPTIMAL COMPLEXITY:

\mathcal{O}(Q*\log(N))

AUTHOR’S SOLUTION:

Author’s solution can be found here.

Tester’s solution will be uploaded soon.