A simple approach consists of modeling the cube as six 3x3 matrices of letters, representing each face of it. So, you may write simple procedures for each movement. Notice that a counterclockwise rotation is equivalent to three clockwise rotations, which may save some lines in your algorithm.
The solution for this problem is very intuitive. Each sentence may be seen as a vertex in a graph. If sentence i is about sentence j, create an edge from vertex i to vertex j using as its label what i says about j (if it is true or false). It is worth seeing that this graph will have various components, each one composed of a unique cycle and some "tails" formed by vertices which are connected to the cycle but are not part of it. In each component, once you define one of its vertices (sentences) as true or false, all the other sentences of the component can have a value assigned. If a vertex i has value v, each vertex j connected to it by an outgoing edge (from i's viewpoint) will have value (v == label(i,j)), where label(i,j) refers to the label of the edge which connects vertex i to vertex j; and each vertex k connected to it by an incoming edge will have value (v == label(k,i)), where label(k,i) refers to the label of the edge which connects vertex k to vertex i. By this principle, two things may be inferred:
{ This algorithm solves only one instance }
create the graph
separete each component of it
inconsistent := false
solution := 0
for each component do
if the component's cycle has an odd number of false edges then
inconsitent := true
{ If you want, you may break the for here }
else
Assign the value true to one vertex in the component
Calculate the values of the other vertices
Let tv be the number of vertices labelled true
Let fv be the number of vertices labelled false
solution := solution + max(tv,fv)
end
end
if inconsistent then
print "Inconsistent"
else
print solution
end
|
A simple approach consists of constructing a complete undirected graph
where each vertex corresponds to a wall section. Every edge (i,j)
has a cost c(i,j) associated, which is 0 when the two segments
intersect or corresponds to the distance between the two segments if
they do not intersect. After that, you may execute an algorithm very
similar to Dijkstra's shortest path algorithm.
Maintain a set S, initially empty, of vertices whose minimum size
wooden board necessary to get to it has already been calculated. Create
an array board[N] which contains the value of the smallest board Indiana
will need to get to every wall section passing only through the wall
sections in S. Let s be the vertex which refers to the wall
section on which Indiana stand. During initialization, make
board[s] equal to 0 and board[i] equal to INFINITE, for
every i different from s.
In every step, select a vertex i which is not in S and whose
value board[i] is minimal. Add i to S. It is worth
seeing that if board[i] is minimal, then it will need a bigger
wooden board to get to i through another vertex not in S. So, the
best way to get to vertex i is using the wooden board previously
calculated. Now that board[i] is fixed, we can recalculate
board[j], for all j not in S, testing the best path
through i. So, for all j not in S, execute the following
line:
board[j] = min(board[j],max(board[i],c(i,j)))
This is a variation of the classical Knapsack problem which is
found in many books. A common strategy consists of maintaining an array
V of size M+1 (range 0..M), representing the number of Mindt chocolates
that can be grouped in small boxes. V[j] is 0 if it is not
possible to group j Mindt chocolates in small boxes and it is
1<=k<=N if it is possible to group j Mindt chocolates in
small boxes, being the k-th small box (in the order given by the
input) the last one used. Initially, make V[0] equal to -1 to
indicate that 0 Mindt chocolates can be boxed without any small
box.
On step i, take the i-th small box and let vi be its
capacity. Then, execute the following:
for j := M downto vi do
if (V[j] == 0) and (V[j-vi] <> 0) then
V[j] := i
end
end
|
This is the most difficult problem in the problem set. It involves
geometry and dynamic programming. A possible approach starts ordering
(clockwise or counterclockwise) the nails around the Origin. Let's say
that N is the number of points without the Origin (actually, in the
problem statement, N includes the Origin). So, after the ordering, we
have defined points 1..N. Define a circular queue of the points, so that
when we refer to points 4 .. 2 in a set of 6 points, we mean a working
set composed of points 4, 5, 6, 1 and 2. After that, it is necessary to
calculate a matrix CH[N][N], where CH[i][j] corresponds to
the area used by a single rubber band wrapping points i
... j (in the order defined before). If the angle formed by
points i and j with the Origin is bigger than PI (in
radians), define CH[i][j] as INFINITE because a rubber band
involving them does not touch the Origin. Also define
CH[i][j] as INFINITE if i == j because a wrapping
containing only two nails is invalid. Otherwise CH[i][j]
can be calculated using any convex hull algorithm together with some
area calculation algorithm. A good approach would use a variation of the
Graham's Scan algorithm, using the Origin as pivot in such a way that an
entire line CH[i] can be calculated in O(N) time. So,
calculating the entire matrix CH would take O(N^2) time.
Let NTCH( r, i, j ) be the total area of the best
wrapping of r rubber bands involving points i
... j (in the order defined before). The following recurrence
defines NTCH recursively and can be used to develop an efficient
algorithm to solve the problem. A correctness proof for this recurrence
is straightforward.
NTCH(1,i,j) = CH[i][j]
NTCH(r,i,j) = INFINITE { if i == j }
min( k := i to j-1, NTCH(r-1,i,k) + CH[k+1][j]) ) { otherwise }
|
This easy problem consists of verifying reachability and degree of vertices in a graph. For every SPAM message, verify if it reaches a person (i.e. if there is a path from the originator to the person in the given graph). If so, the number of SPAM messages sent by that person is equal to its degree in the graph, otherwise it is zero, once it does not receive the message. According to this value, match the correct attribute and print it following the given ordering constraints. Reachability can be easily verified using a transitive closure algorithm (e.g. Floyd-Warshall).
This is certainly the easiest problem in the set. Once you have read both scanned and standard images, test all the four possible rotations of the scanned image comparing it with the standard one. Invert the image (mirror effect) and repeat the previous operations. Choose the best confidence degree and print it.
A simple approach to solve this problem consists of maintaining an array L[M+1] (range 0..M), where L[j] represents the minimum cost necessary to buy the j first items in the list following the given restrictions. Initially, make L[0] equal to 0 and L[j] (j <> 0) equal to INFINITE. On step i, you calculate L for the i first products in the supermarket, based on the array calculated in the previous step. Let LA be the array L calculated in the previous step; if the current supermarket product appears as the j-th element in the list, you have that L[j] = min( LA[j] , LA[j -1] + its cost). In other words, you have to choose between the two possibilities:
{ On step i }
Let sp be the i-th product in the supermarket
Let cost be its cost
for j := 1 to M do
Let lp be the j-th product in the list
if sp == lp then
L[j] := min(LA[j], LA[j-1] + cost)
else
L[j] := LA[j]
end
end
|