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.
I'm going to try to give some guidence without explaining all the logic on this one. We have 3 fundamental parts to this problem. The hackonacci function (I'll call h() for simplicity), understanding the matrix format, and rotating the matrix.
First: the h() function. This part is pretty easy to get some insight on by building the function literally and testing it with some numbers and trying to see a pattern (if you're timing out, look at memoizing fibonacci functions). It's not a big help, but once you realize that you're testing if h(n) is even or odd, it's easy to see the h(n-2) in the recursive definition can safely be ignored.
Once you find the pattern, you can create a simple function to output even or odd simply based on whan n%(the size of the pattern) outputs. If you're worried, the length of the pattern is not huge.
Second: the value of each cell in the matrix is defined as X if (i*j)^2 fed into the h() function where i, j are the indices is even or Y if it's odd. One important thing to note is that, because multiplication is commutative, cell i,j will equal cell j,i. This actually tells us that this is a symmetric matric.
I recommend building and printing several of these matrices, say up to 20 or so. You'll probably note that the pattern of the matrices also have similarities based on the pattern of the h() function.
Last (and longest): Ok, so now we need to think about rotations... but we can break 90 and 270 degree rotations into a transpose and reflection. Also, since the matrix is symetric, it's equal to its transpose. Also, reflecting vertically will result in the same matrix as reflecting horizontally, meaning that rotating 90 or 270 degrees will result in the same output.
Also, thanks to symmetry, a 180 degree rotation will be the same as reflection along the right to left diagonal.
Now, you should be able to use that to traverse the matrix and compare each cell to its reflection position (either one for 90 or 270).
I recommend testing a lot of numbers this way. You'll probably note a pattern again.
If you don't know how look up how to try and build a polynomial solution to sequences. Last hint: think about the pattern and how two matrices of size n and m s.t. n%(length of sequence) = m%(length of sequence) are similar (ok, one more hint, you'll have to build quite a few polynomials: several for both 180 and 90/270).
This can be solved in O(q) time, once you realize that the even/odd parity of the hackonacci(n) function is periodic, with a prime period.
Print out the (Y/N) pattern of the Hackonacci Matrix for, say n=41 and see what I mean. It's easier to see if you use something like * and . instead of Y and N.
This means you don't need a 2000x2000 array or carry around a huge memoization table for the hackonacci function.
Hint: Do write up the slow, straightforward implementation of the problem statement to give yourself something to compare your optimized output to. The test cases here are pretty thin.
My program works but experts as usual came with refinements. Following two points can speed up the program by 40%:
1) Matrix need not be created explicitly.
2) Two kinds of rotations give identical results.
After doing these improvements, Python3 program runs within 4 sec for the worst case on i7.
No more comments
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
n,q=map(int,input().split()) for _ in range(q): angle=int(input()) angle=angle%360
I'm going to try to give some guidence without explaining all the logic on this one. We have 3 fundamental parts to this problem. The hackonacci function (I'll call h() for simplicity), understanding the matrix format, and rotating the matrix.
First: the h() function. This part is pretty easy to get some insight on by building the function literally and testing it with some numbers and trying to see a pattern (if you're timing out, look at memoizing fibonacci functions). It's not a big help, but once you realize that you're testing if h(n) is even or odd, it's easy to see the h(n-2) in the recursive definition can safely be ignored.
Once you find the pattern, you can create a simple function to output even or odd simply based on whan n%(the size of the pattern) outputs. If you're worried, the length of the pattern is not huge.
Second: the value of each cell in the matrix is defined as X if
(i*j)^2fed into the h() function where i, j are the indices is even or Y if it's odd. One important thing to note is that, because multiplication is commutative, cell i,j will equal cell j,i. This actually tells us that this is a symmetric matric.I recommend building and printing several of these matrices, say up to 20 or so. You'll probably note that the pattern of the matrices also have similarities based on the pattern of the h() function.
Last (and longest): Ok, so now we need to think about rotations... but we can break 90 and 270 degree rotations into a transpose and reflection. Also, since the matrix is symetric, it's equal to its transpose. Also, reflecting vertically will result in the same matrix as reflecting horizontally, meaning that rotating 90 or 270 degrees will result in the same output.
Also, thanks to symmetry, a 180 degree rotation will be the same as reflection along the right to left diagonal.
Now, you should be able to use that to traverse the matrix and compare each cell to its reflection position (either one for 90 or 270).
I recommend testing a lot of numbers this way. You'll probably note a pattern again.
If you don't know how look up how to try and build a polynomial solution to sequences. Last hint: think about the pattern and how two matrices of size n and m s.t. n%(length of sequence) = m%(length of sequence) are similar (ok, one more hint, you'll have to build quite a few polynomials: several for both 180 and 90/270).
This can be solved in O(q) time, once you realize that the even/odd parity of the hackonacci(n) function is periodic, with a prime period.
Print out the (Y/N) pattern of the Hackonacci Matrix for, say n=41 and see what I mean. It's easier to see if you use something like * and . instead of Y and N.
This means you don't need a 2000x2000 array or carry around a huge memoization table for the hackonacci function.
Hint: Do write up the slow, straightforward implementation of the problem statement to give yourself something to compare your optimized output to. The test cases here are pretty thin.
My program works but experts as usual came with refinements. Following two points can speed up the program by 40%: 1) Matrix need not be created explicitly. 2) Two kinds of rotations give identical results. After doing these improvements, Python3 program runs within 4 sec for the worst case on i7.