Table of Contents
King Richard’s Knights – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ King Richard’s Knights HackerRank Solution
#include <bits/stdc++.h>
using namespace std;
int S,N,L;
typedef complex<int> pt;
struct state {
pt orig;
pt now;
int d,idx;
pt get_at(int x,int y) {
x-=real(now);
y-=imag(now);
int rots=idx%4;
swap(x,y);
for(;rots--;) {
int tmp=x;
x=y;
y=d-tmp;
}
swap(x,y);
return pt(real(orig)+x,imag(orig)+y);
}
bool has(int x,int y) {
return x>=real(orig) && y>=imag(orig) && x<=real(orig)+d && y<=imag(orig)+d;
}
pt rlook(int x,int y) {
swap(orig,now);
idx = 4-(idx%4);
pt ans=get_at(x,y);
idx=4-(idx%4);
swap(orig,now);
return ans;
}
};
vector<state> vs;
int main() {
cin>>N>>S;
vs.push_back({pt(1,1),pt(1,1),N-1,0});
for(int i=1;i<=S;i++) {
int a,b,d; cin>>a>>b>>d;
pt ul=vs.back().get_at(a,b);
pt dr=vs.back().get_at(a+d,b+d);
pt neworig={min(real(ul),real(dr)), min(imag(ul),imag(dr))};
pt newnow={a,b};
vs.push_back({neworig,newnow,d,i});
}
for(auto &st : vs) {
// cout<<st.orig<<" "<<st.now<<" "<<st.d<<" "<<st.idx<<endl;
}
cin>>L;
for(;L--;) {
long long w; cin>>w;
int x=w/N+1;
int y=w%N+1;
int lb=0,rb=S;
for(;lb<rb;) {
int mb=(lb+rb+1)/2;
if(vs[mb].has(x,y)) lb=mb;
else rb=mb-1;
}
pt p=vs[lb].rlook(x,y);
cout<<real(p)<<" "<<imag(p)<<endl;
}
}
Java King Richard’s Knights HackerRank Solution
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
public class Solution {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int s = sc.nextInt();
long[] a = new long[s+1];
long[] b = new long[s+1];
long[] d = new long[s+1];
long[] tln = new long[s+1];
a[0] = 1;
b[0] = 1;
d[0] = n-1;
for (int i = 1; i <= s; i++) {
a[i] = sc.nextInt();
b[i] = sc.nextInt();
d[i] = sc.nextInt();
if (i%4==1) {
tln[i] = tln[i-1]+(a[i]-a[i-1])*n+(b[i]-b[i-1]);
} else if (i%4==2) {
tln[i] = tln[i-1]+((b[i-1]+d[i-1])-(b[i]+d[i]))*n+(a[i]-a[i-1]);
} else if (i%4==3) {
tln[i] = tln[i-1]+((a[i-1]+d[i-1])-(a[i]+d[i]))*n+((b[i-1]+d[i-1])-(b[i]+d[i]));
} else if (i%4==0) {
tln[i] = tln[i-1]+(b[i]-b[i-1])*n+((a[i-1]+d[i-1])-(a[i]+d[i]));
}
}
int l = sc.nextInt();
long[] w = new long[l];
for (int i = 0; i < l; i++) {
w[i] = sc.nextLong();
int low = 0;
int high = s;
while (low != high) {
int mid = (low+high+1)/2;
if (w[i] >= tln[mid] && w[i] < tln[mid]+(d[mid]+1)*n && w[i]%n >= tln[mid]%n && w[i]%n <= (tln[mid]%n)+d[mid])
low = mid;
else
high = mid-1;
}
long off1 = (w[i]-tln[low])/n;
long off2 = (w[i]-tln[low])%n;
if (low%4==0) {
System.out.println((a[low]+off1)+" "+(b[low]+off2));
} else if (low%4==1) {
System.out.println((a[low]+off2)+" "+(b[low]+d[low]-off1));
} else if (low%4==2) {
System.out.println((a[low]+d[low]-off1)+" "+(b[low]+d[low]-off2));
} else if (low%4==3) {
System.out.println((a[low]+d[low]-off2)+" "+(b[low]+off1));
}
}
}
}
Python 3 King Richard’s Knights HackerRank Solution
from __future__ import print_function
try: input = raw_input
except: pass
# i is rows/down, j is cols/across
# Carry out order for a given position
def rotate_clockwise(pos, i, j, width):
(offi,offj) = (pos[0]-i, pos[1]-j)
return (i+offj, j+width-1-offi)
def rotate_cntr_clockwise(pos, i, j, width):
(offi,offj) = (pos[0]-i, pos[1]-j)
return (i+width-1-offj, j+offi)
class Rotation:
def __init__(self,i,j,width,oidx,parent=None):
(self.i,self.j,self.width,self.dom_i,self.dom_j) = (i,j,width,i,j)
if parent is not None:
(posi,posj) = (parent.dom_i+i-parent.i, parent.dom_j+j-parent.j)
for i in range(oidx % 4):
(posi,posj) = rotate_cntr_clockwise((posi,posj), parent.dom_i, parent.dom_j, parent.width)
posi -= width-1 # get top right corner
self.dom_i = posi
self.dom_j = posj
def in_domain(self,pos):
return (pos[0] >= self.dom_i and pos[0] < self.dom_i+self.width and
pos[1] >= self.dom_j and pos[1] < self.dom_j+self.width)
# pos must be in the domain of this rotation (dom_i,dom_j)->(dom_i+w,dom_j+w)
# after rotation, pos is within rectangle (i,j)->(i+w,j+w)
# oidx is the index of this rotation, used to calculate number of rotations
def map_pos(self,pos,oidx):
# assert pos[0] >= self.dom_i and pos[0] < self.dom_i+self.width
# assert pos[1] >= self.dom_j and pos[1] < self.dom_j+self.width
(offi,offj) = (pos[0]-self.dom_i, pos[1]-self.dom_j)
(offi,offj) = (self.i+offi, self.j+offj) # apply new offsets
for i in range((oidx+1) % 4):
(offi,offj) = rotate_clockwise((offi,offj), self.i, self.j, self.width)
# assert offi >= self.i and offi < self.i+self.width
# assert offj >= self.j and offj < self.j+self.width
return (offi,offj)
def __str__(self):
fields = [str(x) for x in [self.i,self.j,self.width,self.dom_i,self.dom_j]]
return "Rotation("+",".join(fields)+")"
N = int(input())
S = int(input())
# for each order, calculate the final offset and number of rotations
rots = []
p = None
for s in range(S):
(a,b,d) = ( int(x) for x in input().split(' ') )
# if d > 0:
rot = Rotation(a-1,b-1,d+1,s,p)
rots.append(rot)
p = rot
# for i in range(len(rots)): print(i,rots[i])
def find_last_rotation(l,pos):
if not l[0].in_domain(pos): return None
if l[-1].in_domain(pos): return len(l)-1
(s,e) = (0,len(l)-1)
while s <= e:
mid = int((s+e)/2)
if l[mid].in_domain(pos):
if not l[mid+1].in_domain(pos): return mid
else: s = mid+1
else: e = mid-1
return s
def knight_to_coord(posidx, N):
return (int(posidx / N), posidx % N)
def get_knight_final_pos(knight, N, orders):
pos = knight_to_coord(knight, N)
oidx = find_last_rotation(orders, pos)
if oidx is not None: pos = orders[oidx].map_pos(pos, oidx)
return pos
L = int(input())
for l in range(L):
knight = int(input())
pos = get_knight_final_pos(knight, N, rots)
print(pos[0]+1, pos[1]+1)
# Print full board
# M = [ [ 0 for y in range(x,x+N) ] for x in range(0,N*N,N) ]
# for i in range(0,N*N):
# pos = get_knight_final_pos(i, N, rots)
# print("#knight",i,"=",pos)
# M[pos[0]][pos[1]] = i
# print("m:")
# for r in M: print(' '.join([ '%2i' % (x) for x in r ]))
Python 2 King Richard’s Knights HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
def add((a,b),(c,d)):
return a+c, b+d
def sub((a,b),(c,d)):
return a-c, b-d
def rot((i,j)):
return j,-i
def rotk(k,x):
for it in xrange(k):
x = rot(x)
return x
def trans((k,d),x):
return add(rotk(k,x),d)
def compose((k,d),(K,D)):
return k + K & 3, trans((k,d),D)
def inv((k,d)):
k = -k & 3
return k, rotk(k^2,d)
def contains((c0,c1),p):
return c0[0] <= p[0] <= c1[0] and c0[1] <= p[1] <= c1[1]
n = input()
s = input()
transes = [None]*(s+1)
corners = [None]*(s+1)
transes[0] = 0, (0,0)
corners[0] = (0,0), (n-1,n-1)
for i in xrange(s):
a,b,d = map(int, raw_input().strip().split())
a -= 1
b -= 1
itr = inv(transes[i]); i += 1
ncorns = [trans(itr,x) for x in [(a,b),(a,b+d),(a+d,b+d),(a+d,b)]]
transes[i] = i & 3, sub((a,b), rotk(i & 3, ncorns[3]))
corners[i] = min(ncorns), max(ncorns)
for qq in xrange(input()):
x = input()
p = x/n, x%n
L = 0
R = s+1
while R - L > 1:
M = L + R >> 1
if contains(corners[M],p):
L = M
else:
R = M
ans = trans((transes[L]),p)
print "%s %s" % add(ans,(1,1))
C King Richard’s Knights HackerRank Solution
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <inttypes.h>
#include <string.h>
int main()
{
int64_t N, S, L;
int64_t * command, *initialArea, *searchArea;
scanf ( "%lld", &N );
scanf ( "%lld", &S );
command = ( int64_t * ) malloc ( 3 * S * sizeof ( int64_t ) );
initialArea = ( int64_t * ) malloc ( 3 * S * sizeof ( int64_t ) );
searchArea = ( int64_t * ) malloc ( 4 * S * sizeof ( int64_t ) );
for ( int64_t i = 0; i < S; i++ )
{
scanf ( "%lld%lld%lld", command + i * 3, command + i * 3 + 1, command + i * 3 + 2 );
command[3 * i + 0]--;
command[3 * i + 1]--;
}
initialArea[0] = command[0];
initialArea[1] = command[1];
initialArea[2] = command[2];
searchArea[4 * 0 + 0] = initialArea[3 * 0 + 0];
searchArea[4 * 0 + 1] = initialArea[3 * 0 + 0] + initialArea[3 * 0 + 2];
searchArea[4 * 0 + 2] = initialArea[3 * 0 + 1];
searchArea[4 * 0 + 3] = initialArea[3 * 0 + 1] + initialArea[3 * 0 + 2];
for ( int64_t i = 1; i < S; i++ )
{
int64_t di = command[3 * i + 0] - command[3 * ( i - 1 ) + 0];
int64_t dj = command[3 * i + 1] - command[3 * ( i - 1 ) + 1];
initialArea[3 * i + 2] = command[3 * i + 2];
switch ( i % 4 )
{
case 0:
initialArea[3 * i + 0] = initialArea[3 * ( i - 1 ) + 0] + di;
initialArea[3 * i + 1] = initialArea[3 * ( i - 1 ) + 1] + dj;
break;
case 1:
initialArea[3 * i + 0] = initialArea[3 * ( i - 1 ) + 0] - dj + initialArea[3 * ( i - 1 ) + 2] - initialArea[3 * i + 2];
initialArea[3 * i + 1] = initialArea[3 * ( i - 1 ) + 1] + di;
break;
case 2:
initialArea[3 * i + 0] = initialArea[3 * ( i - 1 ) + 0] - di + initialArea[3 * ( i - 1 ) + 2] - initialArea[3 * i + 2];
initialArea[3 * i + 1] = initialArea[3 * ( i - 1 ) + 1] - dj + initialArea[3 * ( i - 1 ) + 2] - initialArea[3 * i + 2];
break;
case 3:
initialArea[3 * i + 0] = initialArea[3 * ( i - 1 ) + 0] + dj;
initialArea[3 * i + 1] = initialArea[3 * ( i - 1 ) + 1] - di + initialArea[3 * ( i - 1 ) + 2] - initialArea[3 * i + 2];
break;
}
searchArea[4 * i + 0] = initialArea[3 * i + 0];
searchArea[4 * i + 1] = initialArea[3 * i + 0] + initialArea[3 * i + 2];
searchArea[4 * i + 2] = initialArea[3 * i + 1];
searchArea[4 * i + 3] = initialArea[3 * i + 1] + initialArea[3 * i + 2];
}
// for ( int64_t i = 0; i < S; i++ )
// {
// printf ( "(%d, %d, %d) (%d, %d, %d)\n", command[3 * i + 0], command[3 * i + 1], command[3 * i + 2], initialArea[3 * i + 0], initialArea[3 * i + 1], initialArea[3 * i + 2]);
// }
scanf ( "%lld", &L );
while ( L-- > 0 )
{
int64_t w;
scanf ( "%lld", &w );
int64_t i = w / N, j = w % N;
int64_t max = S - 1, min = -1, last = max / 2;
while ( max > min )
{
if ( i >= searchArea[4 * last + 0] &&
i <= searchArea[4 * last + 1] &&
j >= searchArea[4 * last + 2] &&
j <= searchArea[4 * last + 3] )
{
min = last;
int64_t temp = min + max;
if ( temp % 2 == 1 )
{
last = temp / 2 + 1;
}
else
{
last = temp / 2;
}
}
else
{
max = last - 1;
last = ( min + max ) / 2;
}
}
// printf("last = %lld\n", last);
int64_t di = i - initialArea[3 * last + 0];
int64_t dj = j - initialArea[3 * last + 1];
if ( last >= 0 )
{
switch ( ( last + 1 ) % 4 )
{
case 0:
i = di + command[3 * last + 0];
j = dj + command[3 * last + 1];
break;
case 1:
i = dj + command[3 * last + 0];
j = command[3 * last + 1] + command[3 * last + 2] - di;
break;
case 2:
i = command[3 * last + 0] + command[3 * last + 2] - di;
j = command[3 * last + 1] + command[3 * last + 2] - dj;
break;
case 3:
i = command[3 * last + 0] + command[3 * last + 2] - dj;
j = di + command[3 * last + 1];
break;
}
}
printf ( "%lld %lld\n", i + 1, j + 1 );
}
return 0;
}
Leave a comment below
