Smartphone app Problem

https://www.codechef.com/viewsolution/24437680

here is my solution for the smartphone problem

it says my solution is partially right
can someone please help me
thankyou

Input size is 10^5 so a O(n^2) (as in your case) algorithm will definitely exceed time limit try to do it in at least O(n*logn)

One possible approach

  1. budget array [53,40,59,60]
  2. sort them [60,59,53,40]
  3. now multiply each element with its index [60,118,159,160] (indicates no of people that could buy the app)
  4. find the max in the above array which will be the ans
    this approach will take O(n*logn)
5 Likes

thanks bro
i did it and my solution got accepted

Can you explain it in more detail why and how is this happening?

Refer Editorial for Problems of Codechef-DSA-Learning-Series: 1-Complexity Analysis + Basics Warm Up

I tried it but getting TLE in subtask 2.Please help me to solve this.What does task # mean ?What is the meaning of numbers written in subtask info like TLE (1.010000).
Here is the link to my solution CodeChef: Practical coding for everyone

It simply means that your solution did not complete in the given time limit (in this case, 1 sec).

But why am I getting time limit exceeded?How do I optimize my above code?

The worst case complexity of simple quick-sort is n^2. Try doing randomized quick-sort or better use the sort provided in cpp stl. :slight_smile:

1 Like

Use

void qsort (void* base, size_t num, size_t size,int (*compar)(const void*,const void*));

If you switch to cpp, you can simply use

sort(a,a+n);
Corrected Code
#include <stdio.h>
int compare(const void * a, const void * b){
  return (*(int*)a - *(int*)b);
}
int main(void) {
	// your code goes here
	long long n;
	scanf("%lld",&n);
	long long a[n];
	for(long long i=0;i<n;i++){
	   scanf("%lld",&a[i]);
	}
	qsort(a,n,sizeof(long long),compare);
	long long max=0;
	for(long long i=0;i<n;i++){
	   long long temp;
	   temp=a[i]*(n-i);
	   if(max<temp){
	        max=temp;
	   }
	}
	printf("%lld",max);
    return 0;
}
1 Like

Hey, thats exactly what i did here CodeChef: Practical coding for everyone
Iā€™m still getting it as partially correct. Could you pleasee help me out?

Can someone please explain me how to approach this problem !

1 Like

Nice idea bro but how to get that idea ?

The idea is simple you could sort the array first and then multiply all of them with size-- once you do that you could just print the maximum value in the array as it will be the maximum revenue you could get for the app such that maximum people will pay for your app and still get maximum price for your app.
This way we will be able to sort the array with O(log n) and multiplication would take O(n) time complexity also if you use any extra array then consider O(n) or O(2n) space complexity.

3 Likes

Correct

how did you get this idea of solving the question this way please can u explain in breif