**
Winner Paulo Uribe
**
(dm1)

Gerrymandering is the process of carving up an electoral district into strange shapes in order to derive a political advantage. The name comes from a cross between the name Gerry (from the early Massachusetts governor Elbridge Gerry) and the elongated shape of a salamander.

For example, suppose, given the following census data for Rectanglia in matrix A, you are told to divide the state into N = 3 districts of equal population.

So 3 people live in square (1,1) and 28 people live in square (3,2). A total of 120 people live in the entire state (it's a small state). Our goal, therefore, is to make three separate districts, each of which is connected, each with a population of 120/3, or 40 people. Voting districts must be contiguous, or connected in the four-neighbor sense (no diagonal connections). Thus, district 1 could not consist solely of square (1,1) and square (2,2).

Here's one way to divide the state.

It's easy to see that this solution, while not unique, can't be improved. We have successfully made sure that each district has exactly 40 people. We would label our districts using the matrix B as shown below.

This result corresponds to the number of people that must be redistributed in order to even out the district population. A result of zero is the best you can do, since no one needs to move (pop_{n} is equal to pop_{total}/N for all districts). The example shown above yields a perfect result of zero.

Suppose instead you partitioned matrix A like so.

so the B matrix looks like this.

In this case, pop_{1} is 3 + 0 + 0 + 0 + 2 + 12 + 10 + 2, or 29. pop_{2} is 12 + 11 + 28, or 51, and pop_{3} is still 40. The result is calculated as follows.

result = 1/(2*120) * ( abs(40 - 29) + abs(40 - 51) + abs(40 - 40) )

or

result = (11 + 11)/240 = 11/120

That is, if we could magically move 11 people from district 2 to district 1, the result would be perfect. And 11, expressed as a ratio of the total population, is 11/120, or 0.0917.

The average result for the entire test suite, along with the associated runtime of your entry, gets passed to our scoring algorithm before returning a final score, according to the equation

We don't publish the values k_{1}, k_{2}, and k_{3}, but they aren't hard to figure out.

The routine that does the algorithmic work is `solver.m`.

function b = solver(a,n) b = n*ones(size(a)); b(1:n) = 1:n;Keep in mind that this function must have the right signature: two input arguments, one output argument. Variable names are unimportant.

function b = solver(a,n)To test this function with the test suite in the zip-file, run

>> runcontest

We also encourage you to discuss your solutions and strategies with others. You can do this by posting to the comp.soft-sys.matlab thread that we've started from our newsreader.

The following are prohibited:

MEX-files

Java commands or object creation

eval, feval, etc.

Shell escape such as !, dos, unix

Handle Graphics commands

ActiveX commands

File I/O commands

Debugging commands

Printing commands

Simulink commands

Benchmark commands such as tic, toc, flops, clock, pause

error, clear

Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest:

**Darkness**- You can't see the code or scores for any of the entries.**Twilight**- You can see scores but no code.**Daylight**- You can see scores and code for all entries.**Finish**- Contest end time.