Problem 803. Twist 'n' Match
Given n and m, construct an n-by-n matrix a such that a, when rotated 90 degrees and compared with itself, matches itself in exactly m places.
The number of matches m is calculated as follows:
m = nnz(rot90(a)==a)
Your answer a is clearly not unique. It must only meet the criteria stated above.
Examples:
Input n = 2, m = 1 One possible output: a = [ 1 2 1 3 ]
Input n = 3, m = 7 One possible output: a = [ 0 1 1 1 1 1 1 1 1 ]
Solution Stats
Problem Comments
-
7 Comments
A lot of solutions don't work with something like n=5 and m=0
Not at all...
For n-by-n matrix, m=1 if n is odd number.
ur problems are really interesting
Thanks Asif!
This problem has some issues because some pairs (n,m) do not have a solution. For instance, it is impossible to find a matrix such that m = n^2 -1 since a rotation pivot does not move. Moreover, there are floor((n^2)/4) cycles of numbers, and when we match the cycle beginning with its end, it creates two matches. It is possible to do some manipulations to have an m greater than n^2 - floor((n^2)/4), but not always.
can you give an example of a matrix before and after?
This is a great problem that suffers from poor test cases.
Solutions tend to fall into three categories:
Random
Approaches that fail for some n and m
Approaches that are correct
The random problem could be fixed with a large array (n>500) and moderate m value (100,000). This would also eliminate a lot of the inefficient O(n^4) solutions. (Really they are O(m*n^2), but m can vary between 0 and n^2.)
The second problem could be solved with a test case that steps through a variety of m values, like n=100, m=[1:5000].
For reference, my own code runs n=10000;m=9000000; in about 5 seconds, as it is O(m). It also runs n=100, m=[1:5000] in about 5 seconds without failing. I really wish I could easily compare it to other solutions but the answers are simply full of bad solutions.
Solution Comments
Show commentsProblem Recent Solvers74
Suggested Problems
-
3815 Solvers
-
17048 Solvers
-
496 Solvers
-
400 Solvers
-
Number of Even Elements in Fibonacci Sequence
1262 Solvers
More from this Author50
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!