CRASH - Editorial

editorial
,
1

PROBLEM LINK:

Stock Market Crash

Setter: akshitpanday

Tester: imsarthak

DIFFICULTY:

Easy

PREREQUISITES:

Basic Problem solving, Greedy.

PROBLEM:

Mr Tyagi is an investor and has N shares of different companies. Recently he was caught in a case related to Insider trading because of which SEBI imposed some restrictions on him. He is in need of cash and decides to sell all of his shares. But due to SEBI restrictions he is allowed to sell only 1 share per day. The current price of ith share is Pi and due to the war crisis the price of shares decreases by Rs1 every day.(Note the price of shares does not depreciate below 0) Find the maximum money he can get by selling his shares in an optimal way.

EXPLANATION

To get the highest possible profit he must the sell the shares with decreasing order of share prices. By selling in these order he can maximize his profit.
So to process we just simply need to sort the prices in decreasing order and keep calculating the price along with depreciation of Rs 1 per day.

Example

2
3  
4 12 1
3
3 3 3

Output

15
6

For 1st testcase

  • On 1st day he sells 2nd stock at Rs 12, so profit = 12
  • On 2nd day he sells 1st stock at Rs 3 so profit = 12 + 3 = 15
  • On 3rd day 3rd stock has 0 value so profit = 15 + 0 = 15
    So his profit is 15.

For 2nd testcase
Total profit is 3 + 2 + 1 = 6

SOLUTIONS:

Setter’s Solutions:

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

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	public static void main(String[] args) {
        int numberOfTestCases;
        Scanner sc = new Scanner(System.in);
        numberOfTestCases = sc.nextInt();
        for(int z=0; z<numberOfTestCases; z++) {
            int numberOfStocks;
            long profit=0;
            numberOfStocks = sc.nextInt();
            long [] prices = new long[numberOfStocks];
            for(int i=0; i<numberOfStocks; i++) {
                prices[i] = sc.nextLong();
            }
            Arrays.sort(prices);
            int depreciation = 0;
            for(int i=numberOfStocks-1; i>=0; i--) {
                prices[i] = prices[i] - depreciation;
                if(prices[i]<0)
                    prices[i] = 0;
                profit = profit + prices[i];
                depreciation++;
            }
            System.out.println(profit);
        }
    }
}

Tester’s Solution:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define mp make_pair
#define pof pop_front
#define fri(i,r,s)  for(ll i=r;i<s;++i)
#define loop(i,a) for (auto &i : a)
#define ftio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pd(x) cout<<fixed(set_precision(10))<<x;
int main()
{
    ftio;
    ll t;
    cin>>t;
    // isPrime();
    // fib();
    while(t--)
    {
        ll n;
        cin>>n;
        vector<ll>v(n);
        fri(i,0,n) cin>>v[i];
        
        sort(v.begin(),v.end(),greater<int>());
        
        fri(i,0,n){
            v[i] = (v[i]>=i)?(v[i]-i): 0 ; 
            
        }
        
        cout<< accumulate(v.begin(),v.end(),0)<<"\n";
        
       
    }
    return 0;
}
1 Like