CARSELL - Editorial

What are u doing in the last for loop where u are going from 0 to 2n?

You are implementing your solution after getting the input from all test cases. The value stored in the price vector is the last input of the test case.
Try this test case:
4
3
0 1 0
3
6 6 6
3
0 1 0
3
6 6 6

Can someone help me and explain why I am getting TLE for this solution for the unconstrained sub-task?

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

int main() {
int t;
int n;
int i;
long long int price[n];
long long int sum;
cin>>t;
while(t–)
{
cin>>n;
sum = 0;
for(i=0;i<n;i++)
{
cin>>price[i];
}
sort(price,price+n,greater());
/* for(i=0;i<n;i++)
{
cout<<price[i]<<" “;
}*/
for(i=0;i<n;i++)
{
if((price[i]-i)<=0)
{
break;
}
sum = sum + price[i] - i;
// sum = sum%1000000007;
}
sum = sum%1000000007;
cout<<sum<<”\n";
}
return 0;
}

It gave correct answer for sub-task 1 but failed and gave TLE for sub-task2

You are not doing mod

Where should I correct the mistake?

We need to sort the input.
Without sorting it would fail for the test case of 2 3 5 4 1
When sorted, will give maximum profit of 9, without sorting it would give 8.

Could you please explain your test case?

1 Like

Your logic of decrementing the price array is wrong because the loop checks if price is greater than zero and then just decrements it.
Eg. The test case
1
3
6 6 6

Your code give same answer 15 but it coincidently matches with the answer.
The condition given in question is “the price of each car decreases by 1 unit per year until it is sold.” Your are decrementing each element once. You must decrement the remaining elements the by k times if k years have passed.

For this test case
2 3 5 4 1
After sorting
5 4 3 2 1
Now profit is 0
After selling a car profit is 5 and price of rest car decrement by 1 [3,2,1,0]
Now selling the other car profit 5+3=8 and price of rest car decrement by 1 [1,0,0]
Now selling the other car profit 5+3+1=9 and the price of rest cars [0,0].

So profit is 9.
But according to your code the final price array is
[4,3,2,1] profit=10.

1 Like

Thanks mate, Looked over your solution too, amazing!

My commented code for the solution.

Thanks for the clarification. I didn’t thought about that test case.

I think the problem is while declaring the array.
You are declaring the array without any value of n.
n in the first line will store any garbage value and that will be the size of your array.
Declare the array after taking the input n, and it works fine.
And also in sort function, it will be greater<int>().
I hope that helps.

1 Like

You are not doing %10e9+7 in profit+=(a[i]-1). It should be profit+=(a[i]-1)%1000000007

I am a beginner and I had written this solution and when i run it through sample test case, i get the answer but I would like to get some help as this code didnt get accepted. Please let me know what things I have missed and your suggestions would help me a lot

#include <bits/stdc++.h>

using namespace std;
#define endl ‘\n’;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin>>t;
while(t–)
{
int n,sum=0;
cin>>n;
vector v(n);
for(int i=0;i<n;i++){
int a;
cin>>a;
v.emplace_back(a);
}
sort(v.begin(),v.end());
for(int i=0;i<n;i++){
int z=v.size();
int m=v[z-1];
int mt;
v.pop_back();
if(m>0)
{
mt=m-i;
}
else
{
mt=m;
}

        sum+=mt;
      }
      cout<<sum<<endl;

}
}

Is it compulsory to sort in non-increasing order as only 1 is reduced each year. What if I starting adding from smaller number and goto biggest number?
When I started adding from biggest to solve it passed all testcases but while adding smallest to biggest it failed.
Passed
Failed

if(m-i > 0){
      mt = m-i;
}
else{
      mt = 0;
}

This should fix your code.

https://www.codechef.com/viewsolution/31367781
My approach →

  1. I sorted the array in decreasing using merge sort
  2. then until (arr[i]-i>0) i add the modulo sum
    sum= ((sum%modulo)+((arr[i]-i)%modulo))%modulo;

I am getting wrong answer . Please tell me if i am missing any corner case or anything wrong with my approach. Thank you.

I can’t get my solution accepted at all! I can’t find the mistake in my code. My answer was same but I got WA even during the contest. Please someone tell what’s wrong. You can check my profile I have done more than wrong attempts to this lol

#include

#include <bits/stdc++.h>

using namespace std;

#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

typedef unsigned long long ull;

typedef long long ll;

int main(int argc, char const *argv[])

{

#ifndef ONLINE_JUDGE

// for getting input from input.txt

freopen("input.txt", "r", stdin);

// for writing output to output.txt

freopen("output.txt", "w", stdout);

#endif

boost;

const int MOD = 1000000007;

int t;

cin>>t;

while(t--){

    int n;

    cin>>n;

    vector<int> arr(n);

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

        cin>>arr[i];

    }

    sort(arr.rbegin(), arr.rend());

    int ans = 0;

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

        ans += max(arr[i] - i, 0);

        if(ans > MOD){

            ans -= MOD;

        }

    }

    cout<<ans<<"\n";

}

return 0;

}

without using modulo it is giving WA bro
@taran_1407