Contest Link:
[Contest][1]
Difficulty:Medium
Explanation
The easiest way to tackle this problem is to look at the stop condition first. It states: “You may stop once the difference between the maximum and minimum likeness of the problems you’ve solved is greater than or equal to the int d.” Because the constraints are low enough, we can just fix the two problems for which the pleasantness between the two problems is large enough by iterating over all possible pairs of problems. If the constraints allow you to fix some important variables, it is usually a good thing to do, since it usually reduces the problem to a much simpler one. In this case, the problem becomes: “find the minimum number of problems needed to solve problems i and j, starting at problem 0 and skipping at most one problem at a time.”
This remaining problem can be solved as follows. Suppose i < j. Then what we have to do is first solve problem 0, from there solve some sequence of problems ending at problem i and finally from there solve some problems ending at problem j. In formula, this is 1+calc(0,i)+calc(i,j). It is easy to see that the number of problems we need to solve to get from problem i to problem j is only dependant on the difference between i and j, so our formula becomes 1+calc(i-0)+calc(j-i). The last thing needed is to determine calc(x). By drawing it on paper, we directly see that the result is (x+1)/2, using integer division.
All this gives us the following algorithm:
int calc(int x) { return (x+1)/2; }
int minNumber(int likeness[],int n, int d) {
int ret=n;
for(int i=0;i<n;++i) for(int j=i+1;j=d)
ret=min(ret,1+calc(i-0)+calc(j-i));
return ret;
}
[1]: http://www.codechef.com/CDCR2015/problems/CDCR15_4