Connection Status:
Competition Arena > MiningGoldHard

MiningGoldHard

SRM 610 · 2013-12-22 · by rng_58

SRM 610 · 2013-12-22 · by rng_58 · Dynamic Programming
Class Name: MiningGoldHard
Return Type: int
Method Name: GetMaximumGold
Arg Types: (int, int, vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

You are a goblin miner. Your job is to mine gold.



Picture yourself located in a mine. The mine can be seen as a rectangular grid of (N+1) times (M+1) cells. Rows are numbered 0 through N, columns 0 through M.



You will work in the mine for several days. You can choose the cell where you will work today (on day 0). On each of the next days, you can either stay in the cell where you were on the previous day, or you can move to some other cell - within some limits that are explained below.



Whenever somebody discovers gold in the mine, each goblin profits! Your profit is N + M, minus your Manhattan distance from the cell where the gold was discovered. Formally, if the gold is discovered at (a, b) and you are located at (c, d), your profit is N + M - |a-c| - |b-d|, where || denotes absolute value.



You are given the ints N and M. You are also given two int[]s: event_i and event_j. Both will contain the same number of elements. Assume that for each valid k, there will be exactly one gold discovery on day k: in the cell (event_i[k], event_j[k]).



Finally, you are given two more int[]s: event_di and event_dj. Both will contain the same number of elements, and this number of elements is one fewer than the number of elements in event_i. The elements of these int[]s are the restrictions on your movement between days.



More precisely, for each k, between days k and k+1 your row coordinate can change by at most event_di[k], and your column coordinate can change by at most event_dj[k]. In other words, if you were in the cell (a, b) on day k, you can be in the cell (c, d) on day k+1 if and only if |a-c| <= event_di[k] and |b-d| <= event_dj[k].



Compute and return the maximum total profit you can get by correctly choosing the cells where you work on each day.

Constraints

  • N and M will be between 1 and 1,000,000, inclusive.
  • event_i will contain between 1 and 1,000 elements, inclusive.
  • event_j will contain the same number of elements as event_i.
  • The number of elements in event_di will be one fewer than the number of elements in event_i.
  • event_dj will contain the same number of elements as event_di.
  • The elements of event_i will be between 0 and N, inclusive.
  • The elements of event_j will be between 0 and M, inclusive.
  • The elements of event_di will be between 0 and N, inclusive.
  • The elements of event_dj will be between 0 and M, inclusive.
Examples
0)
3
3
{1}
{1}
{}
{}
Returns: 6

Gold will be discovered today in the cell (1, 1). Your optimal strategy is to work there today.

1)
3
3
{0, 2}
{0, 2}
{1}
{1}
Returns: 10

Gold will be discovered in the cell (0, 0) today and in the cell (2, 2) tomorrow. Note that you cannot move directly from (0, 0) to (2, 2), because both the difference in rows and the difference in columns is too great. One optimal strategy is to work in the cell (0, 0) today and in the cell (1, 1) tomorrow. Your profit today will be 6, tomorrow it will be 4, thus the total profit is 6+4 = 10.

2)
4
2
{1, 4, 4}
{1, 2, 0}
{1, 1}
{1, 1}
Returns: 15
3)
6
6
{0, 2, 1, 5, 6, 4}
{4, 3, 1, 6, 2, 0}
{2, 3, 1, 5, 6}
{2, 4, 0, 5, 1}
Returns: 63
4)
3
4
{2, 3, 2, 0}
{0, 1, 4, 4}
{3, 3, 2}
{2, 1, 1}
Returns: 26

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

Coding Area

Language: C++17 · define a public class MiningGoldHard with a public method int GetMaximumGold(int N, int M, vector<int> event_i, vector<int> event_j, vector<int> event_di, vector<int> event_dj) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous