Problem A
https://codejam.withgoogle.com/codejam/contest/8284486/dashboard#s=p0
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
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 .
