Connection Status:
Competition Arena > Coversta

Coversta

SRM 660 · 2015-05-01 · by subscriber

SRM 660 · 2015-05-01 · by subscriber · Brute Force
Class Name: Coversta
Return Type: int
Method Name: place
Arg Types: (vector<string>, vector<int>, vector<int>)
Problem Statement

Problem Statement

There is a rectangular field divided into a grid of n rows by m columns of unit square cells. Each cell (i, j) has some strategic value which is an integer between 0 and 9, inclusive. You are given these values as a String[] a where each a[i][j] is a digit between '0' and '9', inclusive.

It is possible to build stations in some cells. A station built in a cell covers some set of cells. You are given the offsets of those cells as int[]s x and y. More precisely, for each valid k, a station in the cell (i, j) covers the cell (i + x[k], j + y[k]) if a cell with those coordinates exists. Note that it may be the case that a station in (i, j) does not cover the cell (i, j).

Your task is to place two stations into two distinct cells. The total strategic value of the two stations is the sum of strategic values of all cells that are covered by at least one of the stations. Return the largest possible total strategic value of the two stations.

Notes

  • The two stations must be built in two distinct cells of the given rectangular array. It is not allowed to build the stations at coordinates that are outside the given array.

Constraints

  • n will be between 2 and 100, inclusive.
  • m will be between 2 and 100, inclusive.
  • a will contain exactly n elements.
  • Each element of a will contain exactly m characters.
  • Each character in a will be a digit ('0'-'9').
  • x will contain between 1 and 10 elements, inclusive.
  • x and y will contain the same number of elements.
  • Each element in x will be between -(n-1) and (n-1), inclusive.
  • Each element in y will be between -(m-1) and (m-1), inclusive.
  • The pairs (x[k], y[k]) will be distinct.
Examples
0)
{"11",
 "11"}
{0,0}
{0,1}
Returns: 4

A station at (i, j) covers the cells (i, j) and (i, j+1). The optimal solution is to place the two stations at (0, 0) and (1, 0).

1)
{"11",
 "11"}
{0,1}
{0,1}
Returns: 3

Here a station at (i, j) also covers (i+1, j+1). One optimal solution is to place the two stations at (0, 0) and (0, 1). The first station also covers the cell (1, 1).

2)
{"15",
 "61"}
{0}
{0}
Returns: 11

In this test case each station only covers its own cell. The optimal solution is to build the two stations in the two most important locations.

3)
{"151",
 "655",
 "661"}
{0,0,-1}
{0,1,0}
Returns: 33
4)
{"303",
 "333",
 "000"}
{-1,-1}
{-1,1}
Returns: 12

Note that in this test case the offset (0, 0) is not among the offsets (x[k], y[k]).

5)
{"0000000",
 "1010101"}
{-1,-1}
{-1,1}
Returns: 0

The stations must be built on some cells of the given field. They cannot be built outside the field.

Submissions are judged against all 157 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Coversta with a public method int place(vector<string> a, vector<int> x, vector<int> y) · 157 test cases · 2 s / 256 MB per case

Submitting as anonymous