King Richard's Knights
King Richard's Knights
+ 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
+ 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.
+ 0 comments lol...
I want to say that the answer they offered still can not pass case 3 and case 4...
+ 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?
+ 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))
Sort 23 Discussions, By:
Please Login in order to post a comment