January 2012 Contest Problem Editorials

Problem Tester for the contest was Hiroto Sekido.

----------------------------------------------------------

RHOUSE (written by Sergey Kulik)

Obviously, all the roads that will be profitable should be decorated. So we will include them in the answer at the very beginning. Then we can sort the rest of edges by their cost and apply the following greedy approach: if the edge connects two connected components and there is no restaurant in at least one of these components then this edge should be included into the answer and the components should be merged. Merging components can be done by union-find data structure. Another similar approach is to connect all the restaurants in the very beginning, after including the edges with negative weight and simply build a mst then. Also pay attention that the upper bound of the answer may fit into int but the lower bound of the answer could be about -8*10^9 so 64-bit type should be used for storing the answer(long long in C++, int64 in Pascal).

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------

CARDSHUF (written by Tomaz Hocevar)

The key to solving this problem are dynamic trees data structures. The dynamic trees problem involves maintaining a forest of trees, which change through series of edge insertions or deletions. The most known solution are link/cut trees developed by Sleator and Tarjan. However, they are a bit difficult to implement and adapt for different applications. As we are dealing with a small number of trees in our problem, the constraints are low enough and inputs are random, we can make a compromise and choose some easier solution which still works in sub-quadratic time.

A good candidate are splay trees with their amortized logarithmic time complexity. They are a very flexible data structure. To split a tree at some point just splay adjacent node to the root and remove the edge. Merging two trees can be implemented in a similar way. Splay the rightmost node of the first tree to the root and attach the root of the second tree as its child. You will also have to maintain the sizes of subtrees at each node so that you can find and splay the k-th node to the root and detach first k nodes from a tree. Reversing the order of elements in a subtree should be done in a lazy way. Instead of reversing an entire subtree, just mark the root node for reversal. Next time before you access this node, swap its children and mark them for reversal.

We saw a variety of different approaches in the contest so lets list a few:

1. You can perform a split on any binary tree by cutting off multiple branches and merging them back together. This solution was the easiest and most popular among contestants.
2. Use a Treap instead of a Splay tree.
3. Check tester's implementation for a skip list approach.
4. Simulate the shuffling process with ranges of numbers and rebuild the entire structure every sqrt(N) steps for a total time complexity of O(N*sqrt(N)).

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------

GAPFILL (written by Nikhil Garg)

This was the first problem I wrote for Codechef and I'm glad so many people could solve it. I hope it was fun solving it :)

As I understand, many people tried to find the pattern and did some guess work. Here I provide a fully combinatorial solution to the problem. I wont be surprised if a shorter (& smarter) solution exists.

Call OP1(i,j) the operation given in problem statement applied at cell(i,j). Trick to solve this problem is to be able to break OP1 in simpler operations with same power.

Before counting number of solvable configurations, we need to first characterise solvable configurations. Lets try to look at different cases:

1. Case 1 : Both sides even
   • This is the easiest of all the cases. By a smart sequence of moves( shown below), we can toggle any given cell without changing any of the other cells. By this we can solve any initial configuration of the board. Hence in case when N & M are both even answer is 2^(N*M).
   • If you want to toggle cell (i,j) : Press switch in all those cells which are in same row or column as that of(i,j). Note (i,j) is to be pressed exactly once. This results only cell(i,j) getting flipped.
2. Case 2 : 1 side even, 1 side odd.

   Without loss of generality assume number of rows is even and number of columns is odd. This case is tougher to analyze as all configurations are not solvable. However one can represent OP1 as a sequence of moves of following two operations:

   • OP2 : Flip one whole column
   • OP3 : Flip any row keeping any one element of this row unchanged.

   Also both OP2 & OP3 can be created by sequence of moves of OP1(Find that, as homework ;-] ). Hence a board is solvable by OP1 move iff its solvable by OP2 & OP3 moves. Now take a solvable configuration and list the sequence of OP2 & OP3 moves that solve it. No operation as before is repeated on same location. Hence all moves are independent & we can change their order. Bring all OP2 moves before before all OP3 moves. When all OP2 moves have ended look at grid. As OP3 operation can't change parity of ones in any row so each row much have an even number of 1s already. Now flip each row exactly as many times as there are 1s in it with not flipping those cells which have a 1 in them at this stage. All 1s get flipped odd times ( total 1s (even) - 1(for ownself) ). Also all 0s get flipped even times hence whole row is 0.

   So now what could've happened in column phase ? A single column flips parity of all rows so all rows should've started with same parity. Convince yourself that this is in fact an if and only if condition. So only those configurations are solvable that have same parity in all rows. Counting it is not so tough. There are two choices for parity of first row : odd or even. Here is a combinatorial way of counting the same. Fill up first N-1 cells of first row arbitrarily. If parity of these N-1 match option chosen before keep Nth cell blank else put 1 in it. So number of ways of making a row have even(or odd) parity is 2^(N-1). As all rows have same parity, so for all rows number of ways of getting odd (or even) parity is : 2^( (N-1) * M). And as we have option of choosing even or odd : final answer is 2 * (2^ ((N-1) *M))

3. Case 3 : Both sides odd.

   As before one can represnt OP1 as sequence of moves of two operations :

   • OP4 : Flip whole grid
   • OP5 : Flip any two rows while keeping 1 same column element unchanged in both

   Try to represent OP1 using OP4 & OP5. Also try to represent OP4 using OP1 & similarly OP5 using OP1. As before each row should've even number of 1s as OP5 can't change parity. Similarly another decomposition of OP1 is using following 2 moves :

   • OP4 : Flip whole grid
   • OP6 : Flip any two columns while keeping 1 same row element unchanged in both.

   So by this, all columns too should've even number of ones. As grid flip is also allowed, so it suffices if each row and each column has same parity. This is infact an if and only if condition, convince yourself. Counting number of configurations where each row and each column has same parity is not so easy. Here is a combinatorial solution : Take N-1 * M-1 subgrid leaving last row and last column. Fill up this grid arbitrarily. Further suppose we wish to make parity of each row or column odd. So for each column if parity is even put 1 in last row of same column else keep it zero. Do same for rows. By now parity of last row and last column is same. If its even put 1 at (N,M) the cell else let it stay 0. So number of configurations which have odd parity in all rows and columns is 2 ^ ( ( N-1) * (M-1) ). As even parity case is similar (bijection being flipping of the grid), total number of solvable configurations are 2 * ( 2 ^( (N-1) * (M-1) ) )

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------

AMBIDEX (written by David Stolp)

This problem is a superset of the problem of partitioning a graph into perfect matchings, which is NP-complete. But that didn't stop 8 competitors from producing optimal solutions to all of the test cases, including lightning-fast solutions by gennady.korotkevich and ACRush.

A brief note on the scoring mechanism: C*N is the number of single-handed chefs it would take to form the same numbef of chef teams. Supposing it costs the same amount to hire an ambidextrous chef an a single-handed chef, C*N-H is a measure of how much money Head Chef would save by hiring ambidextrous chefs. Dividing this value by M normalizes the test cases so that the theoretical maximum score on a test case is 1.

Construct a multigraph with N vertices (one for each tool), and for each of the M chefs add an edge between the vertices corresponding to the 2 tools that chef can use. Our task is to extract from this graph as many edge covers as possible, with the secondary goal of minimizing the total number of edges used. In the case that N is even and every tool is usable by the same number of chefs (that is, every vertex has the same degree), the problem reduces to finding a partitioning into perfect matchings, as mentioned above.

The condition that every tool is usable by at least one chef (that is, no vertex has degree 0) implies that an edge cover exists, and with at most N-1 vertices. Such an edge cover can be constructed as follows: Hire an arbitrary chef. Then for each remaining chef, hire that chef only if that chef can use a tool that none of the currently hired chefs can use. Initially, 1 chef is hired, and 2 chefs are usable. For each additional chef hired, the number of usable tools will increase by at least one, hence at all stages the total number of usable tools will exceed the number of chefs hired. In the end all N tools will be usable, thus at most N-1 chefs will have been hired. Note that in the worst case, the minimum edge cover contains exactly N-1 vertices: a graph with N-1 vertices of degree 1, and 1 vertex of degree N-1 (i.e. the star graph with N vertices).

An approach that did very well is greedily extracting minimum edge covers from the graph. Minumum edge covers can be found in polynomial time. By randomizing the order of the edges and repeating this process several times, the probability of finding an optimal solution increases with each iteration. Several of the winning solutions were based on this idea.

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------

MISINT2 (written by Anton Lunyov)

The Editorial can be found here

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------

LUCKY3 (written by Vitaliy Herasymiv)

First of all, notice that there are exactly 1022 lucky number of length between 1 and 9. We can solve problem for each lucky number independently, then sum up all results and get total result.

Now we need to solve problem for some lucky number L (L[i] - i-th digit if number L, starting from right). If there is some number W[i] in input array W that has some digit on some postion which is greater than corresponding digit in L (i. e. there exits some j, that W[i][j] > L[j]), then we can delete W[i] from W (because if we pick that number to subsequence then we'll never get lucky number L).

Now we should think about dynamic programming approach to solve problem for current lucky number L. You can read about this method here: http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg

Lets start think about what information we need to handle in DP state. Here we need 2-dimensional state space. Of course, we need to review all numbers of W, so first dimension of DP sate must be [pos], pos = [0; n) (0-based numberation of array W, n - size of W). State [pos] means that we already have reviewed all numbers up to position pos in array W and have picked some to our set. But what set? We don't know that. We need some more information to know whenever we will achieve current lucky number in current set (using lucky sum operation). If we already have some set of numbers (with indexes up to pos) and some digits of lucky sum of all numbers in that set are already lucky, we need to now that. To achieve that we need to handle bitmask ( http://en.wikipedia.org/wiki/Mask_(computing) ) of digits that are already the same like in current lucky L, i. e. j-th bit of bitmask must be turned on if j-th digit of lucky sum of current selected set is equal to L[j] (it can not be greater than L[j], because of second paragraph). So, now we have new state of DP, now it is [pos][mask].

Now we should think about transitions of DP. If we are on state [pos][mask] we can do two things. First - do not choose W[pos] to current set. Then mask, of course, will not changes (because we do not change out current set) and we go to the sate [pos+1][mask]. If we choose W[pos], then we go to the state [pos+1][new_mask]. What is new_mask? This is new_mask created by turning on some bit of musk, which are corresponding to the positions of digits of W[pos] that are equal to L (i. e. if for some j W[pos][j] = L[j] and j-th bit is not turned on in mask, then new_mask should have j-th bit turned on. All bits that were turned on in mask must be also turned on in new_mask).

So, considering 2D DP approach we can handle all possible states which will include all subsequences. Please, read setters solution for further understanding of DP approach.

Problem Setter's solution.
Problem Tester's solution.

----------------------------------------------------------