Still making up for the 2nd SRM. Easy set. Solved the Level 1 and Level 2 (for the first time), as did most of the others.
Level 1: Passed (~32 mins!)
What the hell was I thinking? Why does my mind go blank when the timer is ticking? This problem did not need more than 10 min (5 to think + 5 to code). It had something to do with anagram-free subsets. Basically, had to find no. of strings with unique signatures (example: signature of both abtgd and bgdat is abdgt ie characters of string in lexicographical order). Instead, I jumped up and started coding some complex hashing method where each string will be hashed to a value based on its characters enabling quick comparison of equal strings. Thinking for a minute would have made me realise that this a Div 2 Level 1 which cannot be this complex. Thankfully, I ran into some problem with my logic. So, I had to step back and look at the problem again. Realised there was a simpler alternative that if I just sorted each string (to reduce them to signatures) and then removed the duplicates from the collection of strings, I would get the solution. Less than 10 lines of code. Done. Felt stupid.
Level 2: Passed (~14 mins)
Wasting time is one thing. Realising it later only makes it worse. Having messed up Level 1, anything other than an easy problem would have been hard to concentrate on. Thankfully, it was a very similar in approach to the Level 2 problem that I messed up in SRM 494. I knew the pitfalls (like messing up row and column indices while modifying row-wise code to work for column-wise) and avoided most of them. Expectedly, I was done in pretty good time. This problem is proof enough that 'practice makes perfect'. The sense of comfort with a known problem and the corresponding coding time have to be seen to be believed.
Level 3 : Clueless
Having solved the first two for the first time and 20+ mins to go, had no choice but to look at this problem. What if I lucked out with some easily identifiable straightforward Dijkstra or BFS? Not to be.
Challenges : None.
Bottomline : Good (Averaging poor Level 1 and great Level 2). Could have been great. Division 1 was within grasp. Rating graph is still moving up.
Lessons learnt :
1.Think and plan before coding.
2.Learn to use predefined functions properly. Avoid wasting time by looking up correct usage.
Post-match rating : 1112 (+49)
Match Editorial : http://www.topcoder.com/wiki/display/tc/SRM+496
No comments:
Post a Comment