B. Binary-tree-array:
B. Binary-tree-array:
Just convert the string into binary notation.
ie:L to 0 and R to 1.
let that value be b in decimal.
then the answer will be 2^n+b
.
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.
note: hidden node will be at height n.
Overall complexity: O(29*q) worst case.
#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;
}
Left child of a node at ith position in array will be at 2*i th position.
similarly right child will be at 2*i+1 position in same array.
So, using the given left or right information, we can recursively find position of hidden node, starting from i=1.
Overall complexity: O(29*q) worst case.
#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;
}
C. Edge-vs-node-mapping:
C. Edge-vs-node-mapping:
Tree has one property that all the nodes except root node will have exactly one parent node.
So for all node except root node, we can map the node with edge connecting it with it's parent node.
This can be done with dfs with assuming some random node root.
Overall complexity: O(n).
#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;
}
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.
Overall complexity: O(n).
#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;
}
D. MAX-MIN:
B. MAX-MIN:
It is just an implementation problem.
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.
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 has only one edge(ie:adj[par].size()==1).
Do this upto k iterations and then do dfs on final tree to find the ans.
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)).
Overall complexity: O(n*log(n)) worst case.
where dfs takes O(n) but adjacency set insertion and leaf removal will take O(n*log(n)) worst case.
#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;
}