TCO hasn’t really been drawing the crowds this year – another relatively low turn out again for R1C. Only 815 people registered out of 2500 available slots, 750 to advance (in theory), but again the positive score requirement kicked in and only 622 will advance as a result. So including byes there is only ~2150 people advancing to round 2. The problems were pretty easy this time round, although problem 2 wore a pretty good disguise. I think I could have solved all 3.
Q1) In a given 2xN grid, no two filled in cells are touching by edge or corner. Without clearing any of the existing filled in cells, what is the maximum number of filled in cells that can be without any 2 touching by edge or corner?
A1) So this problem doesn’t look that difficult, but it becomes trivial once you realize that in a 2xN grid, if no two filled cells can touch by edge or corner, there is no change in restriction if you move every existing filled cell to the first row, and delete the second row entirely. Obviously only at most one can be filled in any column, and if it is, both of its neighbouring columns have to be empty.
Once the problem is reduced to 1xN, its trivially a greedy left to right fill in while both neighbours aren’t filled in – then count how many are filled in.
Q2) Given a rooted tree and defining a path as being a sequence of one or more distinct vertexes where consecutive elements in the sequence are connected by an edge, determine the maximum number of paths that you can select at once, such that no element of any one path is an ancestor of any element in any other.
A2) Key here is that a path is a sequence of one or more vertexes. But every vertex you add to a path can only decrease the number of other paths that could be selected such that there is no ancestor commonality. Therefore the whole paths thing can be disregarded, the question is just how many vertexes can you select such that none are a parent of any others.
Given a non leaf node in a tree, if it is selected, none of its (direct or indirect) children can be selected. So if it has more than one direct child, it is obviously better to replace it with its children instead. If it does have only one child replacing it with its child doesn’t make anything worse, but it does potentially lead to a further replacement if there a branching factor greater than 1 anywhere in its indirect children. Ultimately this means there is no point selecting anything other than leaf nodes. Leaf nodes also cannot possibly be an ancestor of any other leaf node or vice versa, so the problem reduces down to counting the leaf nodes in the tree.
Q3) In a list of boolean values, its ‘value’ is equal to the number of distinct subsections which are entirely made of alternating 1’s and 0’s. A subsection of length 1 is considered to trivially ‘alternating’. For a given n and k determine how many possible lists of boolean values of length n have ‘value’ k.
A3) This problem is clearly the hardest of the 3, but it has a fairly obvious dynamic program style solution. A sequence of length i ending with alternating section of length j, with existing value v, can either be extended to i+1 with alternating length 1 with value v+1, or length i+1, alternating length j+1 with value v + (j+1)*j/2. So if you have x of such sequences, you can add x to both of the destination cells. Start with a seed of length 1 with alternating section length 1 and value 1. Each target cell is always strictly greater in i and v, so iterate over j last.
Note that I didn’t talk about 0 or 1 here. But you don’t need to, every sequence has a complement of same value by swapping all 0 to 1 and vice versa. So the basic program output just needs to be doubled. Then finally the n and k from the original input map to i and v, and you sum over all j.