Nitpy-TnP-week-05 -TREES(EDITORIAL)
Difference between en32 and en33, changed 0 character(s)
#### B. Binary-tree-array: ↵

<spoiler summary="Tutorial">↵
B. Binary-tree-array:↵
---------------------↵

Just convert the string into binary notation.<br>↵
ie:L to 0 and R to 1.<br>↵
let that value be b in decimal.<br>↵
then the answer will be `2^n+b`.↵
<br>where 2^n is the position of first node at height n, and b is distance between first node at height n and position of node having sequence of traversal(from root 1) as binary representation of b.↵
<br>note: hidden node will be at height n.↵
<br>Overall complexity: O(29*q) worst case.<br>↵

</spoiler>↵


<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

int main()↵
{↵
    int h, q;↵
    cin >> h >> q;↵
    while (q--)↵
    {↵
        int n;↵
        cin >> n;↵
        string s;↵
        cin >> s;↵
        string m = "";↵
        for (int i = 0; i < n; i++)↵
        {↵
            if (s[i] == 'L')↵
                m += "0";↵
            else↵
                m += "1";↵
        }↵
        int ans = stoi(m,0,2);↵
        ans = (1 << n) | (ans);↵
        printf("%d\n", ans);↵
    }↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵


<spoiler summary="alternative">↵
Left child of a node at ith position in array will be at 2*i th position.↵
<br> similarly right child will be at 2*i+1 position in same array.↵
<br>So, using  the given left or right information, we can recursively find position of hidden node, starting from i=1.↵
<br>Overall complexity: O(29*q) worst case.↵
<br>↵
</spoiler>↵


<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

int main()↵
{↵
    int h, q;↵
    cin >> h >> q;↵
    while (q--)↵
    {↵
        int n;↵
        cin >> n;↵
        string s;↵
        cin >> s;↵
        int ans=1;↵
        for (int i = 0; i < n; i++)↵
        {↵
            if (s[i] == 'L')↵
                ans=2*ans;↵
            else↵
                ans=2*ans+1;↵
        }↵
        printf("%d\n", ans);↵
    }↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵

#### C. Edge-vs-node-mapping: ↵

<spoiler summary="Tutorial">↵
C. Edge-vs-node-mapping:↵
------------------------↵

Tree has one property that all the nodes except root node will have exactly one parent node.↵
<br>So for all node except root node, we can map the node with edge connecting it with it's parent node.↵
<br>This can be done with dfs with assuming some random node root.↵
<br>Overall complexity: O(n).<br>↵

</spoiler>↵


<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

void dfs(int root, int par, vector<int> arr[])↵
{↵
    for (auto &x : arr[root])↵
    {↵
        if (x == par)↵
            continue;↵

        printf("%d %d %d\n", x, root, x); // root is parent of x, so mapping them↵
        dfs(x, root, arr);↵
    }↵
}↵

int main()↵
{↵
    int n;↵
    scanf("%d", &n);↵
    vector<int> arr[n + 1];↵
    for (int i = 1; i <= n - 1; i++)↵
    {↵
        int a, b;↵
        scanf("%d %d", &a, &b);↵
        arr[a].push_back(b);↵
        arr[b].push_back(a);↵
    }↵
    dfs(1, -1, arr); // choosing 1 as root↵
    return 0;↵
}↵
~~~~~↵
</spoiler>↵


<spoiler summary="alternative">↵
Same logic is used , but instead of doing dfs, we can do bottom up approach from leaf nodes to parent, as shown in below code.↵
<br>Overall complexity: O(n).<br>↵

</spoiler>↵


<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

int main()↵
{↵
    int n;↵
    scanf("%d",&n);↵
    vector<set<int>> arr(n + 1); ↵
    for (int i = 1; i <= n - 1; i++)↵
    {↵
        int a, b;↵
        scanf("%d %d", &a, &b);↵
        arr[a].insert(b);↵
        arr[b].insert(a);↵
    }↵

    queue<int> leaf;↵

    for (int i = 1; i <= n; i++)↵
        if (arr[i].size() == 1)↵
            leaf.push(i);↵

    while (leaf.size() != 0)↵
    {↵
        int x = leaf.front();↵
        leaf.pop();↵

        if (x == 1)↵
            continue;↵

        int par = *arr[x].begin();↵
        printf("%d %d %d\n", x, par, x);↵
        arr[par].erase(x);↵
        if (arr[par].size() == 1)↵
            leaf.push(par);↵
    }↵

    return 0;↵
}↵
~~~~~↵
</spoiler>↵

#### D. MAX-MIN: ↵

<spoiler summary="Tutorial">↵
B. MAX-MIN:↵
---------------------↵

It is just an implementation problem.↵
<br>↵
Have set of current leaf nodes in queue. And may use adjacency set representation instead of adjacency vector, so that edges can be added and removed in O(logn) worst case.<br>↵
<br> For each leaf node in current tree(from queue), just remove edges between it and it's parent, and add the parent to the queue if it became leaf for next iteration.↵
<br>ie:it will have only one edge(ie:adj[par].size()==1).<br>↵
<br> Do this upto k iterations and then do dfs on final tree to find the ans.↵
<br>ie:for each node, the maximum distance leaf node length will be 1+(max(maximum distance length of all immediate child nodes)), similarly minimum distance leaf length will be 1+(min(minimum distance length of all immediate child nodes)).↵
<br>Overall complexity: O(n*log(n)) worst case.↵
<br>where dfs takes O(n) but adjacency set insertion and leaf removal will take O(n*log(n)) worst case.  ↵
<br>↵
</spoiler>↵


<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

pair<int, int> dfs(vector<set<int>> &arr, int root, int par)↵
{↵

  int maxm = 0, minm = INT_MAX;↵
  for (auto &x : arr[root])↵
  {↵
    if (x == par)↵
      continue;↵

    pair<int, int> p = dfs(arr, x, root); // getting maxm and minm value of child node.↵
    maxm = max(maxm, p.first + 1);        // updating maxm to max of all child node maxm values.↵
    minm = min(minm, p.second + 1);       // updating minm to min of all child node minm values,↵
  }↵
  if (maxm == 0)↵
    minm = 0; // for leaf node.↵
  return {maxm, minm};↵
}↵

int main()↵
{↵
  int n, k;↵
  scanf("%d %d", &n, &k);↵
  vector<set<int>> arr(n + 1); // adjacency set representation for easy removal of edges.↵
  for (int i = 1; i <= n - 1; i++)↵
  {↵
    int a, b;↵
    scanf("%d %d", &a, &b);↵
    arr[a].insert(b);↵
    arr[b].insert(a);↵
  }↵

  queue<int> leaf;↵

  for (int i = 1; i <= n; i++)↵
    if (arr[i].size() == 1)↵
      leaf.push(i); //inserting first set of leaf nodes.↵

  int cnt = 0, m = 0, c = 0;↵
  while (leaf.size() != 0) // leaf nodes of current iteration tree and next iteration tree stored in same queue, but next iteration nodes present at the end.↵
  {↵
    if (c == m)↵
      c += leaf.size(), cnt += 1; // to differentiate between current tree and next tree↵
    m++;                          // cnt get incremented after each complete iteration.↵

    if (cnt > k) // cnt stores number of complete iteration happened so far.↵
      break;↵

    int x = leaf.front();↵
    leaf.pop();↵

    assert(x != 1 || leaf.size() == 0);↵
    if (x == 1) // reached root node, and after this, answer is always 0.↵
    {↵
      printf("0\n");↵
      return 0;↵
    }↵
    assert(arr[x].size() == 1);↵

    int par = *arr[x].begin(); // parent of current leaf node↵

    arr[par].erase(x); // removing edge between current leaf node from current tree.↵
    if (arr[par].size() == 1)↵
      leaf.push(par); // if parent node became new leaf node, then add it to the end of queue.↵
  }↵

  pair<int, int> p = dfs(arr, 1, -1); // to find ans in final tree.↵

  cout << p.first - p.second << "\n";↵

  return 0;↵
}↵

~~~~~↵
</spoiler>↵


<spoiler summary="alternative">↵
<br>↵
it can also be done without doing any of k iterations but just one dfs from initial tree, and no removal of edges.↵
<br>the maximum in final tree will be just `maximum length in initial tree - maximum length in final tree`.↵
<br>But finding minimum in final tree will need some modification, cause those nodes having it's `minm length +1 < k` should not pass it's value to parent, as it will removed before kth iteration.↵
<br>so if all child nodes of a node has `minm length + 1 < k` then maximum of them should be chosen for current node otherwise minimum of `minm length +1` from all child nodes such that `minm length+1>k` should be choosen for current node.↵
<br>Below is implementation of above approach.↵
<br><br>Overall complexity: O(n) worst case.<br>↵
</spoiler>↵


<spoiler summary="code">↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵

pair<int, int> dfs(vector<int> arr[], int root, int par, int k)↵
{↵

  int maxm = 0, minm;↵
  int mink2 = INT_MAX, mink1 = -1;↵
  for (auto &x : arr[root])↵
  {↵
    if (x == par)↵
      continue;↵

    pair<int, int> p = dfs(arr, x, root, k);↵
    maxm = max(maxm, p.first + 1); // same as previous method↵
    int minj = p.second + 1;       // but finding minm is different↵
    if (minj > k && minj < mink2)↵
    {↵
      mink2 = minj;↵
    }↵
    else if (minj < k && minj > mink1)↵
    {↵
      mink1 = minj;↵
    }↵
    else if (minj == k)↵
    {↵
      if (x == 1)↵
        mink2 = minj;↵
      else↵
        mink1 = minj;↵
    }↵
  }↵

  if (mink2 == INT_MAX)↵
    minm = mink1;↵
  else↵
    minm = mink2;↵

  if (maxm == 0)↵
    minm = 0; // for leaf node.↵
  return {maxm, minm};↵
}↵

int main()↵
{↵
  int n, k;↵
  scanf("%d %d", &n, &k);↵
  vector<int> arr[n + 1];↵
  for (int i = 1; i <= n - 1; i++)↵
  {↵
    int a, b;↵
    scanf("%d %d", &a, &b);↵
    arr[a].push_back(b);↵
    arr[b].push_back(a);↵
  }↵

  pair<int, int> p = dfs(arr, 1, -1, k);↵

  cout << p.first - p.second << "\n";↵

  return 0;↵
}↵
~~~~~↵
</spoiler>↵



History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en39 English beyondpluto 2023-03-16 19:48:37 29 Tiny change: 'hallenges/binary-tree-array"> C. Edge' -> 'hallenges/edge-vs-node-mapping"> C. Edge'
en38 English beyondpluto 2022-05-30 13:48:33 0 (published)
en37 English beyondpluto 2022-05-30 13:47:34 232
en36 English beyondpluto 2022-05-30 13:45:17 630
en35 English beyondpluto 2022-05-30 13:41:00 8
en34 English beyondpluto 2022-05-30 13:38:09 97 (saved to drafts)
en33 English beyondpluto 2022-05-29 20:59:36 0 (published)
en32 English beyondpluto 2022-05-29 20:58:34 208
en31 English beyondpluto 2022-05-29 08:41:05 5 Tiny change: 'n initial - maximum' -> 'n initial tree - maximum'
en30 English beyondpluto 2022-05-29 08:40:27 48 Tiny change: 'ach.\n<br>\n</sp' -> 'ach.\n<br><br>Overall complexity: O(n) worst case.<br>\n</sp'
en29 English beyondpluto 2022-05-29 08:39:42 1823
en28 English beyondpluto 2022-05-28 16:58:00 8
en27 English beyondpluto 2022-05-28 16:56:45 51
en26 English beyondpluto 2022-05-28 16:54:02 15
en25 English beyondpluto 2022-05-28 16:51:05 4 Tiny change: '`2^n+b`.\nwhere 2^n ' -> '`2^n+b`.\n<br>where 2^n '
en24 English beyondpluto 2022-05-28 16:49:57 6
en23 English beyondpluto 2022-05-28 16:47:54 4
en22 English beyondpluto 2022-05-28 16:46:58 2 Tiny change: 'eight n.\n\n<br>Over' -> 'eight n.\n<br>Over'
en21 English beyondpluto 2022-05-28 16:46:41 63
en20 English beyondpluto 2022-05-28 16:40:38 246
en19 English beyondpluto 2022-05-28 16:33:22 3593
en18 English beyondpluto 2022-05-28 15:46:46 28
en17 English beyondpluto 2022-05-28 15:46:01 3473
en16 English beyondpluto 2022-05-28 15:14:28 3 Tiny change: '"../../../i' -> '"../../../../i'
en15 English beyondpluto 2022-05-28 15:14:06 9 Tiny change: '<a href="instagram.' -> '<a href="../../../instagram.'
en14 English beyondpluto 2022-05-28 15:13:11 13 Tiny change: '<a href="google.com">####' -> '<a href="instagram.com">####'
en13 English beyondpluto 2022-05-28 15:12:11 29
en12 English beyondpluto 2022-05-28 15:08:55 15 Tiny change: 'ight n.\n<spoiler' -> 'ight n.\n</spoiler>\n<spoiler'
en11 English beyondpluto 2022-05-28 15:07:57 30
en10 English beyondpluto 2022-05-28 15:07:07 64
en9 English beyondpluto 2022-05-28 15:06:26 4
en8 English beyondpluto 2022-05-28 15:04:41 156
en7 English beyondpluto 2022-05-28 15:02:14 378
en6 English beyondpluto 2022-05-28 14:43:44 34
en5 English beyondpluto 2022-05-28 14:01:36 35
en4 English beyondpluto 2022-05-28 13:54:40 36
en3 English beyondpluto 2022-05-28 13:54:21 48
en2 English beyondpluto 2022-05-28 13:53:59 77
en1 English beyondpluto 2022-05-28 13:52:54 231 Initial revision (saved to drafts)