# Minimum sum of distance from entrance gate

Assumes we have N position, and 3 entrance gate. For example 10 position:

1--2--3--4--5--6--7--8--9--10

For each entrance gate, there is some people waiting to enter and fill positions, first number is position of gate, associated with chair(front of what chair) and second number is number of people to enter:

5 -> 4

6 -> 2

10 -> 2

If each people seats on chair front of gate, it's cost is 1, for every chair in right or left, the cost increase by 1. What is minimum total sum of cost of people distance to their gates? For example:

10 (number of chairs)

4 5 ( gate front of seat 4 with 5 people)

6 2 (gate front of seat 6 with 2 people)

10 2 (gate front of seat 10 with 2 people)

Minimum cost is 18. The seats cost is is:

4 3 2 1 2 1 2 0 2 1

Zero means nobody sits on chair 9.

For above example number of gate associated with each people is:

1 1 1 1 2 2 1 0 3 3

Another example:

10

8 5

9 1

10 2

Answer is 24 and positions are:

0 0 7 5 4 3 2 1 2 1

And number of gate associated with each chair is:

0 0 2 1 1 1 1 1 3 3

What algorithm do you propose?

• This looks like a standard (if tricky) question in dynamic programming. – Yuval Filmus Aug 3 '17 at 20:00
• How? I can't fit on dynamic programming. How can I break the question to suboptimal parts? – Saber mim Aug 3 '17 at 20:09
• Last one is 25. Kindly change it. – User Not Found Aug 4 '17 at 6:43
• It seems to me that if gate A comes before gate B, and if we have an optimal solution, then we can swap in this solution every person from gate A that is seated on the right of a person from gate B untill all the people are seated in the same order as their initial gate. We only need to find an optimal solution in a much smaller set of candidates. – Gribouillis Aug 4 '17 at 9:13

I will try to give a solution. Tell me if I am mistaking anywhere.

First observation : When we have equal number of chairs and persons the solution is trivial.Ask all the people from 1st gate to fill chairs from start. then next gate starts where 1st gate stopped. I leave it to you to check that this is the optimal solution.

Second observation : We can use dynamic programming here and start removing chairs. (Here I must say I am sorry as my notations might not match with general notations but I will try my best)

Let us denote the first problem as $f(10,(4,5),(6,2),(10,2))$. 10 is number of chairs, rest are ordered pairs stating number of gate and number of people. Now we will start removing chairs. There are 4 cases : chair is removed before 1st gate or between 1st and 2nd gate or 2nd and 3rd gate or after 3rd gate.

Now we can make the following observation : $f(10,(4,5),(6,2),(10,2))=\min[f(9,(3,5),(5,2),(9,2)),f(9,(4,5),(5,2),(9,2)),f(9,(4,5),(6,2),(9,2))]=\min(19,20,18)=18$ (Note that there are 3 cases here as the 4th case doesn't make sense.)

Here as there are 9 people we get the result (of $f$ using the first observation) from here. This is how you can do the problems. There might even be more gates you just have to generalize the function.

Did you understand what I tried to do?

Given a set $G$ of gates, let $C(G)$ be the total cost of people whose position is at most $\max G$ given that $G$ is the set of gates.

For every $i,j$, determine $a(i,j) = \min \{ C(G) : |G| = i, \max G = j \}$. Use dynamic programming to compute $a(i,j)$, and use this array to solve your problem.

(There are some details missing here – this is on purpose.)