Connection Status:
Competition Arena > SquareSeries

SquareSeries

TCO11 Qual 1 · 2011-05-07 · by vexorian

TCO11 Qual 1 · 2011-05-07 · by vexorian · Brute Force, Greedy
Class Name: SquareSeries
Return Type: String
Method Name: completeIt
Arg Types: (string, int)
Problem Statement

Problem Statement

Taro and Brus are playing a new game called Square Series. The game involves placing a non-empty sequence of black and white squares following a couple of rules:

  • The first square has side length 1.
  • For i > 1, if the color of square i (1-indexed) is different than the color of square i-1, its side length will be equal to the side length of the previous square plus 1. If the colors are the same, then the side length will be equal to the previous side length minus 1. Note that a side length of 0 would make the shape not a square, so it is not legal to repeat the color after a length 1 square.

Taro wants to prepare new challenges for Brus and would like you to make a program that will generate valid square series such that it matches String pattern and the length of the last square is equal to lastLength. The pattern contains 'W' and 'B' representing white and black squares respectively and exactly one '?' character. To generate a sequence of strings that matches the pattern, replace the '?' character with a (possibly empty) sequence of white and black squares.

Given the pattern and lastLength, if there is no valid sequence of squares that follows the aforementioned rules, matches the pattern and finishes with a square of side length equal to lastLength, then return "..." (quotes for clarity). Otherwise, return the shortest possible sequence that matches the pattern and finishes with a square of the appropriate side length. In case there is more than one sequence with a length equal to the shortest possible, return the lexicographically first of them.

Notes

  • The lexicographically earlier of two Strings of the same length is the one that has the earlier character (using ASCII ordering) at the first position at which they differ.

Constraints

  • lastLength will be between 1 and 100, inclusive.
  • pattern will contain between 1 and 50 characters, inclusive.
  • Each character in pattern will be 'W', 'B' or '?'.
  • pattern will contain exactly one '?' character.
Examples
0)
"W?B"
2
Returns: "WB"

It is possible to replace the '?' character with an empty sequence. The sequence "WB" is the shortest one that matches the pattern and ends with a square of length 2.

1)
"?"
5
Returns: "BWBWB"

Any sequence can match the "?" pattern. "BWBWB" and "WBWBW" are the shortest sequences possible that end with a square of size 5. "BWBWB" is the lexicographically earlier of the two.

2)
"BWBBBBW?WB"
10
Returns: "..."

Every sequence that begins with BWBBBB is invalid because it will require an invalid square of size 0 at position 6 (1-based).

3)
"BWBWBW?WBWBWBW"
15
Returns: "BWBWBWBBWBWBWBWBW"
4)
"WBWBWBWBWBWWBB?W"
1
Returns: "WBWBWBWBWBWWBBBBBBBBBBBWW"
19)
"B?W"
1
Returns: "BWW"

Not "BBW"

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

Coding Area

Language: C++17 · define a public class SquareSeries with a public method string completeIt(string pattern, int lastLength) · 199 test cases · 2 s / 256 MB per case

Submitting as anonymous