How to solve this problem?

Revision en1, by WalidMasri, 2016-09-17 12:33:35

Hello everyone, I wrote down a problem statement in class because I was bored. Sadly, I didn't figure out its solution.

Problem: -------- Walid was assigned to build a network, however the required network is unique in it's own sense. The assigned network consists of 2 types of nodes: Group Owners and Slaves. Each group consists of a group owner and at most d slaves. Note: You can't have a group inside a group.

Each second, r nodes will join the network. There will be a total of m insertions. A node can either declare itself as a group owner, or join an existing network if possible. However, creating a GO costs an overhead of weight d, while joining an existing network costs an overhead of weight 1. Walid task is to create the network with minimum weight possible.

Input:

  • n0 : Initial number of nodes
  • m : Number of insertions
  • r : Number of nodes joining the network
  • d : Maximum number of slaves allowed per group

Output:

Print the initial number of groups required to build a network with least cost at time m.

I think this problem is a DP problem. Any help? Thanks!

Tags help, dp, network

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English WalidMasri 2016-09-17 12:45:51 186
en2 English WalidMasri 2016-09-17 12:38:30 199
en1 English WalidMasri 2016-09-17 12:33:35 1165 Initial revision (published)