# CHEFCAR - Editorial

Author: Akshat mangal
Editorialist: Ritesh Gupta

EASY

# PREREQUISITES:

Math, Observation

# PROBLEM:

Initially, you are at 1 with empty tank and need to travel at N with your car. To travel 1 Km, you need 1 liter of water. There is a gas station after each 1 Km means at 1, 2, …, N, but the cost of filling 1 liter of gas at a gas station is equal to the number of gas station. you can not store more than V liters of gas in the tank of a car. Find both minimum as well as the maximum cost of filling that can happen to reach at N.

# QUICK EXPLANATION:

As cost of the gas is increasing by going towards the N and we need only 1 liter of gas to reach from i-th station to (1+1)-th station

• which means that to maximise the cost, we can only take 1 liter of gas at each station. So, we need to travel total N-1 Km and we are starting from 1 that means (N*(N-1))/2 is the maximum cost.
• which means that to minimise the cost, we can try to fill the tank as soon as there is some empty space. So, we are filling the tank with V liters at station 1 and after that at each station we are consuming 1 liter to reach there so filling that 1 liter at that station itself. This way minimum cost is ((N - V)*(N - V + 1))/2 + V - 1 but if the tank capacity V is more or equal to N-1 then the minimum cost is (N-1) only.

# EXPLANATION:

## Maximum Cost:

As cost of filling the gas at each station is more then it’s previous one, to maximise the cost we try to buy gas from a station which is giving us in more money. Or if we have a choice that we can buy the gas either from i-th station or (i+x)-th station where x > 0 then we better choice would be to choose (i+x) station.

So, at any station will buy only the gas which will help us to reach the next station.

• at station 1, we take 1 liter gas which cost us 1 and we can go upto station 2
• at station 2, we take 1 liter gas which cost us 1 and we can go upto station 3
• at station N-1, we take 1 liter gas which cost us N-1 and we can go upto station N

Overall cost is (1 + 2 + ... + (N-1)) or (N*(N-1))/2

## Minimum Cost:

As cost of filling the gas at each station is more then it’s previous one, to minimise the cost, we need to do the opposite of the maximum or if we have a choice that we can buy the gas either from i-th station or (i+x)-th station where x > 0 then we better choice would be to choose (i) station.

Now, if we have enough capacity in the tank then we can fill the tank at station 1 only with the required gas and complete the journey. Mathematically, if V >= (N-1) then minimum cost will be (N-1)

Otherwise, we try to fill the tank as soon as possible.

• at station 1, we take V liter gas which cost us V and we reach station 2
• at station 2, we take 1 liter gas which cost us 2 and we reach station 3
• at station N-V, we take 1 liter gas which cost us N-V and we reach station N-V+1
• at station N-V+1, we take 0 liter gas which cost us 0 and we reach station N-V+2
• at station N-2, we take 0 liter gas which cost us 0 and we reach station N-1
• at station N-1, we take 0 liter gas which cost us 0 and we reach station N

Overall cost is (V + 2 + 3 + ... + (N-V)) or ((N - V)*(N - V + 1))/2 + V - 1

# TIME COMPLEXITY:

O(1) per testcase

# CODE:

Setter (C++)
```#include
typedef long long ll;
using namespace std;

void pre()
{

}

void solve()
{
ll n,v;
cin>>n>>v;
ll min_cost;
if(n-1<=v)
min_cost=n-1;
else
min_cost=v+(n-v)*(n-v+1)/2-1;

cout<<n*(n-1)/2<<" "<<min_cost<<'\n';

}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout<<fixed<>t;
for(ll tt=1;tt<=t;tt++)
{
// cout<<"Test Case #"<<tt<<": \n";
solve();
}
return 0;
}

```
Tester (C++)
```#include
using namespace std ;

int n , v ;

void input ( ) {
cin >> n >> v ;
}

void solve ( ) {
if ( v >= n - 1 ) {
cout << 1LL * n * ( n - 1 ) / 2 << " " << n - 1 << "\n" ;
}
else {
cout << 1LL * n * ( n - 1 ) / 2 << " " << v + ( 1LL * ( n - v + 1 ) * ( n - v ) / 2 - 1 ) <> t ;
while ( t -- ) {
input ( ) ;
solve ( ) ;
}
return 0 ;
}

```
Editorialist (C++)
```#include
using namespace std;

int main() {
int t;
cin >> t;

while(t--) {
long long n,v;
cin >> n >> v;

if (v >= n-1) {
cout << (n*(n-1))/2 << " " << n-1 << endl;
} else {
cout << (n*(n-1))/2 << " " << ((n-v)*(n-v+1))/2 + v - 1 << endl;
}
}

return 0;
}

```
2 Likes

To maximise the cost, we can only take 1 liter of gas at each station. So, we need to travel total N-1 Km and we are starting from 1 that means (N * (N-1))/2 is the maximum cost.

Could anyone explain why aren’t we filling up the tank completely at the first station. As that would lead to a maximum cost of ((N * (N-1)/2) - 1 + V).

No, just consider this analogy, 1+1+1+1+1< 1+2+3+4+5 considering there are 6 stations or posts

For example, take 5 3:
N=5, V=3
Here, we need to go from 1->2,2->3,3->4,4->5.
Change Cost
—1-2 ------1
—2-3 ------2
—3-4 ------3
—4-5 ------4
Total cost = 1+2+3+4 = 10 (or from formula (N * (N-1))/2 = 5*(5-1)/2 = 5*4/2 = 10).
if we use the formula ((N * (N-1)/2) - 1 + V), then we get 12.
But 12 is not correct. So, the formula ((N * (N-1)/2) - 1 + V) is incorrect.
Correct me if I am wrong.

You can fill up your tank fully at the 1st station then put 1 liter in your tank in the subsequent checkpoints.

1 Like

I feel uncomfortable with the way that the maximum cost scenario has been handled.

Take for instance the case where you buy only 1 liter of gas at every stop except for the (n-1)th one, where you completely fill your tank.

From here, you get:
1 + 2 + … (n - 2) + v * (n - 1) >= 1 + 2 + … (n-2) + (n-1).

Clearly the case that we have taken here has a greater cost. There might be some other scenario where it’s maximum, but the solution given in the editorial definitely isn’t it.

The problem statement says:

You shouldn’t have any water left after reaching Nth checkpoint. Also you are not allowed to pour out water.

1 Like

No, maximum cost scenario looks fine. Just intuitively it makes sense to spend maximum at the very last.

In the case of minimising the cost ,we stop taking gas when we don’t need it.

• at station N-V+1, we take 0 liter gas which cost us 0 and we reach station N-V+2