PROBLEM SETTER -
ZCO 2014
DIFFICULTY -
Easy
PREREQUISITES -
Sorting
KEY OBSERVATIONS -
- Sorting the array will not affect the answer as the answer doesn’t depend on the index of an element.
- The answer would always be some element of the array, which is trivial to prove.
- The revenue earned if we fix the price to be a[i], (for some 1 <= i <= N) will be a[i] * (N-i+1). Remember, the array is sorted in ascending order, and thus, there are(N-i-1) customers which have budget greater than a[i].
FIRST SUBTASK SOLUTION -
Simply try all combinations by putting price equal to every element one by one and check the number of integers/elements bigger than this price. multiplying price and the bigger numbers will give the revenue for that price. Take the maximum of all such revenues and output it. Since we are trying every element and checking the bigger numbers in whole array takes O(N), time complexity comes out to be O(N^2).
int ans=0;
for(int i = 1;i < n+1;i++)
{
int cnt=0;
for(int j = 1;j < n+1;j++)
if(a[j] <= a[i])
cnt++;
ans = max(ans,cnt*a[i]);
}
cout << ans;
SECOND SUBTASK SOLUTION -
Solution is to iterate on sorted array and take maximum of the term [ a[i] * (N-i+1) ] for all i between 1 and N.
sort(a+1,a+n+1);
ll ans=0,cnt=0;
for(ll i = 1;i < n+1;i++)
{
cnt = a[i]*(n-i+1);
ans = max(ans,cnt);
}
cout << ans;
This works because, after sorting, the checking process that was initially happening in O(N) for each index will now happen in O(1) time as the number of elements bigger than the i^{th} element is already known to be (N-i+1).
Don’t forget to store answer in long long format.
TIME COMPLEXITY -
O(N * Log(N))