Looks like it's been some time since I last posted. In fact I probably wouldn't have blogged today if it weren't for an interesting incident that left me with a bit of free time. Details follow...
It's like this - usually on Independence Day or Republic Day, college is closed on both that day as well as the day after. Since 15th August(Independence Day) was yesterday, we fully expected a holiday today. Then we found out that there had been this circular that said that we did in fact have college on the 16th...Bummer, but what the heck.
So I arrived at college today, and saw the most astonishing sight - at least half of my class was standing around downstairs looking vaguely puzzled. I went over and was informed that people were "unsure" whether we had college or not.
Investigations followed, and eventually it turned out that the offending circular had been sent to the Electronics people - not to us. Somehow we'd gotten the idea that it applied to us...
And so we went back home...so here I am blogging away.
The TopCoder Open Qualification Round is tonight, so I've been practicing for that. I've done a couple of practice sets from previous qualifiers to warm up. Hopefully I'll make it past the qualifiers...I seriously doubt that more progress is possible, given my current skill level. Maybe next year...
There's an old saying - "The man that knows how to use a hammer sees nails everywhere." This is sadly true of me - whenever I learn a useful technique, practically every problem I see seems to use it, even if that isn't true...
In fact, just a few minutes ago I did this interesting 1000 pointer from one of the TCCC 2005 Qualifiers. My latest acquisition is breadth-first search - it's something I hadn't really used until now, and I figured it would come in handy in cases where depth-first search might time out. Naturally, I opened it up and saw a solution using BFS...
Well, not exactly. I first thought of BFS while I quickly typed out some of the preliminary stuff - helper functions, parsing the input, that kind of thing. But just as I was about to start up the BFS, I came up with this weird idea. I spent a stupidly long time on that(it would have been simpler than BFS, for one thing), without seeing that it was obviously flawed.
Eventually I came to my senses and went back to coding the BFS. Finished it off and it worked first time - yay!
Then I open up the match editorial and it turns out that DFS won't time out. Yeesh - what a waste - DFS is so much shorter in implementation than BFS...
And now to lunch...hope the TCO goes off well...
Subscribe to:
Post Comments (Atom)
1 comment:
Ahhhh - jacked for no reason. I did the 250 with no trouble at all, but the 750 kept timing out. I figured that DFS couldn't handle input of this size, but it turns out that the bug was somewhere else - in the preliminary stuff where you parse the input and all that...
I haven't actually found the bug, just commented out parts of the code and isolated the bug to the first part - not the DFS...
Update: Been talking to Vishwesh while commenting - he said the approach does time out for really large input. Turns out there's a way to speed it up - hell, I figured it out almost instantly after he said it. Fixed it up a moment ago, and lo and behold - it works!
So it wouldn't have worked out anyway...sad.
Post a Comment