We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. Cut the Tree
  5. Discussions

Cut the Tree

  • ihorfinance
     + 0 comments

    C++ (more at https://github.com/IhorVodko/Hackerrank_solutions , feel free to give a star:) )

    1. All input edges are a graph edges in a random order and vertexes are also in a random order [3,4] vs [4,3], so we create 'treeEdgesPossible' with all possible tree edges(parent to child). We need to know actual tree edges which are directed so we need to choose [3,4] or [4,3]
    2. 'while(!bfsQueue.empty())' is very important part - here we reconstruct our tree using BFS. Main point is that the tree root node is guaranteed to be a first edge at the problem's input. So it is our start point - tree root node
    3. we store our found parent to child tree edges at 'treeEdgesActual'
    4. also very importent optimization logic is at 'values.at(treeEdge.first) += values.at(treeEdge.second);'. Here we prepare values to find the minimum absolut difference.
    5. Finally we simulate a cut at each tree node starting from the root(top). At the previous step we precomputed sub-tree sums at each cut.
    static constexpr int treeRoot = 0;

int cutTheTree(
    std::vector<int> & values,
    std::vector<std::vector<int>> const & graphEdges
){
    using namespace std;
    auto treeEdgesPossible{vector<vector<int>>(values.size(),
        vector<int>{})};
    for_each(begin(graphEdges), end(graphEdges), [&](auto & edge){
        treeEdgesPossible.at(edge.front() - 1).push_back(edge.back() - 1);
        treeEdgesPossible.at(edge.back() - 1).push_back(edge.front() - 1);
    });
    auto bfsQueue{queue<int>{}};
    auto treeEdgesActual{vector<pair<int, int>>{}};
    auto visited{vector<bool>(values.size(), false)};
    bfsQueue.push(treeRoot);
    visited.at(treeRoot) = true;
    while(!bfsQueue.empty()){
        for_each(cbegin(treeEdgesPossible.at(bfsQueue.front())),
            cend(treeEdgesPossible.at(bfsQueue.front())),
            [&](auto & childNode){
                if(visited.at(childNode)){
                    return;
                }
                visited.at(childNode) = true;
                bfsQueue.push(childNode);
                treeEdgesActual.emplace_back(bfsQueue.front(), childNode);
            }
        );
        bfsQueue.pop();
    }
    for_each(crbegin(treeEdgesActual), crend(treeEdgesActual), [&](auto treeEdge){
        values.at(treeEdge.first) += values.at(treeEdge.second);
    });
    auto absDiffMin = numeric_limits<int>::max();
    for_each(cbegin(values) + 1, cend(values), [&](auto const & value){
        absDiffMin = min(absDiffMin, abs(values.front() - 2 * value));
    });
    return absDiffMin;
}