谷歌代码Jam 2013 R1B - Falling Diamonds

本文关键字：Falling Diamonds R1B 2013 代码 Jam 谷歌 | 更新日期: 2023-09-27 18:12:08

昨天的Code Jam有一个题目是Falling Diamonds。全文可以在这里找到，但总结:

  • 钻石沿Y轴下落。
  • 如果一个钻石与另一个钻石点对点碰撞，有50/50的机会它会向右或向左滑动，前提是它没有被阻挡。
  • 如果一个菱形被阻止向一个方向滑动，它将始终向另一个方向滑动。
  • 如果一个钻石在两个方向上都被阻挡，它将停止并停留在阻挡钻石上。
    • 如果钻石碰到地面，它会把自己埋在一半的地方，然后停下来。
  • 钻石的方向永远不会改变，即它会滑动或下沉，但不会翻滚。
  • 目标是找到一个钻石在给定坐标上停留的概率，假设N个钻石落下。

上述要求基本上归结为钻石建造一个接一个更大的金字塔，一次一层。

我只想说，我没能解决这个问题，让谷歌满意。我从问题描述中得到正确的示例，但在实际输入文件上失败。理想情况下，我希望看到一个匹配的输入和正确的输出文件，我可以玩，试图找到我的错误。除此之外，我还欢迎对我的代码进行评论。

通常，我的方法是找出需要多少层才能有一个包含坐标的层。一旦我知道我在看哪个图层，我就可以确定一些与图层和我们想要达到的点相关的值。例如，当这一层是空的时候，金字塔里有多少钻石，有多少钻石可以在另一边堆积起来，然后其余的钻石被迫向另一边移动，有多少钻石必须向同一方向滑动才能到达所需的点，等等。

然后我检查掉落的钻石数量是否使我们无法到达该点(概率为0)，或者保证我们将覆盖该点(概率为1)。挑战是在可能但不保证的中间地带。

对于中间地带，我首先检查我们是否掉落了足够多的东西来填充一侧，并迫使剩余的掉落物向相反的方向滑动。原因是在这种情况下，我们可以保证一定数量的钻石会滑落到每一边，这减少了我们需要担心的滴的数量，并且解决了当一侧满时概率变化的问题。例如:如果掉落12颗钻石，则外层的每一面都有2颗或更多的钻石，无论给定的一面有2颗，3颗还是4颗，都取决于只掉落2颗钻石的结果，而不是落在这一层的所有6颗钻石。

一旦我知道了有多少雨滴与成功有关，以及为了覆盖到点必须以相同的方式打破的数量，我就会计算必要数量或更多的雨滴以相同的方式打破的概率。

正如我所说，我可以解决问题描述中的示例，但我没有得到输入文件的正确输出。不幸的是，我没有找到任何东西告诉我正确的输出是什么，以便我可以将它与我得到的进行比较。以下是我的代码(自比赛结束以来，我花了相当多的时间试图调整它以获得成功，并添加注释以防止自己迷失方向):

protected string Solve(string Line)
{
    string[] Inputs = Line.Split();
    int N = int.Parse(Inputs[0]);
    int X = int.Parse(Inputs[1]);
    int Y = int.Parse(Inputs[2]);
    int AbsX = X >= 0 ? X : -X;
    int SlideCount = AbsX + Y;  //number that have to stack up on one side of desired layer in order to force the remaining drops to slide the other way.
    int LayerCount = (SlideCount << 1) | 1; //Layer is full when both sides have reached slidecount, and one more drops
    int Layer = SlideCount >> 1; //Zero based Index of the layer is 1/2 the slide count
    int TotalLayerEmpty = ((Layer * Layer) << 1) - Layer; //Total number of drops required to fill the layer below the desired layer
    int LayerDrops = N - TotalLayerEmpty; //how many will drop in this layer
    int MinForTarget; //Min number that have to be in the layer to hit the target location, i.e. all fall to correct side
    int TargetCovered; //Min number that have to be in the layer to guarantee the target is covered
    if (AbsX == 0)
    {//if target X is 0 we need the layer to be full for coverage (top one would slide off until both sides were full)
        MinForTarget = TargetCovered = LayerCount;
    }
    else
    {
        MinForTarget = Y + 1; //Need Y + 1 to hit an altitude of Y
        TargetCovered = MinForTarget + SlideCount; //Min number that have to be in the layer to guarantee the target is covered
    }
    if (LayerDrops >= TargetCovered)
    {//if we have enough dropping to guarantee the target is covered, probability is 1
        return "1.0";
    }
    else if (LayerDrops < MinForTarget)
    {//if we do not have enough dropping to reach the target under any scenario, probability is 0
        return "0.0";
    }
    else
    {//We have enough dropping that reaching the target is possible, but not guaranteed
        int BalancedDrops = LayerDrops > SlideCount ? LayerDrops - SlideCount : 0; //guaranteed to have this many on each side
        int CriticalDrops = LayerDrops - (BalancedDrops << 1);//the number of drops relevant to the probablity of success
        int NumToSucceed = MinForTarget - BalancedDrops;//How many must break our way for success
        double SuccessProb = 0;//Probability that the number of diamonds sliding the same way is between NumToSucceed and CriticalDrops
        double ProbI;
        for (int I = NumToSucceed; I <= CriticalDrops; I++)
        {
            ProbI = Math.Pow(0.5, I); //Probability that I diamonds will slide the same way
            SuccessProb += ProbI;
        }
        return SuccessProb.ToString();
    }
}

谷歌代码Jam 2013 R1B - Falling Diamonds

你的一般方法似乎适合这个问题，尽管最后一个概率的计算并不完全正确。

让我描述一下我是如何解决这个问题的。我们在看金字塔。这些金字塔可以根据金字塔有多少钻石来划分一层。1层的金字塔中只有1钻石。2层的金字塔中有1 + 2 + 3钻石。3层的金字塔有1 + 2 + 3 + 4 + 5钻石。n层的金字塔有1 + 2 + 3 + ... + 2*n-1颗钻石，等于(2 * n - 1) * n。

在此基础上，我们可以用给定数量的钻石计算出最大金字塔的层数:

layer = floor( ( sqrt( 1 + 8 * diamonds ) + 1 ) / 4 )

和建造这个金字塔不需要的钻石的数量。这些钻石将开始填充下一个更大的金字塔:

overflow = diamonds - layer * ( 2 * layer - 1 )

我们现在可以看到以下内容:

  • 如果点在layer层内，它将被覆盖，所以p = 1.0。
  • 如果点不在layer + 1层内(即下一个更大的金字塔)，它将不会被覆盖，所以p = 0.0。
  • 如果点在layer + 1层内，它可能被覆盖，所以0 <= p <= 1。

因为我们只需要解决最后一个问题，我们可以把问题表述简化一点:已知三角形的两条边，r和l。每一方都有一个固定的容量，即它可以携带的最大钻石数量。一个构型(nr, nl)的概率是多少，其中nr表示右边的菱形，nl表示左边的菱形，nr + nl = overflow。

这个概率可以用伯努利轨迹计算:

P( nr ) = binomial_coefficient( overflow, k ) * pow( 0.5, overflow )

然而，在一种情况下，这将失败:如果一侧完全被方块填满，概率就会改变。现在，钻石落在完全填充的一面的概率是0，而落在另一面的概率是1。

假设如下情况:每边最多可以拿4个方块，剩下6个方块。现在有趣的情况是P( 2 )，因为在这种情况下，左侧将取4个方块。

6个钻石如何掉落的例子。r代表决策向右，而l代表向左:

  • l r l r l l =>对于每个菱形，每条边的概率为0.5。这种情况与以前的情况没有什么不同。这种情况的概率是pow( 0.5, 6 )。有4个不同的案例(rllllr, lrlllr, llrllr, lllrlr)。这样的案例有10个。情况的数量是一个元素可以从5中选择的方法的数量:binomial_coefficient( 5, 2 ) = 10
  • l r l l l r =>最后一个菱形会落在右边，因为左边是满的。最后一个概率右边是1左边是0。这种情况的概率是pow( 0.5, 5 )。有四种不同的情况:binomial_coefficient( 4, 1 ) = 4
  • l l l l r r =>最后两颗钻石会落在右边，因为左边是满的。最后两个概率右边是1左边是0。这种情况的概率是pow( 0.5, 4 )。这样的情况只有一个，因为binomial_coefficient( 3, 0 ) = 1 .

一般算法是假设最后一个0, 1, 2, 3, ..., nr元素将不可避免地移到右边，然后计算每种情况的概率(最后一个0, 1, 2, 3, ..., nr的概率将是1)，并将每个概率乘以最后一个0, 1, 2, 3, ..., nr的概率是1的不同情况的数量。

见下面的代码。p表示nr菱形在右边而左边满了的概率:

p = 0.0
for i in range( nr + 1 ):
    p += pow( 0.5, overflow - i ) * binomial_coefficient( overflow - i - 1, nr - i )

现在我们可以计算每个单独组合(nr, nl)的概率，我们可以简单地将nr > k的所有情况相加，其中k为所需点仍然覆盖的一侧的最小菱形数。

请参阅我用于此问题的完整python代码:https://github.com/frececroka/codejam-2013-falling-diamonds/blob/master/app.py

你的假设过于简单了。您可以下载使用我的解决方案计算的大型数据集的正确答案:

http://pastebin.com/b6xVhp9U

你必须计算出占据你兴趣点的所有可能的方块组合。为了做到这一点，我使用了这个公式:

https://math.stackexchange.com/a/382123/32707

你基本上必须:

  • 计算金字塔的高度(即计算固定钻石)
  • 计算可以向左或向右自由移动的钻石的数量
  • 计算概率(用二项系数和)

对于后者和Y点，您可以应用该公式来计算概率。

也不要担心，如果你不能解决这个问题，因为它是相当困难的。如果你想要我在PHP中的解决方案，它是:

请注意，您必须计算该点是在固定金字塔内还是在固定金字塔外，您还必须做其他小检查。

<?php

set_time_limit(0);

$data = file('2bl.in',FILE_IGNORE_NEW_LINES);

$number = array_shift($data);
for( $i=0;$i<$number;$i++ ) {
    $firstLine = array_shift($data);
    $firstLine = explode(' ',$firstLine);

    $s = $firstLine[0];
    $x = $firstLine[1];
    $y = $firstLine[2];
    $s = calcCase( $s,$x,$y  );
    appendResult($i+1,$s);
}

function calcCase($s,$x,$y) {
    echo "S: [$s] P($x,$y)'n<br>";
    $realH = round(calcH($s),1);
    echo "RealHeight [$realH] ";
    $h = floor($realH);
    if (isEven($h))
        $h--;
    $exactDiamonds = progression($h);
    movableDiamonds($s,$h,$exactDiamonds,$movableDiamonds,$unfullyLevel);   

    $widthLevelPoint = $h-$y;

    $spacesX =  abs($x) - $widthLevelPoint;
    $isFull = (int)isFull($s,$exactDiamonds);

    echo "Diamonds: [$s], isFull [$isFull], Height: [$h], exactDiamonds [$exactDiamonds], movableDiamonds [$movableDiamonds], unfullyLevel [$unfullyLevel] <br> 
         widthlevel [$widthLevelPoint], 
         distance from pyramid (horizontal) [$spacesX]<br> ";

    if ($spacesX>1)
        return '0.0';
    $pointHeight = $y+1;

    if ($x==0 && $pointHeight > $h) {
        return '0.0';
    }

    if ($movableDiamonds==0) { 
        echo 'Fixed pyramid';
        if ( $y<=$h && abs($x) <= $widthLevelPoint )    
            return '1.0';
        else
            return '0.0';
    } 

    if ( !$isFull ) {
        echo "Pyramid Not Full ";

        if ($spacesX>0)
            return '0.0';

        if ($unfullyLevel == $widthLevelPoint)  
            return '0.5';

        else if ($unfullyLevel > $widthLevelPoint)
            return '0.0';

        else
            return '1.0';
    }

    echo "Pyramid full";

    if ($spacesX<=0)
        return '1.0';
    if ($movableDiamonds==0)
        return '0.0';


    if ( $movableDiamonds > ($h+1) ) {
        $otherDiamonds = $movableDiamonds - ($h+1);
        if ( $otherDiamonds - $pointHeight >= 0  ) {
            return '1.0';
        }

    }
    $totalWays = totalWays($movableDiamonds);
    $goodWays = goodWays($pointHeight,$movableDiamonds,$totalWays);
    echo "<br>GoodWays: [$goodWays], totalWays: [$totalWays]<br>";

    return sprintf("%1.7f",$goodWays / $totalWays);
}

function goodWays($pointHeight,$movableDiamonds,$totalWays) {

    echo "<br>Altezza punto [$pointHeight] ";
    if ($pointHeight>$movableDiamonds)
        return 0;

    if ( $pointHeight == $movableDiamonds )
        return 1;
    $good = sumsOfBinomial( $movableDiamonds, $pointHeight );
    return $good;
}
function totalWays($diamonds) {
    return pow(2,$diamonds);    
}

function sumsOfBinomial( $n, $k ) {
    $sum = 1;   //> Last element (n;n)
    for($i=$k;$i<($n);$i++) {
        $bc =  binomial_coeff($n,$i);
        //echo "<br>Binomial Coeff ($n;$i): [$bc] ";
        $sum += $bc;
    }
    return $sum;
}

// calculate binomial coefficient
function binomial_coeff($n, $k) {
  $j = $res = 1;
  if($k < 0 || $k > $n)
     return 0;
  if(($n - $k) < $k)
     $k = $n - $k;
  while($j <= $k) {
    $res = bcmul($res, $n--);
    $res = bcdiv($res, $j++);
  }
  return $res;
}
function isEven($n) {
    return !($n&1); 
}
function isFull($s,$exact) {
    return ($exact <= $s);
}
function movableDiamonds($s,$h,$exact,&$movableDiamonds,&$level) {
    $baseWidth = $h;
    $level=$baseWidth;
    //> Full pyramid
    if ( isFull($s,$exact) ) {
        $movableDiamonds = ( $s-$exact );
        return;
    }

    $movableDiamonds = $s;
    while( $level ) {
        //echo "<br> movable [$movableDiamonds] removing [$level] <br>" ;
        if ($level > $movableDiamonds)  
            break;
        $movableDiamonds = $movableDiamonds-$level;
        $level--;
        if ($movableDiamonds<=0)
            break;
    }
    return  $movableDiamonds;
}

function progression($n) {
    return (1/2 * $n *(1+$n) );
}
function calcH($s) {
    if ($s<=3)
        return 1;
    $sqrt = sqrt(1+(4*2*$s));
    //echo "Sqrt: [$sqrt] ";
    return ( $sqrt-1 ) / 2;
}


function appendResult($caseNumber,$string) {
    static $first = true;
    //> Cleaning file
    if ($first) {
        file_put_contents('result.out','');
        $first=false;
    }
    $to = "Case #{$caseNumber}: {$string}";
    file_put_contents( 'result.out' ,$to."'n",FILE_APPEND); 
    echo $to.'<br>';
}
相关文章：