


Petr is the new Algorithm Champion
ShipBoxesby radeyeThis problem is straightforward in conceptsimply consider all six orientations of each box stacked on top of each other, and for each such stack consider all three possibilities for the ends with the double layer of cardboard. That's only 108 combinations, so clearly your solution will not time out; the main question is how to minimize the amount of code you need to write to consider all of the possibilities. Probably the simplest way to do it is to just use a set of four nested loops: int r = 2000000000 ; for (int a=0; a<3; a++) for (int b=0; b<3; b++) if (a != b) for (int d=0; d<3; d++) for (int e=0; e<3; e++) if (d != e) { int c = 0+1+2  a  b, f = 0+1+2  d  e ; int[] box3 = new int[] { Math.max(box1[a], box2[d]) Math.max(box1[b], box2[e]), box1[c] + box2[f] } ; Arrays.sort(box3) ; r = Math.min(r, 4 * box3[0] * box3[1] + 2 * (box3[0] + box3[1]) * box3[2]) ; }If you have a nextpermutation() function handy, that can also be used. There are probably a dozen equivalent ways to do this, and none of them should be particularly difficult to code. NotchedWoodBarsPuzzleby Andrew_LazarevThe solution for this problem is quite straightforward. Clearly the half of the bars will form the top part of the puzzle and another half will form the bottom part. Let's iterate all possible configurations of the bottom part. There are 26880 variants possible at most. For each bottom configuration, top configuration is determined unambiguously and we just need to check if it possible to create such configuration using the bars left. PhoneNetworkby Jan_KuipersIt is very easy to check whether it is possible to construct a valid network: just check whether the graph is connected. After this the hard part starts: how to find the best quality/cost ratio. Since it seems really hard to determine this number from scratch, one can ask a slightly simpler question: "Is it possible to achieve a ratio r?" and perform a binary search to find the optimal one. To determine whether a given ratio r can be achieved, one can do the following. Assign to every edge a weight of its qualityr*cost. If for a given subset of the edges the sum of the weights is greater than zero, it is easy to see that the quality/cost ratio of those edges must be greater than r. So we have to look for the subset of edges that spans the graph and has the sum of the weights as large as possible. If this subset has sum of the weights greater than zero, one can obtain that ratio r; if not, one can't. To make sure that the subset of the edges is spanning the graph and has maximal sum of the weights, we compute a maximal spanning tree, which can be determined in the same way as the standard minimal spanning tree. To maximize the sum of the weights we also add to this spanning tree all unused edges with positive weight. Now we have our maximal weight spanning graph and can start the binary search to determine the best ratio. 

Home 
About TopCoder 
Press Room 
Contact Us 
Careers 
Privacy 
Terms
Competitions  Cockpit 
Copyright TopCoder, Inc. 2001 