10538 - Powerful Magic Squares

WanBa · Post by **WanBa** » Wed Jul 30, 2003 6:40 am

Befuddled how to contrive this problem, I bogged down in the mire.
Any one can pull me out ?!!

thanx in advance

little joey · Post by **little joey** » Thu Aug 07, 2003 5:03 pm

Two hours of google + one hour of coding + four hours of debugging = AC P.E.

That was my magic formula.

To the problemsetter:
Very nice problem! Can't imagine that anyone can succeed in a real programming contest (without access to relevant literature).
Please check the judges output, since everybody got Presentation Error upto now, and I know my output is well formatted.

SnapDragon · Post by **SnapDragon** » Thu Aug 07, 2003 6:34 pm

The only way I could see to solve this in a real contest would be to run a search for all the magic squares (eliminating translations/reflections) for an hour or so, put them into a table, and look them up for each example. This still isn't fast enough because of the 15,000 cases, though, so you'd need more optimizations (I used bitmasks and precomputed translations).

It's theoretically possible to do in-contest, anyway.

bugzpodder · Post by **bugzpodder** » Thu Aug 07, 2003 8:09 pm

Rujia Liu has posted something in his site (chinese)... which unfortunately isnt there anymore... but i remember it saying something about solving a system of linear equations and a link to a pdf file (english) about these kinds of perfect magic squares i think it was called

Larry · Post by **Larry** » Thu Aug 07, 2003 8:42 pm

That solution is obvious, because for each line we have:

a + b + c + d + e = k

for some k, and basically, you're just solving tons of those such that it's integer values (from 1-25).. but I'm not that strong in linear alegbra, so I don't know..

but it boils down to a 26 column, 12 row matrix that we can solve..

little joey · Post by **little joey** » Thu Aug 07, 2003 10:40 pm

Actually it's 20 rows and 26 columns, but whichever way you do it, it's a lot of work (both coding and execution time) and you have to be a darn good programmer to get it all right under real contest conditions. I doubt SnapDragons hour or so is enough, but I haven't tried. And once you've generated the perfect magic squares, the real challenge only starts...
There is of course the 'magic carpet method' that generates them almost instantly, but no one can invent that by himself in a few hours (unless you're Srinivasa Ramanujan).

Anyway, it's a great problem and I had a great time researching it.

Larry · Post by **Larry** » Thu Aug 07, 2003 10:56 pm

Oh, ya, that's not what I meant, there's no doubt that if I finished the other 8 or whatever problems, and I have 3 hours left, I don't think I would start on it, because I really don't think I can do it..

of course, it is Snappy, so surely it's possible for *him*.. for the rest of mortals.. well.. I wouldn't even try.. =)

(PS: Ya, even though I read the problem, when I post the message, I forgot about the non-main diagonals anyhow.. ah well.. hence 12.. )

SnapDragon · Post by **SnapDragon** » Wed Aug 13, 2003 7:39 pm

Hehe. I should have explained that that's how I actually did solve the problem. My not-really-optimized search took an hour (though I did remove translations and reflections by fixing a 1 in the upper-left corner, and applying two A > B restrictions to the 4 numbers adjacent to the 1). You need to pick a search order that completes as many rows as early as possible, of course.

But I think that's a little much to expect someone to do in-contest!

Not to mention that I still, um, screwed up my first search. One of my diagonal checks was wrong.