Match Editorial

		MATCH EDITORIAL LINKS:
	Room 1 Review Archive   Rookie Review Discuss this match   Problem Set Want to write a feature?

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 floating-point, 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 brute-force 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 branch-and-bound a little more effectively.

It's not possible to simply brute-force 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.

Comment from doeth
Just wanted to note an error in Zorbathut's analysis of the SRM 83 Div 1 1000 pt. problem. Indeed, a brute-force search without any pruning of the search examines 10! possibilities; however this *does* finish in time. Look at both of the room 22 solutions. I've also written up the pure brute-force method myself in Java and got each individual test to finish in less than 5 seconds.