Problem 42290. GJam 2015 Rd1B: Noisy Neighbors
This Challenge is derived from GJam 2015 Rd 1B: Noisy Neighbors. Fastest completion - 8 minutes.
Determine minimum number of adjacencies for N placed people in an RxC hotel matrix
Input: m, an RxC zeros array; N number of rooms to be filled
Output: NN, minimum number of common walls
Examples: Small Case 1<=R*C<=16, 0<=N<=R*C
[1 1 1;1 0 1;1 1 1] has minimum 8 common walls vs [1 1 1;1 1 1;1 1 0] has 10 common [1;0;0;1] has 0 common walls ones(2,3) has 7 common walls
Theory: The small case can be solved with brute force using vector set with nchoosek followed by processing of convolutions. The large case has 10000 rooms making brute force hopeless.
Additional GJam solutions can be found at Example GJam Matlab solutions. Select Find Solutions, change Language to Matlab. The Test Suite, at the bottom, contains a full GJam Matlab solution.
Solution Stats
Problem Comments
-
1 Comment
There is no need to test all cases. The ideal case is a swiss cheese in which no guest share a wall. Just start filling rooms from there if needed (the only problems is that room filling must follow an order, which makes the code quite large (but repetitive and boring), and there are two base cases for the swiss cheese structure). Maybe it's possible to create a function and decrease code size, but unless you see it at the moment that you are coding it, it would mean loosing too much time during competition when a Ctrl+C, Ctrl+V would be faster (and better than testing all cases).
Solution Comments
Show commentsProblem Recent Solvers10
Suggested Problems
-
101825 Solvers
-
The Hitchhiker's Guide to MATLAB
3301 Solvers
-
Return elements unique to either input
771 Solvers
-
61 Solvers
-
204 Solvers
More from this Author308
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!