Connection Status:
Competition Arena > Mountains

Mountains

SRM 567 · 2012-12-13 · by gojira_tc

SRM 567 · 2012-12-13 · by gojira_tc · Brute Force, Dynamic Programming
Class Name: Mountains
Return Type: int
Method Name: countPlacements
Arg Types: (vector<int>, vector<string>)
Problem Statement

Problem Statement

Manao is developing a simple 2-D computer game. The screen of the game is H pixels high and W pixels wide (1 <= H, W <= 50).

Manao is currently working on the background which should be filled with N mountains (1 <= N <= 10). The mountains are numbered from 0 to N-1. The contents of the screen are stored in an array of characters pix where pix[x, y] gives the contents of the pixel at column x, row y. Both indices are 0-based. Columns are numbered left to right and rows are numbered bottom to top. The parts of the screen where the i-th mountain is visible are denoted by digit i. Character '.' means that the corresponding pixel is not covered by any mountains.

The i-th (0-based index) mountain is described by its peak position (X[i], Y[i]), 0 <= X[i] < W, 0 <= Y[i] < H. In order to draw the mountains, the following pseudocode is used:

Fill all elements of pix with '.' characters.
For 0 <= i < N:
  For 0 <= x < W:
    For 0 <= y <= Y[i] - |x - X[i]|:
      pix[x, y] := i + '0'

For example, consider three mountains with peaks at (1, 1), (2, 2) and (4, 1). Once these mountains are drawn on a screen with H = 3, W = 6, the resulting picture will look as follows: 
..1...
.1112.
111222

Manao has recently filled the background with N mountains as described above. After that he wrote down the height of each mountain. Also, for each column he wrote down which mountains were visible at that column. You are given a int[] heights containing N elements. Element i of heights gives the height of the i-th mountain in pixels (which is equal to Y[i] + 1). You are also given a String[] visibility. It contains N elements and each element is W characters long. The j-th character of visibility[i] is equal to 'X' if the i-th mountain was visible at column j of the screen and '-' otherwise. In other words, the j-th character of visibility[i] is equal 'X' if and only if at least one pixel of column j contained digit i after all mountains were drawn.

Count the number of sequences of exactly N mountains that match the information given by heights and visibility. Return this number modulo 1,000,000,009. It is guaranteed that there exists at least one such sequence.

Notes

  • The value of H is not directly given in the input parameters. For the purposes of this problem, you can assume that H is equal to the largest element of heights.

Constraints

  • heights will contain between 1 and 10 elements, inclusive.
  • Each element of heights will be between 1 and 50, inclusive.
  • visibility will contain the same number of elements as heights.
  • Each element of visibility will be between 1 and 50 characters long, inclusive.
  • All elements of visibility will be of the same length.
  • Each element of visibility will consist of 'X' and '-' characters only.
  • At least one sequence of mountains matching the given information will exist.
Examples
0)
{2, 3, 2}
{"------",
 "XXXX--",
 "---XXX"}
Returns: 4

The given information corresponds to the three mountains from the problem statement. Mountains 1 and 2 are uniquely determined. Mountain 0 can have the peak in each column from 1 to 4.

1)
{4, 3, 4}
{"XXXXX--------",
 "----------XXX",
 "----XXXXXXX--"}
Returns: 4

The four possible mountain sequences are: (2, 3), (10, 2), (7, 3) (2, 3), (11, 2), (7, 3) (3, 3), (10, 2), (7, 3) (3, 3), (11, 2), (7, 3) After drawing these sequences, the following pictures are obtained: ..0....2.....      ..0....2.....      ...0...2.....      ...0...2..... .000..222.1..      .000..222..1.      ..000.222.1..      ..000.222..1. 000002222211.      0000022222111      .00002222211.      .000022222111 0000222222211      0000222222211      0000222222211      0000222222211

2)
{13, 2, 3, 2}
{"XXXXXXXXX",
 "-XXX-----",
 "----XXXXX",
 "-----XXX-"}
Returns: 9
3)
{8, 2, 9, 3, 10}
{"X------",
 "-------",
 "------X",
 "-------",
 "XXXXXXX"}
Returns: 98
4)
{20, 20, 20, 20, 20, 20, 45, 50, 49, 50}
{"-------------------",
 "-------------------",
 "-------------------",
 "-------------------",
 "-------------------",
 "-------------------",
 "-------------------",
 "------------XXXXXXX",
 "XXXXXXX------------",
 "XXXXXXXXXXXXXXXXXXX"}
Returns: 973726691

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

Coding Area

Language: C++17 · define a public class Mountains with a public method int countPlacements(vector<int> heights, vector<string> visibility) · 82 test cases · 2 s / 256 MB per case

Submitting as anonymous