Problem 803. Twist 'n' Match
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 Solvers69
Suggested Problems
-
15047 Solvers
-
653 Solvers
-
How many trades represent all the profit?
583 Solvers
-
594 Solvers
-
1227 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!