OneWhoKnocks's blog

By OneWhoKnocks, history, 7 weeks ago, In English,

Rick is planning to install n programs on his computer. He has to figure out how many days will it take for him to install n programs. There are a couple of things though which he has to keep in mind:

a) A program can be dependent on other program(s) — it means if program B is dependent on program A. A will have to be installed any day before B will be installed.

b) He can install at most k programs in a day.

We will be given the dependency relationship between the programs. Eg:

n : 6, K : 2

1 -> 5,6

2 -> 5,6

3 -> 4

4 -> 5,6

It will take Rick 3 days to install all the programs ->

(1st day: 1,3) (2nd Day: 2,4) (3rd Day: 5,6)

I thought of converting the above problem to a graph and then use topological sorting. But i am not able to come up with the whole solution to this problem.

Can anyone help me with this? Thanks.

 
 
 
 
  • Vote: I like it
  • -19
  • Vote: I do not like it

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by OneWhoKnocks (previous revision, new revision, compare).

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

(Take this with a grain of salt, as I have not vigorously proved that the proposed sort of the priority queue works.)

Similar to how we can use a priority queue in the solution to finding the lexicographical minimum topological sort, I believe we could sort the PQ by the longest “dependency chain” a particular node leads to. For example, in 0->1, 1->2, 3->2, 2->4, the depth of 0 is 3 (0->1->2->4). This could be precomputed in linear time before performing the actual topsort. The rest of the solution involves doing the topsort with a PQ, taking at most K elements out of the priority queue at a time before adding new programs that no longer have dependencies.

REDACTED: Exchange argument doesn't work. :(

I will leave this here in case someone else wants to try a similar idea, however.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thanks, I'm going to start using "vigorously proved" instead of "rigorously", sounds much cooler :D.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This doesn't work.

    Consider if we have a graph in two parts. One has 6 chained steps. The other has many steps (the top fan) that block a single center step and many steps (the bottom fan) that depend on that same center step.

    We could construct this test case such that k is large, the top fan has k steps and the bottom fan has 8*k-5 steps. Then your algorithm would prioritize emptying the chain first, meaning the center step is pushed until day 3 and completion until day 11. The correct solution is to instead do the k steps in the top fan first, then the center step and the top step of the chain, and finish on day 10.

    The worst bottleneck is not necessarily the longest dependency chain, but can also be caused by the size of k.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      To be able to install a program — all the programs it is dependent on, has to be installed atleast a day before.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Do you have a time limit or limits for n and k?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No. Actually i was asked this problem by a friend. I also came up with the similar idea, as suggested by vamaddur but wasn't able to prove it though. I posted this problem here to discuss various approaches through which we can solve this problem.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Without bounds it's impossible to tell if a problem is solved or not.

      One valid solution would be to take all permutations, check each if it is a valid topological ordering, and calculate the install time greedily. The minimum time encountered is the correct solution.

      However, that solution would be very slow. Naively it could only handle n under 10 or so. Maybe closer to 20 with some smart DP.