HackerRank The Crazy helix problem solution

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;
}