3x3 The problem is typical for game-play trees. There are 24 edges, each one of them been 0 or 1. 2^24 means around 16 milions possibilities, without introducing rotations, mirroring etc. Since each computation is trivial to be calculated based on the others, the calculation of all configurations can be done relatively fast (even precomputed). AMAX3D We consider a three dimensional matrix v were v[i][j][k] is the representative of the cube with coordinates of the upper left back :) corner (i,j,k) and volume 1; if such a cube is not complete than it cannot be found in the cube with the largest volume So we precompute the matrix v v[i][j][k]=1 if the cube it reprezents is not complete ;else 0; So we have to find out if the cube intersects or it is contained by a sphere. Since the coordinates of the sphere's center and radius are integers the above condition is satified if one of the cubes corners are inside the sphere. A point is inside a sphere is the distance between the point and the center of the sphere if smaller than it's radius. After that we find the bigest cube in the matrix v that contains only 0. To do that we use DP for every cell j,x in the matrix at level i we compute max[i][j][x]=the side of the largest square that contains only 0 with the upper left corner in that cell. And then for every cell j,x we go down in the three dimensional matrix. When we arive at a level H We check If the side of the cube can be of lenght i-H. This is true if for all the level k between i and H ,including i and H, max[k][j][x]>=i-H; To find max[i][j][x] we use this formula: if v[i][j][x]=1 max[i][j][x]=min(max[i][j-1][x], max[i][j][x-1], max[i][j-1][x-1])+1 ; else max[i][j][x]=0; SPOILED BRAT For each connected component of the graph the minimal number of helicopter rides equals (the number of vertices of odd degree) / 2. If the connected component doesn't have any such vertex, then the number of rides is 1. FIND THE MAP This is a clasical max-flow problem. Double each node, add a sink and a destination node. Connect the sink to each of the first half of the nodes using capacity inner degree and connect each of the second half of the nodes to the destination using capacity outer degree. Then connect every node in the first half to every node in the second graph using capacity 1. Use a max-flow algorithm to determine a flow from the sink to the destination. If the value of the flow equals the sum of the inner and the sum of the outer degrees, then there is a solution. FUNCTION This problem was inspired by the IOI 2001 olympiad (the cryptography problem). The idea is to firstly combine 2 sets of labels, and compute the possible outcomes. Since N <= 1000, we have <= 1000000 (one milion) possible numbers generated by only 2 players (with 2 labels). Now we sort those partial sums from the smallest to the biggest. Also, for each such sum S, we also compute M-S, and we also sort those numbers. The key now is to find a match (this is trivial): 0 --- S1 ...... (M - S1) --- M 0 ---- S2 ..... (M - S2) --- M 0 ---- S3 .... (M - S3) ---- M 0 ----- S4 ... (M - S4) ---- M 0 ----- S5 .. (M - S5) ----- M ... The complexity is O(N*N*lgN*lgN) (sorting takes the most in this). IMPAS The problem is typical for game-play trees. There are at most 1820 combinations (16! / 12! / 4!), and they can be even pre-calculated using elementary algorithms. The game was invented for a 8x8 board and 16 pieces by Serban Paun around 1985. On the 4x4 board, after precalculating the positions, it can be deducted that the first player always looses. JOHN We'll use dynamic programming & backtracking. For each line we keep an array a[512] (512 = 2^9) of distinct configurations. We generate using backtracking all the ways to go from one line to the other. TESTER The objective of the problem is to test the programer's knowledge regarding the 0-1 principle applied to sorting networks. Using this principle, complexity can be reduced from O(n!*n*n) to O(n*n*(2^n)). For n = 18, such a reduction is mandatory for solving all the tests of the problem. Details can be found in CLR 28.2.