**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:

http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n

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! :)

ReplyDeleteThank 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.

ReplyDeleteMany a time, the going gets really tough, but I am going for sure :-)