Editorial for CODEX problems?

editorial
, ,
1

It would be very nice if someone could write an editorial or explain their approach for the last two problems of CODEX’18, namely Battle of LAMAK and Sonic And Family Tree. Perhaps the responsible people can take note? @spawncodex @s_k_m @ritesh_cfc121
Taking the liberty of tagging @teja349 here to request him to explain his solution of both the problems. :slight_smile:

2

Battle of LAMAK

Basically, the problem asks to divide the graph into two components by deleting a single edge such that the difference between the sum of ‘powers’ of the components is minimum.

My Approach:

  1. The edge to be deleted must be a bridge, as it must connect two components of the graph.
    Therefore, first we need to identify each of the bridges. Here is a useful article.

  2. Now, if you remove all the bridges, you will be left with several tiny clusters of interconnected vertices. It is easier to imagine than to explain in words. The bridges hold these clusters and form a tree. As these tiny clusters can never be separated by deleting only a single edge, merge them and treat them as a single vertex. The ‘power’ of the merged vertex is the sum of its constituent vertices. Useful article: here.

  3. Now, you have a tree, and you need to find an edge which divides the total ‘power’ into two almost equal groups. This is yet another simple prefix sum problem. Each vertex can store the sum of powers of all the vertices in its subtree. Now, on deleting an edge (u, v), the sum of powers of the resulting components are:

    subtreeSum[v] and totalPower - subtreeSum[v] provided, depth[v] > depth[u]

  4. Answer is

**min(abs(subtreeSum[i] - (totalPower - subtreeSum[i])))**     where, 'i' iterates through each of the vertices.

Here’s my solution. To be honest, it’s a bit messy and I don’t expect anyone to understand from it.

@orlon I have rushed things a bit. Please let me know if you have any doubt.
And, I am also waiting for someone to explain the last problem…

1 Like
3

Thanks a lot for the explanation. :slight_smile: