GASOLINE - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Ildar Gainullin
Tester: Nikolay Budin
Editorialist: Alei Reyes

DIFFICULTY:

Easy

PREREQUISITES:

Sorting

PROBLEM:

There are n cars on a circular track of length n, the i-th of them is on clockwise distance i-1 from the car 1.

You can fill the i-th car with at most f_i litres of gasoline and pay c_i coins for each litre. Then you choose one of the cars, and start driving clockwise, the car spends one litre of gasoline per unit of distance. When you pass through another car, you steal all its gasoline.

Fill the cars with the minimum cost in such a way, that is possible to choose a car and travel a distance n clockwise.

QUICK EXPLANATION:

Greed is good: Iterate over the cars in non-decreasing order of cost and greedily fill it with the maximum possible (and necessary) litres of gasoline.

EXPLANATION:

Let’s suppose that the i-th car is filled with q_i litres of gasoline, the necessary and sufficient conditions to be able of driving a full circle are:

  • q_i \leq f_i
  • q_1 + q_2 + ... + q_N = N

If the second condition is not quite clear, you can imagine that buying a litre of gasoline from the i-th car creates a bridge of length one between positions i and i+1. If one bridge intersects another one, it pushes it clockwise. In order to drive a full circle we need N bridges.

The cost expended in the i-th car is q_i \cdot c_i, so we are asked to minimize P=q_1 \cdot c_1 + q_2 \cdot c_2 + ... + q_n \cdot c_n.

Intuitively we should try to use the maximum litres of gasoline from the cheapest cars.

Let’s fill the cars with gasoline in increasing order of cost. Suppose that we already purchased optimally G litres of gasoline from the i cheapest cars. How much gasoline should we buy from car i+1?

  • If G \geq N, we have enough gasoline, so we don’t have to buy more.
  • Otherwise, we can buy at most g = min(f_i, N-G) litres of gasoline. Should we buy all the g litres? Yes, if we buy one unit less, then that unit will be purchased from another more expensive (or at least not cheaper) car!

SOLUTIONS:

Setter's Solution
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    int n;
    cin >> n;
    vector <int> f(n),c(n);
    for (int i = 0; i < n; i++) {
      cin >> f[i];
    }
    vector <pair <int, int> > e;
    for (int i = 0; i < n; i++) {
      cin >> c[i];
      e.push_back({c[i], f[i]});
    }
    sort(e.begin(), e.end());
    int sum = 0;
    ll ans = 0;
    for (auto c : e) {
      if (sum + c.second <= n) {
        sum += c.second;
        ans += c.first * (ll) c.second;
      } else {
        ans += (n - sum) * (ll) c.first;
        break;
      }
    }
    cout << ans << '\n';
  }
}
Tester's Solution
void solve() {
  int n;
  cin >> n;
  vector<int> arr;
  for (int i = 0; i < n; ++i) {
    int num;
    cin >> num;
    arr.push_back(num);
  }
  vector<int> cost;
  for (int i = 0; i < n; ++i) {
    int num;
    cin >> num;
    cost.push_back(num);
  }

  vector<int> order(n);
  iota(order.begin(), order.end(), 0);
  sort(order.begin(), order.end(), [&](int a, int b) {
    return cost[a] < cost[b];
  });

  ll ans = 0;
  int left = n;
  for (int pos : order) {
    int val = min(left, arr[pos]);
    left -= val;
    ans += (ll) val * cost[pos];
    if (!left) {
      break;
    }
  }
  cout << ans << "\n";
}

VIDEO EDITORIAL:

9 Likes

thanks,
if any one needs Hindi video editorial - LINK

3 Likes

I submitted a totally random solution, which surprisingly passed.
Can someone please explain why it works? I couldn’t prove it.

5 Likes

Hi @alei, What does this mean
When we move from 1 car to another are we going to steal its gasoline or buy gasoline?

2 Likes

Dont know why there are no explanations for test cases in codechef… I mean we cant extract sol from ur explanaton. LOL.
in this question many things were unclear like what does stealing mean, does it mean buying only or taking for free etc…
pls explain at least one case in questions.

13 Likes

First you have to buy gasoline and then put it into some car (which cost you coins )and later you can steal from it without any cost . Thus both are same.

Guess you’re only one who pays and steals :slight_smile:

5 Likes

Yes. This question was so unclear. Really a painful experience. Seemed like a screwed up English test.

2 Likes

LOL… Well i at least solved the problem either by paying or stealing whatever…
what abt u?
Take care.

Actually You’re using an ordered map which is sorted . Thus it’s like iterating a sorted array . You can read more about it from here

1 Like

i did use the greedy way but got WA can someone help where it goes wrong.
My sol:
https://www.codechef.com/viewsolution/39887116

You didn’t even participate how can you say🌚 ?

It worked because you can start from any point , so you would surely start from where the answer could be found . I would suggest you to right down some examples.
P.S. : I too had the same solution and was sure that it’s right but because I started late I thought after solving 2nd I would submit both together , which surely I wasn’t able to solve
EDIT:any point means that if your sum of capacity of tank is N , then there is always atleast one node via which you can cover distance N.

1 Like

After reading the tutorial I realized I didn’t understand the question correctly.

Yes, I’m aware of the fact that a map sorts values. Actually, I had seen the submissions page for that problem when I was trying to solve it. Many C++ solutions took ~1s. So I knew that it had to be O(n\log{n}). I did random stuff with a map and it luckily passed. I still don’t understand why my solution works.

2 Likes

I knew this had to be greedy approach. Just couldn’t implement it…

anyone please explain how sorting work here ?

1 Like

Problem statement was too poor. What do you mean by stealing??? At least you could have explained the test cases or could have replied to our comments :confused:

9 Likes

following

1 Like

True, things are unclear here, whether we refill our existing car or change the car itself, point here is how much gasoline we take.