Endagorion's blog

By Endagorion, 5 years ago, ,

Somehow I don't feel sleepy at all at 6am, which is kinda weird. I wonder if writing an editorial will help.

SquareScores (250)

The standard trick is to use the linearity of expectation: for every substring count the probability that it consists of the same characters, and sums all these probabilities. There are O(n 2) substrings, which is a reasonable amount in the given limitations. However, iterating over all symbols in the substring yields O(n 3) solution, so we should optimize something.

My way was as follows: fix the beginning of the substring, and process all substrings with this beginning altogether. Count q c — the probability that current substring consists only of characters c. If we append one symbol from the right, q c changes in a simple way: if the symbol is a letter x, then all q c with c ≠ x become zeros, while q x does not change; else, if the symbol is question mark, every q c gets multiplies by p c. So, we process all substrings with fixed beginning in O(mn) (where m is the number of different symbols), for a O(mn 2) solution.

Do you have a more effective/simple solution for this problem?

SuccessiveSubstraction (450)

When we open all the brackets, every number adds up with a plus or a minus sign by it. Which configurations are possible? It is not difficult to prove that all possible configurations are as follows: the first number is always a plus, the second is always a minus, while all other numbers with a plus sign form no more than two consecutive segments. So, we just have to find two subsegments of the array with the greatest total sum. There are lots of ways to do it in O(n), the most straightforward (IMO) being DP (how many elements are processed; the number of consecutive segments already closed; is a segment currently open). Simply recalculate the DP after every change in the array, for a solution of O(n 2) complexity.

TwoEntrances (850)

What if there is only one entrance in the tree? The problem becomes a classic one: count the number of topological orderings of rooted tree with edges directed from the root. There is a simple subtree DP solution; also, a closed formula is available: , where n is the total number of vertices, w(v) is the number of vertices in the subtree of v.

Now, two entrances s 1 and s 2 are present. Consider vertices that lie on the path connecting s 1 and s 2 in a tree; every vertex of the path can be associated with a subtree consisting of vertices not on the path. The last vertex to cover will be either s 1 or s 2 (WLOG, assume it's s 1), the second-to-last will be either s 2 or the neighbour of s 1 in the path, etc. The observation is that at any moment there is a consecutive subsegment of the s 1- s 2 path which is covered.

Count dp l, r — the number of ways to cover the subsegment from l-th to r-th vertex in the path with all the hanging subtrees. The number of ways such that the l-th vertex is the last to cover is , where ord l is the number of topological orderings of the subtree of l-th vertex (which can be calculated as described above), t l is the size of this subtree, and T l, r is the total number of vertices in the subtrees of l-th, ..., r-th vertices. The intuition behind this formula is that we independently deal with the segment [l + 1;r] and the l-th subtree, and the last vertex is always the l-th vertex of the path. The number of ways that cover r-th vertex in the last place is obtained symmetrically; dp l, r is simply the sum of those two quantities. The base of DP is clearly dp l, l = ord l.

Clearly, this subsegment DP is calculated in O(n 2), with all the preliminaries being simple DFS'es and combinatorial primitives which also can be done in O(n 2).

• +74

 » 5 years ago, # |   +16 OIerRobbin in my room coded a different solution to 450, which I think is quite cool.He finds the maximum consecutive segment in the data, inverts signs on that segment and then simply finds the maximum consecutive segment again. In case he finds two overlapping segments that way, it is still a valid solution, since one could achieve the same result by choosing two non-overlapping parts.
 » 5 years ago, # |   0 Thanks for this, I didn't see it before, and I had just made a comment on the topcoder editorial about an O(mn) solution — please excuse the (sortof) duplication. Without wildcards, you can move through the string left to right. If you come across an 'a', that gives you +1 for the single character substring, then another +1 if there was an 'a' before it due to the extra 'aa', then another +1 if there was an 'aa' before it, up to a total of n+1 for n matching characters before it. So you can get O(mn) by storing the previous character and a counter for how many in a row that character has been.Dealing with expectation values, the 'previous character' becomes an array of doubles. If an 'a' comes along, you get a score of 1 + previous['a'], previous['a'] gets incremented, all other previous[] go to zero. If '?' comes along, you get a score of +1, a score of previous[i] for all i, and previous[i] gets +1 at a rate of p[i]. I wonder if I can figure out how to post code... double score = 0; double[] previous = new double[26]; for (int i = 0; i < s.Length; i++) { if (s[i] == '?') { score += 1; for (int j = 0; j < 26; j++) { score += previous[j] * p[j]; previous[j] = (previous[j] + 1) * p[j]; } } else { int index = s[i] - 'a'; score += 1 + previous[index]; for (int j = 0; j < 26; j++) { if (j == index) previous[j] += 1; else previous[j] = 0; } } } return score; 
 » 5 years ago, # |   0 How do we care about vertices in subtrees rooted not in [l,r]? We can partially fill some of them.