Challenge: Hackonacci Matrix Rotations
Subdomeniu: Algebra (algebra)
Scor cont: 35.0 / 35
Submission status: Accepted
Submission score: 1.0
Submission ID: 464740734
Limbaj: python3
Link challenge: https://www.hackerrank.com/challenges/hackonacci-matrix-rotations/problem
Cerinta
We define a $hackonacci$ series as follows:
- $hackonacci(n) = 1 \cdot hackonacci(n-1) + 2 \cdot hackonacci(n-2) + 3 \cdot hackonacci(n - 3)$
- $hackonacci(1) = 1$
- $hackonacci(2) = 2$
- $hackonacci(3) = 3$
We define a *Hackonacci Matrix* to be an $n \times n$ matrix where the rows and columns are indexed from $1$ to $n$, and the top-left cell is $(1, 1)$. Each cell $(i, j)$ must contains either the character `X` or the character `Y`. If $hackonacci((i \cdot j)^2)$ is *even*, it's `X`; otherwise, it's `Y`.
Next, we want to perform $q$ queries where each query $i$ consists of an integer, $angle_i$. Each $angle_i$ is a multiple of $90$ degrees and describes the angle by which you must rotate the matrix in the *clockwise* direction. For each $angle_i$, we want to count the number of cells that are different after the rotation. For example, the diagram below depicts the $270°$ rotation of a Hackonacci Matrix when $n = 2$:
As you can see, there are two cells whose values change after the rotation. Note that we filled each initial cell using the Hackonacci formula given above:
- $(1, 1)$: $hackonacci((1 \cdot 1)^2) = hackonacci(1) = 1$
Because this is an odd number, we mark this cell with a `Y`.
- $(1, 2)$: $hackonacci((1 \cdot 2)^2) = hackonacci(4) \\ \Rightarrow 1 \cdot hackonacci(3) + 2 \cdot hackonacci(2) + 3 \cdot hackonacci(1) \\ \Rightarrow 1 \cdot 3 + 2 \cdot 2 + 3 \cdot 1 = 3 + 4 + 3 = 10$
Because this is an even number, we mark this cell with an `X`.
- $(2, 1)$: $hackonacci((2 \cdot 1)^2) = hackonacci(4) \Rightarrow 10$
Because this is an even number, we mark this cell with an `X`.
- $(2, 2)$: $hackonacci((2 \cdot 2)^2) = hackonacci(16) \Rightarrow 296578$
Because this is an even number, we mark this cell with an `X`.
Given the value of $n$ and $q$ queries, construct a Hackonacci Matrix and answer the queries. For each query $i$, print an integer on a new line denoting the number of cells whose values differ from the initial Hackonacci Matrix when it's rotated by $angle_i$ degrees in the clockwise direction.Input Format
The first line contains two space-separated integers describing the respective values of $n$ and $q$.
Each line $i$ of the $q$ subsequent lines contains an integer denoting $angle_i$.Output Format
For each $angle_i$, print a single integer on a new line denoting the number of different cells that differ between the initial matrix and the matrix rotated by $angle_i$ degrees.Constraints
+ $1 \le n \le 2000$
+ $1 \le q \le 10^4$
+ $0 \le angle_i \le 10^5$
+ It is guaranteed that each $angle_i$ is multiple of $90$ degrees.Cod sursa
import sys
# hackonacci(n) parity is periodic with period 7 and odd for n % 7 in {0,1,3,6}.
ODD_MOD = {0, 1, 3, 6}
SQ_MOD = [(i * i) % 7 for i in range(7)]
def build_matrix(n):
mat = [bytearray(n) for _ in range(n)]
jmods = [j % 7 for j in range(1, n + 1)]
for i in range(1, n + 1):
im = i % 7
row = mat[i - 1]
for j in range(n):
m = (im * jmods[j]) % 7
k = SQ_MOD[m]
# 1 for X (even), 0 for Y (odd)
row[j] = 0 if k in ODD_MOD else 1
return mat
def diffs(mat):
n = len(mat)
d90 = d180 = d270 = 0
for i in range(n):
row_i = mat[i]
ni = n - 1 - i
row_ni = mat[ni]
for j in range(n):
v = row_i[j]
nj = n - 1 - j
if v != mat[nj][i]:
d90 += 1
if v != row_ni[nj]:
d180 += 1
if v != mat[j][ni]:
d270 += 1
return d90, d180, d270
def main():
data = sys.stdin.buffer.read().split()
if not data:
return
n = int(data[0])
q = int(data[1])
mat = build_matrix(n)
d90, d180, d270 = diffs(mat)
out = []
idx = 2
for _ in range(q):
a = int(data[idx]) % 360
idx += 1
if a == 0:
out.append('0')
elif a == 90:
out.append(str(d90))
elif a == 180:
out.append(str(d180))
else: # 270
out.append(str(d270))
sys.stdout.write('\n'.join(out))
if __name__ == '__main__':
main()
HackerRank Algebra – Hackonacci Matrix Rotations