if(m-i > 0){
mt = m-i;
}
else{
mt = 0;
}
This should fix your code.
https://www.codechef.com/viewsolution/31367781
My approach →
- I sorted the array in decreasing using merge sort
- 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 <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;
}
you need to use mod as ans%mod not subtract it
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;
}
}
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))
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
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;
}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.
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.
- Your
mod = 10^9 + 7is a bit wrong.^is the XOR operator in C++, not power. Replace it withmod = 1e9 + 7 - You should initialize
max_profitto 0 at each iteration ofias it holds the value of the previous test case. - Not actually a mistake but it’s better to make a new vector for each test case.
Your code should give AC now.
if(ans >= MOD){
Should give AC now 
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.
anyone any suggestion ?
#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
#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;
}
can somebody tell me what’s t error and how can i remove it thankyou
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