The best location of a path

[kollipsi]

Hi!

I've a problem to solve. I was given some fields divided into ranges. For example, field has 22 units in length, and contains some ranges (I don't know how to describe it well :P).

Except of this field, I was given also a length of a path. This path has to include the field's max ranges. For example, if the length of the path is 3 units, my algorithm should calculate that the path should start at 12th unit. It will contain 3 max possible ranges (99, 98, 97) for this lenght.

On the other hand, if the lenght of the path would be 4, the algorithm should calculate that the beggining of the path should be at 12th unit, and the end of the path - at 16 unit.

I hope you understand what I mean

My problem is that I don't know whether should I choose the bruteforce algorithm to find this optimal location of the given path, as sometimes the calculations can take a lot of time...

If the bruteforce algorithm wouldn't be good in this case, then could you give me a little clue about the solution ?

Best regards,
John.

[Zachm]

This seems like a rather straight forward problem, though some optimizations come to my mind. There exists an O(n) algorithm to solve this problem, where n is the total number of units.

What did you have in mind ? how did you try to solve it by using "brute force" ?

I can give you one hint. Take your example for instance:
What is the difference in between a path of 3 units length, which starts at 14 and ends at 17, and a different path of the same length which starts at 15 and ends in 18 ?

PS. I assume that the maximization problem applies to the "weights" (numbers) you put on the ranges, so if a range of length 3 has a number 30 written on it, and your path covers 2 units of it, does it some up to 20 ? I assumed that it does, and my hint is partially based on this assumption, so correct me if I'm wrong.

Regards,
Zachm

[kollipsi]

[QUOTE=Zachm;1993490]if a range of length 3 has a number 30 written on it, and your path covers 2 units of it, does it some up to 20/QUOTE]

No, it sums up to 60.

By saying "brute-force", I meant checking all possibilities - iterating over the whole field in order to find the path, which contains the maximal values for the given length.

If the length of the path is 3, my program should point 12-15, as this choice gives us 99+98+97 - the maximum value for the 3-units long path.

I hope you understand me

[Zachm]

No, it sums up to 60.

This makes it even simpler.
You can think of your segment as having only ranges which are 1 unit in length by dividing each range with weight w of x units length to x ranges with weight w each.

Think about the question from my first post and post any ideas you might have.

Regards,
Zachm

[kollipsi]

I can give you one hint. Take your example for instance:
What is the difference in between a path of 3 units length, which starts at 14 and ends at 17, and a different path of the same length which starts at 15 and ends in 18 ?

The first one contains 161 value, and the second one contains 164 value... But is it actually a hint ???

[Zachm]

Yes, it is.
Think about how you can sum the value of a path starting at index i, given the sum of the path starting at index i-1, in O(1):
161 = 97 + 32 + 32
164 = 32 + 32 + 100

164 = 161 - 97 + 100

Kind regards,
Zachm

[kollipsi]

Get it, thanks