### 2007 Canadian Computing Competition, Stage 2

## Day 2, Problem 1: Gerrymandering

Politicians like to get elected. They will do just about anything to get elected. Including changing the rules of the voting: who can vote, where you can vote, when you can vote, etc. One very common practice is called *gerrymandering*, where the boundaries of "ridings" are redrawn to favour a particular candidate (the one doing the redrawing, of course).

Your task is to help determine how to do some simple, linear gerrymandering.

You will be given the information about `N` ridings (2 ≤ `N` ≤ 1,000) where there are candidates from p (2 ≤ `p` ≤ 10) different parties. These `N` ridings are linear, in the sense that they are side-by-side; there are two ridings (on the ends) that have only one adjacent riding, with the rest of the ridings having two adjacent ridings. A picture is shown below for `N` = 4 and `p` = 2 (which is also the sample data):

Riding 1 | Riding 2 | Riding 3 | Riding 4 | |

Votes for Party 1 | 1 | 4 | 1 | 6 |

Votes for Party 2 | 5 | 3 | 2 | 1 |

Note that Riding 1 and Riding 2 are adjacent, Riding 2 and 3 are adjacent, Riding 3 and 4 are adjacent. No other ridings are adjacent.

You have some financial backing that will let you bribe the people in charge of setting the boundaries of ridings: in particular, there is a fixed rate to merge two adjacent boundaries. When you merge two ridings, the votes of the ridings merge together, in the sense that the number of votes of party 1 is the sum of the votes of party 1 in each riding, and likewise for all other parties.

Your task is to merge the minimum number of regions such that the first party (your party!) has a majority of the ridings. Note that to win a riding, the party must have more votes than any other party in that riding. Also note that to have a majority of ridings, if there are `Q` ridings (where `Q` ≤ `N`), then your party has won at least `floor(Q/2)+1`

of the ridings.

### Input

The first line of input will consist of the integer `N`. The second line of input will consist of the integer `p`. The next `N` lines will each contain `p` non-negative integers (where each integer is at most 10,000), separated by one space character. Specifically, the `p` integers on each line are `v1` `v2` ... `vp` where `v1` is the number of votes that party 1 will receive in this riding, `v2` is the number of votes that party 2 will receive in this riding, etc. You may also assume that the total number of voters is less than 2 billion.

### Output

One line, consisting of an integer, which gives the minimum number of ridings that need to be merged in order for the first party to win a majority of ridings. If the first party cannot win, even with any number of mergers, output -1.

### Sample Input 1

`4`

2

1 5

4 3

1 2

6 1

### Sample Output 1

`1`

### Sample Input 2

`3`

3

2 0 1

1 3 0

0 0 1

### Sample Output 2

`-1`

All Submissions

Best Solutions

**Point Value:** 20 (partial)

**Time Limit:** 10.00s

**Memory Limit:** 256M

**Added:** Dec 09, 2008

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

Kiritoon Jan 25, 2017 - 4:01:54 pm UTC Bounds on N