LELEMON - Editorial

editorial
, , , ,
1

PROBLEM LINKS

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Ad Hoc, Sorting

PROBLEM

There are N rooms, numbered from 0 to N-1. Room number i contains Ci bottles of lemonade.

You visit M rooms in some order. You may visit a room more than once.

When you visit a room that contains at least one bottle of lemonade, you drink all the lemonade from that bottle in the room, which contains the largest volume of lemonade.

Find the amount of lemonade you will drink.

EXPLANATION

We can simulate the instructions for the problem directly in code.

When we visit a room, we can find the index of the bottle of lemonade with the largest volume and mark that bottle such that it is not picked up again.

The complexity of this solution is O(m * max(Ci)).

Alternate Approach

There is a faster solution though.

Sort the bottles in each room by volume. This takes O(n2 log n) time.

Now, we must pick as many bottles from each room as the number of times we visit that room.** We can iterate over the list of rooms visited and store how many times each room is visited**.

From this much pre processing, we can now find the answer by adding the volumes of as many bottles from each room.

The complexity of this solution is O(m + n + n2 log n).

CODING COMMENTARY

The high acceptance rate is quite clearly indicative of there being few crucial pitfalls. Simulation problems require implementing all the ideas carefully.

The answer fits inside 32-bit signed integer data type.

You visit the same room several times. It is possible that you visit a room that has no more bottles of lemonade left.

It is easy to see that in such cases, care must be taken to ignore the latest visit.

This problem requires storing a 2D array of integers where the number of elements in each row may be different, and are specified as well.

  • If you are in the habit of implementing such arrays by storing the number of elements in the first element of the row, make sure your array dimensions account for that extra element as well.

PSEUDO CODE

Given: N, M, A[M], C[N], V[N][C[i]]

for i = 1 to N
	sort( V[i][1] to V[i][C[i]] )

result = 0

for i = 1 to M
	_i = A[i]
	if C[_i] > 0 then
		result = result + V[_i][C[_i]]
		C[_i]--

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

1 Like
2

i have used priority_queues just for the taste of it, we put there volumes and on final simulation step, we just top and pop if queue is not empty

here is my solution
https://www.codechef.com/viewsolution/8664115