In this HackerRank The crazy helix problem solution you are given some natural numbers from 1 to N that placed in an increasing order over some helix. when the helix starts rotating then it is easy to find out the position of a given number and the number located at the given position. so we need to print the output a line saying element A is at position x if the input is of the form 2 A.
Problem solution in 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)
Problem solution in Java Programming.
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Random;
public class Solution {
static InputStream is;
static PrintWriter out;
static String INPUT = "";
static void solve()
{
int n = ni(), Q = ni();
Node root = null;
Node[] nodes = new Node[n];
for(int i = n;i >= 1;i--){
nodes[i-1] = new Node(i);
root = insert(root, 0, nodes[i-1]);
}
for(int q = 0;q < Q;q++){
int type = ni();
if(type == 1){
int a = ni()-1, b = ni()-1;
if(a <= b){
root = reverse(root, a, b+1);
}else{
Node[] sp = split(root, b+1);
root = merge(sp[1], sp[0]);
root = reverse(root, n-(b+1+n-a), n);
sp = split(root, n-b-1);
root = merge(sp[1], sp[0]);
}
}else if(type == 2){
int a = ni()-1;
int x = index(nodes[a]);
out.println("element " + (a+1) + " is at position " + (x+1));
}else{
int a = ni()-1;
int x = get(root, a).v;
out.println("element at position " + (a+1) + " is " + x);
}
}
}
public static Random gen = new Random();
static public class Node
{
public int v; // value
public long priority;
public Node left, right, parent;
public int count;
public boolean rev;
public Node(int v)
{
this.v = v;
priority = gen.nextLong();
update(this);
}
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("Node [v=");
builder.append(v);
builder.append(", count=");
builder.append(count);
builder.append(", parent=");
builder.append(parent != null ? parent.v : "null");
builder.append(", rev=");
builder.append(rev);
builder.append("]");
return builder.toString();
}
}
public static Node update(Node a)
{
if(a == null)return null;
a.count = 1;
if(a.left != null)a.count += a.left.count;
if(a.right != null)a.count += a.right.count;
return a;
}
public static Node reverse(Node a, int L, int R)
{
Node[] MR = split(a, R);
Node[] LM = split(MR[0], L);
if(LM[1] != null)LM[1].rev ^= true;
return merge(merge(LM[0], LM[1]), MR[1]);
}
public static void fall(Node a)
{
if(a == null)return;
if(a.rev){
Node n = a.left; a.left = a.right; a.right = n;
if(a.left != null)a.left.rev ^= true;
if(a.right != null)a.right.rev ^= true;
a.rev = false;
}
if(a.left != null){
update(a.left);
}
if(a.right != null){
update(a.right);
}
update(a);
}
public static Node disconnect(Node a)
{
if(a == null)return null;
a.left = a.right = a.parent = null;
return update(a);
}
public static Node merge(Node a, Node b)
{
if(b == null)return a;
if(a == null)return b;
if(a.priority > b.priority){
fall(a);
setParent(a.right, null);
setParent(b, null);
a.right = merge(a.right, b);
setParent(a.right, a);
return update(a);
}else{
fall(b);
setParent(a, null);
setParent(b.left, null);
b.left = merge(a, b.left);
setParent(b.left, b);
return update(b);
}
}
public static int count(Node a)
{
return a == null ? 0 : a.count;
}
public static void setParent(Node a, Node par)
{
if(a != null)a.parent = par;
}
// [0,K),[K,N)
public static Node[] split(Node a, int K)
{
if(a == null)return new Node[]{null, null};
fall(a);
if(K <= count(a.left)){
setParent(a.left, null);
Node[] s = split(a.left, K);
a.left = s[1];
setParent(a.left, a);
s[1] = update(a);
return s;
}else{
setParent(a.right, null);
Node[] s = split(a.right, K-count(a.left)-1);
a.right = s[0];
setParent(a.right, a);
s[0] = update(a);
return s;
}
}
public static Node insert(Node a, int K, Node b)
{
if(a == null)return b;
fall(a);
if(b.priority < a.priority){
if(K <= count(a.left)){
a.left = insert(a.left, K, b);
setParent(a.left, a);
}else{
a.right = insert(a.right, K-count(a.left)-1, b);
setParent(a.right, a);
}
return update(a);
}else{
Node[] ch = split(a, K);
b.left = ch[0]; b.right = ch[1];
setParent(b.left, b);
setParent(b.right, b);
return update(b);
}
}
// delete K-th
public static Node erase(Node a, int K)
{
if(a == null)return null;
fall(a);
if(K < count(a.left)){
a.left = erase(a.left, K);
setParent(a.left, a);
return update(a);
}else if(K == count(a.left)){
setParent(a.left, null);
setParent(a.right, null);
Node aa = merge(a.left, a.right);
disconnect(a);
return aa;
}else{
a.right = erase(a.right, K-count(a.left)-1);
setParent(a.right, a);
return update(a);
}
}
public static Node get(Node a, int K)
{
while(a != null){
fall(a);
if(K < count(a.left)){
a = a.left;
}else if(K == count(a.left)){
break;
}else{
K = K - count(a.left)-1;
a = a.right;
}
}
return a;
}
public static int index(Node a)
{
if(a == null)return -1;
List<Node> nodes = new ArrayList<Node>();
for(Node x = a;x != null;x = x.parent)nodes.add(x);
for(int i = nodes.size()-1;i >= 0;i--){
fall(nodes.get(i));
}
int ind = count(a.left);
while(a != null){
Node par = a.parent;
if(par != null && par.right == a){
ind += count(par.left) + 1;
}
a = par;
}
return ind;
}
public static Node[] nodes(Node a) { return nodes(a, new Node[a.count], 0, a.count); }
public static Node[] nodes(Node a, Node[] ns, int L, int R)
{
if(a == null)return ns;
nodes(a.left, ns, L, L+count(a.left));
ns[L+count(a.left)] = a;
nodes(a.right, ns, R-count(a.right), R);
return ns;
}
public static String toString(Node a, String indent)
{
if(a == null)return "";
StringBuilder sb = new StringBuilder();
sb.append(toString(a.left, indent + " "));
sb.append(indent).append(a).append("n");
sb.append(toString(a.right, indent + " "));
return sb.toString();
}
public static void main(String[] args) throws Exception
{
long S = System.currentTimeMillis();
is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
out = new PrintWriter(System.out);
solve();
out.flush();
long G = System.currentTimeMillis();
tr(G-S+"ms");
}
private static boolean eof()
{
if(lenbuf == -1)return true;
int lptr = ptrbuf;
while(lptr < lenbuf)if(!isSpaceChar(inbuf[lptr++]))return false;
try {
is.mark(1000);
while(true){
int b = is.read();
if(b == -1){
is.reset();
return true;
}else if(!isSpaceChar(b)){
is.reset();
return false;
}
}
} catch (IOException e) {
return true;
}
}
private static byte[] inbuf = new byte[1024];
static int lenbuf = 0, ptrbuf = 0;
private static 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 static boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
private static int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
private static double nd() { return Double.parseDouble(ns()); }
private static char nc() { return (char)skip(); }
private static 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 static 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 static 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 static int[] na(int n)
{
int[] a = new int[n];
for(int i = 0;i < n;i++)a[i] = ni();
return a;
}
private static 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 static 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) { if(INPUT.length() != 0)System.out.println(Arrays.deepToString(o)); }
}
Problem solution in 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 %dn", 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 %dn", u, ans);
}
}
return 0;
}
Problem solution in 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 %dn", a, indexOf(&NODES[a]));
break;
case 3:
scanf("%d", &b);
printf("element at position %d is %dn", b, kthChild(root, b) -> key);
break;
}
}
return 0;
}