Problem 42290. GJam 2015 Rd1B: Noisy Neighbors

Created by Richard Zapor in Community

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

74.19% Correct | 25.81% Incorrect
Last solution submitted on Jan 10, 2019