Most of us are familiar with google codejam, those who don’t visit https://code.google.com/codejam for more information. This is the second problem from Online Round 1B 2013, top 1000 from this round will be eligible for next online round.
Problem Statement
Diamonds are falling from the sky. People are now buying up locations where the diamonds can land, just to own a diamond if one does land there. You have been offered one such place, and want to know whether it is a good deal.
Diamonds are shaped like, you guessed it, diamonds: they are squares with vertices (X-1, Y), (X, Y+1), (X+1, Y) and (X, Y-1) for some X, Y which we call the center of the diamond. All the diamonds are always in the X-Y plane. X is the horizontal direction, Y is the vertical direction. The ground is at Y=0, and positive Y coordinates are above the ground.
The diamonds fall one at a time along the Y axis. This means that they start at (0, Y) with Y very large, and fall vertically down, until they hit either the ground or another diamond.
When a diamond hits the ground, it falls until it is buried into the ground up to its center, and then stops moving. This effectively means that all diamonds stop falling or sliding if their center reaches Y=0.
When a diamond hits another diamond, vertex to vertex, it can start sliding down, without turning, in one of the two possible directions: down and left, or down and right. If there is no diamond immediately blocking either of the sides, it slides left or right with equal probability. If there is a diamond blocking one of the sides, the falling diamond will slide to the other side until it is blocked by another diamond, or becomes buried in the ground. If there are diamonds blocking the paths to the left and to the right, the diamond just stops.
falling diamonds problem google codejam round 1b 2013
Consider the example in the picture. The first diamond hits the ground and stops when halfway buried, with its center at (0, 0). The second diamond may slide either to the left or to the right with equal probability. Here, it happened to go left. It stops buried in the ground next to the first diamond, at (-2, 0). The third diamond will also hit the first one. Then it will either randomly slide to the right and stop in the ground, or slide to the left, and stop between and above the two already-placed diamonds. It again happened to go left, so it stopped at (-1, 1). The fourth diamond has no choice: it will slide right, and stop in the ground at (2, 0).
Input
The first line of the input gives the number of test cases, T. T lines follow. Each line contains three integers: the number of falling diamonds N, and the position X, Y of the place you are interested in. Note the place that you are interested in buying does not have to be at or near the ground.
Output
For each test case output one line containing “Case #x: p”, where x is the case number (starting from 1) and p is the probability that one of the N diamonds will fall so that its center ends up exactly at (X, Y). The answer will be considered correct if it is within an absolute error of 10-6 away from the correct answer. See the FAQ for an explanation of what that means, and what formats of floating-point numbers we accept.
Limits
1 ≤ T ≤ 100.
-10,000 ≤ X ≤ 10,000.
0 ≤ Y ≤ 10,000.
X + Y is even.
Small dataset
1 ≤ N ≤ 20.
Large dataset
1 ≤ N ≤ 106.
Sample
| Input | Output |
7 |
Case #1: 1.0 |
Falling Diamonds problem Google codejam Online Round 1B 2013 solution with explanation
First of all it is important to understand the trend of diamonds settling in the XY plane, basically they will form a shape of triangle of 1, 5, 15, 28 diamonds as in the below image
falling diamonds solution google codejam
If you observe we can get the number of diamonds in the triangle of n layers as per this formula:
Tn = Tn-1 + 4n-3
Now for any X,Y, we can say that if number of falling diamonds are less than the diamonds in the triangle of one layer less, the probability of falling a diamond at X,Y position is 0. similarly we can say if number of diamonds are more than the number of diamonds in the triangle of (abs(X) + abs(Y))/2 +1 layer, the probability of falling a diamond at (X,Y) position is 1.
Lets say for any X,Y n = (abs(X) + abs(Y))/2 +1.
If you note we can further say if number of diamonds are less then Tn-1+Y, they probability of falling a diamond at (X,Y) position is 0.
And, if number of diamonds are more then Tn-X then the probability of falling a diamond at (X,Y) position is 1.
Now for any (X,Y) we can first get the n and calculate Tn-1, Tn-1 diamonds will form the triangle shape no matter how they fall. Now the remaining number of diamonds r = N-Tn-1 can fall left or right with 0.5 probability. Further, we can also say that probability of falling a diamond at -X,Y and X,Y will be the same.
So for any Y, we will calculate probability of falling a diamond on left side at Y+1 height(for Y position).
P(of 3 diamonds going left with 0 diamond on right and r diamonds remaining) = P(of next diamond going left, 0.5)*P(of 2 diamonds going left with 0 diamond on right and r-1 diamonds remaining) + P(of next diamond going right, 0.5)*P(of 3 diamonds on left with 1 diamond on right and r-1 diamonds remaining)
Here is the Java code for Falling Diamonds problem in Google codejam Online Round 1B 2013
package googlecodejam2013;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.Reader;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
public class FallingDiamonds {
private static Map<Integer, BigInteger> tnMap = new HashMap<Integer, BigInteger>();
public static double getProbability(int N, int X, int Y){
int n = ((Math.abs(X) + Math.abs(Y))/2) +1;
BigInteger minimumDiamonds = tnMap.get(n-1).add(new BigInteger(""+Math.abs(Y)));
if(X == 0){
minimumDiamonds = minimumDiamonds.add(new BigInteger(""+Math.abs(Y)));
}
BigInteger maximumDiamonds = tnMap.get(n).subtract(new BigInteger(""+Math.abs(X)));
if(N <= minimumDiamonds.longValue() ){ return 0; } if(N >= maximumDiamonds.longValue()){
return 1;
}
N -= tnMap.get(n-1).longValue();
int left = Y+1;
int right = 0;
int maxHeight = Math.abs(X) + Math.abs(Y);
return getProbabilityHelper(left, right, N, maxHeight);
}
private static void initaTnMap(){
tnMap.put(0, new BigInteger("0"));
tnMap.put(1, new BigInteger("1"));
for(int i = 2; i < 10001; i++){
tnMap.put(i,tnMap.get(i-1).add(new BigInteger(""+ (4*i-3))));
}
}
private static double getProbabilityHelper(int left, int right, int r, int maxHeight) {
if (left == 0) {
return 1.0;
}
if (r == 0) {
return 0.0;
}
if (right == maxHeight) {
return getProbabilityHelper(left - 1, right, r - 1, maxHeight);
}
return getProbabilityHelper(left - 1, right, r - 1, maxHeight) / 2.0 + getProbabilityHelper(left, right + 1, r - 1, maxHeight) / 2.0;
}
public static void main(String[] argv) {
try {
long startTime = System.currentTimeMillis();
//First initialize the Tn map
initaTnMap();
Reader reader = new FileReader("sample.in");
BufferedReader bufReader = new BufferedReader(reader);
String x = bufReader.readLine();
int numOfTestCases = Integer.parseInt(x);
int count = 0;
File file = new File("sample.out");
FileWriter writer = new FileWriter(file);
for(count =1; count<= numOfTestCases; count++) {
ArrayList firstLine = getIntegerList(bufReader.readLine());
// ArrayList secondLine = getIntegerList(bufReader.readLine());
String output = getProbability(firstLine.get(0), firstLine.get(1), firstLine.get(2))+"";
writer.write("Case #" + count + ": " + output+"\n");
System.out.println("Case #" + count + ": " + output);
}
writer.close();
System.out.println("Total time = " + (System.currentTimeMillis() - startTime));
} catch (Exception e) {
e.printStackTrace();
}
}
private static ArrayList getIntegerList(String s) {
ArrayList intList = new ArrayList();
String[] strArr = s.split(" ");
for (String str : strArr) {
intList.add(Integer.parseInt(str.trim()));
}
return intList;
}
}
