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 networkis unique inhas it's own sense.↵
↵
The assigned network consistsproperties.↵
↵
The network is divided into groups; each group is made of 2 types of nodes: Group Owners andSslaves.↵
↵
Each group consists of a group owner and at most d slaves ↵
There can be a maximum of d slaves in a group.↵
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, for a node to declare itself as a group owner, there will be an overhead of cost d, while joining an existing network costs an overhead of weight 1.↵
↵
At time 0, the network is empty.↵
Walid task is to create a network with minimum overhead.↵
↵
Input:↵
------↵
- m : Number of insertions↵
- r : Number of nodes joining the network↵
- d : Maximum number of slaves allowed per group↵
↵
Output:↵
-------↵
Print the number of groupsat t = 1for each t, to build a network with least cost at time m.↵
↵
I think this problem is a DP problem.↵
Any help?↵
Thanks!
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
↵
The assigned network consists
↵
The network is divided into groups; each group is made of 2 types of nodes: Group Owners and
↵
Each group consists of a group owner and at most d slaves
There can be a maximum of d slaves in a group.↵
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, for a node to declare itself as a group owner, there will be an overhead of cost d, while joining an existing network costs an overhead of weight 1.↵
↵
↵
Input:↵
------↵
- m : Number of insertions↵
- r : Number of nodes joining the network↵
- d : Maximum number of slaves allowed per group↵
↵
Output:↵
-------↵
Print the number of groups
↵
I think this problem is a DP problem.↵
Any help?↵
Thanks!
