We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Search
  4. King Richard's Knights
  5. Discussions

King Richard's Knights

Sort 25 Discussions, By:

  • shadymansour19
     + 0 comments

    I just solved this problem, but in a different way than editorial. Time complicity is O(L log S) same as editorial.

    My approach was based on these points:

    1. Let's define the square to be rotated by its top left & button right corners
    2. Let's say top left corner is at index (strtRow, strtCol)
    3. Buttom right corner is at index (endRow, endCol)
    4. If cell (i, j) is inside the square to be rotated, it can be proven that the new index for that cell will be (strtRow - strtCol + j, endCol + strtRow - i)
    5. If cell (i, j) is outside the square to be rotated, it will stay at (i, j)
    6. We can know if a cell is inside/outside the square by assuming it's inside the square and finding its new position. If the result position is inside the square, then the original position is inside the square. Otherwise, it's outside the square.
    7. If cell (i, j) is outside some square, it's definitely outside all its next squares
    8. If cell (i, j) is rotated by some square, it's definitely rotated by all its previous squares
    9. We can take overall effect of each prefix set of rotations using point 4
    10. For every cell to be searched for, find the last rotation contains the target cell, then get final position of that cell
    11. Finding last rotation contains the target call can be done with aid of observations 6 & 7 and binary search

  • bhautik4avenger4
     + 0 comments

    https://zeroplusfour.com/king-richards-knights-hackerrank-solution/

    Here's how I did in all languages Java 8 , C++ , C , Python 3, Python 2.

  • TChalla
     + 0 comments
    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))

  • kochetkov_av
     + 0 comments

    Looks like i've managed to solve this task using idea different from ones author described in editorial.

  • tagliani_gerardo
     + 0 comments

    Java starting resolution code is broken. Check it please

Load more conversations