Greedily add the smallest coin you need.

Another solution (too complicated, I guess, but seems interesting to me :) )

Imagine that we are to check that existing values cover 0 ... v:

we could iterate through them in decreasing order and recalculate v as max(v - c·val_i, val_i - 1) and check if v = 0 in the end.

So, let's do the following dymanic programming:

dp[add][i] -- minimum v we can achieve if the first i values were used and we added add new values.

One can do transitions in O(1) (the best value to add for 0 ... v is or ); .

I personally didn't take part and had no chance to submit my solution, but it seems not hard to prove the correctness of the following solution.
Suppose we have already managed to add coins in such a way that the requirements of the problem are fulfilled and we got all values in range [1,p] and considered first i-1 coins in sorted order. So now there is two cases to be considered.
1.a[i]<=p+1. This means that we can collect all the values until p+c*a[i] inclusive, so we can set i=i+1,p=p+c*a[i]. 2.a[i]>p+1. This means that we need to get all values in range [p+1,a[i]-1]. So it is better choice to add coins starting from value p+1. So here we need to decide how many coins to add starting from p+1 in order get values from required range. So we can make either binary search to find out exact number or write out sum of arithmetic progression and solve linear equation. Let k is that number, so we need to add all [p+1,p+k] coin denominations, like in the first case we will set i=i+1,p=p+sum[p+1;p+k]+(c-1)*sum[p+1;p+k] and we should increase answer by k.

For each row, except the last one you need to ensure that there's no way to place the ship.

The code is:
"""""""" answer = R*(C/W) + W;

if(C%W == 0)

--answer; """"""""""""

That means that you 'hit' all possible squares (C/W),and we multiply it by R. After the '+W' means that we fill correct final squares. the 'If' statement, decrease 'answer' by 1,because if W is multiple of C,then in our 'last' option we have one option instead of two.

Dynamic programming: dp[ind][suff] — expected number bananas you will give monkey where covered ind letters and suffix with length suff is equal to prefix of target with length suff. Then iterate next letter and go to the state — (ind + 1, nsuff), where is nsuff the maximal length of suffix of current string equals to the prefix of target. Also be careful with state (ind, L). L  =  |target|.

But at the start you need to calculate how many bananas you need to bring. This value can be computed greedily (val).

Answer will be: dp[0][0] - val.

Code

Cool. Any advice for how to practice and becoming better for beginners? I thought coming up for a solution for problem 2 and problem 3 was really tough. How to remove this mental block which comes up with every new problem?