0
$\begingroup$

problem statement for SKICOURSE is this

Farmer John has N hills on his farm (1 <= N <= 1,000), each with an integer elevation in the range 0 .. 100. In the winter, since there is abundant snow on these hills, FJ routinely operates a ski training camp.

Unfortunately, FJ has just found out about a new tax that will be assessed next year on farms used as ski training camps. Upon careful reading of the law, however, he discovers that the official definition of a ski camp requires the difference between the highest and lowest hill on his property to be strictly larger than 17. Therefore, if he shortens his tallest hills and adds mass to increase the height of his shorter hills, FJ can avoid paying the tax as long as the new difference between the highest and lowest hill is at most 17.

If it costs x^2 units of money to change the height of a hill by x units, what is the minimum amount of money FJ will need to pay? FJ can change the height of a hill only once, so the total cost for each hill is the square of the difference between its original and final height. FJ is only willing to change the height of each hill by an integer amount.

and Naive way of doing this problem is like this

The problem can be solved with different approaches. A simple idea is of course brute-force -- try all possible elevations and find the minimum amount. We can try all possible values as follows: try the modification for elevation interval (0,17) then (1,18), (2,19), ..., (83,100). For each elevation interval (i,i+17), we need to calculate the cost for each hill j:

If the elevation of hill j, say hill[j], is in the interval (i,i+17) then there is no cost.
If it is less than i then the cost increases by (i-hill[j])^2
If it is greater than i+17 then the cost increases by (hill[j]-(i+17))^2 

Is there any better way of doing this i mean if limits exceed drastically

$\endgroup$
  • $\begingroup$ Does the sum of elevations remain constant after hills shortening? Also I don't understand your elevation intervals $\endgroup$ – HEKTO Sep 21 '16 at 3:39
1
$\begingroup$

I know, this question is really old, but I will answer it anyway. You can just pick wether you higher the lowest distance or lower the highest one. Then greedy pick the cheaper one until you have your maximum height equal or smaller than 13. In this case, you only need O(max-min-13) steps. Hope it helps.

Just keep in mind that you need to track the former changes because of the quadratic equation.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.