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 has its own properties.

The network is divided into groups; each group is made of 2 types of nodes: Group Owners and 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.

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

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

Is there any good tutorials on persistent data structures?

I've seen many solutions for this problem, some uses bitwise trick and some used graphs and dfs which i don't really get how can it be applied to such a problem.

Would any of you mind explaining his approach?

Many Thanks.

Hello everyone!

Having found the SCC of a directed graph G, how can I contract each SCC to a single node?

Thanks.

Hello everyone

I recently joined the competitive programming world and i really loved it.

Therefore, i started learning algorithms and data structures so i can solve more and more problems and get that beautiful green AC.

However, my issue revolves about having a limited scope of the wider world of algorithms, hence, I don't know what to learn next.

My Request: Is there anyone in codeforces whom i can talk with, that is willing to help me by tellinge what to learn next? And I'll surely tell him everything about my progress and knowledge.

Thank you.

Hello codeforces!

Recently i was searching for a good explanation of Tarjan Strongly connected components algorithm but i failed to understand the concept and the algorithm. can anyone help me by providing a good explanation of this algorithm or providing a useful link?

One more question: Does tarjan algorithm works on undirected graph for finding biconnected components?

Thanks!

Hello everyone!

i was trying to solve this problem , but the modulo behavior caused me to get WA as a verdict.

When computing the formula , once n is reduced by modulo, the prime divisors (p1,p2... pk) wont remain divisors of n, hence, getting a non-integer result.

MORE Explanation : Given (n%k)/ m, where m is a divisor of n ... if i performed n%k then divided by m, i will get a non-integer result.

What can i do to avoid such problem?

Thanks!

Hello codeforces!

I recently got interested in the LCA problem and read a lot about it. I learned three methods for computing LCA queries:

• Using Sparse Table (But i didn't like that approach since the 2-d array gives me outofmemory exception when number of nodes is 10^5 )

• Transforming my rooted tree into an array and apply segment trees on it. This method works well for me but takes much too long to code.

• Using Union-Find data structure.

Which approach do you use and why? Thanks!

Hello CodeForces!

I have the following problem : Given a rooted tree, i have 2 types of queries: 1 q : Mark the Node q colored/uncolored. (Initially they are all uncolored). 2 p : Get the sum of the colored nodes in the p-subtree.

How can i solve this problem using segmentTrees? I couldn't figure out the part where i need to transform my rooted tree into an array, how to do that as well?

Thanks!