Sunday, December 2, 2012

Topcoder SRM 562 Div2 250 point problem: Cucumber Market

Problem in short: Kid goes to cucumber market with a budget and chooses k items out of available n items.  He can choose any of all possible k combinations and the return is 'YES' if he can successfully buy any such combination, otherwise 'NO'. The inputs being the array of prices and the number k.

My approach: Initially, I sorted the price array and got totals of k items (0..k, 1..k+1, 2..k+2, so on until n) and found test cases to pass except the 2nd one. I seemed to have gotten lost when I needed to sum up items 0, 2, 3,.. which is basically taking any of the k elements from the n elements.
Now, the problem seemed to need all possible k combination from n items. I thought of looking up how to get all the k combinations and then coding phase time ran out. 

Challenge phase: In this phase, I looked up one solution which had picked up the worst possible set of k items and if that did not satisfy the criterion, it returned 'NO'. This felt rather intimidating. How could I possibly miss this?

Anyway, one thing I need to learn is to figure out how to find all k items from n items.
Found an interesting link in StackOverflow:


  1. Good to see ya blogging again, Raghava, though I'm catching up a little late. Looks like you've your hands full with something similar to ACM UVA probs. Enjoy! :)

  2. Thank you Bhau. Yup, hands full for sure. I remember you each time such a problem is picked. Thank you for introducing UVA, TopCoder to me.
    Many a time, the going gets really tough, but I am going for sure :-)