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, 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 groups at t = 1 to build a network with least cost at time m.

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