Table of Contents
Tree Splitting – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Tree Splitting HackerRank Solution
#include<cstdio>
#include<ctime>
#include<cstdlib>
#include<vector>
using namespace std;
int INF, N, M, nr, V, v[400009], ap[200009], t[200009];
bool scos[200009];
vector < int > muchii[200009];
struct nod
{
int K, P, nr;
nod *l, *r, *t;
nod (int K, int P, int nr, nod *l, nod *r)
{
this->nr = nr;
this->l = l;
this->r = r;
this->P = P;
this->K = K;
this->t = 0;
}
}*adresa1[200009], *adresa2[200009], *nil, *R;
int Rand(){return ((rand()%32768)<<15)+(rand()%32768)+1;}
void reup (nod *&n)
{
if (n->l != nil) n->l->t = n;
if (n->r != nil) n->r->t = n;
n->nr = n->l->nr + n->r->nr + 1;
}
void rot_left (nod *&n)
{
nod *t=n->l;
n->l = t->r, t->r = n;
t->t = n->t;
reup (n);
reup (t);
n = t;
}
void rot_right (nod *&n)
{
nod *t=n->r;
n->r = t->l, t->l = n;
t->t = n->t;
reup (n);
reup (t);
n = t;
}
void balance (nod *&n)
{
if (n->l->P > n->P)
rot_left (n);
else
if (n->r->P > n->P)
rot_right (n);
}
void Insert (nod *&n, int Poz, int K, int P)
{
if (n == nil)
{
n = new nod (K, P, 1, nil, nil);
return ;
}
if (n->l->nr >= Poz) Insert (n->l, Poz, K, P);
else Insert (n->r, Poz - n->l->nr - 1, K, P);
reup (n);
balance (n);
}
void Erase (nod *&n, int Poz)
{
if (n->l->nr >= Poz)
Erase (n->l, Poz);
else
if (n->l->nr + 1 < Poz)
Erase (n->r, Poz - n->l->nr - 1);
else
{
if (n->l == nil && n->r == nil)
{
delete n;
n = nil;
}
else
{
if (n->l->P > n->r->P)
rot_left (n);
else
rot_right (n);
Erase (n, Poz);
}
}
if (n != nil) reup (n);
}
void join(nod *&R, nod *&Rl, nod *&Rr)
{
R=new nod(0, 0, Rl->nr + Rr->nr + 1, Rl, Rr);
Erase ( R, Rl->nr+1 );
}
void split(nod *&R, nod *&Rl, nod *&Rr, int Poz)
{
Insert (R, Poz, 0, INF);
Rl = R->l, Rl->t = 0;
Rr = R->r, Rr->t = 0;
delete R, R = nil;
}
bool nu_radacina (nod *&n)
{
if (n->t != 0 && (n->t->l == n || n->t->r == n)) return 1;
return 0;
}
void det_root (nod *n, nod *&R)
{
while (1)
{
if ( nu_radacina (n) )
n = n->t;
else
break;
}
R = n;
}
int Get_Pos (nod *n)
{
int ans = n->l->nr + 1;
while (1)
{
if (nu_radacina(n))
{
if (n->t->l == n) n = n->t;
else ans += n->t->l->nr + 1, n = n->t;
}
else break;
}
return ans;
}
void dfs (int nod)
{
ap[nod] = 1;
v[++nr] = nod;
for (vector < int > :: iterator it = muchii[nod].begin(); it != muchii[nod].end(); it++)
if (ap[*it] == 0)
{
dfs (*it);
t[*it] = nod;
}
v[++nr] = -nod;
}
void build (nod *&n)
{
if (n == nil) return ;
if (n->K < 0)
adresa2[-n->K] = n;
else
adresa1[n->K] = n;
build (n->l);
build (n->r);
}
void afis (nod *&n)
{
if (n == nil) return ;
afis (n->l);
printf ("%d ", n->K);
afis (n->r);
}
void Del (int a, int b)
{
if (t[b] == a)
{
int aux = a;
a = b;
b = aux;
}
/////t[a] == b, deci vad in ce treap este a, si ii dau split pentru a separa subarborele
nod *R, *R1, *R2, *R3, *R4;
det_root (adresa1[a], R);
/////sunt in treapul cu radacina R
int p1, p2;
p1 = Get_Pos (adresa1[a]);
p2 = Get_Pos (adresa2[a]);
split (R, R4, R3, p2);
split (R4, R1, R2, p1-1);
R2->t = 0;
join (R, R1, R3);
/*afis (R);
printf ("\n");
afis (R2);
printf ("\n");*/
}
int main()
{
//freopen ("input", "r", stdin);
//freopen ("output", "w", stdout);
srand(time(0));
INF=(1<<30)+7;
scanf ("%d", &N);
for (int i=1; i<N; i++)
{
int X, Y;
scanf ("%d %d", &X, &Y);
muchii[X].push_back(Y);
muchii[Y].push_back(X);
}
dfs (1);
nil = new nod (0, 0, 0, 0, 0);
R = nil;
for (int i=1; i<=nr; i++)
Insert (R, i-1, v[i], Rand());
build (R);
int V = 0;
scanf ("%d", &M);
for (int i=1; i<=M; i++)
{
int x;
scanf ("%d", &x), x ^= V;
nod *R;
det_root (adresa1[x], R);
printf ("%d\n", R->nr / 2), scos[x] = 1, V = R->nr / 2;
for (auto it = muchii[x].begin (); it != muchii[x].end (); it ++)
if (!scos[*it]) Del (x, *it);
}
return 0;
}
Java Tree Splitting HackerRank Solution
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;
public class E2 {
InputStream is;
PrintWriter out;
String INPUT = "";
// 1-5
// |
// 4-3
// |
// 2
void solve()
{
int n = ni();
int[] from = new int[n - 1];
int[] to = new int[n - 1];
Node[] nodes = new Node[n];
for(int i = 0;i < n;i++){
nodes[i] = new Node(i);
}
for (int i = 0; i < n - 1; i++) {
from[i] = ni() - 1;
to[i] = ni() - 1;
}
int[][] g = packU(n, from, to);
int[][] pars = parents3(g, 0);
int[] par = pars[0];
for(int i = 0;i < n;i++){
if(par[i] != -1){
link(nodes[par[i]], nodes[i]);
}
}
int ans = 0;
boolean[] deled = new boolean[n];
for(int Q = ni();Q > 0;Q--){
int x = ni()^ans;
x--;
// int x = ni()-1;
// for(int i = 0;i < n;i++)tr(i, nodes[i]);
expose(nodes[x]);
// for(int i = 0;i < n;i++)tr(i, nodes[i]);
// tr();
ans = nodes[x].size + nodes[x].sumexsize;
// tr(nodes[x].size, nodes[x].sumexsize);
// tr("ans", ans);
out.println(ans);
for(int e : g[x]){
if(!deled[e]){
if(par[x] == e){
cut(nodes[x]);
}else{
cut(nodes[e]);
}
}
}
deled[x] = true;
}
}
public static int[][] parents3(int[][] g, int root) {
int n = g.length;
int[] par = new int[n];
Arrays.fill(par, -1);
int[] depth = new int[n];
depth[0] = 0;
int[] q = new int[n];
q[0] = root;
for (int p = 0, r = 1; p < r; p++) {
int cur = q[p];
for (int nex : g[cur]) {
if (par[cur] != nex) {
q[r++] = nex;
par[nex] = cur;
depth[nex] = depth[cur] + 1;
}
}
}
return new int[][] { par, q, depth };
}
static int[][] packU(int n, int[] from, int[] to) {
int[][] g = new int[n][];
int[] p = new int[n];
for (int f : from)
p[f]++;
for (int t : to)
p[t]++;
for (int i = 0; i < n; i++)
g[i] = new int[p[i]];
for (int i = 0; i < from.length; i++) {
g[from[i]][--p[from[i]]] = to[i];
g[to[i]][--p[to[i]]] = from[i];
}
return g;
}
public static class Node
{
public int val;
public Node left, right, parent;
public Node exparent;
public int size;
public int sumexsize;
public int exsize;
public Node(int val)
{
this.val = val;
update();
}
public void update()
{
this.sumexsize = this.exsize + exsize(left) + exsize(right);
this.size = 1 + size(left) + size(right);
}
@Override
public String toString() {
return "Node [val=" + val + ", size=" + size
+ ", exsize=" + exsize
+ ", sumexsize=" + sumexsize
+ ", exparent=" + (exparent != null) + "]";
}
public String toString(String indent) {
StringBuilder builder = new StringBuilder();
if(left != null)builder.append(left.toString(indent + " "));
builder.append(indent).append(this.toString()).append("\n");
if(right != null)builder.append(right.toString(indent + " "));
return builder.toString();
}
}
public static Node expose(Node x)
{
if(x == null)return null;
while(splay(x).exparent != null)promote(x);
return x;
}
private static void promote(Node x)
{
Node xp = x.exparent;
splay(xp);
xp.exsize -= size(x) + exsize(x);
xp.exsize += size(xp.right) + exsize(xp.right);
Node xpr = xp.right;
xp.right = x;
x.parent = xp;
x.exparent = null;
if(xpr != null){
xpr.exparent = xp;
xpr.parent = null;
}
xp.update();
}
public static void cut(Node x)
{
expose(x);
Node left = x.left;
if(left != null)left.parent = null;
x.left = null;
x.update();
}
public static void link(Node par, Node ch)
{
expose(par);
expose(ch);
Node xpr = par.right;
par.right = ch;
ch.parent = par;
if(xpr != null){
xpr.exparent = par;
xpr.parent = null;
par.exsize += size(xpr) + exsize(xpr);
}
par.update();
}
public static Node root(Node x)
{
return first(expose(x));
}
public static boolean inSameLC(Node x, Node y)
{
return first(expose(x)).equals(first(expose(y)));
}
public static boolean inSameSplay(Node x, Node y)
{
Node rx = x, ry = y;
while(rx.parent != null)rx = rx.parent;
while(ry.parent != null)ry = ry.parent;
boolean ret = rx.equals(ry);
splay(x); splay(y);
return ret;
}
public static Node lca(Node x, Node y)
{
expose(x);
Node lastPromoted = null;
while(splay(y).exparent != null){
lastPromoted = y.exparent;
promote(y);
}
if(inSameSplay(x, y)){
// if(first(x).equals(first(y))){
if(index(x) < index(y)){
return x;
}else{
return y;
}
}else{
return lastPromoted;
}
}
public static void update(Node x, int v)
{
x.val = v;
x.update();
splay(x);
}
private static int size(Node n){ return n == null ? 0 : n.size; }
private static int exsize(Node n){ return n == null ? 0 : n.sumexsize; }
public static Node get(Node any, int K)
{
splay(any);
if(K < 0 || K >= size(any))throw new IllegalArgumentException();
Node cur = any;
while(true){
if(K == size(cur.left))break;
if(K < size(cur.left)){
cur = cur.left;
}else{
K -= size(cur.left) + 1;
cur = cur.right;
}
}
return splay(cur);
}
public static int index(Node x)
{
return size(splay(x).left);
}
public static Node first(Node any)
{
splay(any);
while(any.left != null)any = any.left;
return splay(any);
}
public static Node last(Node any)
{
splay(any);
while(any.right != null)any = any.right;
return splay(any);
}
public static Node erase(Node x)
{
splay(x);
if(x.left != null)x.left.parent = null;
if(x.right != null)x.right.parent = null;
if(x.left != null){
Node last = last(x.left);
last.right = x.right;
if(x.right != null)x.right.parent = last;
last.update();
}
Node ret = x.left != null ? x.left : x.right;
x.left = x.right = null;
x.update();
return ret;
}
public static void insert(Node any, int K, Node x)
{
splay(any);
if(K < 0 || K > size(any))throw new IllegalArgumentException();
if(any == null)return;
Node cur = any;
while(true){
if(K == 0 && cur.left == null){
cur.left = x;
x.parent = cur;
break;
}
if(K == size(cur) && cur.right == null){
cur.right = x;
x.parent = cur;
break;
}
if(K <= size(cur.left)){
cur = cur.left;
}else{
K -= size(cur.left) + 1;
cur = cur.right;
}
}
splay(x);
}
public static Node splay(Node x)
{
if(x == null)return null;
while(x.parent != null){
Node p = x.parent;
if(p.parent == null){
// zig
if(p.left == x)rotateRight(p);else rotateLeft(p);
}else{
Node g = p.parent;
if(g.left == p){
if(p.left == x){
// zig-zig
rotateRight(g); rotateRight(p);
}else{
// zig-zag
rotateLeft(p); rotateRight(g);
}
}else{
if(p.left == x){
// zig-zig
rotateRight(p); rotateLeft(g);
}else{
// zig-zag
rotateLeft(g); rotateLeft(p);
}
}
}
}
return x;
}
// x y
// y c -> a x return y
// a b b c
private static Node rotateRight(Node x)
{
if(x == null || x.left == null)return x;
Node y = x.left;
x.left = y.right;
y.right = x;
y.exparent = x.exparent;
x.exparent = null;
Node par = x.parent;
if(par != null){
if(par.left == x)par.left = y;
if(par.right == x)par.right = y;
}
if(x.left != null)x.left.parent = x;
x.parent = y;
y.parent = par;
x.update();
y.update();
return y;
}
// x y
// a y -> x c return y
// b c a b
private static Node rotateLeft(Node x)
{
if(x == null || x.right == null)return null;
Node y = x.right;
x.right = y.left;
y.left = x;
y.exparent = x.exparent;
x.exparent = null;
Node par = x.parent;
if(par != null){
if(par.left == x)par.left = y;
if(par.right == x)par.right = y;
}
if(x.right != null)x.right.parent = x;
x.parent = y;
y.parent = par;
x.update();
y.update();
return y;
}
public static Node[] nodes(Node any)
{
splay(any);
int n = any.size;
Node[] ret = new Node[n];
dfsNodes(0, any, ret);
return ret;
}
private static void dfsNodes(int offset, Node cur, Node[] ret)
{
if(cur == null)return;
ret[offset + size(cur.left)] = cur;
dfsNodes(offset, cur.left, ret);
dfsNodes(offset+size(cur.left)+1, cur.right, ret);
}
void run() throws Exception
{
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
long s = System.currentTimeMillis();
solve();
out.flush();
if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
}
public static void main(String[] args) throws Exception { new E2().run(); }
private byte[] inbuf = new byte[1024];
private int lenbuf = 0, ptrbuf = 0;
private int readByte()
{
if(lenbuf == -1)throw new InputMismatchException();
if(ptrbuf >= lenbuf){
ptrbuf = 0;
try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
if(lenbuf <= 0)return -1;
}
return inbuf[ptrbuf++];
}
private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private double nd() { return Double.parseDouble(ns()); }
private char nc() { return (char)skip(); }
private String ns()
{
int b = skip();
StringBuilder sb = new StringBuilder();
while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
sb.appendCodePoint(b);
b = readByte();
}
return sb.toString();
}
private char[] ns(int n)
{
char[] buf = new char[n];
int b = skip(), p = 0;
while(p < n && !(isSpaceChar(b))){
buf[p++] = (char)b;
b = readByte();
}
return n == p ? buf : Arrays.copyOf(buf, p);
}
private char[][] nm(int n, int m)
{
char[][] map = new char[n][];
for(int i = 0;i < n;i++)map[i] = ns(m);
return map;
}
private int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private int ni()
{
int num = 0, b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private long nl()
{
long num = 0;
int b;
boolean minus = false;
while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
if(b == '-'){
minus = true;
b = readByte();
}
while(true){
if(b >= '0' && b <= '9'){
num = num * 10 + (b - '0');
}else{
return minus ? -num : num;
}
b = readByte();
}
}
private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}
C Tree Splitting HackerRank Solution
#include <stdlib.h>
#include <stdio.h>
struct Set {
int count;
};
typedef struct Set Set;
struct node{
int number;
struct node * parent;
struct node * next;
struct node * prev;
struct node * first_child;
Set * set;
};
typedef struct node node;
void print_children(node * n){
node * child = n->first_child;
while(child){
printf("%d\n", child->number);
child = child->next;
}
}
void add_child(node * n, node * c){
node * cur = n->first_child;
n->first_child = c;
if (cur){
cur->prev = c;
c->next = cur;
}
}
void fill_children(node * root, node ** nodes, node ** result_nodes){
node * repr = nodes[root->number];
if(repr == 0){
return;
}
node * child = repr->first_child;
while(child){
if (result_nodes[child->number] != 0){
child = child->next;
continue;
}
node * c = calloc(1, sizeof(node));
c->number = child->number;
c->parent = root;
result_nodes[c->number] = c;
add_child(root, c);
fill_children(c, nodes, result_nodes);
child = child->next;
}
}
void compute_below(node * root, Set * set) {
if (set == 0) {
set = calloc(1, sizeof(set));
}
root->set = set;
set->count++;
node * child = root -> first_child;
while(child){
compute_below(child, set);
child = child->next;
}
}
void remove_node(node * item) {
// subtract_below(item, item->below+1);
int everyChild = item->parent != 0;
node * child = item->first_child;
int childCount = 0;
int toRemove = 1;
while (child) {
childCount++;
if (everyChild || childCount > 1) {
compute_below(child, 0);
toRemove += child->set->count;
}
child->parent = 0;
child = child->next;
}
item->set->count -= toRemove;
node * parent = item->parent;
if(parent){
if(parent->first_child == item){
parent->first_child = item->next;
}
if(item->next){
item->next->prev = item->prev;
}
if(item->prev){
item->prev->next = item->next;
}
}
}
int main(int argc, char **argv){
int n;
scanf("%d\n", &n);
int i = 0;
node ** nodes = calloc(n+1, sizeof(node *));
for(i = 0; i < n-1; i++){
int a,b;
scanf("%d %d\n", &a, &b);
node * node_a = nodes[a];
if(node_a == 0) {
node_a = calloc(1, sizeof(node));
node_a->number = a;
nodes[a] = node_a;
}
node * x = calloc(1, sizeof(node));
x->number = b;
add_child(node_a,x);
node * node_b = nodes[b];
if(node_b == 0){
node_b = calloc(1, sizeof(node));
node_b->number = b;
nodes[b] = node_b;
}
x = calloc(1, sizeof(node));
x->number = a;
add_child(node_b, x);
}
node * root = calloc(1, sizeof(node));
root->number = 1;
node ** result_nodes = calloc(n+1, sizeof(node *));
result_nodes[1] = root;
fill_children(root, nodes, result_nodes);
compute_below(result_nodes[1], 0);
int ans = 0;
int num_queries;
scanf("%d\n", &num_queries);
for(i = 0; i < num_queries; i++){
int m;
scanf("%d\n", &m);
int q = m^ans;
node * n = result_nodes[q];
ans = n->set->count;
printf("%d\n", ans);
remove_node(n);
}
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
