Pole (Hackerrank)

Problem Description


Kevin was thinking about telephone poles and came up with an idea for a fun programming challenge. There are n telephone poles ascending a mountain and each pole has a weight and a unique altitude. Our program must move the poles into k number of stacks, but we can only rearrange the poles according to certain criteria:

• Poles can only be moved from higher altitudes to lower altitudes.

• Stacks can only be formed at the initial pole altitudes.

• A stack can consist of at least one pole.

The image below shows how poles can be moved into stacks at altitudes and .





Moving the poles down the mountain also costs money. Moving a pole with weight \$w_i\$ and altitude \$x_i\$ to an altitude of \$x_j\$ where \$(x_i > x_j)\$ costs \$w_i * (x_i - x_j)\$ .


Write a program to determine the least amount of money needed to rearrange the poles into k stacks.


Input Format


The first line of input contains two integers n (the number of poles) and k (the number of stacks needed).


Each of the next n lines include two integers \$x_i\$ indicating the \$i^{th}\$ pole's altitude and \$w_i\$ indicating the \$i^{th}\$ pole's weight. The poles will always be listed from lowest to highest altitude.


Constraints

• \$1

• \$1

Output Format


Print the minimum cost of rearranging the poles into stacks.


Sample Input 1

6 2
10 15
12 17
16 18
18 13
30 10
32 1

Sample Output 1

216

This is my code, but the complexity is very high.

```
import itertools
import math
def ruleAscLen(n, l):
a = [0 for i in range(n + 1)]
k = 1
a[0] = 0
a[1] = n
while k > 0:
x = a[k - 1] + 1
y = a[k] - 1
k -= 1
while x <= y and k < l - 1:
a[k] = x
y -= x
k += 1
a[k] = x + y
if( k< (l-1)):
break;
yield a[:k + 1]

n,k = input().strip().split(' ')
n,k = [int(

This is my code, but the complexity is very high.

How high?

Python has standard formatting conventions, known as PEP8. There are free tools to lint code to those standards (e.g. this online checker, which was my first search result). Use them.

a = [0 for i in range(n + 1)]

This is usually written [0] * (n + 1).

But more importantly, what do the values it stores mean? a is not a descriptive name. There is no comment explaining what it's for, or even explaining what the method ruleAscLen is for.

n,k = [int(n),int(k)]

There's no need to wrap the values in a list just to unwrap them again. n, k = int(n), int(k) would work perfectly well.

mincost = 99999999999999999999999

That's a scary magic number. How do you ensure that it's identical to the value used in the later test? How do you know it's big enough? Is there any reason not to use a self-documenting upper bound such as float("+inf")?

for setList in itertools.permutations(expression):

I think we've found the reason for the slowness. If you find yourself reaching for permutations in a coding challenge you've probably missed an opportunity to decompose the problem.

It's often useful to think about small values of the parameters first.

• When \$k=1\$ the stack must be made at \$x_1\$, so the cost is \$\sum_{i=1}^n w_i (x_i - x_1)\$.

• When \$k=2\$ one stack must be made at \$x_1\$, and the other will be made at \$x_j\$. Obviously there's no point moving a log past a stack, so the cost is \$\sum_{i=1}^{j-1} w_i (x_i - x_1) + \sum_{i=j}^n w_i (x_i - x_j)\$.

There's already a clear decomposition, based on some simple observations:

• Since logs can't go uphill, there must be one stack where the lowest log is, at \$x_1\$.

• There's no point moving a log past a stack, since that is guaranteed to cost more.

• If we're allowed \$k\$ stacks, there's no point having fewer than \$k\$ stacks unless there are fewer than \$k\$ distinct values of \$x_i\$. That would be equivalent to having a stack of zero somewhere, which means that we've moved a log past that stack of zero.

So we have

def stack_cost(xs, ws):
    return sum(ws[i] * (xs[i] - xs[0]) for i in range(len(xs)))

def cost(xs, ws, k):
    return min(stack_cost(xs[0:j], ws[0:j]) + cost(xs[j:], ws[j:], k-1)
               for j in range(1, len(xs)))

as a sketch decomposition. It needs a bit more work to handle special cases correctly and, more importantly, to memoise or otherwise exploit the dynamic programming structure of the problem.

StackExchange Code Review Q#157995, answer score: 3