Tuesday, December 25, 2012

TopCoder SRM 565 Div2 500points: MonstersValley2

I thought this was a very simple problem, but not so :-)
Compressed problem statement: Given a list of monsters with their dread score (scariness score) and the price to be paid for bribing, what is the total minimum bribe to be paid. Monster 1 has to be bribed. You bribe a monster and it becomes a part of your troop. You don't need to bribe monster[i] if the total scariness of the monsters with you exceed the scariness score of monster[i], otherwise you better be wise to bribe.
I get the idea that while maximizing the dread score, we need to minimize the total price. Interesting combination. What algo fits here? Found it - Dynamic programming. Now, it is time to understand, write code and get practice points :-)


  1. Hey this works as well. Can you share ur DP solution.

    class MonstersValley2
    public int minimumPrice(int[] dread, int[] price)
    return minCoinStep(0, 0, 0, dread, price);

    public int minCoinStep(int i,long s,int c,int[] d,int[] p)
    if(i==d.length)return c;

    return minCoinStep(i+1, s+d[i], c+p[i], d, p);

    return Math.min(minCoinStep(i+1, s, c, d, p),
    minCoinStep(i+1, s+d[i], c+p[i], d, p));

  2. Hi Mihir,
    Haven't coded it up yet. Will let you know shortly. Thank you for the comment.