Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/helix/problem?isFullScreen=true
In this HackerRank in Data Structures -
Natural numbers from 1 to N have been placed in an increasing order over some helix ( a circular structure ). When the helix starts rotating, it is easy to find out
- The position of a given number
- The number located at a given position.
The helix has numbers arranged in the following fashion:
[1, 2, 3, ..., N]
Due to some malfunction, the helix has started rotating in a weird manner. Right now, every possible contiguous interval can be rotated, and hence, locating a particular number or identifying the number at a given position is almost impossible. For example, if at some particular instant, the integer list is like this:
[1, 2, 3, 4, 5, ..., N]
rotating the interval [5...N] will leave the list like this:
[1, 2, 3, 4, N, N - 1, N - 2, ..., 5]
We need a software to handle this. Can you help us?
Input Format
The first line of the input consists of two space separated integers, N, Q. N signifies that initially our list contains numbers from 1 to N, placed in an increasing order. Q lines follow and contain input in one of the following formats:
1 A B
indicating that the helix rotated circularly in the interval [A..B] ( both inclusive);
2 A
indicating that we are interested in knowing the current position of the number A
3 A
indicating that we are interested in knowing the number at position A.
Output Format
For each line in the input of the form 2 A
output a line saying
element A is at position x
where A is the number we are interested in and x is its current position.
For each line of the form 3 A
output a line saying
element at position A is x
where A is the position we are interested in and x is the integer located at this position.
Constraints
1 ≤ N, Q ≤ 105
positions are 1-indexed.
Sample Input
5 10
1 1 3
2 3
3 3
1 3 5
1 2 4
3 1
3 5
2 4
1 5 5
2 2
Sample Output
element 3 is at position 1
element at position 3 is 1
element at position 1 is 3
element at position 5 is 1
element 4 is at position 2
element 2 is at position 4
Explanation
Initially elements are placed like this:
[1, 2, 3, 4, 5]
after the first rotation, they are placed like this:
[3, 2, 1, 4, 5]
and that's how we get the first 2 results (first 2 lines in the output). After second rotation, they are placed like this:
[3, 2, 5, 4, 1]
and third one does this:
[3, 4, 5, 2, 1]
In the last rotation (1 5 5), it's easy to see that output matches the initial positions of the elements. Last rotation doesn't change the positions of the elements.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include<stdio.h>
#include<stdlib.h>
typedef struct Node
{
int size, rev, key;
struct Node *left, *right, *parent, *haxx;
}Node;
static Node *NODES;
static inline int size(Node *n)
{
return n ? n -> size : 0;
}
static inline void resize(Node *n)
{
if(n)
{
n -> size = size(n -> left) + size(n -> right) + 1;
}
}
static inline Node *createNode(int key, Node *left, Node *right)
{
Node *n = &NODES[key];
if(left)
{
left -> parent = n;
}
if(right)
{
right -> parent = n;
}
n -> key = key;
n -> left = left;
n -> right = right;
n -> rev = 0;
n -> parent = NULL;
n -> haxx = NULL;
resize(n);
return n;
}
static inline void pushDown(Node *n)
{
Node *tmp;
if(!( n && n -> rev ))
{
return;
}
if(n -> left)
{
n -> left -> rev ^= 1;
}
if(n -> right)
{
n -> right -> rev ^= 1;
}
tmp = n -> left;
n -> left = n -> right;
n -> right = tmp;
n -> rev = 0;
}
static inline int indexOf(Node *n)
{
Node *np = n, *p;
int i;
while(np -> parent)
{
np -> parent -> haxx = np;
np = np -> parent;
}
while( np != n )
{
pushDown(np);
np = np -> haxx;
}
pushDown(n);
i = size(n -> left);
while(n -> parent)
{
np = n -> parent;
if( n == np -> right )
{
i += size(np -> left) + 1;
}
n = np;
}
return i;
}
static inline Node *kthChild(Node *n, int k)
{
int ls;
while(1)
{
pushDown(n);
ls = size(n -> left);
if( k < ls >
{
n = n -> left;
}
else if( k > ls )
{
n = n -> right;
k = k - ls - 1;
}
else
{
return n;
}
}
}
static inline Node *zig(Node *n)
{
Node *left, *lr;
pushDown(n -> left);
left = n -> left;
lr = left -> right;
left -> right = n;
left -> parent = n -> parent;
n -> parent = left;
n -> left = lr;
if(lr)
{
lr -> parent = n;
}
resize(n);
resize(left);
return left;
}
static inline Node *zag(Node *n)
{
Node *right, *rl;
pushDown(n -> right);
right = n -> right;
rl = right -> left;
right -> left = n;
right -> parent = n -> parent;
n -> parent = right;
n -> right = rl;
if(rl)
{
rl -> parent = n;
}
resize(n);
resize(right);
return right;
}
static inline Node *splay(Node *p, Node *n)
{
Node *swap, *np, *gp;
while(1)
{
np = n -> parent;
if( p == np )
{
return n;
}
gp = np -> parent;
pushDown(gp);
pushDown(np);
swap = ( n == np -> left ) ? zig(np) : zag(np);
if(gp)
{
if( np == gp -> left )
{
gp -> left = swap;
}
else
{
gp -> right = swap;
}
}
n = swap;
}
}
static inline Node *reverseInterval(Node *root, int a, int b)
{
Node *left, *right, *rl;
left = kthChild(root, a - 1);
right = kthChild(root, b + 1);
root = splay(NULL, left);
root -> right = splay(root, right);
rl = root -> right -> left;
pushDown(rl);
rl -> rev = 1;
return root;
}
static inline Node *splayTree(int min, int max)
{
int mid;
if( min < max )
{
mid = min + ( ( max - min ) >> 1 );
return createNode(mid, splayTree(min, mid - 1), splayTree(mid + 1, max));
}
else if( min == max )
{
return createNode(min, NULL, NULL);
}
else
{
return NULL;
}
}
int main()
{
int N, Q, q, a, b;
scanf("%d%d", &N, &Q);
NODES = malloc(sizeof(Node) * ( N + 2 ));
Node *root = splayTree(0, N + 1);
while(Q--)
{
scanf("%d", &q);
switch(q)
{
case 1:
scanf("%d%d", &a, &b);
root = reverseInterval(root, a, b);
break;
case 2:
scanf("%d", &a);
printf("element %d is at position %d\n", a, indexOf(&NODES[a]));
break;
case 3:
scanf("%d", &b);
printf("element at position %d is %d\n", b, kthChild(root, b> -> key);
break;
}
}
return 0;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <iostream>
#include <cstdio>
#include <string>
#include <string.h>
#include <queue>
#include <math.h>
#include <cmath>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <bitset>
#include <ctype.h>
#include <cassert>
#include <stack>
#include <fstream>
#include <unordered_set>
using namespace std;
#define snd second
#define fst first
#define mp make_pair
#define ll long long
#define ull unsigned long long
#define ld long double
#define pb push_back
#define left _left
#define y1 _y1
template < typename T > T abs(T x)
{
return x > 0 ? x : -x;
}
struct node
{
node *l, *r, *p;
int key, pr;
int size;
bool rev;
node()
{
l = r = p = NULL;
pr = rand();
size = 1;
rev = false;
}
void push()
{
if (rev)
{
if (l)
l->rev ^= 1;
if (r)
r->rev ^= 1;
swap(l, r);
rev = false;
}
}
void update()
{
size = 1 + (l ? l->size : 0) + (r ? r->size : 0);
}
};
int getSize(node *v)
{
return v ? v->size : 0;
}
typedef node* pnode;
pnode merge(pnode l, pnode r)
{
if (!l || !r)
return l ? l : r;
l->push();
r->push();
if (l->pr > r->pr)
{
l->r = merge(l->r, r);
l->r->p = l;
l->update();
return l;
}
else
{
r->l = merge(l, r->l);
r->l->p = r;
r->update();
return r;
}
}
void split(pnode v, pnode &l, pnode &r, int key)
{
if (!v)
{
l = r = NULL;
return;
}
v->push();
v->p = NULL;
if (1 + getSize(v->l) < = key)
{
l = v;
split(l->r, l->r, r, key - 1 - getSize(v->l));
if (l->r)
l->r->p = l;
}
else
{
r = v;
split(r->l, l, r->l, key);
if (r->l)
r->l->p = r;
}
if (l)
l->update();
if (r)
r->update();
}
const int maxn = 100005;
node *a[maxn];
int main(int argc, char *argv[])
{
//freopen("a.in", "r", stdin);
int n, q;
scanf("%d %d", &n, &q);
a[0] = new node();
a[0]->key = 0;
node *root = a[0];
for (int i = 1; i < n; i++)
{
node *v = new node();
v->key = i;
a[i] = v;
root = merge(root, v);
}
for (int i = 0; i < q; i++)
{
int type;
scanf("%d", &type);
if (type == 1)
{
int u, v;
scanf("%d %d", &u, &v);
pnode left, center, right;
split(root, left, right, u - 1);
split(right, center, right, v - u + 1);
center->rev ^= 1;
root = merge(merge(left, center), right);
}
else if (type == 3)
{
int u;
scanf("%d", &u);
pnode left, center, right;
split(root, center, right, u);
split(center, left, center, u - 1);
printf("element at position %d is %d\n", u, center->key + 1);
root = merge(merge(left, center), right);
}
else
{
int u;
scanf("%d", &u);
node *v = a[u - 1];
vector < pnode > b;
while (v != NULL)
{
b.pb(v);
v = v->p;
}
for (int j = b.size() - 1; j >= 0; j--)
{
b[j]->push();
}
v = a[u - 1];
int ans = getSize(v->l) + 1;
while (v->p != NULL)
{
if (v->p->r == v)
{
ans += getSize(v->p->l) + 1;
}
v = v->p;
}
printf("element %d is at position %d\n", u, ans);
}
}
return 0;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.io.*;
import java.util.*;
public class Solution {
public static void main(String[] args)throws IOException {
BufferedReader obj=new BufferedReader(new InputStreamReader(System.in));
String s[]=obj.readLine().split(" ");
int n=Integer.parseInt(s[0]);
int Q=Integer.parseInt(s[1]);
int a[]=new int[n+1];
for(int i = 1; i < = n; i++)
a[i]=i;
for(int t = 0; t < Q; t++)
{
String s1[]=obj.readLine().split(" ");
int p,q,r;
p=Integer.parseInt(s1[0]);
switch(p)
{
case 1:
q=Integer.parseInt(s1[1]);
r=Integer.parseInt(s1[2]);
for(int i = 0; i < (r-q) / 2+1; i++)
{
int temp=a[r-i];
a[r-i]=a[i+q];
a[i+q]=temp;
}
break;
case 2:
q=Integer.parseInt(s1[1]);
for(int i = 1; i < = n/2+1; i++)
{
if(a[i]==q)
{
System.out.println("element "+q+" is at position "+i);
break;
}
if(a[n-i+1]==q)
{
System.out.println("element "+q+" is at position "+(n-i+1));
break;
}
}
break;
case 3:
q=Integer.parseInt(s1[1]);
System.out.println("element at position "+q+" is "+a[q]);
break;
}
}
// System.out.println(Arrays.toString(a));
}
}
#4 Code Example with Python Programming
Code -
Python Programming
def size(node):
if node:
return node.size
return 0
class Node:
def __init__(self, id=-1):
self.id = id
self.left =None
self.right =None
self.parent = None
self.size = 1
self.rev = False
def release(self):
if self.rev:
self.rev = False
self.left, self.right = self.right, self.left
if self.left:
self.left.rev ^= True
if self.right:
self.right.rev ^= True
def update(self):
self.size = 1 + size(self.left) + size(self.right)
def zig(p):
q = p.parent
r = q.parent
q.left=p.right
if q.left:
q.left.parent = q
p.right = q
q.parent = p
p.parent=r
if p.parent:
if r.left == q:
r.left = p
if r.right == q:
r.right = p
q.update()
def zag(p):
q = p.parent
r = q.parent
q.right=p.left
if q.right:
q.right.parent = q
p.left = q
q.parent = p
p.parent=r
if p.parent:
if r.left == q:
r.left = p
if r.right == q:
r.right = p
q.update()
def splay(root, p, b=None):
p.release()
while p.parent != b:
q = p.parent
if q.parent == b:
q.release()
p.release()
if q.left == p:
zig(p)
else:
zag(p)
else:
r = q.parent
r.release()
q.release()
p.release()
if r.left == q:
if q.left == p:
zig(q)
zig(p)
else:
zag(p)
zig(p)
elif q.left == p:
zig(p)
zag(p)
else:
zag(q)
zag(p)
p.update()
if b == None:
root = p
else:
b.update()
return root
def find(k, p):
if not p or p.size < k:
return None
while k:
p.release()
if p.left and p.left.size >= k:
p = p.left
else:
if p.left:
k -= p.left.size
k -= 1
if k > 0:
p = p.right
return p
def build( a, b):
global T
if a > b:
return None
if a == b:
prx = T[a]
prx.left =None
prx.right =None
prx.parent = None
return prx
mid = (a + b)//2
prx = T[mid]
prx.parent = None
prx.left = build( a, mid - 1)
if prx.left:
prx.left.parent = prx
prx.right = build( mid + 1, b)
if prx.right:
prx.right.parent = prx
prx.update()
return prx
def reverse(root, a, b):
if a == b:
return
lfx = a + 1
rgx = b + 1
prev = find(lfx - 1, root)
nxt = find(rgx + 1, root)
root=splay(root, prev)
root=splay(root, nxt, prev)
nxt.left.rev ^= True
return root
n, q = map(int, input().split())
T = [None for i in range(n + 2)]
for i in range(n + 2):
T[i] = Node(i)
root = build( 0, n + 1)
s = ''
for k in range(q):
query = tuple(map(int, input().split()))
t = query[0]
if t == 1:
i, j = query[1], query[2]
root=reverse(root, i, j)
elif t == 2:
i = query[1]
ptx = T[i]
root = splay(root, ptx)
s += 'element {} is at position {}\n'.format(i, size(ptx.left))
else:
i = query[1]
ptx = find(i + 1,root)
s += 'element at position {} is {}\n'.format(i, ptx.id)
print(s)