6

How to solve this problem ( K burners and N gas cylinders)

 2 years ago
source link: http://codeforces.com/blog/entry/96165
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
By ocelo7, history, 2 weeks ago, In English

This question was asked in a coding test.

There are K burners in the lab and N gas cylinders for the fuel. Each cylinder has a different capacity. Now in each lab K students come to use the K burners. When lab starts all students connect their burner to a cylinder and start the burner. Students can change the cylinder in between themselves and with the cylinder which is idle, exchange takes negligible time. Now find the maximum time possible for which all K burners can burn simultaneously. Exchange can be done only in integral units not fractional. (you can exchange at 1 second or 2 seconds, not at 1.5 seconds).

Constraints: N < 1e5 K < N X[i] < 1e9

Sample Case:

N=3, K=2, X=[3,3,3] Answer = 4

N=5 K=3, X = [10,10,6,9,3] Answer = 12

  • 2 weeks ago, # ^ |

    I think not always e.g. 

    N=3 K=2  X=[1, 1, 5]

    Here the answer is 2.
    I think we have to build K subsets from X such that sum of the minimum subset is maximized. I think we have to do binary search on the answer

    • 2 weeks ago, # ^ |

      Same cylinder may be used to satisfy different students at different times. For example, in a case like following

      N=4, K=3, X = [2,2,2,4]

      the answer would be 3 as the last cylinder can be given once at different times to all 3 students. So forming partitions of X beforehand may not work

2 weeks ago, # |

← Rev. 2 →  

0

pick K burners with least capacity subtracting from them the least of this group you picked repeat this as long as you have at least K burners with capacity > 0, now this seems brute force but I guess there might be an efficient way to do this.

2 weeks ago, # |

← Rev. 10 →  

+7

Rough solution, might be some mistakes somewhere, do let me know if you find any.

Some basic intuition:

  • Each cylinder can clearly burn at most 1 unit / second, so if the burn time is , then the true capacity of a cylinder is .

  • We can exchange cylinders freely at any integer instant of time. Combined with the true capacity constraint this gives us a simple check if a burn time is possible, by just checking if .

(A different way of visualizing this is by considering a grid with rows and columns. We have items, the -th of which can be placed at most times. Additionally we can't place the same item in the same column multiple times.)

This gives us an easy way to check the condition for a given in time.

It might feel like binary search on won't work here because the part might result in being impossible but being possible. Logically such a case is clearly absurd, and mathematically we can prove that case is impossible:

If , it is impossible for to be or larger, since this would immediately contradict the aforementioned equation, so and therefore definitely less than . So the range is monotonic and can be binary searched on yielding an solution.

  • 2 weeks ago, # ^ |

    Agreed.But I have one doubt-

    Consider current , lets remove all so now we left with some burners and cylinders now problem becomes as . Now problem is that if this hold how you can claim that you will always be able to distribute these cylinders among burners for time? Can you provide the proof for this?

    • 2 weeks ago, # ^ |

      Note that "Students can change the cylinder in between themselves and with the cylinder which is idle, exchange takes negligible time. Exchange can be done only in integral units not fractional."

      As far as I understand this means at every integer instant of time I can arbitrarily exchange cylinders. This means in essence I can arbitrarily choose the cylinders I want to use from the -th to -th second as long as I don't use the same cylinder twice in the same second and a cylinder at most times. Since there clearly exists a valid arrangement.

      Formal proof of a general construction which satisfies it:

      We can view this assignment as a grid with rows and columns where the cylinder in the cell (x, y) is the cylinder that will be used by the -th burner between the -th to -th second where clearly no column must use the same cylinder twice.

      We can just fill this grid row by row (say left to right for a given row), using the cylinders one at a time.

      Since the grid has columns and , while filling in this manner we will never have the same cylinder used for the same column multiple times.

      Example taken from another comment for clarity of the construction — , , , where

      By your definition , with the corresponding remaining cells being , or a sequence , which when filled row by row becomes:

      which is a valid arrangement.

      • 2 weeks ago, # ^ |

        Ahh I can see it. Thank you!

2 weeks ago, # |

We choose the largest K elements, and take the sum of rest of the elements and distribute this sum to these K elements maximizing the minimum value of these K elements, and finally return answer as the minimum value of the K elements. (This works in O(N*log(N)))

For example N=5, K=3 X=[10,10,10,11,12] Then the largest K elements are [10,11,12] and we try to maximize the minimum of these K elements by distributing 20(=10+10) in them (this could be done by binary search) here in optimal case the K elements will become [17,18,18] (or any K values which can give the minimum value as 17) and thus the answer will be 17.

Now this approach is just by some intution and I am not sure why exactly will this work but I tried stress testing it with a brute code that reduces the maximum K elements by 1 everytime it's possible and increasing the ans by 1, and probably both these codes doesen't seem to contradict on any test case.

If someone could explain why this should work or should not work please help...

  • 2 weeks ago, # ^ |

    (Your username checks out.)

    I have a constructive proof to show that your approach is correct.

    Let's call the largest cylinders main and the rest spare. The idea is to supplement the main cylinders with spare ones such that each spare one is used for at most one main cylinder (i.e., at most one student) at a time. Suppose the answer is seconds. Then we know, for each main cylinder, how many seconds to supplement it. We will process the main ones in some fixed order, one at a time. Likewise for the spare ones.

    We will consider the time second by second in a loop: , , . For each time unit in the sequence, we schedule the current spare one to supplement the current main one. This way, each spare one will be used for at most two consecutive time intervals (exactly two if the whole interval breaks across the boundary). Since is greater than or equal to the smallest main one, the intervals will not overlap, and so each spare is used for at most one main cylinder at a time. For the rest of the time, the main ones are used. And there you have it.

    The idea is related to a problem where you have to pair colored socks so that each pair has two different colors. A solution exists if and only if each color appears at most times.

2 weeks ago, # |

Could someone in brief explain how the answer for sample1 is 4?

  • 2 weeks ago, # ^ |

    (1-based indexing)

    sec to sec: Student-1 uses cylinder-1, Student-2 uses cylinder-3

    to : Student-1 uses cylinder-1, Student-2 uses cylinder-2

    to : Student-1 uses cylinder-1, Student-2 uses cylinder-2

    to : Student-1 uses cylinder-3, Student-2 uses cylinder-2

    There are other ways of arranging it, but the ans does not exceed .

20 hours ago, # |

Spoiler

4 hours ago, # |

Binary search over answer. For time t check


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK