Google Kickstart (previously APAC) 2017 Round A

Problem A
https://codejam.withgoogle.com/codejam/contest/8284486/dashboard#s=p0

Solution : http://ideone.com/lPWmS1

Approach : 

Let no, of dots be r rows and c columns. 

For side length=1  => No. of squares = (r-1)*(c-1)

For side length=2  => No. of squares=2*(r-2)*(c-2)

     Because all axis aligned can also be diagonally arranged atmost 1 way

For side length=3  => No. of squares=3*(r-3)*(c-3)

    Because all axis aligned can also be diagonally arranged atmost 2 way

      .

      .

      .

So on till side length=min(r,c)-1

Summing up all : we get 

          
S(n)=((r*(r-1))/2)^2-((r+c)*(r-1)*r*(2r-1))/6+(r*c*(r-1)*r)/2

      

     Modulo can be taken using modular inverse of 2 , 6 .

Problem B:
https://codejam.withgoogle.com/codejam/contest/dashboard?c=8284486#s=p1

Problem C:
https://codejam.withgoogle.com/codejam/contest/dashboard?c=8284486#s=p2