PROBLEM LINK:
Author: Akshay Padte
Tester: Rushang Gajjal
Editorialist: Aditya Prajapati
DIFFICULTY:
EASY
PROBLEM:
We’ve got the expected rainfall of n days in form of an array A, and a tank with capacity V. We need to collect the water so we will have to empty the tank once it’s capacity is full. Now, Shivam being a lazy official wants to go to the facility only when the tank capacity is full. We need to find the number of days and the last day when he’ll have to go to the facility.
EXPLANATION:
For each test case, we are provided with the number of days n and the number of queries Q.
Now, since we know that the water will be filled continuously, we can maintain a presum array, and then for each query find the position where we need to transfer the water.
SOLUTION
For an example test case,
1
17 1
1500 1500 1500 1500 1000 1000 1000 1500 1500 1000 1000 1500 1500 1500 1000 1000 1500
10000
The presum array would be:
[1500, 3000, 4500, 6000, 7000, 8000, 9000, 10500, 12000, 13000, 14000, 15500, 17000, 18500, 19500, 20500, 22000]
Now, we can see that since the capacity of the tank is 10000, Shivam will have to empty it on the 7th day or else it would overflow on the 8th one.
But, now that the tank has been emptied on the 7th day, we need to somehow change our search element so that w can directly search for it in this array. So, what we do is add the amount of rain on the day we emptied the tank to the capacity of the tank (9000+10000=19000 here), and search for this element in the presum array, since now that the tank was empty, shivam will have to visit the facility again when the capacity(10000) is full after the day the tank was emptied.
Search : Can be done using either linear search or binary search (preferred, since it is faster).
We also maintain a count variable to count the number of days the facility had to be visited, and the terminating condition will be when the element we are searching for isn’t in the presum array.
COMPLEXITY
for each query -
q*lg(n)
TESTER AND AUTHORS SOLUTIONS
Tester’s solution can be found here.
Author’s solution can be found here.