|
|
|
Hello.
I wonder, if You could simply generate a row of the triangle modulo d.
I know You can do it in O(i^2) by generating subsequent rows modulo d (example for d=2 below), but given the constraints, this is not enough.
I couldn`t figure out, how to do it in a better time, but the resulting drawing is amazingly 'recursive' (for any d) . Can You do it?
1
1 1
1 0 1
1 1 1 1
1 0 0 0 1
1 1 0 0 1 1
1 0 1 0 1 0 1
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 1
1 1 0 0 0 0 0 0 1 1
1 0 1 0 0 0 0 0 1 0 1
1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 0 0 0 1 0 0 0 1
1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
|
|
|
|
Hm.. this is not to answer your question but, your comment that it looks "amazingly recursive" made me look at it closely, and then I thought that pattern of ones and zeroes looked similar to a well-known fractal pattern called Sierpinski's triangle, or Sierpinski's gasket.
For a minute I wondered if you had uncovered some cool new fact, but apparently this is already known: Pascal's triangle (mod 2), which is what you generated above, exactly results in Sierpinski's triangle.
e.g. http://mathworld.wolfram.com/SierpinskiSieve.html
Wow. *I* certainly didn't know it.
|
|
|
|
I did know it... and to be honest, this was my first idea on how to solve the problem.
Luckily, it was immediately followed by the second one: "Hey, this is the 500, not the 1000! Stop it riiiight there and look for a brute force solution that involves less thinking."
Still, I do think that this is a possible way of solving the problem -- and most probably the time will be only (poly)logarithmic in the row number if implemented well.
Ah well, maybe I'll just submit it as a 1000 sometimes :-P |
|
|
|
hmmm....interesting page on Mathworld...
yeah, this is THE triange.
Not only Sierpinski's triangle....
Not ONLY Pascal's triangle MOD 2
NOT ONLY the XOR triangle (1)
BUT ALSO the amazing-OR triangle (2)
(1) Take a row of bools, numbered 1, 2, 3, 4, ....
Xor each with it's neighbour:
1^2, 2^3, 3^4, 4^5, ...
Do it again and again:
1^3, 2^4, 3^5, ... [as (1^2)^(2^3) = 1^(2^2)^3 = 1^3]
1^2^3^4, 2^3^4^5, ...
1^5, 2^6, ....
Now, look at the first column:
1, 1^2, 1^3, 1^2^3^4, 1^5....
let me draw an appears / doesn't appear table:
12345
oxxxx
ooxxx
oxoxx
oooox
oxxxo
Amazing?
Oh, and the formula in the mathworld site is a bit over-complicated.
If you make the rows and columns one-based, it is much easier to see that (r, c) is on iff r|c = r. (nice pictorial proof using the recursivenes)
This means that nCr is odd iff (n+1) | (r+1) == (n+1).
BTW - the amazing list of properties doesn't end there! There are more things you can do...
for instance draw towers of height 1,2,1,4,1,2,1,8,1,2.....
Now, turn it sideways 90 degrees, and on the taller towers (height >= 4) do it again...and again...and again...
Oh, and do this in paint, then flood-fill....only takes one click :D
enought for now |
|
|
|
Ye, very cool - thanks! :-)
|
|
|
![[ TopCoder ]](/i/logo_ghosted_bracket.gif){kind=logo}
Launch Arena Applet
Calendar
