I competed in SRM 433 on TopCoder this morning. It didn’t go all that well. I solved the first problem quickly, although I could have been a little faster.
The problem was to minimize an expression S = A1*B1 + A2*B2 + … AN*BN, where A and B are vectors of integers and you can re-order A in anyway you choose. The solution is simple, sort both vectors, one in ascending order and one in descending, and then multiply the two vectors together. The small numbers from A end up being multiplied by the large numbers of B, which gives you the smallest possible S. I wasted a bit of time writing an operator to sort in descending order, when I could have just sorted both A and B in ascending and multiplied the values of A starting at 0 through N-1 against B starting at N-1 through to 0.
When I first read the second problem, I realized that it would probably involve using C++’s next_permutation algorithm from the STL and basically bruteforcing an answer. However, I wasted a lot of time trying to understand exactly what was asked in the problem. Frustrated by the problem, I went and looked at the 1000 point problem for a bit. It looked reasonable, but I abandoned it as I felt with the time left, I should probably try to fix my 500 point problem.
When I finally got my 500 point solution to come out with the right answers, it was too slow on the larger test cases. Just as I fixed it to run under the time limit, the contest ended, and I couldn’t submit. If I had have had 30-60 more seconds, I would have had it in. So, now I have a complete solution sitting on my laptop that I didn’t even get to submit. Very frustrating.
I think only one person solved all 3 problems from the competition, so I could have been possibly in the top 50 or so if my second problem was submitted. Unfortunately, I ended up 195th, so my TopCoder standing hardly changed.
My friend Oleg competed in Div 1. The Div 2 500 point problem was the 250 point problem in Div 1. Oleg had similar difficulties with the problem, so his standing also hardly moved.
I’m somewhat happy I didn’t move into Div 1 right now as I would like a chance to redeem myself in Div 2 before moving on. My next chance will be Feb. 7th. Why is it that practice sessions always go better than real competitions? š
Hi… i 've recently joined topcoder… I want to improve my programming skills.. before participating i want to practise such problems more and more. Can u suggest me something on this. As i am new to topcoder dont knw much about it.. is there any way by which i can access problems asked in previous SRMs alongwith their solutions(incase if I am not able solve those problems)? I would b vry grateful to u if u can spend some of ur time answering my question. thank u..
my id is: jkabhishek88@gmail.com
Hi, sorry, didn't see your comment. Yes, you can practice previous SRMs on topcoder. Simply load the competition applet by going to this page: http://www.topcoder.com/tc and expand the Algorithms link and click "Launch Arena". After you log into the applet, you can go to old SRMs by clicking on the Practice Rooms menu. There's thousands available.