You are not logged in. Please login at www.codechef.com to post your questions!

×

ZCO14003 - Editorial

PROBLEM SETTER -
ZCO 2014

DIFFICULTY -
Easy

PREREQUISITES -
Sorting

KEY OBSERVATIONS -
1. Sorting the array will not affect the answer as the answer doesn't depend on the index of an element.
2. The answer would always be some element of the array, which is trivial to prove.
3. 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))$

This question is marked "community wiki".

asked 23 Jun '17, 15:34

vivek1_007's gravatar image

5★vivek1_007
7025
accept rate: 0%

edited 24 Jan, 20:23

admin's gravatar image

0★admin ♦♦
19.6k349497539


This code does literally the same thing, still getting WA on most TCs. Please help. https://www.codechef.com/viewsolution/21759944

link

answered 06 Dec, 20:47

shardic's gravatar image

2★shardic
22
accept rate: 0%

Please help @vivek1_007

link

answered 08 Dec, 11:56

shardic's gravatar image

2★shardic
22
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,198
×419
×74
×53

question asked: 23 Jun '17, 15:34

question was seen: 441 times

last updated: 08 Dec, 11:56