April 27, 2002 Match summary Saturday's 200pt problem had a reasonable point value on it  it was straightforward and basically laid out in the description. Nothing clever, just do what they said. I suppose some people might have made mistakes with floatingpoint, but if you read the notes it turned out that it was simple standard integer division. Do the steps and return the answer, about as simple as it gets. Look at basically anybody in the first room for a good solution  dmwright's is perhaps better laid out than some (though slightly slower to write). The 550, on the other hand, was messy and hateful. Look at five people and you'll find five completely different totally unreadable solutions. I'm rather proud of mine, as ugly as it is  I set up an enormous 2001x2001 array representing the entire grid, then fill in the edges using bitmasks. I have a small array of each combination of edges between the different bounding boxes (the first four bits are box 1, the second four are box 2) and I simply count how many times each combination shows up. If it's more than 1, there's a segment there. If it isn't, there isn't. I also count the intersection points themselves  if there isn't a segment, that distinguishes between POINT and POINTS. Finally, if none of those yield results, I fill in the entire array that one polygon occupies, then test to see how much overlapping area they have. If it's equal to either polygon's total area, then they're nested. Unfortunately I forgot to clear the array causing it to fail in systest, but without that problem this is probably one of the easiest ways to conceptualize it. Anything else will involve an enormous number of if statements with an equally enormous number of potential typos, leading to the dismal success ratio (there are a grand total of 12 working solutions in the entire competition.) The 1000 wasn't a lot more pleasant  in effect, it's a basic bruteforce search, but if at any point the equation ends up in a form where it can't work, you drop it and try again. I'd recommend picking one end to start from then just trying all the possibilities from there and moving on. Keep an array of which digits you've used and which letters mean what, and that's basically all. However, the problem's complexity kept most people from completing it. Note that which end you start from changes your approach slightly  if you start from the smaller side, it's a bit easier to deal with carries, where if you start from the larger side, you can use branchandbound a little more effectively. It's not possible to simply bruteforce it, as that would be up to 10! tests, which doesn't stand a chance of executing in time. In C++, a simple permutation loop without anything in it takes 1.2 seconds at that point, and obviously the test inside would be slow enough to completely time out.

