Problem Setter : Ayush Shah
Editorialist : Ayush Shah
Contest link : GPYRD
Practice link : GPYRD
The problem is related with Pascal’s Triangle.
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.
Some bricks are stolen.
Some bricks magically disappear.
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.
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
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).