4

I came up with the following problem but I am not able to find a solution for it.

Statement:

There are N wine glasses. Each wine glass is assumed to have infinite capacity. The amount of wine in each glass is a positive non-zero integer, where the unit is ml. A move of type-1 is defined as transfer of one ml from glass i to glass j. A move of type-2 is defined as discarding of one ml from glass i. All moves of type-1 have a cost of one. All moves of type-2 have a cost of k. Given the initial amount of wine in each glass, we need to make some moves of the two kinds to ensure that the amount of wine in each glass is a prime number(or zero). Print the minimum cost for such a transformation.

How to tackle this problem? Any ideas for a possible solution?

Guru Prasad
  • 127
  • 1
  • 6

2 Answers2

1

Here's a rough sketch of my idea:

Prime numbers are distributed like this x/ln(x).

Also use the bounds on that page to find where is the closest prime relative to the amount of wine in that glass.

After you find those numbers you can reduce the problem to a graph with edges which have costs which represent values to move from one glass to the other(your type-1 move). And the nodes will be the glasses themselves.

From here on you're left with a graph problem and you have to think about paths of minimum cost in this graph. Your goal is to find a path of minimum cost that leads to a state where all glasses are prime numbers.

If there are glasses which prevent you from doing that, drink them(type-2 move), wine is good for you :)

UPDATE:

I'll write here some of the valid thoughts we discussed in the chat:

  • bipartite matching was mentioned and there's a possibility the problem can be reduced to that
  • you can first get the prime partitions between each 2 glasses(the prime partitions of the sum of each 2 glasses) and these partitions are edges in a graph. you then also add edges for the type-2 moves. You can associate costs somehow and then run a minimum flow algorithm to solve the problem
  • the problem may also be that you need all those edges mentioned above as an optimal solution may not imply taking the optimal prime parititon for each of the glasses
wsdookadr
  • 2,584
  • 1
  • 21
  • 44
  • 1
    I had a similar idea in mind. I thought of summing the initial amount of wine in all the glasses. After that we can find the nearest number lesser than or equal to the sum that can be expressed as a sum of primes.But we need to find a 1-1 correspondence between the amounts in the glasses and the prime numbers that constitute the sum and that mapping must have minimal cost. Not sure about how to do the later part. If you have some ideas, please help me. – Guru Prasad Mar 06 '13 at 14:06
  • You can go for a [discrete knapsack](http://en.wikipedia.org/wiki/Knapsack_problem#0-1_knapsack_problem) to find the primes that amount to the sum you mention above. But you need to invert the costs associated to the items in the knapsack because in your problem, you want to minimize the cost, not maximize it and the classical formulation of knapsack maximizes it :) Then the graph thing I described above would not be needed anymore – wsdookadr Mar 06 '13 at 14:16
  • 1
    Yeah, i could achieve the first part by using dynamic programming. I would like to know how to find the bijection between initial amounts and primes in the sum such that it has minnimum cost. How do i model that into a graph problem? – Guru Prasad Mar 06 '13 at 14:19
  • Well I think the graph is not needed anymore. You can go straight for classic knapsack(with the customizations mentioned above). The costs you can find by finding the nearest primes to the wine amount in each glass. – wsdookadr Mar 06 '13 at 14:21
  • 1
    But i figured out that taking the nearest prime might not always lead to the optimal solution because the interval between prime numbers is an increasing function. I can find an example case where it might not work. – Guru Prasad Mar 06 '13 at 14:23
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/25698/discussion-between-guru-prasad-and-jojo-modjo) – Guru Prasad Mar 06 '13 at 14:34
1

This type of problem is solvable by dynamic programming and is analogous to calculating the minimum edit distance of a string which you can solve using Hirschberg's Algorithm.

There are actually two stages here. First you have to find the candidate prime combinations then calculate the minimum edit distance to each of these candidates. The one with the lowest edit distance is the answer.

For example, let's say you have totals such as 16 14 8. The first step is you have to enumerate each possible prime combination: { 37 0 0 } { 31 7 0 }, etc. Then you use Hirschberg's algorithm to calculate the minimum edit distance to each of these candidates.

Tyler Durden
  • 11,156
  • 9
  • 64
  • 126