Connection Status:
Competition Arena > Worms

Worms

2018 TCO Semi 2 · 2018-11-14 · by misof

2018 TCO Semi 2 · 2018-11-14 · by misof · Dynamic Programming, Math
Class Name: Worms
Return Type: int
Method Name: count
Arg Types: (vector<string>)
Problem Statement

Problem Statement

A worm on a square grid is a sequence of one or more squares such that each square other than the first one is either directly below or directly to the left of the previous one. Examples of worms: 

....a.   ....   cccccc   .d.
.aaaa.   .b..   c.....   dd.
.a....   ....   c.....   d..
......   ....   ......   ...

Given a rectangle on the grid, a worm decomposition of the rectangle is a set of disjoint worms such that the rectangle is their union.

Jessie had a picture of one particular worm decomposition of a rectangle. She wanted to print it. Sadly, at some point during the process the printer ran out of ink.

You are given the String[] printed representing the original rectangle. The cells that were printed are represented by lowercase English letters ('a'-'z'), the remaining cells are question marks ('?'). Different letters are cells of different worms, same letters are cells of the same worm. (As we only use lowercase letters to describe the worms, the printed part will contain parts of at most 26 worms. The original worm decomposition may have had arbitrarily many worms.)

The printer was printing the cells of the rectangle one at a time, in row major order. Hence, printed will always look as follows:

  • First, there are zero or more elements that contain only letters.
  • Then, there is at most one element that contains some letters followed by some question marks.
  • Finally, there are zero or more elements that only contain question marks.

Count all worm decompositions that match the partially-printed rectangle. Return that count modulo (10^9 + 7).

Notes

  • The letters are only used to encode input. A worm is just a set of squares. Two worms are distinct if they contain a distinct set of squares. Two decompositions are distinct if they contain a distinct set of worms.

Constraints

  • printed will contain between 1 and 50 elements, inclusive.
  • Each element of printed will contain between 1 and 50 characters, inclusive.
  • Each element of printed will contain the same number of characters.
  • printed will have the form described in the statement: first some lowercase letters, then some question marks.
  • There will be at least one worm decomposition that matches printed.
Examples
0)
{"x?",
 "??"}
Returns: 9

The printer only printed a single cell before it ran out of ink. This means that we need to count all possible worm decompositions of the 2x2 grid: the 'x' in the top left cell does not carry any useful information. Here are all nine possible decompositions, ordered by the number of worms: 4 worms: xy zw 3 worms: xx xy xy xy yz xz zz zy 2 worms: xx xy xx xy xy yy yy xy

1)
{"???"}
Returns: 4

Four options: either this was a single worm, or two worms (two possibilities), or three tiny worms.

2)
{"aabb",
 "bbby",
 "bxyy",
 "bxyq",
 "qqqq"}
Returns: 1

A valid and complete worm decomposition.

3)
{"aaa",
 "???"}
Returns: 6
4)
{ "?" }
Returns: 1
133)
{"abccd",
 "eff??",
 "?????"}
Returns: 504

One of the 504 matching worm decompositions is shown below: abccd efffg zzzgg Here is another one: abccd effgd ggggd

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

Coding Area

Language: C++17 · define a public class Worms with a public method int count(vector<string> printed) · 134 test cases · 2 s / 256 MB per case

Submitting as anonymous