×

# ZCO14003 - Editorial

 1 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 70●2●5 accept rate: 0% 0★admin ♦♦ 19.6k●349●497●539

 0 This code does literally the same thing, still getting WA on most TCs. Please help. https://www.codechef.com/viewsolution/21759944 answered 06 Dec, 20:47 2★shardic 2●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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