HackerRank King Richard’s Knights problem solution

In this HackerRank King Richard’s Knights problem solution we have a troop of N*N with knights into battle and all are very organized. the knights are labeled from K0, K1 … KN and arranges in an NxN square formation. first, we need to test the waves of knights and then we need to find the locations of the knights and print then knights row and column locations as two space-separated values on a new line.

Problem solution in Python.

#!/bin/python3

import os
import sys


def identity():
    return [
        [1, 0, 0],
        [0, 1, 0],
        [0, 0, 1],
    ]

def cw(x, y, k):
    return [
        [1, x - y, k + x + y],
        [0, 0, -1],
        [0, 1, 0],
    ]

def ccw(x, y, k):
    return [
        [1, k + x + y, -x + y],
        [0, 0, 1],
        [0, -1, 0],
    ]


# from profiler import line_profile

def multiply(a, b):
    c = [
        [0] * len(b[0])
        for _ in range(len(a))
    ]
    for i in range(len(a)):
        for j in range(len(b[0])):
            for k in range(len(a[0])):
                c[i][j] += a[i][k] * b[k][j]

    return c
# return [
#         a[0][0]*b[0][0] + a[0][1]*b[1][0] + a[0][2] * b[2][0]
#     ]

def multiply_ccw(x, y, k, a):
    return [[
        a[0][i] + (k + x + y) * a[1][i] + (-x + y) * a[2][i]
        for i in range(3)
    ], [
        a[2][i]
        for i in range(3)
    ], [
        -a[1][i]
        for i in range(3)
    ]]

def multiply_cw(x, y, k, a):
    return [[
        a[0][i] + (x - y) * a[1][i] + (k + x + y) * a[2][i]
        for i in range(3)
    ], [
        -a[2][i]
        for i in range(3)
    ], [
        a[1][i]
        for i in range(3)
    ]]


#
# Complete the kingRichardKnights function below.
#
# from profiler import line_profile
#
# @line_profile()
def kingRichardKnights(n, commands, knights):
    new_commands = []

    t = identity()
    for ind, c in enumerate(commands):
        m = multiply([[1, c[0], c[1]]], t)

        new_command = [m[0][1], m[0][2], c[2]]
        if (ind % 4) == 1:
            new_command[0] -= c[2]
        elif (ind % 4) == 2:
            new_command[0] -= c[2]
            new_command[1] -= c[2]
        elif (ind % 4) == 3:
            new_command[1] -= c[2]
        new_commands.append(new_command)

        # t = multiply(ccw(c[0], c[1], c[2]), t)
        t = multiply_ccw(c[0], c[1], c[2], t)

    to_process = {}
    for k in knights:
        i, j = (k // n) + 1, (k % n) + 1

        l = -1
        r = len(new_commands)
        while r - l > 1:
            s = (l + r) // 2
            x, y, k = new_commands[s]
            if (x <= i <= x + k and
                    y <= j <= y + k):
                l = s
            else:
                r = s

        to_process.setdefault(l, [])
        to_process[l].append((i, j))

    ans = {
        k: k
        for k in to_process.get(-1, [])
    }

    t = identity()
    for ind, c in enumerate(new_commands):
        # t = multiply(cw(c[0], c[1], c[2]), t)
        t = multiply_cw(c[0], c[1], c[2], t)
        for k in to_process.get(ind, []):
            m = multiply([[1, k[0], k[1]]], t)
            ans[k] = [m[0][1], m[0][2]]

    result = []
    for k in knights:
        result.append(ans[(k // n) + 1, (k % n) + 1])

    return result

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    # import sys
    # sys.stdin = open('input', 'r')

    n = int(input())
    s = int(input())

    commands = []
    for _ in range(s):
        commands.append(list(map(int, input().rstrip().split())))

    kn = int(input())
    knights = []
    for _ in range(kn):
        knights.append(int(input().strip()))

    result = kingRichardKnights(n, commands, knights)

    fptr.write('n'.join([' '.join(map(str, x)) for x in result]))
    fptr.write('n')

    fptr.close()

Problem solution in Java.

import java.io.*;
import java.util.*;

public class Solution2 {

  static class Drill {
    int x1;
    int y1;
    int z;

    int num = 1;
    long sumX;
    long sumY;

    int invX1;
    int invY1;
    long invSumX;
    long invSumY;
    int inNum = 0;

    Drill(int x1, int y1, int z) {
      this.x1 = x1;
      this.y1 = y1;
      this.z = z;
      this.sumX = x1 - y1;
      this.sumY = (long) y1 + z + x1;

      this.invX1 = x1;
      this.invY1 = y1;
      this.invSumX = (long) y1 + z + x1;
      this.invSumY = y1 - x1;
    }

    @Override
    public boolean equals(Object obj) {
      Drill c = (Drill) obj;
      return x1 == c.x1 && y1 == c.y1 && z == c.z;
    }

    void addInvRotation(Drill c) {
      sumX += c.sumY;
      sumY -= c.sumX;
      num = (num + c.num) % 4;

      long tinvSumX = invSumX;
      inNum = (c.inNum + 1) % 4;
      int x = invX1;
      int y = invY1;
      invX1 = (int) c.invSumX;
      invY1 = (int) c.invSumY;
      switch (inNum) {
        case 0:
          invSumX = c.invSumX + invSumX;
          invSumY = c.invSumY + invSumY;

          invX1 += x;
          invY1 += y;
          break;

        case 1:
          invSumX = c.invSumX - invSumY;
          invSumY = c.invSumY + tinvSumX;

          invX1 -= y + z;
          invY1 += x;
          break;

        case 2:
          invSumX = c.invSumX - invSumX;
          invSumY = c.invSumY - invSumY;

          invX1 -= x + z;
          invY1 -= y + z;
          break;

        case 3:
          invSumX = c.invSumX + invSumY;
          invSumY = c.invSumY - tinvSumX;

          invX1 += y;
          invY1 -= x + z;
          break;
      }
    }

    boolean check(int x, int y) {
      return (x >= invX1 && x <= invX1 + z && y >= invY1 && y <= invY1 + z);
    }
  }

  static Drill findDrill(Drill[] commands, int sCount, int x, int y) {
      if (!commands[0].check(x, y)) {
          return null;
      }
      int last = sCount - 1;
      if (commands[last].check(x, y)) {
          return commands[last];
      }
      int first = 0;
      while (first < last - 1) {
          int pivot = first + (last - first) / 2; 
          if (commands[pivot].check(x, y)) {
              first = pivot;
          } else {
              last = pivot;
          }
      }

    return commands[first];
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());

    st = new StringTokenizer(br.readLine());
    int s = Integer.parseInt(st.nextToken());

    Drill[] commands = new Drill[s];
    int sCount = 0;
    for (int i = 0; i < s; i++) {
      st = new StringTokenizer(br.readLine());
      int x = Integer.parseInt(st.nextToken()) - 1;
      int y = Integer.parseInt(st.nextToken()) - 1;
      int z = Integer.parseInt(st.nextToken());

      if (z == 0) {
        continue;
      }

      Drill c = new Drill(x, y, z);
      if (sCount == 0) {
        commands[0] = c;
        sCount++;
      } else {
        c.addInvRotation(commands[sCount - 1]);
        if (commands[sCount - 1].equals(c)) {
          commands[sCount - 1] = c;
        } else {
          commands[sCount] = c;
          sCount++;
        }
      }
    }

    st = new StringTokenizer(br.readLine());
    int l = Integer.parseInt(st.nextToken());
    for (int i = 0; i < l; i++) {
      st = new StringTokenizer(br.readLine());
      long item = Long.parseLong(st.nextToken());
      int x = (int) (item / n);
      int y = (int) (item % n);

      Drill c = findDrill(commands, sCount, x, y);

      if (c != null) {
        long mx = c.sumX;
        long my = c.sumY;
        switch (c.num) {
          case 0:
            mx += x;
            my += y;
            break;

          case 1:
            mx += y;
            my -= x;
            break;

          case 2:
            mx -= x;
            my -= y;
            break;

          case 3:
            mx -= y;
            my += x;
            break;
        }
        x = (int) mx;
        y = (int) my;
      }
      bw.write((x + 1) + " " + (y + 1) + "n");
    }

    bw.newLine();
    bw.close();
    br.close();
  }
}

Problem solution in C++.

#include <fstream>
#include <iostream>
#define NMX 500005
#define fin cin
#define fout cout

using namespace std;

struct nod {
  long long a, b, d;
};
nod v[NMX];

long long s1[NMX], s2[NMX];
long long n, m1, m2, t;

int init() {
  // sg i%2

  s1[1] = (-v[1].b + 1 + v[1].a - 1);
  s2[1] = v[1].d + 1 - (-v[1].a + 1) + 1 + v[1].b - 1;

  long long x, y;

  for (int i = 2; i <= m1; i++) {
    x = s1[i - 1];
    y = s2[i - 1];

    x = x - v[i].a + 1;
    y = y - v[i].b + 1;

    s1[i] = y;
    s2[i] = v[i].d + 1 - x + 1;

    s1[i] += (v[i].a - 1);
    s2[i] += (v[i].b - 1);
  }

  return 0;
}

pair<long long, long long> cord(long long x) {
  std::pair<long long, long long> aux;

  aux.first = (x / n) + ((x % n) != 0);
  aux.second = (((x % n) == 0) * n) + (x % n);

  return aux;
}

int solve(pair<long long, long long> aux) {
  long long st, dr, mid, sol = -1;

  st = 1;
  dr = m1;

  while (st <= dr) {
    mid = (st + dr) >> 1;

    if (v[mid].a <= aux.first) {
      if (v[mid].a + v[mid].d < aux.first)
        dr = mid - 1;
      else {
        if (v[mid].b <= aux.second) {
          if (v[mid].b + v[mid].d < aux.second) {
            dr = mid - 1;
          } else
            sol = mid, st = mid + 1;
        } else
          dr = mid - 1;
      }
    } else
      dr = mid - 1;
  }

  return sol;
}

pair<long long, long long> verif(int pz, pair<long long, long long> aux) {
  int ps;

  if (pz & 1) {
    ps = (pz - 1) >> 1;

    if (ps & 1) {
      return make_pair(s1[pz] - aux.second, s2[pz] + aux.first);
    } else
      return make_pair(s1[pz] + aux.second, s2[pz] - aux.first);
  } else {
    ps = pz >> 1;

    if (ps & 1) {
      return make_pair(s1[pz] - aux.first, s2[pz] - aux.second);
    } else {
      return make_pair(s1[pz] + aux.first, s2[pz] + aux.second);
    }
  }

  return make_pair(0, 0);
}

int fnd(pair<long long, long long> aux) {
  int st, dr, mid, sol = -1;

  st = 1;
  dr = m1;

  pair<long long, long long> aux1;

  while (st <= dr) {
    mid = (st + dr) >> 1;

    aux1 = verif(mid, aux);

    if (v[mid].a <= aux1.first && aux1.first <= v[mid].a + v[mid].d &&
        v[mid].b <= aux1.second && aux1.second <= v[mid].b + v[mid].d) {
      st = mid + 1;
      sol = mid;
    } else
      dr = mid - 1;
  }

  return sol;
}

int main() {
  //   ifstream fin ("test.in");
  //   ofstream fout ("test.out");

  fin >> n;

  fin >> m1;

  for (int i = 1; i <= m1; i++) {
    fin >> v[i].a >> v[i].b >> v[i].d;
  }

  init();

  fin >> m2;

  std::pair<long long, long long> aux, aux1, aux2;

  int ps;

  while (m2--) {
    fin >> t;

    t++;

    aux = cord(t);

    int pz = fnd(aux);

    if (pz == -1) {
      fout << aux.first << " " << aux.second << "n";

      continue;
    }

    aux1 = verif(pz, aux);

    fout << aux1.first << " " << aux1.second << "n";
  }

  return 0;
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
int inside(int a,int b,int d,int x,int y);
int command[200000][3],action[200000][6];

int main(){
  int N,S,L,y,l,h,m,a1,a2,b1,b2,c1,c2,i;
  long long x;
  scanf("%d%d",&N,&S);
  for(i=0;i<S;i++){
    scanf("%d%d%d",&command[i][0],&command[i][1],&command[i][2]);
    command[i][0]--;
    command[i][1]--;
    if(i){
      a1=action[i-1][0];
      b1=action[i-1][1];
      c1=action[i-1][2];
      a2=action[i-1][3];
      b2=action[i-1][4];
      c2=action[i-1][5];
    }
    else{
      a1=b2=1;
      b1=c1=a2=c2=0;
    }
    action[i][0]=a2;
    action[i][1]=b2;
    action[i][2]=c2-command[i][1]+command[i][0];
    action[i][3]=-a1;
    action[i][4]=-b1;
    action[i][5]=command[i][2]-(c1-command[i][0])+command[i][1];
  }
  scanf("%d",&L);
  while(L--){
    scanf("%lld",&x);
    y=-1;
    l=0;
    h=S-1;
    while(l<=h){
      m=(l+h)/2;
      a1=x/N;
      b1=x%N;
      if(m){
        a1=x/N*action[m-1][0]+x%N*action[m-1][1]+action[m-1][2];
        b1=x/N*action[m-1][3]+x%N*action[m-1][4]+action[m-1][5];
      }
      if(inside(command[m][0],command[m][1],command[m][2],a1,b1)){
        y=m;
        l=m+1;
      }
      else
        h=m-1;
    }
    l=x/N;
    h=x%N;
    if(y!=-1){
      l=x/N*action[y][0]+x%N*action[y][1]+action[y][2];
      h=x/N*action[y][3]+x%N*action[y][4]+action[y][5];
    }
    printf("%d %dn",l+1,h+1);
  }
  return 0;
}
int inside(int a,int b,int d,int x,int y){
  return x>=a && x<=a+d && y>=b && y<=b+d;
}