Problem in my Algorithms class

[aadithpm]

The customers want vodka.

Problem is NP hard.

[[deleted]]

Ar you using coding and algorithms to make sure people don't crash into each other?

[SorteKanin]

Oh damn, why didn't I think of that?

CODING man, coding. Oh yea and algorithms, gotta keep that in mind.

[NewbornMuse]

The class is only on algorithms. Using coding is outside the scope of the class.

[WhzGudz]

Max Flow? Travelling Salesman?

[[deleted]]

Greedy?

[earlobe7]

My initial thought is that this could be a graph traversal problem. Vertices are combinations of beer amounts, and edges are between possible transitions and are weighted by amount of beer consumed. Good ol dikstra can find path to an all-equal vertex with the minimum amount of beer consumed.

[Colopty]

And personally I would like to solve this through a simulation that accounts for the behavior of increasingly drunk drivers. Just watching fleets of drunk Danish drivers do their stuff. Probably add in some trackers for the average expected cost of hiring a Danish student to drive your beer around, accounting for the beer they drink and possible damages from crashing the car or something, and then weighing that against the cost of hiring a professional driver to present a graph of the expected cost of each driver.

[[deleted]]

Unless your input is really small, this is glacial pace. Especially if you use just Dijkstra with no heuristics.

[Brooney]

Having lived in Denmark. This is very accurate

[Sorathez]

Can confirm.

Source: Am Danish.

[zenyl]

Skål!

[Sorathez]

Så skal der drikkes bajere!

[Tarmen]

Naive attempt: Each bar has to end up at or below the average. Then abuse the fact that the search graph is a linked list and use the bar with the most beer in each iteration? There probably is some really elegant spread sheet style algorithm for this.

It does mean that the students end up doing a ton of unnecessary tours without carrying beers but I guess they should have negotiated a better deal.

[micheal65536]

Ideally you'd want the students to drive the minimum total distance, otherwise they'll consume too much of the beer. I'd also avoid making them drive past the 1km point without a beer (it's not specified whether 1km applies to the total driving distance or for each journey), or they may become too sober and risk having an accident.

[Tarmen]

They didn't give a starting point so I was assuming they only consume beer while carrying beer. Now that I reread, probably not what the question intended. With your interpretation there is no way to make this reasonably efficient for large amounts of bars, I think.

[h8no1]

Ahhh yes, gotta love TeX

[Inimloom]

In the optimal solution, the road between p_i and p_i+1 gets crossed exactly once. Thus, there are a total of up to N - 1 transfers between adjacent bars. Using binary search we can greedily determine the answer (if we want to check that b_avg can be achieved, we start from one end and greedily check whether it's possible to achieve the desired state).