DMOPC '15 Contest 4 P6 - Alarms - Olympiads Online Judge

DMOPC '15 Contest 4 P6 - Alarms

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 64M

Authors:

Problem type

Library and Archives Canada recently decided to install an alarm system to safeguard the English essays of past generations, and they've hired you to help them.

The Archives may be represented by an $N \times N$ ~N \times N~ matrix, with a cell containing 1 representing an empty room, and 0 representing a wall. Your task is to place exactly $A$ ~A~ alarms in the building so that the essays are maximally safeguarded. Each alarm $i$ ~i~ has a square range of $R_i$ ~R_i~ units around its radius, and you're interested in covering a maximum number of rooms.

There are a couple of restrictions:

no alarm may be placed in a wall
you may only place one alarm per column or row
an alarm's range cannot overlap with the outside of the building
alarm ranges can overlap

Knowing this, what is the maximum number of rooms you can hope to secure?

Input Specification

The first line of input will contain the integer $N$ ~N~ $(1 \le N \le 6)$ ~(1 \le N \le 6)~.
The next $N$ ~N~ lines will each contain $N$ ~N~ space-separated integers, representing one row of the Archives.
The next line of input will contain the integer $A$ ~A~ $(1 \le A \le 6)$ ~(1 \le A \le 6)~.
The final line of input will contain $A$ ~A~ space-separated integers, with the $i$ ~i~-th integer denoting $R_i$ ~R_i~ $(1 \le R_i \le 3)$ ~(1 \le R_i \le 3)~.

Output Specification

A single integer; the maximum number of rooms that may be covered by alarms.

Sample Input

Sample Output

Explanation

You can place the radius $2$ ~2~ alarm at $(1,2)$ ~(1,2)~, and two radius $1$ ~1~ alarms at $(2, 0)$ ~(2, 0)~ and $(3, 1)$ ~(3, 1)~ for a coverage of $10$ ~10~. You are left with one more alarm, but you cannot cover any more rooms without placing multiple alarms on the same row or column.

Comments

0

aeternalis1 commented on Aug. 23, 2017, 8:26 a.m. ← edited →

Clarification

The problem statement states that you need to place exactly $A$ ~A~ alarms; along with the row/column restriction, isn't it possible for certain test cases to be impossible to fulfill? Such as any test case with $A>N$ ~A>N~, or less rooms than alarms.

Edit: Nevermind, I didn't see Xyene's reply to the earlier comment.

-1

jimgao commented on Jan. 12, 2016, 11:46 p.m.

What does it mean exactly by

has a square range of Ri units around its radius

5

d commented on Jan. 12, 2016, 11:11 p.m. ← edited →

4
FatalEagle commented on Jan. 12, 2016, 11:44 p.m. ← edited →
For example, a square range of radius 2 covers

1 1 1 1 1 1 1 1 1

3

Quantris commented on Jan. 12, 2016, 10:11 p.m.

"You can place the radius 2 alarm at (1,2), and two radius 1 alarms at (1,0) and (3,1) for a coverage of 10"

doesn't this break the rule about alarms sharing a row or column: (1,2) vs. (1,0).

(it's also a bit unclear which cell is meant by "(1, 2)")

also, given "Your task is to place exactly A alarms in the building"; sometimes the restrictions make this impossible. Is the answer 0 in that case or are we allowed to use fewer than A alarms (it seems to me that placing 4 alarms while obeying restrictions in the example makes it impossible to cover 10 rooms).

0

Xyene commented on Jan. 12, 2016, 11:35 p.m.

Apologies; while the sample input is not wrong, the explanation does include a typo: the alarm should be placed at $(2, 0)$ ~(2, 0)~ (indexing from top left, from 0) rather than $(1, 0)$ ~(1, 0)~. The final alarm may be placed at $(0, 3)$ ~(0, 3)~ (a solution always exists).

0

Quantris commented on Jan. 12, 2016, 11:52 p.m.

Thanks, makes sense now. I was thinking of the origin at bottom-left (and had a minor bug in my program which was returning 9 at the time).

1

StouffvilleTeam commented on Jan. 12, 2016, 7:53 p.m.

what does it mean:

an alarm's range cannot overlap with the outside of the building

Does it mean the alarm range cannot include wall or go outside the n*n squre?

Thx

1
Xyene commented on Jan. 12, 2016, 7:55 p.m.
It cannot go outside the $N\times N$ ~N\times N~ area. For example, in

1 1 0 0 1 0 1 1 1

you may only place an alarm with $R=2$ ~R=2~ in the center.