Algorithm


Problem Name: Data Structures - The crazy helix

Problem Link: https://www.hackerrank.com/challenges/helix/problem?isFullScreen=true

In this HackerRank in Data Structures - The crazy helix solutions,

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

  1. The position of a given number
  2. 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;
}
Copy The Code & Try With Live Editor

#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;
}
Copy The Code & Try With Live Editor

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


}
Copy The Code & Try With Live Editor

#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)
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Rooted Tree solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Network administration solution in Hackerrank - Hacerrank solution C, C++, java,js, Python