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. 
