Water Leve
You have G number of glasses in a row. initially each glass has
some amount of water or is empty.
Given an array of integer numbers denoting the water present in
each glass in millilitre (ml).
You can exchange only on litre of water in one move, and the
condition is that you can pour the water in adjecent glass only.
provided an interger array of glasses representing the water level
in ml
Your task is to find out the minimum number of moves to make
all the glasses have the same level of water. if it is not possible to
do it, return -1.
Ghggvb
Answers
I don't understand the question
Answer:
for the second problem, you can keep adding up the numbers from 1 to N until you either reach N or you find sum >= K. Since you are adding up consecutive numbers for 1 to min(X, N) where X is the first number between 1 and N such that sum upto X is >= K, you can use arithmetic sequence sum formula. I guess you can set K = (n * (n + 1))/ 2 and solve for n using quadratic formula. This should give you minimum glasses if possible. To check if it is not possible, just use the same formula n * (n + 1) /2 to calculate the sum upto N and if the sum is less than K then return -1
Explanation:
In this problem the rates at which glasses get filled in are rational numbers, whose numerators form the binomial coefficients and denominators are powers of 2 - specifically 2 raised to the power of level at which glasses are present.
A litre of water (overflowed from previous level) gets distributed among the glasses at each level as follows:
level 0: 1
level 1: 1/2 1/2
level 2: 1/4 2/4 1/4
level 3: 1/8 3/8 3/8 1/8
level 4: 1/16 4/16 6/16 4/16 1/16
The above distribution pattern provides with a partial progress towards the actual algorithm that finds the amount of water in jth glass of ith row. The algorithm gets tricky because all the glasses at a level might not be completely filled yet, before water starts getting filled up in levels below (albeit, in an inverted triangle fashion).
----------------------------------------------------------------------------
The above observation apart, a DP-like algorithm below(that remembers quantities in glasses of the previous row) to find out the amount of water in jth jug of ith row can solve the problem.
0. For each glass, maintain 2 variables - the amount of water it holds and the amount of water it overflows.
1. For a glass at index i in the given row, look up two glasses in the previous row at index i-1 & i. (Boundary cases of indices need to be checked though)
2. The inflow into the current glass = half of outflow of glass in the previous row at i-1 + half of outflow of glass in the previous row at index i
3. Based on the inflow, volume held in the current glass = min(1, inflow) and the overflow at the current glass = inflow - volume held by the current glass
4. Repeat steps 1 to 3 until we reach the required glass.
An implementation in java goes like the below:
import java.util.Scanner;
import java.util.regex.Pattern;
class GlassStatus {
float heldVolume;
float overflownVolume;
}
public class GlassPyramid {
static int ipRowNum, ipGlassNum, ipVolume;
public static float computeWaterAt(float volume, int level, GlassStatus[] previousRows) {
if (volume <= 0)
return 0;
GlassStatus[] rows = new GlassStatus[level + 1];
float overflow1 = 0, overflow2 = 0, inflow = 0, tempVol = 0;
for (int i = 0, prev = i-1, next = i; i <= level; i++, prev++, next++) {
rows[i] = new GlassStatus();
if (prev < 0) {
overflow1 = 0;
} else {
overflow1 = previousRows[prev].overflownVolume/2;
}
if (next >= level) {
overflow2 = 0;
} else {
overflow2 = previousRows[next].overflownVolume/2;
}
if (level == 0) {
inflow = volume;
} else {
inflow = overflow1 + overflow2;
}
tempVol += rows[i].heldVolume = Math.min(1, inflow);
rows[i].overflownVolume = inflow - rows[i].heldVolume;
}
if (level == ipRowNum) {
return rows[ipGlassNum].heldVolume;
} else {
return computeWaterAt(volume - tempVol, level + 1, rows);
}
}
public static void readInput() {
Scanner scanner = new Scanner(System.in);
scanner.useDelimiter(System.getProperty("line.separator"));
Pattern delimiters = Pattern.compile(System.getProperty("line.separator")+"|\\s");
scanner.useDelimiter(delimiters);
System.out.println("Input row#:");
ipRowNum = scanner.nextInt();
System.out.println("Input glass#:");
ipGlassNum = scanner.nextInt();
System.out.println("Input volume:");
ipVolume = scanner.nextInt();
}
public static void main(String[] args) {
readInput();
System.out.println("Volume in the glass=" + computeWaterAt(ipVolume, 0, new GlassStatus[] {}));
}
}