problem link : Goblet of Fire
Author : Ritesh Gupta
Tester : Shubham Gupta
Editorialist : Rajan Kumar Raj
PreRequisite : Number theory
Problem : You are given with a 3*3 matrix and a integer “k”. You have to find the number of matrices that
satisfies the given condition.

Sum of all the numbers in each row is equal to k

Sum of all the numbers in each column is equal to k

Sum of all the numbers in each diagonal is equal to k

All the numbers in the magic square are in the range of 1 to k (including both)

There should be at least 1 odd number in the matrix.
All the numbers need not be distinct.
Explanation : Let us observe step by step
Observation 1: Let us consider the given matrix
. 1 2 3
1 a b c
2 d e f
3 g h i
Now as we know that sum of each column , row and diagonal is equal to k.
Therefore we make equations from diagonals and 2nd row and 2nd column.
We get:
b+e+h=k
d+e+f=k
a+e+i=k
c+e+g=k
Now adding these equation and arranging in required way we get:
(a+d+g)+(c+f+i)+(b+h+e)+3e=4k
3e=k
e=k/3;
Let n=k/3.
So we can clearly see that proper value of e will exist only if k is divisible by 3.
Observation 2:
In this observation we are first not considering the condition that 1 element of a matrix must be an odd number.
Now let us make a matrix in which value of k is divisible by 3.
. 1 2 3
1 1 x _
2 _ e _
3 _ _ _
Now we know that sum of diagonal is k.
If we make equation and try to find value of x then it will lie between 2n2 and 2n ,i.e., we will get 1 value.
If we update the value of A(1)(1) to 2 then we will get 3 values after solving the equation.
Similarily till n it will increase to 2n1 and then it will start decreasing till it reaches 1.
So the series will be like 1 3 5 . . . . . 2n3 2n1 2n1 . . . . 5 3 1
So our required answer will be n^2+(n1)^2.
Let us denote our obtained answer by G(k).
Observation 3:
Now let us see the case where an odd number must exist in the matrix.
In this case the required answer will be G(k)G(k/2).
This part is left for user interpretation.
Time Complexity : O(1)
Setter Solution :Click here