CARSELL - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Chaithanya Shyam
Tester: Felipe Mota
Editorialist: Taranpreet Singh

DIFFICULTY:

Simple

PREREQUISITES:

Greedy

PROBLEM:

Chef owns N cars whose price is given by array A. Every day, he wants to sell one car each day. Every day, the value of the car reduces by 1 unit if not already sold. Find the maximum profit Chef can make by selling these cars optimally.

QUICK EXPLANATION

  • It is best to sell the cars in non-increasing order of prices.
  • The maximum profit is \displaystyle\sum_{i=1}^N max(0, A_i-i) where max condition takes care of price dropping below zero.

EXPLANATION

The explanation has two parts, finding the optimal order of selling cars, and finding the profit from the chosen order.

Finding the optimal order of selling cars
Let’s assume that the price of a car can drop below zero. The total profit would be \displaystyle\sum_{i = 1}^N (A_i-i) = \sum_{i = 1}^N A_i - N*(N+1)/2 where N*(N+1)/2 denote the sum of value lost over all cars.

Irrespective of the order of selling cars, the profit remains the same in this case.

Coming back to the original problem, the order of selling cars become important because some car might stop losing value if it reaches zero.

If the value of the car drops to zero, it doesn’t drop further, so the final loss of value over all the cars reduces. So, it is actually beneficial to keep low valued cars for later, and selling high valued car before.

This gives us an optimal order to sell cars.

Proof by exchange argument

Consider cars with value [0, 1], If sold in order [0, 1] it yields profit 0+(1-1) = 0

However, if sold in order [1, 0], it yields a profit 1+0 = 1. This happened because the first car had already hit zero value, so it couldn’t lose value further. So it was better to sell the car with value 1 first, rather than keeping it and losing its value.

Finding the maximum profit

Now that optimal order is decided, we know, the car sold on i-th day has lost i units of value (0-based). So, we can calculate the contribution of each car to profit as \displaystyle \sum_{i = 1}^N (A_i-i) where A_i is sorted in non-increasing order.

But if A_i < i, this means the value has fallen below zero, which is not allowed. So we need to take max(0, A_i-i)$ as it ensures non-negative value.

Hence, the final profit is \displaystyle\sum_{i = 1}^N max(A_i-i, 0)

PS: The maximum possible value of answer is 10^5*10^9 - 10^5*(10^5+1)/2 which easily fits within the range of long long int. The modulo was just there to cause confusion.

TIME COMPLEXITY

The time complexity is O(N*log(N)) per test case.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

#define MOD (1000000000+7)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) x.begin(), x.end()
#define print(vec,l,r) for(int i = l; i <= r; i++) cout << vec[i] <<" "; cout << endl;
#define forf(i,a,b) for(int i = (a); i < (b); i++)
#define forr(i,a,b) for(int i = (a); i > (b); i--)

typedef long long int ll;

void solve(){
	int N;
	cin >> N;

	vector<ll> vec(N);
	for(int i = 0; i < N; i++) cin >> vec[i];

	sort(all(vec), greater<ll>()); //  sorting the elements in decreasing order

	ll ans = 0;
	for(int i = 0; i < N; i++){
		// The price of the ith car is either 0 or the inital price-number of years passed
		ans += max((ll)0,vec[i]-i); 
		ans %= MOD;
	}
	cout << ans << endl;
}

int main(){
 	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int T;
	cin >> T;
	while(T--){
		solve();
	}

	return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	/**
	Claim: the solutions it's selling the most expensive car available each day
	Proof:
	In the i-th year (0-index) the car will have lost i in value. 
	Supose that the car with value X is selled in the year i
	   and that the car with value Y is selled in the year i + 1
	Showing that if X < Y we can make a swap: 
	    if max(X - i, 0) equals 0 and max(Y - i - 1, 0) equals 0: 
	        we can swap X and Y as the contribution can't decrease
	    if max(X - i, 0) equals 0 and max(Y - i - 1, 0) equals Y - i - 1:
	        we can swap X and Y and achieve: Y - i, which improves the answer
	    if max(X - i, 0) equals X - i and max(Y - i - 1, 0) equals 0:
	        it's impossible because of X < Y
	    if max(X - i, 0) equals X - i and max(Y - i - 1, 0) equals Y - i - 1:
	        we can swap X and Y and achieve the same contribution
	 * */
	const int mod = 1'000'000'007;
	int t;
	cin >> t;
	while(t--){
	    int n;
	    cin >> n;
	    vector<int> a(n);
	    for(int i = 0; i < n; i++) 
	        cin >> a[i];
	    sort(a.rbegin(), a.rend());
	    int ans = 0;
	    for(int i = 0; i < n; i++){
	        ans += max(a[i] - i, 0);
	        if(ans > mod)
	            ans -= mod;
	    }
	    cout << ans << '\n';
	}
	return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class CARSELL{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni();
	    Long[] p = new Long[n];
	    for(int i = 0; i< n; i++)p[i] = nl();
	    Arrays.sort(p, Collections.reverseOrder());
	    long ans = 0;
	    for(int i = 0; i< n; i++)ans += Math.max(0, p[i]-i);
	    pn(ans);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new CARSELL().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

3 Likes

Detailed Solution.

5 Likes

Please help. I applied the following solution. But it didn’t seem to work. Can someone explain why?
#include <bits/stdc++.h>

using namespace std;

int main() {
int tc;
for(int q = 0; q < tc; q++){
int n;
int p=0;
cin >> n;
int arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
sort(arr, arr+n, greater());
for(int i = 0; i < n; i++){
if(arr[i]!=0){

        p=p+arr[i]-i;}
    }
    cout<<p<<"\n";
    
}

}

But even if we directly to calculation without any sorting we will get same ans. So no need to sort them

This was the last line of the problem statement “this number may be large, compute it modulo 1000000007.”

just print the result with modulo (10^9+7)
i.e.
cout<<p%1000000007<<"\n";

1 Like

the if condition is a bit wrong. It should be “if(arr[i]-i > 0)” and since your “p” variable is an int you should take modulo 10^9+7 at each iteration of the for loop.

1 Like

Please help. I applied the following solution. But it shows Wrong Answer when i submit it . Can someone explain why? Sorry for Indentation.

t=int(input())
while(t):
n=int(input())
profit = 0
a = list(map(int,input().strip().split()))[:n]
a.sort(reverse=True)
for i in range(len(a)):
if((a[i]-i)>0):
profit+=(a[i]-i)

print(profit)
t=t-1
2 Likes
int t;
cin>>t;
for(int i=0;i<t;i++){
    int n;
    cin>>n;
    vector <int> a;
    int p;
    int sum=0;

    for(int j=0;j<n;j++){
        cin>>p;
        a.push_back(p);
    }
    sort(a.begin(), a.end(), greater<>());
    for(int k=0;k<n;k++){
        if((a[k]-k)>0){
            sum+=(a[k]-k);
        }else{
            break;
        }
    }
    cout<<sum%1000000007<<"\n";
}

Why there was a need for greedy approach when you are getting the right answer through this but on submitting it gives WA? Any relevant test case that shows only greedy approach is right?

yeah even I am unable to get this. Someone please help!

Better to use long long int instead of int
:slight_smile:

You are Not printing ans%1000000007

Thanks for the reply!
I tried the following solution, but still it isn’t working. Can you please explain.
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
int tc;
for(int q = 0; q < tc; q++){
int n;
ll p=0;
ll m=1e9+7;
cin >> n;
ll arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
sort(arr, arr+n, greater());
for(int i = 0; i < n; i++){
if(arr[i]-(ll)i>0) p=p+arr[i]-(ll)i;
}
cout<<p%m<<"\n";

}

}

Thanks for the reply!
I tried the following solution, but still it isn’t working. Can you please explain.
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int main() {
int tc;
for(int q = 0; q < tc; q++){
int n;
ll p=0;
ll m=1e9+7;
cin >> n;
ll arr[n];
for(int i = 0; i < n; i++){
cin >> arr[i];
}
sort(arr, arr+n, greater());
for(int i = 0; i < n; i++){
if(arr[i]-(ll)i>0) p=p+arr[i]-(ll)i;
}
cout<<p%m<<"\n";

}

}

import java.util.;
import java.lang.
;
import java.io.*;

class Codechef
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		int m = 1000000007;
		int t = sc.nextInt();
		 
		for(int i = 0; i< t; i++ ) {
		    
		    
		    int n = sc.nextInt();
		    int depriciation = 0;
		    int profit = 0;

            List<Integer> arr = new ArrayList<Integer>();
            
		    for(int j = 0; j < n; j ++ ) {
		     int price = sc.nextInt();
		     arr.add(price);
		    }
		  
		    
		    Collections.sort(arr, Collections.reverseOrder());
		    
		    for(int x = 0; x<=arr.size(); x ++) {
		        
		        if(x == arr.size()) 
		            System.out.println(profit);
		        else if(arr.get(x) - depriciation > 0) 
		      	    profit += arr.get(x) - depriciation;
		     
		         depriciation ++;
		         
		         
		    }
		}
           System.out.println(profit);
	}
}

I was getting the right answer through this , sorting the array before deducting the depriciation does give you the best results according to me. I’m New to code competitions , and above is my code to CARSELL problem , can anyone tell me where i went wrong ?

  1. You are not taking input for “tc”
  2. sort(arr, arr+n, greater<int>());
    It should work now
  1. Try using long long int ( don’t know in java )
  2. You are outputting the answer two times

I can’t find where I am going wrong.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	long long int T,n,p,k=0,MOD=1000000007;
	cin>>T;
	if(T>=1&&T<=25)
	{
	vector<long long int>prices;
	while(k<T)
	{
	    cin>>n;
	   // years.push_back(n);
	   if(n>=1&&n<=100000)
	    for(int i=0;i<n;i++)
	    {
	        cin>>p;
	        if(p>=0&&p<=1000000000)
	        prices.push_back(p);
	       // profits.push_back(p);
	    }
	        sort(prices.begin(), prices.end(), greater<int>());

	   // for(int i=0;i<n;i++)
	   // {
	   //     cout<<prices[i]<<" ";
	   // }
	   // prices.clear();
	    k++;
	}
	for(int i=0;i<n;i++)
	{
	    if(prices[i]>0)
	        --prices[i];
	}
	int Q=0,Z=0;
	 for(int i=0;i<n;i++)
	    {
	       // int Q=0;
	        Q+=prices[i];
	       // cout<<Q<<endl;
	    }
	    for(int i=n;i<2*n;i++)
	    {
	       // int Z=0;
	        Z+=prices[i];
	       // cout<<Z<<endl;
	    }
	   // for(int i=0;i<2*n;i++)
	   // {
	   //    // int Z=0;
	   //     cout<<prices[i];
	   //    // cout<<Z<<endl;
	   // }
	    if(Q==0&&Z!=0){cout<<Z%MOD<<endl<<1;}
	    else if(Z==0&&Q!=0){cout<<Q%MOD<<endl<<1;}
	    else{cout<<Q%MOD<<endl<<Z%MOD;}
	   
	}
	  return 0;
}

Yes , i corrected the printing of answer twice. apart from using long in the code , is there any other logical change that needs to be done ?

you are not using modulo

I can’t find any mistake in my soln…

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
	long long int T,n,p,k=0,MOD=1000000007;
	cin>>T;
	if(T>=1&&T<=25)
	{
	vector<long long int>prices;
	while(k<T)
	{
	    cin>>n;
	   // years.push_back(n);
	   if(n>=1&&n<=100000)
	    for(int i=0;i<n;i++)
	    {
	        cin>>p;
	        if(p>=0&&p<=1000000000)
	        prices.push_back(p);
	       // profits.push_back(p);
	    }
	        sort(prices.begin(), prices.end(), greater<int>());

	   // for(int i=0;i<n;i++)
	   // {
	   //     cout<<prices[i]<<" ";
	   // }
	   // prices.clear();
	    k++;
	}
	for(int i=0;i<n;i++)
	{
	    if(prices[i]>0)
	        --prices[i];
	}
	int Q=0,Z=0;
	 for(int i=0;i<n;i++)
	    {
	       // int Q=0;
	        Q+=prices[i];
	       // cout<<Q<<endl;
	    }
	    for(int i=n;i<2*n;i++)
	    {
	       // int Z=0;
	        Z+=prices[i];
	       // cout<<Z<<endl;
	    }
	   // for(int i=0;i<2*n;i++)
	   // {
	   //    // int Z=0;
	   //     cout<<prices[i];
	   //    // cout<<Z<<endl;
	   // }
	    if(Q==0&&Z!=0){cout<<Z%MOD<<endl<<1;}
	    else if(Z==0&&Q!=0){cout<<Q%MOD<<endl<<1;}
	    else{cout<<Q%MOD<<endl<<Z%MOD;}
	   
	}
	  return 0;
}

Please correct me if you find the mistakes.