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
-
Find best placement for ordered dominoes (harder)
309 Solvers
-
Generate a string like abbcccddddeeeee
262 Solvers
-
Multiples of a Number in a Given Range
609 Solvers
-
Sum the numbers on the main diagonal
578 Solvers
-
533 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!