[UVA] 10364 Square (DP solution)

 After series of TLE, I finally solved this problem by DP combining with bitmask. 

https://github.com/wilson100hong/UVAOJ/blob/master/Volume_103/10364/square.cpp

We can view each bitmask as a set of "used" sticks (bit = 1 is used, 0 is not). So, bitmask "10011" means a subset of sticks {sticks[0], sticks[1], sticks[4]}.

Here comes the meaty DP part: for each bitmask B, we store: 

  1. value[B] : which is the sum of used sticks' length in B. 

  2. dp[B] : the max number of "edges" that B can achieve as part of a square. Each edge is formed by a set of sticks, with sum equals to square's side length. edge (= sum(sticks) / 4). 

Let's use an example to see the meaning dp[]. Say sum(sticks) = 20, so 

edge = 5. For a bitmask B meaning sticks with length {2, 3, 4, 5, 6}, we can group into 2 edges: {2,3} and {5}, with 4 and 6 remaining not grouped. We name the sum of such ungrouped sticks "residue". In this example, the residue is 10 (4 +  6). 

You can observe that when a residue of B > edge, it is possible to form a square starting from B by adding more sticks.

If we flip any bit which is '1' in B to '0', we will get another bitmask B'. A bitmaks B could have multiple such flipped bitmask, as the number of '1' in B. Lets called all this flipped bitmasks "child-bitmask". The index of flipped bit is "flipped-bit" fb', it connects to a stick[fb']

The main idea of DP solution is, for every B, we try all its child bitmask B', to see what is the best dp[B] we can get by adding stick[fb']. This will needs to refer dp[B'] and residue[B'], lets list different cases:

Do this for all B' of B:

1. residue[B'] > edge :

    There is no way to construct a square by adding sticks in B', Prune it!

2. If residue[B'] == edge :

    This never happens (think about it!)

3. If residue[B'] < edge : 

    use temp variables new_dp, new_res

    There could another three possibilities: 

    a. residue[B'] + stick[fb'] < edge:

        new_dp = dp[B'], new_res = residue[B'] + stick[fb']

    b. residue[B'] + stick[fb'] == edge:

        new_dp = dp[B'] + 1, new_res = 0

    c. residue[B'] + stick[fb'] > edge:

        Same as 1. Prune it! 

Finally, pick the max new_dp in B' for dp[B], and use the corresponding new_res in residue[B].

In implementation, we can scan the DP array for all B by nature ordering (0000, 0001, 0010, ...1111), since every child bitmask B' will be encountered before its parent B. (think about it!)

In order to get AC, some optimization tips: 

1. We only need to try half of all bitmask -- we can always assume stick[m - 1] is not used, because of symmetry (think about it!) 

2. Don't precompute for whole bitmask -- this prohibits any potential pruning, and will get you TLE.