July 12, 2017 2017 TCO Algorithm Round 2B Editorials

TCO17Algorithm Round 2B Editorials are now published. Special thanks to Egor for the editorial and overview of TCO17 Algorithm Round 2B.
Round 2B presented penultimate opportunity to qualify to round 3. 40 more contestants seized that opportunity with dotory1158, _pperm and kuniavski in top 3. Meanwhile in the first parallel round of this TCO Petr won with a huge margin.
 
2017 TCO Algorithm Round 2B – Division I, Level One DengklekGaneshAndChains
In this problem you are given some chains with letters on them, you need to cut parts of the given length out of them (with condition that each chain may be used exactly once) and compose string out of them. Your target is to make this string lexicographically maximal.
There are two possible approaches to this task. First you can compose message step by step without strictly assigning chains to corresponding part. For each new part and each chain you need to check if you can compose previously constructed message without using this chain (using matching algorithm). For implementation refer to Petr’s solution.
Another approach is for each chain to find lexicographically maximal shift and then apply kind of a greedy algorithm – sort all chains in decreasing order, go left to right and then for given part take the chain with maximal number among those not taken already that would produce same string of given length as chain with minimal number among those not taken. See qwerty787788’s solution for implementation details.
 
2017 TCO Algorithm Round 2B – Division I, Level Two  – DengklekGaneshAndTree
Here you are given a rooted tree and each vertex is labeled with letter. You want to change some letters from lowercase to uppercase so that:
If 2 vertices are connected by edge and corresponding labels are same ignoring case, then they should be in the same case.
On each level of the tree there should be at least one uppercase letter.
The question is how many different ways is there to do so.
First if there is connected component of vertices with same letter and at least one of those letters are in uppercase we need to convert all letters in this component to uppercase. For each entirely lowercase component we can either convert it to uppercase or not. For each such component we would store minimal and maximal level of vertices in it. We would also mark levels that are guaranteed to have uppercase letter.
Now we would sort all lowercase components by minimal level and resort to dynamic solutions with state (k = first k levels are accounted for and has uppercase letter, n = first n lowercase components are processed and either left lowercase or converted to uppercase). For details on transitions you can look up my solution.
 
2017 TCO Algorithm Round 2B – Division I, Level Three  – DengklekGaneshAndDetention
In this problem you are given description of process of tossing coin and turning lamps on and off and you need to calculate expected number of lamps turned on.
Main insight into this problem is that expect value of sum of several random variables is sum of expected values of those variables even if they are not independent. We would process rooms from 1 to N as Dengklek enter them and we would calculate current answer, probability that Dengklek flipped tails even number of times so far, expected number of turned off lamps from first to current room if Dengklek flipped tails even number of times so far and the same expected value if he flipped tails odd number of times.
For details on transitions see rng_58’s solution.