SRM621

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.

Statistical Machine Learning

Last 1 semester I have dabbled in Statistical Machine Learning. My thesis is in a related field. Ideas here need a very clear understanding of linear algebra, probability statistics and optimization and sometimes a bit of complexity theory. Some proofs are very very non intuitive to me at present. Looking at the profile of people working in this field give me self doubt. I think the best strategy is to not think to much about this and just do it! Let us see...I should be optimistic, if they have done it then so can I!

Cards, bags and coins

http://www.codechef.com/APRIL14/problems/ANUCBC/

I have invested almost 2 days in the above problem...but all in vain...I am still getting wrong answer. I believe my algorithm is right and I am not able to catch the error. It is frustrating and I'll stop now. After the contest, I'll make sure the reason for this.

Library Etiquette

Library is wonderful place, full of knowledge and silence. People should learn and respect the silence part(at least) or have the common courtesy to have discussion in the lonely corner. Some students of IITK don't comprehend this or chose to ignore it completely. Feeling Annoyed!

I Hate Real Analysis

This is a rant....Real analysis doesn't make any sense to me....weird things to prove weird things...this sequence subsequence interior point closure really annoyed me today...little I learnt.

Topcoder problem took me whole day to solve! :(

This problem took me almost the entire day to solve, even when I peeked at the solution and read the editorial. Phew!!! Before I could further glorify my failure let me note down here what I learnt.
1) If you are going for a recursive solution always think in terms of recursion tree. What is going to be the input to the recursive function and what is going to be the output.
2) Finding expectation can be broken down as sum of conditional expectation.
3) Be cautious about the base case, what should you return so that recursive function gives right solution.
4) Use bitwise masking for configurations/subsets etc if applicable, constaraints give the hint.
5) Cry some more.

Big integer in C++

I am not a big fan of code ppl write in coding competitions as it looks ugly. Too much is compromised for efficiency. One case in point is using big integer in C++. Some of the problems expect the use of big integer class. As there is no standard big integer in C++, one is left with 2 options. Write your own or copy somebody elses. But as one is allowed to submit only one file, it means everything will be dumped in that single file. I have decided to write my own when need arises. Only including the functions that I need.

Basically, a short way, at least for these competitions is to take every integer as a vector of intgeres (representing digits) and then do the operations as one did in school. Create the result digit by digit. Define operators for comparison on vector<int>.