CARSELL - Editorial

editorial
, , , ,
43

you need to use mod as ans%mod not subtract it

44

What is wrong with the solution given below? Please help.

#include<bits/stdc++.h>
using namespace std;

main(){
int t;
cin>>t;
while(t–){
const unsigned int M = 1000000007;
int i,n;
cin>>n;
int arr[n];
for(i=0;i<n;i++){
cin>>arr[i];
}
int sum=0,j=0;
sort(arr,arr+n);
for(i=n-1;i>=0;i–){
if(arr[i]-j>0){
sum=sum+arr[i]-j;
j++;
}
}
cout<<sum%M<<endl;
}
}

45

Simplest Solution in Python for CARSELL

T = input()
for _ in range(int(T)):
N = int(input())
A = list(map(int, input().rstrip().split()))
A.sort()
A = A[::-1] # sorted descending array
for i in range(0,N):
if A[i]-i>0:
A[i] = A[i]-i # adding cost to total after subtracting its index, i.e. the time
else: # when car is sold
A[i] = 0
S = sum(A)
print(S % (10 ** 9 + 7))

46

My approach for CARSELL : CodeChef: Practical coding for everyone
I took the input in a vector v then I just sorted it in ascending order. Then I started the for loop starting from k= 0 to n-1. In that loop I just checked the value of difference between last value of vector and k to be greater than 0 and I stored this difference in a variable res. Then I just removed the element from the vector and then this process continues till k=n-1.

1 Like
47

I am getting time limit exceeded for my solution. Cant figure out the mistake. Here is my solution.

#include <iostream>
#include <vector>
#include <algorithm>

#define ll long long int

using namespace std;

ll mod = 10 ^ 9 + 7;


int main() {
	ll T;
	int N;
	ll max_profit = 0;
	cin >> T;
	ll temp;
	vector<ll> prices;
	
	for (ll i = 1; i <= T; i++)
	{
		cin >> N;
		for (ll c = 1; c <= N; c++)
		{
			cin >> temp;
			prices.push_back(temp);
		}


		sort(prices.begin(), prices.end());
		ll k = 0;
		ll depreciation = 0;
		for (ll j = prices.size() - 1; j >= 0; j--)
		{

			if (k == 0)
			{
				depreciation = prices[j];
			}
			else
			{
				depreciation = prices[prices.size() - 1] - k;
				if (depreciation < 0)
				{
					depreciation = 0;
				}				
			}
			max_profit += depreciation;
			prices.pop_back();
			k++;
		}
		cout << max_profit % mod << endl;
	}

	return 0;
}
48

I think this will not give TLE because the complexity of your solution is O(N*log(N)). But this will give WA as you must do modulus in each iteration instead of doing it in the end.

@sulemanrai

49

hi @ayushomi007 if i replace this line of code max_profit += depreciation; with this max_profit = ((max_profit + depreciation) % mod); and only print max_profit it still gives me TLE error.

50
  1. Your mod = 10^9 + 7 is a bit wrong. ^ is the XOR operator in C++, not power. Replace it with mod = 1e9 + 7
  2. You should initialize max_profit to 0 at each iteration of i as it holds the value of the previous test case.
  3. Not actually a mistake but it’s better to make a new vector for each test case.
    Your code should give AC now.
51

if(ans >= MOD){
Should give AC now :slight_smile:

52

hi @dragonado thanks for the feedback. It got accepted. Thanks.

1 Like
53

Thanks for the reply.
Yes, you were correct. The entire problem lied in declaration of array. When giving the subscript a constant value, the test cases were executed successfully.
Also, I did give greater but it didn’t get copied for some reason.
Once again, thanks for the suggestion.

54

anyone any suggestion ?

55

#include
#include
#include
using namespace std;

int main() {

ios::sync_with_stdio(false);
cin.tie(0);
unsigned long long int T,n,p;
const int mod=1000000007;
vector<long long int>vec;

cin>>T;
for(int i{0};i<T;i++){
   unsigned long long int profit=0;
    cin>>n;
    
    for(int j{0};j<n;j++){
        cin>>p;
        if(p>0)
        vec.push_back(p);
    }
    sort(vec.begin(),vec.end());
    while(vec.size()>0){
       profit+=vec.at(vec.size()-1);
       vec.pop_back();
       for(int k{0};k<vec.size();k++){
            if(vec.at(k)>0)
               vec.at(k)--;
      }
    }
    cout<<profit%mod<<endl;
    vec.clear();
}
return 0;

}

I don’t know what is wrong with this solution. It shows only partially correct solution. I got only 30 points. Someone please help

56

#include
using namespace std;
void swap(long long int *xp, long long int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}

// A function to implement bubble sort
void bubbleSort(long long int arr[], long long int n)
{
int i, j;
for (i = 0; i < n-1; i++)

// Last i elements are already in place  
for (j = 0; j < n-i-1; j++)  
    if (arr[j] > arr[j+1])  
        swap(&arr[j], &arr[j+1]);

}
int main() {
// your code goes here
int t;
cin>>t;
while(t–){
long long int n;
cin>>n;
long long int car[n];
for(long long int i=0;i<n;i++){
cin>>car[i];
}
bubbleSort(car,n);
long long int m=n,s=0;

    for(long long int i=0;i<n;i++){

        for(long long int j=0;j<m;j++){
           long long int max=car[0];
            for(long long int k=0;k<m;k++){
                if(car[k]>max) {max=car[k];}
                else if(car[k]>0) --car[k];
            }
            s+=max;
            m--;
        }
    }

cout<<s%1000000007<<endl;

}
return 0;

}

57

can somebody tell me what’s t error and how can i remove it thankyou

58

it was really a very good problem . we had to observe the fact that if we sort the array then we need to consider last one instead of first one
for eg :n=5 [1,2,3,15,60]
this tc explains the reason why we had to sort the array in the reverse order rather than to sort in ascending order