Can anyone help me with Squares from Hackon Feb Contest ?

help
, , , ,
1

Hello friends can someone tell me how to make an approach to this problem ?? @vijju123 @kaushal101 @mohit_negi @taran_1407 @vivek_1998299 @meooow

Here is what I tried but it is giving me TLE error .

Thanks in advance :slight_smile:

2

U could try this:-

Firstly the number of squares of edge length x from a square of edge length n is (n-x+1)^2. (U can easily prove it by a considering a window of size x,slide it horizontally (no.of slides would be (n-x+1)),so no.of squares = (horizontal slide)*vertical slide)

So we have to calculate Summation(x=1 to n) { x*(n-x+1)^2}/(Summation(x=1 to n){(n-x+1)^2)}

And i’m assuming u know how to solve this (just Sn,Sn^2 formulas)

1 Like
3

Thanks for your effort . But I could not convert this into code . Could you help me in this ?

4

After solving that eqn u will just end in some equation in terms of n(ie like n/(3) or similar),if u want i could give u the equation.

5

Following on from @vivek_1998299

E = \frac { \sum x (n-x+1)^2 } { \sum (n-x+1)^2 }

with x = 1 \ldots n.

Substitute y=n-x+1 giving

E = \frac { \sum (n-y+1) y^2 } { \sum y^2 } = \frac {(n+1)\sum y^2 - \sum y^3}{ \sum y^2 }

with y = 1 \ldots n in each sum.

Standard results for sum of squares and sum of cubes:

\sum y^2 = \frac 1 6 n (n+1) (2n+1)
\sum y^3 = \frac 1 4 n^2 (n+1)^2

Substitute the standard results:

E = \frac {\frac 1 6 n (n+1)^2 (2n+1) - \frac 1 4 n^2 (n+1)^2}{\frac 1 6 n (n+1) (2n+1)}

Simplify a bit

E= \frac{2(n+1)(2n+1)-3n(n+1)}{2(2n+1)}= \frac {(n+1)(n+2)}{2(2n+1)}

For the example given in the question where n=3, then we have

E = \frac {4 \times 5 } { 2 \times 7 }

which agrees with the corresponding explanation in the question.

2 Likes
6

Very well explained thank-you mate :slight_smile:

1 Like
7

got it now :slight_smile:

8

I used Wolfram Alpha for the simplification as I was making mistakes.

But, I do have a question for @john_smith_3

Isn’t that formula supposed to cause overflow ? That was the main reason I was reluctant to submit, but I was shocked to see it get AC. I don’t understand why it didn’t cause overflow. Can someone please explain ?

9

The simplest method would be to use cpp_int in c++,BigInteger in java,and …(i dont think i have to say about python)

10

C++ is nice .