Bugged by Shaping Regions

Some time ago I got through to section 2 of the USACO training gateway. For those not in the know, it's a pretty cool website where you can learn algorithmic programming. They basically give you a few problems to solve, and as you do them, you can go on ahead, learning more stuff along the way. Very nice way to do things...

Anyway, section 2 is basically graph theory, and I was expecting something to do with flood fill algorithms on the first problem - Shaping Regions. What I found instead was a really painful question involving stacking different coloured rectangles on a large rectangular white sheet. Each new rectangle covers something up, and what you have to do at the end of this is to figure out the visible colors and the associated areas.

My first thought on seeing this was - It's too easy! The most obvious technique is to have a matrix(read 2-D array) holding the colors of every unit square on the sheet. Initialize it to the sheet color to begin with, and overwrite the relevant sections with the color of each rectangle as it comes in. At the end of it, just iterate through the matrix and count the entries for each color.

I would have solved it right there - but with newfound wisdom, I looked at the constraints, and ruled out my solution - the sheet size can go up to 10000x10000...that adds up to a whopping 400 MB of memory! No chance there...

So I looked at their hint, and they said: only keep track of the rectangle bounds and chop up rectangles as new ones are added. Since there are only a maximum of 1000 rectangles - this sounded like a good idea. But how to chop up the rectangles? Figured that out yesterday - there's a neat way to do it by imagining that the new rectangle is completely inside the one you're intersecting with. Then just check all the newly formed rectangles and rule them out if they're not viable...Coding this is a little dirty, but I wanted to get it over with. Fate however, had other plans...

Ended up looking through the Java Collections framework for something useful to hold rectangles - started with an ArrayList and ran into a concurrent access exception. Briefly considered using some kind of Set, then gave up and used an array instead. Not as clean, but no concurrent access problems...

I submitted the solution - it barrelled through a couple of test cases. Then along came the killer - and my program produced some crap results...

So now we come to the central dilemma - how the hell do you debug something so damn ugly? I'm at sea...

Last night, after doing the Mumbai Mirror crossword, four words suddenly flashed through my mind - window to viewport transformation - straight out of Computer Graphics. And that gave me a way to use the original idea - why keep the whole sheet in memory? Instead, break it up into smaller sheets and only keep one in memory at a time. Apply the old algorithm in each case. Simplicity itself...

Coded it up last night and submitted - this one was much cleaner than the other one. It ran all the way through 10 test cases(and really fast too - 0.06 seconds was the slowest one), then failed on the 11th one - weirdly enough, it threw an ArrayIndexOutOfBoundsException at an index value of 1000...and there doesn't seem to be any way that my array indices can ever exceed 999...I fixed that up with a couple of half hearted Math.min()s...but the answer to 11 gets screwed up. To top it off, my IDE began doing weird stuff at the same time. At this point I gave up and decided to try my luck the next day.

Haven't really given it a try yet, though I did reinstall the IDE. Maybe I'll do the other 3 problems first - at least I'll learn some graph theory in the process...From what I've read on the net, I'm not the only one who hates Shaping Regions...

What really gets me is that I can't stop thinking about this damn thing - I have this way of spending an infinite amount of time trying to crack something interesting, but this is getting way out of line. It's not even difficult - but the bloody thing just doesn't work in one case!

Hopefully I'll get it to work...there's probably no way to get out of section 2 without finishing it...

The only other interesting piece of news is that my wisdom teeth are starting to give me trouble...one of them on the left side has begun to painfully lacerate the inside of my mouth.

Can't resist ripping off Confucius...here goes, with bad Chinese flavored English too:

Confucius say: If man know he grow wisdom teeth, he never bother to grow wise. This beginning of wisdom, and so he grow wisdom teeth anyway. When man realise this vicious circle, he become truly wise. But only when he have wisdom teeth removed do he become great sage.

Confusing? Try making sense of these Zen koans then...