Connection Status:
Competition Arena > SkyscraperCounting

SkyscraperCounting

2022 TCO Parallel 1A · 2022-04-14 · by misof

2022 TCO Parallel 1A · 2022-04-14 · by misof · Dynamic Programming
Class Name: SkyscraperCounting
Return Type: int
Method Name: count
Arg Types: (string)
Problem Statement

Problem Statement

There are N skyscrapers built in a row. The bases of all N skyscrapers all stand on one line that goes from the west to the east.

Each skyscraper has between 1 and N floors, inclusive. No two skyscrapers have the same number of floors.


An observer is looking at the row of skyscrapers from an observation point that is far to the west from all of them. For this observer, some skyscrapers are at least partially visible while others are completely invisible. More precisely, a skyscraper floor is visible to the observer if and only if no skyscraper to the west of this one has a floor of the same height.


Below is one sample scene. Arrows ("->") indicate the direction in which we look at the skyscrapers (west is on the left of the figure). There are seven skyscrapers, each shown as one column of 'X's and 'O's. Floors visible to the observer are shown as 'O', floors hidden behind other skyscrapers are shown as 'X'. 


->                   O
->                   O  X
->          O        X  X
->          O  X     X  X
->    O     X  X     X  X
->    O     X  X  X  X  X
->    O  X  X  X  X  X  X
=============================

You are given the String visibility with N characters. For each skyscraper, from the west to the east, this String contains either the character 'O' (uppercase oh) or the character 'X'. The character 'O' represents a skyscraper with some visible floors, the character 'X' a skyscraper with no visible floors.

For the sample scene shown above, visibility = "OXOXXOX".


In other words, visibility tells you what the scene with skyscrapers looks when viewed from above. For each skyscraper, from the left to the right, you are told whether its topmost floor is 'O' (visible from the west) or 'X' (hidden behind another skyscraper when looking from the west).


Count all permutations of skyscrapers that correspond to the given String visibility. Return that count modulo (10^9 + 7).

Constraints

  • visibility will have between 1 and 100 characters, inclusive.
  • Each character in visibility will be either 'O' or 'X'.
Examples
0)
"OXXXX"
Returns: 24

We can deduce that the leftmost skyscraper must be the tallest one (5 floors). Each of the 4! = 24 orders of the other four skyscrapers works.

1)
"OXOXXOX"
Returns: 72

This input corresponds to the figure in the problem statement. The skyscrapers shown in the figure have heights {3, 1, 5, 4, 2, 7, 6}, and this is one of the 72 permutations of heights that produce the given visibility pattern. Some of the other permutations with the same visibility pattern: {3, 1, 5, 2, 4, 7, 6} {2, 1, 5, 3, 4, 7, 6} {4, 3, 6, 5, 1, 7, 2}

2)
"XOXOXO"
Returns: 0

No such permutations: the westmost skyscraper is always visible.

3)
"OXXXXXXXXXXXXXO"
Returns: 227020758

Remember to compute the answer modulo 10^9 + 7.

4)
"OXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
Returns: 104379182

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

Coding Area

Language: C++17 · define a public class SkyscraperCounting with a public method int count(string visibility) · 96 test cases · 2 s / 256 MB per case

Submitting as anonymous