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 Solvers76
Suggested Problems
-
2463 Solvers
-
Calculate the Hamming distance between two strings
323 Solvers
-
Calculate the Number of Sign Changes in a Row Vector (No Element Is Zero)
693 Solvers
-
4976 Solvers
-
559 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!