Algorithm problem [closed]

Closed. This question is off-topic. It is not currently accepting answers.

---

Want to improve this question? Update the question so it's on-topic for Stack Overflow.

Closed 11 years ago.

Improve this question

https://liahen.ksp.sk/ provides some trainig problems for competitions. But they do not have solutions with them. So I would like to ask you how to solve this, since I am trying to solve it for hours and still nothing.

Problem: We have s开发者_如何转开发ome line of length L kilometers. Some person stands in the middle of this line. We have list with two numbers: x, y and z - y is the time in seconds when z crates will fall to the x-th kilometer of the road. Person can stay or move one km to right or left each second. To catch crates, person must be on place where they will fall exactly in the second they are intended to fall.

Point of the algorithm is to find a way to save maximal number of crates.

---

I'd do this as a dp problem: for each time, for each place you can stand, store the maximum number of crates you can have caught.

Runtime would be O(L * timesteps)

EDIT: if L is very large compared to the number of drop points you can get away with storing only information at the drop points, saving a bit on the performance:

• for each drop point store how far it is to the left and right neighbor, and a buffer indicating crates collected at this point at time t-i for i from 0 to the maximum distance to a neighbor.
• at each time step, for each drop point, fetch the possible crates collected from each neighbors at time t-distance, and select the best value.
• add the number of crates dropped at this point, if any.

This algorithm runs in O(droppoints*timesteps), but uses O(L) space.

---

You can solve this problem using dynamic programming. Here's the basic recursive relationship that you need to solve.

saved[y][x] = max(saved[y-1][x-1],saved[y-1][x+1],saved[y-1][x])+crates[y][x]

• crates[y][x] : the # crates that fall at time y at position x. You create this array from your input data.
• saved[y][x] : the maximum number of crates that you have saved so far winding up at time y being in position x.

The equation is based on the fact that at time y-1 ( 1 time step before ), you can only be at position x+1 or x-1, or x (stayed in the same place), so look at both options and pick the one that gives you the most crates saved, and then add the crates saved since you are now at position x at time y ( i.e. crates[y][x] )

Say you start at x = 0, and time y = 0. Then saved[0][x] = 0 ( assuming that crates start to fall at time y > 0 ), and then you can do DP using the above equation.

Your final answer is to find the maximum value of saved[y][x].