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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Search
  4. King Richard's Knights
  5. Discussions

King Richard's Knights

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 23 Discussions, By:

votes

Please Login in order to post a comment

  • Abzollo
    6 years ago+ 0 comments

    if you're solving this problem in O(N^2), you're not even close. You can solve this problem in O(L*S), but that's still not fast enough, not even for a single test case (except sample). Honestly I just gave up and looked up the editorial. You have to do binary search somewhere. sigh

    8|
    Permalink
  • teksalx
    4 years ago+ 1 comment

    (Here's a rewording of the problem, hope it helps)
    You're given a square matrix of size N. You're expected to successively rotate a number of submatrixes +90 degrees and report the -possibly new- indices of a number of element values.
    Each submatrix is also square, and is a submatrix of the previously rotated one.
    Elements are valued columnwise starting from 0, indices start from 1.

    Input:
    First input line is N (size of matrix).
    Second input line is S (the number of rotations), followed by S lines of space separated integer triplets (a b d) describing one submatrix, so that (a b) are indices of top-left element and d is the size.
    S+2nd input line is L (the number of elements, indices of which will be reported), followed by L lines of values.

    Output:
    L lines of space separated integer pairs corresponding to indices of the values specified in input.

    1|
    Permalink
  • ChinaPupil
    6 years ago+ 0 comments

    lol...

    I want to say that the answer they offered still can not pass case 3 and case 4...

    1|
    Permalink
  • martinpsaier
    6 years ago+ 1 comment

    I bought the test case #3 to look at the input... It's a file bigger than 8 MB. How should it be possible to read in the input, compute and put out the resut in less than 4 seconds? I tried to optimize it, but it's still O(n^2) running time... The only correct test is #1, all the others are out of time. I'm a beginner, what could I do to do it better?

    1|
    Permalink
  • TChalla
    1 year ago+ 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))
    
    0|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature