CssRules

SRM 497 · 2010-11-01 · by Mike Mirzayanov

SRM 497 · 2010-11-01 · by Mike Mirzayanov · Dynamic Programming

Show categories

Class Name: CssRules

Return Type: int

Method Name: getMinimalCssRuleCount

Arg Types: (vector<string>)

Problem Statement

In this problem we will use the terms XHTML and CSS. They do not match the real-world XHTML and CSS standards exactly. Read the problem statement to clarify the meanings of these terms in the problem context.

You are given a String[] xhtml. Concatenate elements of xhtml to get a single string formatted as tags. We use BNF to describe tags formally.

tags ::= tag | tag tags
tagContent ::= EMPTY | tags
tag ::= <TAG id='ID' style='color:COLOR'>tagContent</TAG>

Where

EMPTY means an empty string,
TAG is one of the strings "b", "u", "i", which are called tag names.
ID means unique non-empty tag identifier containing only lowercase letters,
COLOR is one of the following seven standard colors: "black", "blue", "gray", "green", "red", "white", "yellow".

The tags in tagContent are called strict descendants of the surrounding tag.

We will say that each tag is assigned the specified color. For example, if tags = "", then the tag with id='x' is assigned the color white, and the tags with id='y' and id='z' are assigned the color red.

You decided to extract the information about assigned colors to CSS rules. Each CSS rule looks like "selector {color:COLOR;}" and assigns a specific color to one or more tags. In this problem we will accept only two types of selectors:

"#id" â means that CSS rule will be applied to the tag with the given id (example, "#x").
"#id tagName" â means that CSS rule will be applied to all tags with the specified tag name which are the strict descendants of the tag with the given id (example, "#x u").

CSS rules are applied in the order they are given, and it is possible for some later rules to override earlier rules for certain tags.

Return the minimal number of CSS rules you need to assign the proper color to each tag.

Constraints

xhtml will contain between 1 and 50 elements, inclusive.
Each element of xhtml will contain between 1 and 50 characters, inclusive.
The concatenation of all elements of xhtml will satisfy the grammar given in the problem statement and conditions given after it.

Examples

{""}
Returns: 1

Use only the rule "#x {color:red;}".

{"","",
 "",""}
Returns: 2

Use two rules "#x {color:red;}" and "#x b {color:red;}".

{"",
"",
"",
"",
"",
"",
"",
""}
Returns: 3

{"",
"",
"",
"",
"",
"",
"",
""}
Returns: 4

{"", ""}
Returns: 2

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

Coding Area

Language: C++17 · define a public class CssRules with a public method int getMinimalCssRuleCount(vector<string> xthml) · 124 test cases · 2 s / 256 MB per case