Algorithm

Problem Name: Data Structures - Network administration

In this HackerRank in Data Structures - Network administration solutions,

Like every IT company, the Uplink Corporation has its own network. But, unlike the rest of the companies around the world, Uplink's network is subject to very specific restrictions:

• Any pair of servers within the network should be directly connected by at most 1 link.
• No server has more than 2 links connected to it, that are controlled by the same administrator.
• For easier management, links controlled by some administrator cannot be redundant (this is, removing any link will disconnect some two previously connected servers)

Notice that 2 connected servers might not have any direct link between them. Furthermore, in order to keep the network in a secured status, Uplink directives periodically try to perform some modifications over the network to mislead hackers. The problem is, having such a huge network, they need a software to efficiently simulate the network status after any of such modifications. You have been assigned to write the core section of that software.

Operations performed by the directives are:

• Place some number of security devices along a particular link.

Also, given a network administrator, they would like to know how many devices are in the path created by links controlled by that administrator (if any) between 2 servers.

Input Format
Input begins with a line containing 4 integers S,L,A,T separated by a single whitespace, denoting the number of servers, links, network administrators and transformations, respectively. L lines follow each one with 3 integers x,y (x < y) and  ai (1 <= ai <= A), saying that there is a link between server x and server y and that link is controlled by administrator ai . Initially, network topology fulfills the restrictions described above and there is no security device along any link. Remaining T lines in the input follow one the next formats:

• 1 AB ai

meaning that link between server A and server B (A < B) is requested to be assigned to administrator ai.

• 2 A B x

meaning that the number of security devices along the link between server A and server B (A < B) will be fixed to x, removing any existing devices on this link before the operation. The involved link will always exist.

• 3 A B ai

meaning that directives want to know the number of security devices placed along the path between server A and server B, just considering links controlled by administrator ai

Output Format
For each network transformation in the form 1 A Bai ou should output:

• "Wrong link" if there is no direct link between server A and server B.
• "Network redundancy" if the requested assignment creates no new connection considering just the links controlled by ai .
• "Assignment done" if none of the above conditions holds. In this case, link directly connecting A with B is assigned to ai .

For each network transformation in the form 2 A Bai you should output:

• "No connection" if there is no path between the requested servers considering just the links controlled by ai .
• "D security devices placed" where D is the number of security devices placed so far on the existing connection between the requested servers considering just the links controlled by ai .

Constraints

1 <= S <= 105

1 <= L <= 5 * 105

1 <= A <= 102

1 <= T <= 5 * 105

1 <= x <= 2000

Sample Input:

4 5 3 15
1 2 1
2 3 1
3 4 2
1 4 2
1 3 3
2 3 4 49
1 1 2 3
2 1 4 64
3 1 4 2
1 1 2 3
3 4 2 3
3 1 3 3
1 1 4 3
3 3 4 2
3 2 4 1
2 1 4 13
2 1 3 21
2 2 3 24
1 2 3 3
1 2 4 3


Sample Output:

Assignment done
64 security devices placed
No connection
0 security devices placed
49 security devices placed
No connection
Network redundancy
Wrong link

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <stdlib.h>
#define HASH_SIZE 123455
typedef struct _ct_node{
int x;
int y;
int size;
int priority;
int a;
int value;
int sum;
int reverse;
struct _ct_node *left,*right,*parent,*next;
} ct_node;
void find(ct_node *p,int *idx,ct_node **ret);
void insert(ct_node *p);
ct_node* search(int x,int y);
ct_node* merge(ct_node *L,ct_node *R);
int sizeOf(ct_node *root);
int sumOf(ct_node *root);
void recalc(ct_node *root);
void split(int x,ct_node **L,ct_node **R,ct_node *root);
int sum(ct_node *p,int x,int y);
void push(ct_node *root);
ct_node *a[100000][100][2],*hash[HASH_SIZE];

int main(){
int S,L,A,T,x,y,z,w,i;
ct_node *p;
scanf("%d%d%d%d",&S,&L,&A,&T);
for(i=0;i < L;i++){
scanf("%d%d%d",&x,&y,&z);
x--;
y--;
z--;
p=(ct_node*)malloc(sizeof(ct_node));
p->x=x;
p->y=y;
p->size=1;
p->priority=rand();
p->a=z;
p->value=p->sum=p->reverse=0;
p->left=p->right=p->parent=p->next=NULL;
insert(p);
}
while(T--){
scanf("%d%d%d%d",&w,&x,&y,&z);
if(w==1){
p=search(x-1,y-1);
if(!p)
p=search(y-1,x-1);
if(!p)
else if(p->a==z-1)
else if(a[x-1][z-1][1] || a[y-1][z-1][1])
else{
w=p->a;
printf("Network redundancy\n");
}
else
printf("Assignment done\n");
}
}
else if(w==2){
p=search(x-1,y-1);
if(p)
else
}
else{
if(x==y){
printf("No connection\n");
continue;
}
if(w==-1)
printf("No connection\n");
else
printf("%d security devices placed\n",w);
}
}
return 0;
}
int ret,idx1,idx2,idx3,idx4;
ct_node *p1,*p2,*p3,*p4,*pp1,*pp2;
p1=a[x][z][0];
p2=a[x][z][1];
p3=a[y][z][0];
p4=a[y][z][1];
if(!p1 || !p3)
return -1;
find(p1,&idx1,&pp1);
find(p3,&idx3,&pp2);
idx2=idx4=-1;
if(p2)
find(p2,&idx2,&pp1);
if(p4)
find(p4,&idx4,&pp2);

/////////////////////
if(idx2!=-1 && !(idx1-idx2==1 || idx2-idx1==1)){
while(1);
printf("Oh no. %d %d\n",idx1,idx2);
}
if(idx4!=-1 && !(idx3-idx4==1 || idx4-idx3==1)){
while(1);
printf("Oh no. %d %d\n",idx3,idx4);
}
/////////////////////

if(pp1!=pp2)
return -1;
if(idx2==-1 && idx4==-1)
return pp1->sum;
if(idx1==idx3)
return sum(pp1,idx1,idx3);
else if(idx1<idx3)
if(idx2==-1)
if(idx3 < idx4)
return sum(pp1,idx1,idx3);
else
return sum(pp1,idx1,idx4);
else if(idx4==-1)
if(idx1 < idx2)
return sum(pp1,idx2,idx3);
else
return sum(pp1,idx1,idx3);
else
if(idx1 < idx2)
if(idx3{
p->value=x;
recalc(p);
for(;p->parent;p=p->parent)
recalc(p->parent);
return;
}
int idx1,idx2;
ct_node *p1,*p2;
p->a=x;
if(!a[p->x][x][0] && !a[p->y][x][0]){
a[p->x][x][0]=p;
a[p->y][x][0]=p;
return 0;
}
else if(!a[p->x][x][0] && a[p->y][x][0]){
find(a[p->y][x][0],&idx1,&p1);
if(idx1)
merge(p1,p);
else
merge(p,p1);
a[p->x][x][0]=p;
a[p->y][x][1]=p;
return 0;
}
else if(a[p->x][x][0] && !a[p->y][x][0]){
find(a[p->x][x][0],&idx1,&p1);
if(idx1)
merge(p1,p);
else
merge(p,p1);
a[p->x][x][1]=p;
a[p->y][x][0]=p;
return 0;
}
find(a[p->x][x][0],&idx1,&p1);
find(a[p->y][x][0],&idx2,&p2);
if(p1==p2)
return 1;
if(!idx1 && !idx2){
p1->reverse^=1;
merge(p1,merge(p,p2));
}
else if(!idx1 && idx2)
merge(p2,merge(p,p1));
else if(idx1 && !idx2)
merge(p1,merge(p,p2));
else{
p2->reverse^=1;
merge(p1,merge(p,p2));
}
a[p->x][x][1]=p;
a[p->y][x][1]=p;
return 0;
}
int idx;
ct_node *p1,*p2;
find(p,&idx,&p1);
split(idx-1,&p1,&p2,p1);
split(0,&p1,&p2,p2);
if(a[p->x][p->a][0]==p)
a[p->x][p->a][0]=a[p->x][p->a][1];
if(a[p->y][p->a][0]==p)
a[p->y][p->a][0]=a[p->y][p->a][1];
a[p->x][p->a][1]=NULL;
a[p->y][p->a][1]=NULL;
return;
}
void find(ct_node *p,int *idx,ct_node **ret){
int d,i;
for(i=-1;p->parent;p=p->parent){
if(i==-1)
if(p->reverse)
i=sizeOf(p->right);
else
i=sizeOf(p->left);
else
if(!d && p->reverse)
i=sizeOf(p->right)+sizeOf(p->left)-i;
else if(d && !p->reverse)
i+=sizeOf(p->left)+1;
else if(d && p->reverse)
i=sizeOf(p->right)-i-1;
if(p->parent->left==p)
d=0;
else
d=1;
}
if(i==-1)
if(p->reverse)
i=sizeOf(p->right);
else
i=sizeOf(p->left);
else
if(!d && p->reverse)
i=sizeOf(p->right)+sizeOf(p->left)-i;
else if(d && !p->reverse)
i+=sizeOf(p->left)+1;
else if(d && p->reverse)
i=sizeOf(p->right)-i-1;
*idx=i;
*ret=p;
return;
}
void insert(ct_node *p){
int bucket=(p->x+100000LL*p->y)%HASH_SIZE;
p->next=hash[bucket];
hash[bucket]=p;
return;
}
ct_node* search(int x,int y){
int bucket=(x+100000LL*y)%HASH_SIZE;
ct_node *t=hash[bucket];
while(t){
if(t->x==x && t->y==y)
return t;
t=t->next;
}
return NULL;
}
ct_node* merge(ct_node *L,ct_node *R){
if(!L)
return R;
if(!R)
return L;
if(L->priority>R->priority){
push(L);
if(L->right)
L->right->parent=NULL;
L->right=merge(L->right,R);
if(L->right)
L->right->parent=L;
recalc(L);
return L;
}
push(R);
if(R->left)
R->left->parent=NULL;
R->left=merge(L,R->left);
if(R->left)
R->left->parent=R;
recalc(R);
return R;
}
int sizeOf(ct_node *root){
return (root)?root->size:0;
}
int sumOf(ct_node *root){
return (root)?root->sum:0;
}
void recalc(ct_node *root){
root->size=sizeOf(root->left)+sizeOf(root->right)+1;
root->sum=sumOf(root->left)+sumOf(root->right)+root->value;
return;
}
void split(int x,ct_node **L,ct_node **R,ct_node *root){
if(!root){
*L=*R=NULL;
return;
}
push(root);
int curIndex=sizeOf(root->left);
ct_node *t;
if(curIndex<=x>{
if(root->right)
root->right->parent=NULL;
split(x-curIndex-1,&t,R,root->right);
if(t)
t->parent=root;
root->right=t;
recalc(root);
*L=root;
}
else{
if(root->left)
root->left->parent=NULL;
split(x,L,&t,root->left);
if(t)
t->parent=root;
root->left=t;
recalc(root);
*R=root;
}
return;
}
int sum(ct_node *p,int x,int y){
int ret;
ct_node *p1,*p2;
split(y,&p2,&p,p);
split(x-1,&p1,&p2,p2);
ret=p2->sum;
merge(p1,merge(p2,p));
return ret;
}
void push(ct_node *root){
if(!root || !root->reverse)
return;
ct_node *t=root->left;
root->left=root->right;
root->right=t;
root->reverse=0;
if(root->left)
root->left->reverse^=1;
if(root->right)
root->right->reverse^=1;
return;
}

Copy The Code &

#2 Code Example with C++ Programming

Code - C++ Programming


#include <bits/stdc++.h>

using namespace std;

typedef pair < int, int> PII;

struct Edge : PII {
Edge(int a = 0, int b = 0, int i = 0, int l = 0){
first = a; second = b; k = i; len = l;
}
int k, len;
} edge[500010];

struct Node {
Node *fa, *ch[2];
int sum, arc[2];
bool rev;

void init(){
fa = ch[0] = ch[1] = 0;
rev = false;
}

int get_sum() const {
return this ? sum : 0;
}
int get_arc(int c) const {
return ch[c] ? edge[arc[c]].len : 0;
}

void mark_rev(){
if(this == 0) return;
rev = !rev;
swap(ch[0], ch[1]);
swap(arc[0], arc[1]);
}

void push_down(){
if(rev){
rev = false;
ch[0]->mark_rev();
ch[1]->mark_rev();
}
}
void update(){
sum = ch[0]->get_sum() + get_arc(0)
+ ch[1]->get_sum() + get_arc(1);
}

void rotate(int c){
Node *y = fa;
y->ch[1 - c] = ch[c];
if(ch[c])
ch[c]->fa = y;
fa = y->fa;
if(y->fa != 0){
if(y->fa->ch[0] == y)
y->fa->ch[0] = this;
else
y->fa->ch[1] = this;
}
ch[c] = y;
y->fa = this;
y->update();
}

void splay(Node *f){
push_down();
while(fa != f){
if(fa->fa == f){
fa->push_down(); push_down();
if(fa->ch[0] == this)
rotate(1);
else
rotate(0);
} else{
Node *y = fa, *z = y->fa;
z->push_down(); y->push_down(); push_down();
if(z->ch[0] == y){
if(y->ch[0] == this)
y->rotate(1), rotate(1);
else
rotate(0), rotate(1);
} else{
if(y->ch[1] == this)
y->rotate(0), rotate(0);
else
rotate(1), rotate(0);
}
}
}
update();
}
} nodes[1000010], *ptr = nodes;

int degree[100010];
Node* mem[100010];

Node* node(int v){
return mem[v] ? mem[v] : (mem[v] = ptr++);
}

bool link(int v, int u, int p){
node(v)->splay(0); node(u)->splay(0);
if(node(v)->fa == 0 && node(u)->fa == 0){
if(node(v)->ch[1]){
node(v)->mark_rev();
node(v)->push_down();
}
if(node(u)->ch[0]){
node(u)->mark_rev();
node(u)->push_down();
}
node(v)->ch[1] = node(u);
node(v)->arc[1] = p;
node(u)->fa = node(v);
node(u)->arc[0] = p;
node(v)->update();
++degree[v], ++degree[u];
return true;
} else{
return false;
}
}

void cut(int v, int u){
node(v)->splay(0); node(u)->splay(node(v));
if(node(v)->ch[0] == node(u)){
node(v)->ch[0] = 0;
} else{
node(v)->ch[1] = 0;
}
node(v)->update();
node(u)->fa = 0;
--degree[v]; --degree[u];
}

int query(int v, int u){
node(u)->splay(0); node(v)->splay(0);
if(node(v)->fa == 0 && node(u)->fa == 0)
return -1;
node(u)->splay(node(v));
if(node(v)->ch[0] == node(u))
return node(v)->get_arc(0) + node(u)->ch[1]->get_sum()
+ node(u)->get_arc(1);
else
return node(u)->get_arc(0) + node(u)->ch[0]->get_sum()
+ node(v)->get_arc(1);
}

void modify(int v, int u){
node(v)->splay(0); node(u)->splay(0);
}

int main(){
int S, L, A, T;
scanf("%d%d%d%d", &S, &L, &A, &T);
for(int i = 0; i < L; ++i){
int a, b, k;
scanf("%d%d%d", &a, &b, &k>;
if(a > b) swap(a, b);
edge[i] = Edge(a, b, k);
}
sort(edge, edge + L);
for(int i = 0; i < L; ++i)
for(int i = 0; i  <  T; ++i){
int opt; scanf("%d", &opt);
if(opt == 1){
int a, b, k;
scanf("%d%d%d", &a, &b, &k>;
if(a > b) swap(a, b);
int p = lower_bound(edge, edge + L, PII(a, b)) - edge;
if(p == L || edge[p] != PII(a, b)){
} else if(edge[p].k == k){
puts("Network redundancy");
} else{
edge[p].k = k;
puts("Assignment done");
}
} else if(opt == 2){
int a, b, x;
scanf("%d%d%d", &a, &b, &x);
if(a > b) swap(a, b);
int p = lower_bound(edge, edge + L, PII(a, b)) - edge;
edge[p].len = x;
} else{
int a, b, k;
scanf("%d%d%d", &a, &b, &k);
if(r == -1){
puts("No connection");
} else{
printf("%d security devices placed\n", r);
}
}
}
return 0;
}


Copy The Code &

#3 Code Example with Java Programming

Code - Java Programming


import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.InputMismatchException;

public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
PrintWriter out = new PrintWriter(outputStream);
solver.solve(1, in, out);
out.close();
}
}

public void solve(int testNumber, InputReader in, PrintWriter out) {
int S = in.nextInt();
int L = in.nextInt();
int A = in.nextInt();
int T = in.nextInt();
byte[][] deg = new byte[A][S];
Info[] infos = new Info[L];

for (int i = 0; i  <  L; i++) {
int x = in.nextInt() - 1;
int y = in.nextInt() - 1;
int a = in.nextInt() - 1;

if (lct[a][x] == null) {
}

if (lct[a][y] == null) {
}

++deg[a][x];
++deg[a][y];
infos[i] = new Info(a, edgeNode, edge(x, y));
}

Arrays.sort(infos, new Comparator < Info>() {
public int compare(Info a, Info b) {
return Long.compare(a.edge, b.edge);
}
});

long[] edges = new long[L];

for (int i = 0; i  <  L; i++) {
edges[i] = infos[i].edge;
}

for (int i = 0; i  <  T; i++) {
int t = in.nextInt();
int a = in.nextInt() - 1;
int b = in.nextInt() - 1;

if (t == 1) {
int admin = in.nextInt() - 1;
long e = edge(a, b);
int index = Arrays.binarySearch(edges, e);
Info info = index  <  0 ? null : infos[index];

out.println("Network redundancy");
} else {
out.println("Assignment done");

}

}

}
} else if (t == 2) {
int x = in.nextInt();
edge(a, b))].edgeNode;
} else {
int admin = in.nextInt() - 1;

out.println("No connection");
} else {
out.println(res + " security devices placed");
}
}
}
}

static long edge(int u, int v) {
return ((long) Math.min(u, v) << 32) + Math.max(u, v);
}

static class Info {
long edge;

this.edgeNode = edgeNode;
this.edge = edge;
}
}

static int queryOperation(int leftValue, int rightValue) {
return leftValue + rightValue;
}

static int getNeutralValue() {
return 0;
}

public static class Node {
int nodeValue;
int subTreeValue;
int size;
boolean revert;
Node left;
Node right;
Node parent;

Node(int value) {
nodeValue = value;
subTreeValue = value;
size = 1;
}

boolean isRoot() {
return parent == null
|| (parent.left != this && parent.right != this);
}

void push() {
if (revert) {
revert = false;
Node t = left;
left = right;
right = t;

if (left != null) {
left.revert = !left.revert;
}

if (right != null) {
right.revert = !right.revert;
}
}
}

void update() {
subTreeValue = queryOperation(
queryOperation(getSubTreeValue(left), nodeValue),
getSubTreeValue(right));
size = 1 + getSize(left) + getSize(right);
}
}

static int getSize(Node root) {
return root == null ? 0 : root.size;
}

static int getSubTreeValue(Node root) {
return root == null ? getNeutralValue() : root.subTreeValue;
}

static void connect(Node ch, Node p, Boolean isLeftChild) {
if (ch != null) {
ch.parent = p;
}

if (isLeftChild != null) {
if (isLeftChild) {
p.left = ch;
} else {
p.right = ch;
}
}
}

static void rotate(Node x) {
Node p = x.parent;
Node g = p.parent;
boolean isRootP = p.isRoot();
boolean leftChildX = (x == p.left);
connect(leftChildX ? x.right : x.left, p, leftChildX);
connect(p, x, !leftChildX);
connect(x, g, isRootP ? null : p == g.left);
p.update();
}

static void splay(Node x) {
while (!x.isRoot()) {
Node p = x.parent;
Node g = p.parent;

if (!p.isRoot()) {
g.push();
}

p.push();
x.push();

if (!p.isRoot()) {
rotate((x == p.left) == (p == g.left) ? p : x);
}

rotate(x);
}

x.push();
x.update();
}

static Node expose(Node x) {
Node last = null;

for (Node y = x; y != null; y = y.parent) {
splay(y);
y.left = last;
last = y;
}

splay(x);

return last;
}

public static void makeRoot(Node x) {
expose(x);
x.revert = !x.revert;
}

public static boolean connected(Node x, Node y) {
if (x == y) {
return true;
}

expose(x);
expose(y);

return x.parent != null;
}

public static void link(Node x, Node y) {
makeRoot(x);
x.parent = y;
}

public static void cut(Node x, Node y) {
makeRoot(x);
expose(y);
y.right.parent = null;
y.right = null;
}

public static int query(Node from, Node to) {
makeRoot(from);
expose(to);

return getSubTreeValue(to);
}

public static void modify(Node from, Node to, int delta) {
makeRoot(from);
expose(to);
to.nodeValue = delta;
}
}
}

final InputStream is;
final byte[] buf = new byte[1024];
int pos;
int size;

this.is = is;
}

public int nextInt() {

while (isWhitespace(c)) {
}

int sign = 1;

if (c == '-') {
sign = -1;
}

int res = 0;

do {
if (c  <  '0' || c > '9') {
throw new InputMismatchException();
}

res = res * 10 + c - '0';
} while (!isWhitespace(c));

return res * sign;
}

if (size == -1) {
throw new InputMismatchException();
}

if (pos >= size) {
pos = 0;

try {
} catch (IOException e) {
throw new InputMismatchException();
}

if (size  < = 0) {
return -1;
}
}

return buf[pos++] & 255;
}

static boolean isWhitespace(int c) {
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
}

Copy The Code &