My first match on Topcoder. i competed in division 2 and solved the 250 and 500 pts problem. Both were easy problem and simple logic was used to solve the problem. 250pt problem was about sorting, lexicographically or length wise. No problems there just define a fucntion for comparison of length and another for lexicographical ordering (use compare functionin string class), just scan through the list and check ith and i+1th string. Takes O(n) time.
500pt problem can be solved just by sorting the sequence and maintaining a marker which says that all the sums from 1 to marker can be obtained using first i numbers of the sorted sequence. Check for this invariant at each step and problem can be solved in O(n logn) for sorting + O(n) for chechking validity time.
I can't solve the third problem. I didn't have enough time. I took long enough to solve these problems. I need to be faster. I got very few points for these because I took way too much time. Now I'll try rest of the problems of i.e. 1000pt and div1 all the problems, in a timed environment.
500pt problem can be solved just by sorting the sequence and maintaining a marker which says that all the sums from 1 to marker can be obtained using first i numbers of the sorted sequence. Check for this invariant at each step and problem can be solved in O(n logn) for sorting + O(n) for chechking validity time.
I can't solve the third problem. I didn't have enough time. I took long enough to solve these problems. I need to be faster. I got very few points for these because I took way too much time. Now I'll try rest of the problems of i.e. 1000pt and div1 all the problems, in a timed environment.
No comments:
Post a Comment