February 12, 2011
SRM 497 Part 1
DURATION
25 mincategories
Tags
share
Match Summary
Round Overview
Discuss this match
Coders from all over the world participated in SRM 497 with a problem set from multiple authors. In division I, the coders had to solve problems that covered different skills, from analysis to implementation skills. Nothing could stop five of the best coders in the world from submitting solutions for all three problems. At first, it appeared that Petr was not going to win this match because his 550 pointer failed the system tests, but it turned out that there were small difficulties with the results and they had to be fixed. Once the official results were in, it became clear that Petr was going to keep his undefeated status in 2011. Finally, of course, ACRush and tomek also dominated, securing the second and third place.
In division 2, more coders were able to submit and correctly solve all three problems. Newcomer HDU_Lost’s speed in all problems and also two succesful challenges secured a first place with over 300 points of advantage over A.I, lasten and huyuanming11 who were very close together in the remaining podium positions.
Used as: Division Two - Level One:
| Value | 250 |
| Submission Rate | 688 / 844 (81.52%) |
| Success Rate | 537 / 688 (78.05%) |
| High Score | bekzattt for 249.12 points (1 mins 41 secs) |
| Average Score | 177.15 (for 537 correct submissions) |
It is frequently useful to recognize the main variables that we need to find and any possible restrictions in them. In this problem, there are two variables, A and B, that are the boundaries set by a valid filter. Since the filter validates the input found in the size array, then we can tell that it is not necessary to ever have a value of B that is higher than the maximum value found in the array. It is also not necessary to have an A that is smaller than the minimum. The maximum size in the array, is 100 due to the problem’s constraints. Therefore, in this case it was possible to simply try a brute force approach: Iterate through all the possible values of B from 0 to 100, for each of them: try a value of A, from 0 to B. Try each of these pairs (A,B) as a possible filter, if the filter is valid, remember the filter that has the smallest B-A. There are O(Max_Size2) such pairs, for each pair you need O(size.length) steps, the total time complexity for this brute force approach is low enough for the 2 seconds limit.
Instead of the brute force approach, let us try something that requires just a little extra thought, but it may require a little less code. The problem statement asks us to minimize B-A. If we want to minimize B-A, then we need to have as small a B as possible and as large an A as possible. Note that for each size[i] that has outcome[i]==‘A’, the size must be ( A <= size[i] <= B ), because we need the filter to validate it, because of this, A cannot be greater than any of the accepted sizes ( Because then there would be a i such that A is not <= size[i]). Similarly, B cannot be smaller than any of the accepted sizes. If we want to maximize A, and A cannot be greater than any of the acceptedsizes, then we need A to be equal to the maximum accepted size. Similarly, we need B to be equal to the minimum accepted size.
We may now have picked a pair (A,B) that accepts all accepted sizes and is such that B-A is minimal. Note that the filter must also reject all of the rejected sizes. This means that for every rejected size size[i] such that (outcome[i]=‘R’), then either (size[i] < A) or (size[i] > B). Note that increasing A will not be useful because a larger A can only increase the likelyhood that a certain size[i] is < A. Similarly, it is not useful to decrease B. We also do not want to decrease A or increase B, because that would only make the filter unable to validate certain accepted filters (ie:the ones with the minimum and maximum size). In other words, we should not change A and B from the values we found as described in the previous paragraph. It is only necessary to check if the found values of A,B reject all of the sizes that must be rejected. If a rejectedsize is validated by the filter (A,B), then it is impossible to have a valid filter.
The following is a Java implementation of the described algorithm. Note that finding the maximum/minimum and iterating through the rejected sizes are both O(sizes.length).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int[] designFilter(int[] sizes, String outcome) {
// Pick the smallest B-A possible.
// To minimize B-A:
// We need A to be as large as possible
// and B to be as small as possible
int A = Integer.MAX_VALUE;
int B = 0;
for (int i = 0; i < sizes.length; i++) {
// A cannot be larger than the smallest allowed size
// B cannot be smaller than the largest allowed size
if (outcome.charAt(i) == 'A') {
A = Math.min(A, sizes[i]);
B = Math.max(B, sizes[i]);
}
}
// The filter must invalidate all rejected sizes, if
// one of the sizes is validated, then it is not possible
// to have a valid filter:
for (int i = 0; i < sizes.length; i++) {
if (outcome.charAt(i) == 'R') {
if ((sizes[i] >= A) && (sizes[i] <= B)) {
return new int[] {};
}
}
}
return new int[] {
A,
B
};
}
PermutationSignature
Problem Details
Used as: Division Two - Level Two:
| Value | 500 |
| Submission Rate | 392 / 844 (46.45%) |
| Success Rate | 204 / 392 (52.04%) |
| High Score | root2 for 499.73 points (0 mins 39 secs) |
| Average Score | 291.23 (for 204 correct submissions) |
Used as: Division One - Level One:
| Value | 250 |
| Submission Rate | 523 / 551 (94.92%) |
| Success Rate | 443 / 523 (84.70%) |
| High Score | UdH-WiNGeR for 246.93 points (3 mins 10 secs) |
| Average Score | 173.89 (for 443 correct submissions) |
There are a few ways to solve this problem even though most use similar ideas. This time we will try a recursive solution, because it is also helpful to show that there is always a valid permutation.
After some observations we can make some sense of the smaller cases. For example, the result for “D” is straightforwardly {2,1}, the result for “I” is, also easily, {1,2}. We are forgetting of the smallest case of all, even though it is not allowed in the constraints, an empty string “” would be the signature of a permutation of size 1, the only possible such permutation is {1}.
Since we know the results for the smaller cases, we should try to find a way to build the results of the larger cases using the smaller ones as a base. Our new objective is to find a way to, for example, build the result for “ID” using our knowledge about “D”. We know that “D” should have {2,1} as result, once we care about a new letter (The first “I” in " ID"), we are worrying about permutations of 3 elements and not just of 2 elements anymore. Basically, to a permutation of two elements, we must insert a new number. An extra observation to make is that “D” is the signature of {2,1}, but in the case of a permutation of 3 elements, it may also be the signature of {3,1} or {3,2}. We wish to append an element, to either {2,1},{3,1} or {3,2} and we must decide between 1, 2 and 3. We cannot append 3 to {3,1} or {3,2}, it would be an invalid permutation, so, we can only append 3 to {2,1}. But {3,2,1} has signature “DD”, not “ID”. We should try appending 2 to {3,1}, or 1 to {3,2} (Note that there is only one permutation for each of the values we can try to insert), the resulting permutations {2,3,1} and {1,3,2} both have a signature equal to “ID”, but we are also interested in the lexicographically first one, so we will pick {1,3,2}. The result for “ID” is therefore {1,3,2}.
We need a fast way to build the new permutations for each possible value of the first element, using the result for the smaller signature as a base. Let us now try to build the result for “DID”. We know that the lexicographically first permutation for “ID” is {1,3,2}, we need to form the permutations for each of the four (1,2,3 or 4) elements that we could put at the beginning of the new permutation. The permutations are : {1,3,2} (for 4), {1,4,3} (for 2), {1,4,2} (for 3) and {2,4,3} (for 1). The key is to see in this case that the way to generate them using {1,3,2} as a base is to simply use the picked value X, and increase the values inside the permutation by 1 in case they are >= X. For example, if we want to use X=2 as the first element, the remaining elements change from {1,3,2} to {1,4,3}. This is akin to merely sliding the numbers >= X to make space for X in the new permutation. So, for “DID” we have four permutations available that will have a signature “ID” for the last three elements: {1,2,4,3}, {2,1,4,3}, {3,1,4,2} and {4,1,3,2}. But we are interested in signature “DID” so the first element must be greater than the second, thus {1,2,4,3} is not valid. Of the three valid permuations we pick the lexicographically first one, therefore the result for signature “DID” is: {2,1,4,3}.
We are only interested in the lexicographically-first valid permutation. For now we can use the current logic to find them, just try all possible numbers from 1 to n (size of the permutation), generate the left side of the permutation using the result we found for the suffix of the signature. And of all the n permutations generated, consider only the valid ones and pick the lexicographically first one. But it is possible to further simplify the problem. To show the idea, we will consider signature “IDID”. We know the result for “DID” (2,1,4,3}, and since we are interested in permutations of n=5 elements, then we can tell that there will be 5 derivate permutations: {1,3,2,5,4}, {2,3,1,5,4}, {3,2,1,5,4}, {4,2,1,5,3} and {5,2,1,4,3}, note that all of them are valid for …“DID”, so when we want to check for validity we only need to worry about the first character of the larger signature: “I” . Another thing is that there is only one permutation for each starting element, so in regards to checking for the lexicographically first permutation, we just need to pick the smallest valid first element. Therefore, in this case, we need to pick the smallest first element such that the second element of the permutation will be greater than it (Because the first character of the signature is “I”). That element is 1. Tthe result for “IDID” is then {1,3,2,5,4}. As a rule of thumb, when the first character of the signature is “I” then we should always pick 1 for the first element of the permutation. It will always be possible to pick 1 because we will always be able to increment the values for all the elements in the permutation we found for the signature suffix, including the first element (so it will always be greater than 1) and 1 is the lowest possible value. Therefore, when the signature begins with “I” and 1 is picked for the first element, the permutation will be the lexicographically first valid one.
If the rule for signatures that begin with “I” is to always pick 1 for the first element, what should we do for signatures that begin with “D”? We still need the smallest first element that yields a valid permutation, but this time the first element must be greater than the second element. Let us give the name next to the permutation that we know is the result for the suffix of the signature. (For example, if “DDID” is the signature, the suffix is “DID” and its result next = {2,1,4,3}.). We call the result permutation res. The first element res[0] simply has to be greater than next[0], that way, when next[0] is moved to the result permutation (as res[1]), it will not be increased, so res[0] will be greater than res[1]. Therefore, we want the smallest element that is greater than next[0]. Since we are dealing with integers, this element is (next[0]+1). As a new rule of thumb, when the first character in the signature is “D”, always pick (next[0]+1) for the first element. It will be the smallest valid first element, and it is always possible to do it (if all elements >= (next[0]+1) in the permutation are incremented, they will all still be <= n).
We can put both rules together: Since there is always a possible decision in regards to what element to pick as the first in the result then there will always be a valid permutation. The decision is simple and only requires us to know the result next for the suffix of the signature. Once the first element is decided, we can use the result next to find the values of the remaining elements. All of this is enough to implement a solution. Note that for each instance of the recurrence, we only need to generate next once (recurse the function on a smaller case), so there is no branching in the recurrence and the only signatures that are sent to the function are those that are suffixes to the original one, this means that the function is going to get called O(n) times. In each of the O(n) times the function is called, we will need a O(n) loop to add the elements in next and increment them accordingly. Therefore, the total time complexity is O(n2). Finally, the base case, is the smallest signature function: an empty string “” for which we found the result to be {1}.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public int[] reconstruct(String signature) {
int n = signature.length() + 1;
if (n == 1) {
/* Base case */
// Empty signature, the result is {1}:
return new int[] {
1
};
}
// declare the res array
int[] res = new int[n];
// recurse to find the next array
// which is the result permutation for the suffix
// of the signature.
int[] next = reconstruct(signature.substring(1));
// Pick the necessary value of res[0]:
res[0] = (signature.charAt(0) == 'D') ? (next[0] + 1) : 1;
// Place the next values in the result array,
// Values higher than res[0] must be incremented.
for (int i = 1; i < n; i++) {
res[i] = next[i - 1] + (next[i - 1] >= res[0] ? 1 : 0);
}
return res;
}
An alternative solution based on the bubble sort can be constructed in this way. Start with the permutation “1234…N”, where N is one greater than the signature length. Then simply swap pairs of elements from left to right such that they satisfy the signature. For example:
“123456789”, “DDIDDDDD”
becomes
“231567894”
after the first pass (“2” swaps with “1”, then “3” swaps with “1”, then “4” does not swap with “1”, etc.). Note that both “1” and the final element (“4”) are now in their correct locations. Each subsequent pass will sort at least one more element into its final position. You can either perform N-1 passes or call the swapping function recursively until no swaps have been made.
There is a O(n) solution for this and the solution is very simple .It is just brute force .Just go through the code you will understand it.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
vector < int > PermutationSignature::reconstruct(string s) {
vector < int > v;
int cur = 1, n = s.size() + 1;
for (int i = 0; i < s.size(); i++) {
int cnt = 0, tmp;
while (cnt + i < s.size() && s[cnt + i] == 'D')
cnt++;
tmp = cur + cnt;
for (int j = i; j <= i + cnt; j++) {
v.push_back(tmp);
tmp--;
}
cur += cnt + 1;
i = i + cnt;
}
if (s[sz(s) - 1] == 'I')
v.push_back(cur);
return v;
}
MakeSquare
Problem Details
Used as: Division Two - Level Three:
| Value | 1000 |
| Submission Rate | 90 / 844 (10.66%) |
| Success Rate | 19 / 90 (21.11%) |
| High Score | z-unit for 892.88 points (10 mins 5 secs) |
| Average Score | 671.52 (for 19 correct submissions) |
When solving a problem, it is sometimes better to try a different perspective than the one provided in the statement. The challenge of turning a string into a square string is actually complicated, because there are many different places in which you can remove , add or replace characters, making the state space very large. Simple bruteforce or a BFS will not work inside the time limit (there may be 50 characters in the string) and the prospect of using dynamic programming or something greedy is not convincing. So, how about, instead of seeing the problem as turning a string into a square string, we modify it a little first.
A square string is one that can be formed by concatenating two equal strings. So, how about, instead of turning a original string into a square, we try to generate the two strings themselves? We generate two strings called roots and if the roots are equal, we concatenate them together and make a square string. When generating the roots, we may or may not use characters from the original string. There are some conditions:
Moving characters around is not a legal operation in the original problem. Therefore, the characters from the original string must keep their original order. Since the characters already exist in the string, without a modification of order, it costs nothing to add characters from the string to either of the roots.
Removing characters from the original string is allowed. This means we are allowed to ignore certain characters from the original string and not add them to the roots. However, removing characters has a cost equal to 1. Therefore, for every character in the original string that is not added to one of the roots, the cost increases by 1.
Adding new characters is also possible, but each character you add costs 1. Therefore, it is possible to add new characters that do not exist in the original string to the roots, but for each of these new characters, the cost increases by one.
It is also possible to replace characters. This will translate to taking a character from the original string and adding a different character to one of the roots, also with cost 1.
When adding characters from the original string, note that it is not legal to add the same character twice (it is possible that there are two equal characters, but it is not possible to add the same character from the same position twice). Once a character is added to one root, it cannot be added to the other.
Also, as mentioned before, the order of the characters that come from the original string is important, but in this regards, we need to consider something. The two roots are simply the two halves of the square string into which we are converting the original one, then in a way there will be two roots, one on the left side of the string and one on the right side. Because of this, the characters inside one of the roots, will keep a certain order in relation to the characters in the other. This basically means that the characters we add to the left root, cannot intersect with the characters we add to the right root. For example, image (A) shows a valid way to add characters from the original string to the roots and image (B) an invalid one:
The move in figure (B) is invalid because the orange ‘a’ that was moved to the right root came before the blue ‘t’ that was added to the left root. As a new condition, all the characters added to the left root must be in a position earlier than all of the characters added to the right root. And all of the characters added to the right root must originally be after all of the characters added to the left root. This new rule has it that the original string should actually be split in two parts, so that the characters that are added to the left root can only come from a left area of the original string and the ones that are added to the right may only come from the remaining right area of the original string. Then a new problem is to decide how to split the original string between the right and left parts, but this is not so difficult, we can just iterate through all the possible sizes leftLimit of the left part (from 0, to N, where N is the length of the string), then the left side of the string will consist of the first leftLimit characters of the string, and the right part will consist of the remaining N-leftLimit characters. For each of these choices of leftLimit, we need to find the minimum cost to make two equal roots, and the final result is the minimum of them all. The variable is called leftLimit because it will act as a limit between the left and right sides of the string.
Our new problem has become to turn two different sides of a string into two equal roots by following the rules described above, and to find the minimum cost of doing so. In order to do this, imagine that we begin with two empty roots. These two roots are initially equal to each other, and we need them to stay equal to each other. For each of the available characters in both sides, we either need to remove them or add them to the appropriate root (possibly replacing them first). Initially, we will have two variables (x,y) pointing to the beginning of each of the sides of the string. x=0, y=leftLimit . We need to reach a point in which every character in both sides of the string has either been added, ignored (removed) or replaced, and when his point is reached, the roots must still be equal. This base case would be (x=leftLimit) and (y=N), in other words, when x reaches the end of the left side and y reaches the end of the right side, if we can assume that the roots are equal, then there is nothing else to do and the cost of doing nothing is 0. If it begins to sound like a recurrence, it is completely intentional. So, our recurrence F takes two arguments (x,y) which are pointers to positions in each of the halves, and we can assume that the roots are currently equal. We need to find what to do with the remaining (leftLimit-x) characters in the left side and the (N - y) characters in the right side. We can add, replace or remove those characters, but the roots must stay equal. Imagine that somewhere in the recurrence we have two arguments (x,y), there are some possibilites:
If x=leftLimit and y=n, then as we mentioned, the end of both sides has been reached, the roots are equal and there is no character left to treat, the remaining cost of creating two equal roots is 0.
If x<leftLimit and y<n, then there are characters left to treat in both sides of the string. However, assume that s[x] was equal to s[y], we could add each of those characters to the roots, the roots would stay equal (because we just added the same character to them), and both pointers will be incremented (x+1,y+1), the total cost of taking this decision would be equal to F(x+1,y+1).
If the characters were different, we can still add both characters to the roots, but in order to make the roots remain equal, one of the characters must be modified to be equal to the other, this has a cost equal to 1. The total cost of this decision would be equal to : (1 + F(x+1,y+1) ).
Another possible choice is to just decide to ignore the character s[x]. This does not modify the roots, so they stay equal. But ignoring (deleting) characters has a cost. The cost of this decision is: (1 + F(x+1,y) ).
Similarly, we can ignore s[y]. The cost of this decision is: (1 + F(x,y+1) ).
It is also possible to add a new character that does not come from the original string. If we add this new character to the left root, we would need to add another character to the right root, and they should be equal, since we can pick any character we want for the one we are adding, we can decide that it is equal to s[y]. We will then also add s[y] to the right root to keep the roots equal. Adding a new character that was not in the original string has a cost. The total cost is (1 + F(x,y+1) ).
Similarly, we can add a whole new character to the right root, but this will also require us to add s[x] to the left root. The cost is (1 + F(x+1,y) ).
Note something about the previous four decision: It is strange, but at least when only calculating the cost the operations of removing (ignoring) a character and adding a completely new character will yield the same result.
The minimum cost among all of the described decisions will be the minimum cost for F(x,y). Note that in every sub-problem, we either call F(x+1,y), F(x,y+1) or F(x+1,y+1), so the recurrence is acyclic which makes it friendly to dp. There are a maximum of N possible values for X and a maximum of N possible values for Y, so there are in total less than N*N different states in this recurrence. This makes the recurrence appropriate for the use of dynamic programming. We will implement it by memoization of each of the results for the recurrence. In total, the complexity of this dynamic programming implementation is O(N2), do not forget that we will be doing it inside a loop that checks for all values of leftLimit, so the whole algorithm will have cubic complexity O(N3), since the size is at most 50, it should do well under the time limit. A c++ implementation follows:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
using namespace std;
class MakeSquare {
public: string s;
int n,
leftLimit;
int mem[51][51];
int rec(int x, int y) {
int & res = mem[x][y];
if (res == -1) {
res = 1000000;
if (x == leftLimit && y == n) {
// the strings are equal and
// there are no characters left.
res = 0;
} else if ((x < leftLimit) && (y < n)) {
if (s[x] == s[y]) {
//Two equal characters found in
//both pointers, we can match them
res = rec(x + 1, y + 1);
} else {
//The different characters, turn
//one into the other, cost is 1:
res = 1 + rec(x + 1, y + 1);
}
}
//delete the left character:
//(or insert a character to the right side)
if (x < leftLimit) {
res = std::min(res, 1 + rec(x + 1, y));
}
//delete the right character:
//(or insert a character to the left side)
if (y < n) {
res = std::min(res, 1 + rec(x, y + 1));
}
}
return res;
}
int minChanges(string S) {
this - > s = S;
n = s.size();
int res = 1000000;
// pick the leftLimit
for (leftLimit = 0; leftLimit <= s.size(); leftLimit++) {
memset(mem, -1, sizeof(mem));
res = std::min(res, rec(0, leftLimit));
}
return res;
}
};
CssRules
Problem Details
Used as: Division One - Level Two:
| Value | 550 |
| Submission Rate | 118 / 551 (21.42%) |
| Success Rate | 55 / 118 (46.61%) |
| High Score | ACRush for 389.36 points (20 mins 4 secs) |
| Average Score | 255.53 (for 55 correct submissions) |
It is clear that there will be two separate sub-problems here. The first sub-problem is to parse the input into a format that can be processed. The second is to find an algorithm that can calculate the minimum number of CSS rules. In this editorial, the former sub-problem is going to be explained first and the implementation issue will be described later. During the match, it may be better to tackle both almost simultaneously. The reason is that it is very helpful to understand what the solution actually needs to use before coding the parsing; But it may also a good idea to begin the implementation before the overall idea for the main algorithm is found, then ideas about the real problem may come while debugging the implementation of the parser.
Minimizing the number of CSS rules
There are three things that we will need about each tag: The name of the tag, the style color of the tag, and the children of the tag. We do not need the id, because we are only interested in the total number of CSS rules, not in actually writting them, and when deciding to color a certain tag, we will not need to specifically use the id, but we may just use the index or pointer to the tag in memory inside our solution. We will need the name, because the second type of CSS rules affects only the tags with a certain name. Anyway, each tag may or may not have children tags, whom may on their part have children of their own. But a children is never going to be shared between two tags, nor is a tag going to be a children of one of its children or grand children. This means that the input may be represented as a tree - A forest, actually, because there may be many tags in the top level, and each of them will be a root to a new tree. Since implementation depends on us, we can plan ahead and assume that the result of the parser will be a list of trees. Each tag will be a node in one of the trees (possibly the root), and each of these nodes will hold the tag name and color as part of its information, and also a list of children nodes (which will be represent children tags).
A note about the colors, there are only seven of them: black, blue, gray, green, red, white, yellow. This is a fairy low number which will be useful later. They are also all strings, but strings are not very useful here, so, we should assume that our parser will instead assign a number from 0 to 6 to each of the colors, and the nodes in our forest will each have one of those numbers.
Another note, this time about overriding rules: “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.”. This does not mean it should be difficult to decide the order in which to add the rules. There are two kinds of CSS rules, one applies to only one tag, and the other to all of its strict descendants. Because of this, it will never be helpful to apply a CSS rule for a descendant before applying all the rules of any of its ascendants. If the ascendant’s rule does not affect the descendant, then the relative order between them does not matter. If the ascendant’s CSS rule affects the descendant, then the descendant’s rule will be entirely cancelled by the ascendant’s rule and it will be the same as not adding the descendant’s rule at all. The order in which CSS rules are added is then to always add the rules of the ancestors before the descendants.
There are four CSS rules in total that we can make for each tag. The first kind of rule, is the one that determines only the color of the tag itself. The second kind of rule, affects the color of all of the tag’s strict descendants of a given name and there are three tag names in total: b, u and i. So, let us visit one of the roots. For this root, we will be forced to add the first kind of rule, because the root must be colored and it does not have any ancestor. We will make a decision about whether to add a strict descendant CSS rule for tags b, u, i, and the colors of each of the rules. After picking a color for each of the tag names (or deciding not to change the color), we must calculate the number of rules that the root’s descendants will need. Each of the children of the root will be affected by a list of 3 colors (one for b, another for u, and one for i), which tags of that name will be assume to have. It is possible for the children to add a new descendant rule that will override the root’s color choice for its descendants. But if the color of one of the children, as determined by the root’s rules is not the one the children wants, then it will need to override its own color by making a type #1 CSS rule.
A way to see the situation is to consider it as a recurrence. The recurrence will take a node, and three colors, the ones assigned for u, b and i by the node ‘s ancestors. When evaluating the node, if the color as determined by its ancestors does not match the color it needs, it will need a type #1 CSS rule, increasing the number of rules by 1. Then it has to be decided whether to create new rules for colors b, i, and u of the ancestors. This will require three nested loops, to pick each of the 8x8x8 triples of decisions to make (do not change color, or use one of the 7 available colors). After the colors are picked, the recurrence will need to call itself for each of the node’s children, to calculate the children’ costs given the current tuple of decisions. The children’ costs plus the number of rules added is the cost of the decision triple. We need to pick the minimum cost of them all.There are 2500 characters in the input, and a tag (node) will take at least 32 characters (The smallest tag is: <b id='x' style='color:red'></b>), then there will be at most 2500 / 32 ~= 78 nodes. There are 8x8x8 possible color arguments. So the maximum number of states is 78888, we can use memoizationto evaluate each state exactly once. In each of the states, we are using a 888 loop, for the decisions, and inside the loop we iterate through all the children of the nodes. We can consider that each edge will be visited once per 8x8x8 tuple, so in total there will be about 888888*(78 + number of edges) steps, the number of edges is O(nodes), because it is a tree we are talking, so we can say that an approximation of the number of steps is 88888878*2 = 40894464. It is not a very large number, but it is not very small either. Assuming the memoization will be O(1), the execution time of this approach will probably be close to the time limit. Adding some small optimizations (like for example, not picking color decisions that are not useful for the children) the execution time can be cut to ensure that it passes.
There is, however, a way to reduce the execution time, by replacing the 8x8x8 loop with a single loop of size 8. The modification is to add a phase argument to the recurrence. Phase can be one of 4 numbers. 0,1,2 or 3. The idea is that in each of the first three phases, we will decide what color to use for only one of the tag names, and in phase 3, we will sum the children’ cost. In phase 0, decide what to do about the children’ b color, then call phase 1 storing the new color decision inside the new arguments. In phase 1, decide about the i tag and call phase 2. In phase 2, decide about the u tag, and call phase 3. There are now at most 888478 states for the recurrence, but each state does either a size 8 loop or iterates through the children. So, the total number of steps can be approximated as 319488 which is much lower (about 100 times smaller). The following c++ class will solve the logic of the algorithm. Note that the parsing phase must create the nodes from the input string.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
const int MAX_COLORS = 7;
// The node class, holds information about a tag.
// Each node (tag) may have its children (tags) and it
// is also the class that solves the main problem.
class node {
public: int color; //Style color that is needed by the tag.
char name;
// Instead of storing a node's id separately and using
// it in the memoization array, we have separate memoization
// arrays for each node.
int mem[MAX_COLORS + 1][MAX_COLORS + 1][MAX_COLORS + 1][4];
// Each node will have a list of children-
vector < node * > child;
// Initialize all indexes of the array as -1
node() {
memset(mem, -1, sizeof(mem));
}
// It is c++ and we are using pointers, let us make
// the deconstructor release the children.
~node() {
for (int i = 0; i < child.size(); i++) {
delete child[i];
}
}
// The memoized recurrence:
// (a,b,c) hold the colors assigned by the ancestors to
// tags of that color.
// a holds the color assigned for b
// b holds the color assigned for i
// c holds the color assigned for u
//
// If the color is -1, it means it was not assigned yet.
//
int solve(int a, int b, int c, int phase = 0) {
int & res = mem[a + 1][b + 1][c + 1][phase];
// -1 means the state has not been evaluated before
if (res == -1) {
res = 0;
// Since phase 0 occurs before changing the
// ancestor's colors, we should consider the
// cost of forcefull changing the color for the
// current tag in this phase.
if (phase == 0) {
// If the color is different than the
// one assigned by the ascendants, increase
// cost by 1
switch (name) {
case 'b':
res += (a != color) ? 1 : 0;
break;
case 'i':
res += (b != color) ? 1 : 0;
break;
case 'u':
res += (c != color) ? 1 : 0;
break;
}
}
int aux = 1000000;
if (phase == 3) {
//Sum all of the children' costs:
aux = 0;
for (int x = 0; x < child.size(); x++) {
aux += child[x] - > solve(a, b, c, 0);
}
} else {
// In each of the first three phases we
// pick a color, but the phases change
// the tag name to which the color is picked
for (int i = -1; i < MAX_COLORS; i++) {
int na = a, nb = b, nc = c;
int newrule = 0;
// phase 0, assigns b's color
if (phase == 0) {
na = (i == -1) ? a : i;
newrule = (na != a) ? 1 : 0;
// phase 1, assigns i's color
} else if (phase == 1) {
nb = (i == -1) ? b : i;
newrule = (nb != b) ? 1 : 0;
// phase 2, assigns u's color
} else { //phase 2
nc = (i == -1) ? c : i;
newrule = (nc != c) ? 1 : 0;
}
// After picking the color, we need to
// advance to the next phase.
aux = std::min(aux, newrule + solve(na, nb, nc, phase + 1));
}
}
res += aux;
}
return res;
}
};
The parsing subproblem
We need to parse the input xhtml string and generate trees for each of the root tags. The nodes in the trees must hold color and tag name information, so that we can call the actual solution later. We do not need to store the tag’s ids. It is in situations like this in which good knowledge of the language you are using can be very useful. For example, you can use Java’ StringTokenizer class , like theycallhimtom did in his solution. Or even sscanf like kuniavski did in his. Of course, you may also try a more manual implementation. Regardless, the logic usually works as follows.
A tag begins with < , after this, you need to extract the tag name and color from it and skip to the next >. For example, in (<b id='x' style='color:red'> ??? </b>),the main declaration of the tag is enclsed by <…> . After the main declaration, there may be a closing tag, or new tags. To identify the closing tag, just check if the two next characters pointed by the index are “<”, in that case, the tag is closed, and we may stop the loop. Else, we have found a children tag. In this situation, recursion is very useful, we can call a new instance of the tag parser again, to get the children tag (and also any possible children and grandchildren) as a new object, which will be added to the list of children for the top tag that is currently being parsed. Because of this, the main parser method should be able to return the position of the closing tag, so that the major instances are able to skip the just-parsed tag. In this case, c++'s reference arguments are useful because it may be simpler to do this using multiple return values. In implementation-heavy problems like this one, you should always try to support yourself with the language’s library and also plan ahead, it can make the implementation easier. A sample implementation follows, however in this case, I would recommend to find the most comfortable way to implement it, since it will probably vary between coders and languages. The example is mostly to show how recursion can help in this case.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class CssRules {
public:
// Moves x until the next occurrence of character ch in s.
void skipTo(string & s, int & x, char ch) {
while (s[x] != ch) {
x++;
}
}
// Useful to assign integers to each found color:
int colorn;
map < string,
int > colors;
void parseOpen(string & s, int & x, char & name, int & color) {
char id[2500]; //The id is not actually bounded in size.
char scol[10];
sscanf(s.c_str() + x, "<%c id='%[^']' style='color:%[^']'>", & name, id, scol);
// After parsing the name, id, and color, skip until
// beating the > mark.
skipTo(s, x, '>');
x++;
// Convert the color to a integer.
if (colors.find(scol) == colors.end()) {
colors[scol] = colorn++;
}
color = colors[scol];
}
// parse a tag.
node * parse(string & s, int & x) {
node * nod = new node();
// Parse the opening tag.
parseOpen(s, x, nod - > name, nod - > color);
// Until the closing tag is found, parse the
// children tags and save them in the children list:
// (closing tag begins with </)
while ((s[x] != '<') || (s[x + 1] != '/')) {
node * ch = parse(s, x);
nod - > child.push_back(ch);
}
// Skip after the next >
skipTo(s, x, '>');
x++;
return nod;
}
int getMinimalCssRuleCount(vector < string > axhtml) {
string xhtml = accumulate(axhtml.begin(), axhtml.end(), string(""));
colorn = 0;
int x = 0;
int c = 0;
// For each tag we find in the input, create its node
// and calculate the number of rules it will need:
while (x < xhtml.size()) {
node * tag;
tag = parse(xhtml, x);
c += tag - > solve(-1, -1, -1);
delete tag;
}
return c;
}
};