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.

1