




snewman is back in the battle by lbackstrom,
As in the TCCC, the wildcard round was extremely close. John Dethridge, antimatter and snewman start off extremely close after each submitting the easy problem within a minute of each other. The remaining three coders weren't too far behind, with the sixth submission coming in after 13 minutes. The medium problem proved to be quite difficult for everyone though, and only antimatter, monsoon, and snewman were able to submit it in time. bstanescu skipped the medium problem after solving the easy, and went straight to the hard problem. John Dethridge also moved on the hard problem without solving the medium, but then went back to the medium. With about 15 minutes remaining in the coding phase, bstanescu submitted the hard problem and maintained his lead till the end of the coding phase.
int ret = 0; for(int i = 0; i*i*i <= N; i++) for(int j = i; j*j*j + i*i*i <= N; j++) for(int k = j; k*k*k + j*j*j + i*i*i <= N; k++) for(int l = k; l*l*l + k*k*k + j*j*j + i*i*i <= N; l++){ if(i*i*i+j*j*j+k*k*k+l*l*l == N)cnt++; } return cnt;However, this solution is much too slow to pass the larger cases. One obvious optimization that we can make is to compute the value of l, rather than looping to find it: int ret = 0; for(int i = 0; i*i*i <= N; i++) for(int j = i; j*j*j + i*i*i <= N; j++) for(int k = j; k*k*k + j*j*j + i*i*i <= N; k++){ int l = cubeRoot(Ni*i*ij*j*jk*k*k); if(i*i*i+j*j*j+k*k*k+l*l*l == N)cnt++; } return cnt;Now, when N is 100 million, this solution requires that the innermost loop be executed approximately 12 million times. Hence, the key to a solution that runs in time is to make the cubeRoot function fast. There are a number of ways to do this, but perhaps the simplest is to store all 465 perfect cubes less than 100 million in an array, and then perform a binary search. Alternatively, you could do a binary search for the cube root itself. There are also other methods that will converge faster than a binary search, but they are not necessary. A more complicated solution, with a significantly better runtime requires that we precompute all the numbers that can be found as the sum of two perfect cubes. Once we have our list, we sort it, and can quickly find all the pairs of integers in the list that add up to N: int p1 = 0, p2 = list.length1; while(p1<=p2){ if(p1+p2<N){ p1++ }else if (p1+p2>N){ p2; }else{ p1++; p2; } }The trick, of course, is what to do once we find two numbers in our list that add up to N. I'll leave the details of that as an excercise to the reader (following this approach, a solution can easy handle N = 1 billion). LeftmostDerviation Usually, when dealing with context free grammars, there are a limited number of derivations that are allowed. In this problem, however, you can make any derivation you like, so long as you are replacing the leftmost nonterminal. The first thing to note is that, since we are after the fewest number of derivations, we should never replace a nonterminal with a string containing another nonterminal, unless doing so causes us to end up at the finish string. If there is no way to replace the nonterminal and end at the finish string, then any nonterminals we insert will simply have to be replaced by another, superfluous derivation. So, assuming that we aren't inserting any nonterminals, we want to know how many terminals to derive from the leftmost nonterminal. To do this, we first find all the contiguous terminals following the leftmost nonterminal. Since these symbols can't be replaced, they need to match symbols in final once we've replaced the leftmost nonterminal. Furthermore, in order to find the lexicographically first derivation, we want to derive the fewest terminals possible, so that the first nonterminal appears earlier in the string. Hence, we insert as few characters as possible so that the terminals to the right of the replaced nonterminal line up. We continue in this way, replacing the leftmost nonterminal with the fewest terminals possible or with a sequence that gives us final. Eventually, we'll finish the derivation, or find that it is impossible. Supply It is tempting to try to use the geometric nature of this problem to your advantage. However, I couldn't come up with any way to do so. Instead, I considered placing the store at each of the 121 potential locations, and applied the standard algorithm used for finding a minimum weight bipartite matching. The algorithm is farily straightforward: Find any valid matching while(true){ search for a sequence of edges (u_{0},v_{0}), ..., (u_{k},v_{k}) such that replacing this sequence with (u_{0},v_{1}), ..., (u_{k1},v_{k}), (u_{k},v_{0}) reduces the total cost. if(no such sequence exists)break }Finding a valid matching is trivial in this case, since there are edges from every factory to every store. Finding a sequence of edges can be done using a brute force, recursive algorithm, since there are typically not that many edges in use. However, we have to run this algorithm for each possible location of the new factory, so we need to be a little bit careful about timeout. There are a number of different ways to optimize this algorithm. One way is to make your search for valid sequences more efficient (using BellmanFord, for instance). However, a simpler way to ensure your algorithm runs quickly is to maintain the same matching as you move the location of a factory, and to only move the factory a distance of 1 each time (either by spiraling, or with an S shaped curve). This way, you never have to do very much work to adjust your matching to make it minimum weight.

