COG1802 - Editorial

general
,
1

PROBLEM LINK:

Practice

Contest

Author: Puneet Kumar

Editorialist: Pawan Mishra

DIFFICULTY:

SIMPLE

PREREQUISITES:

Cumulative Sum

PROBLEM:

Given a very large cylinder open from the top, fills this cylinder with N type of liquids. Each liquid has some Density Pi and covers Hi height. Liquids are immiscible and will remain at the position where they are filled.Q queries follow, In each query, Given values L and R, calculate the total pressure considering only the liquids between height L and R. That means if we remove all the liquid starting from height L to R and put it in some other Cylinder in the same order as they are in the present cylinder then what will be the pressure at the bottom of this new Cylinder.

Output the total pressure for each query. The Formula for calculating Pressure is P∗g∗H.

EXPLANATION:

The naive approach can be to apply a loop from L to R for every query which will exceed the time limit as such.
So, in this problem, the answer lies in the constraint that sum of heights of all liquids ≤ 1000000 for each test case.
So we can create a cumulative array A of size equal to the sum of heights of all liquids, where A[i] will show the total pressure exerted on the bottom due to liquids up to height i. Size of this A will always be less than 1000000.

To do this, First initialize each A[i] with Pk * g which is pressure due to the unit height of liquid k which is present at the height i.
then

h=1
A[0]=0
for i = 1 to N:
	for j = 1 to Hi:
		A[h] = Pi * g
		h++
for i = 2 to h-1:
	A[i] = A[i] + A[i-1]

The double for loop above will run less than 1000000 times due to above constraint.
Now for every query, answer is A[R] - A[L-1] which we have precomputed and can be obtained in O(1).

NOTE: You can also make cumulative array in bottom down fashion.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.

Little Appreciation Keeps us Motivated.

1 Like