Procon Junior (Golden Pyramid) Editorial

editorial
, , ,
1

Problem Setter : Ayush Shah

Problem Tester : Aneesh Dogra and Ayush Shah

Editorialist : Ayush Shah

Contest link : GPYRD

Practice link : GPYRD

The problem is related with Pascal’s Triangle.

alt text

The problem statement states that each brick has a value of nCr. As Pascal’s triangle has the same property, we can conclude that the pyramid is Pascal’s Triangle. In every invasion, there are three things that happen.

  1. Some bricks are stolen.

  2. Some bricks magically disappear.

  3. Some bricks are left.

We need to find the number of bricks that magically disappear, hence we calculate this by finding the value of totalInitialValueOnBricks - ValueOnBricksThatWereStolen - ValueOnBricksThatAreLeft

Now, we have the total number of bricks. Looking at the triangle, we notice that each ith row has i bricks.
So, n(n+1)/2 = noOfBricks (where n is total no of rows). Using this, we calculate the number of rows, which will be sqrt((1 + 8 * n) - 1) / 2.
Now, each row of the pyramid will have total value of pow(2, n). Hence, the total initial value on the pyramid can be calculated.

The value of bricks that are stolen will be 2*n-1.

The value of bricks that are left can be calculated by (pow(2, i)-2)/i for each row with outermost value of the brick as Prime (where i is the row number).