Redirecting to
NADOS


  Prev   Next

Find Water In Glass







The best error message is the one that never shows up.
~ Thomas Fuchs

Find Water In Glass

Welcome Back ,

Hey coder. We welcome you to a new question of dynamic programming, "Find Water in Glass".

Importan Link : Problem Link, Solution Video Link

Before going any further, check out the problem to understand its outline.

Understand the Problem :
  • Pepcoder arranged some glasses in the form of a pascal triangle.
  • Capacity of each glass is 1 liter. If you pour K amount of water in a glass, it will retain 1 liter and the rest of it gets equally distributed in left bottom glass and right bottom glass.
  • If the pepcoder pours K liters of water in the topmost glass, you have to find out the amount of water in the Cth glass of the Rth row.
  • Assumption: There are enough glasses in the triangle till no glass overflows.
  • Let's understand how to solve the problem when k=7, r=3 and c=1. For this example the pascal triangle will be as shown in figure 1 and the amount of water is to be found in the marked glass.
    • img

  • When we pour 7 liters of water in the first glass, it retains only 1 liter and the rest of the 6 liters gets equally distributed in the left bottom and right bottom glasses as shown in figure 2.
    • img

  • Now, the left glass with 3 liters of water retains only 1 liter and distributes the remaining in the glasses below it.
    • img

  • Similarly, the right glass also retains 1 liter out of the 3 liters and distributes 2 liters equally among the bottom glasses which causes a glass to have 2 liters of water as shown below.
    • img

  • Hence, the above process continues for glass with 2 liters of water and we reach the following situation.
    • img

  • We see that our required glass stores 0.5 liters of water.
DYNAMIC PROGRAMMING :
  • Now to make the problem easier to solve, we change the pascal triangle in figure 6.1 to look like figure 6.2.
    • img

  • Reader, a 2d dp array is now made according to the figure 6.2.
    • img

  • We were supposed to store 7 liters in the dp[0][0] cell. But, in reality 1 liter is to be stored. Hence, we introduce a variable "spare" which stores the amount of water which overflows from a glass.
    So, at this moment, spare=7-1=6.
    This spare value gets equally distributed in the cell directly below the current cell and the cell to the south east of the current cell.
    • img

  • We keep calculating the "spare" value for overflowing glasses and follow the rest of the process for the remaining cells.
  • On doing so we reach the dp array which looks like figure 9 and return the value stored in dp[3][1].
    • img

Reader, in case you have any doubts in understanding how to fill the dp array, we strongly suggest you to watch the solution video

If you have understood the above approach for solving the problem, then you will have no problem in coding it.
You can also refer to the code given below if you get stuck somewhere.

CODE :
import java.io.*; import java.util.*; public class Main { public static double solution(int k, int r, int c) { double[][]dp=new double[k+1][k+1]; dp[0][0]=k; for(int i=0;i < dp.length;i++){ for(int j=0;j < = i;j++){ if(dp[i][j] > 1.0){ double spare=dp[i][j] -1.0; dp[i][j]= 1.0; dp[i+1][j]+=spare/ 2.0; dp[i+1][j+1]+=spare/ 2.0; } } } return dp[r][c]; } public static void main(String[] args) { Scanner scn = new Scanner(System.in); int k = scn.nextInt(); int r = scn.nextInt(); int c = scn.nextInt(); System.out.println(solution(k, r, c)); } }
java; true";
Complexity
Time Complexity:

O(n^2)

Space Complexity:

O(n^2)

We conclude this problem here. We hope you were able to understand it. In case you face any difficulties, you can also watch the solution video.

All the best for an exciting future!
Happy Coding!

Dynamic Programming
Author: Shreeya Gupta
 
Run
Id Name