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