Topcoder: SRM 638 (Div. 1)

First Problem
Div 1. (300) - ShadowSculpture
Summary:
You are given a 3D array describing a 3D figure. Then a shadow is casted from the 3D figure to XY, YZ, and ZX planes (or in other words, XY, YZ and ZX contains the projection of the 3D object). Given the projections, output whether there is a possible 3D object satisfying the required projections, given that the object must be 6-connected (which means if two cubes are a part of the 3D object, then they must share a face).



Solution:
This problem is actually a graph problem, and the approach itself is straight forward, but the implementation is quite error prone.. First we need to model the problem as a graph problem:
1. Let M[i][j][k] be an array containing information about the probable 3D structure, starting with all 0.
2. For each projection plane, for eg XY plane, if XY[i][j] contains a shadow, then we add 1 to each corresponding M[i][j][k].
3. For each M[i][j][k] that has value equals to 3 (that means it has a projection on each of the planes), we do a DFS as following: We traverse all neighbors of the current cube that share a face and has corresponding value in array M equals to 3. For each of the visited cube, we have an array result[i][j][k] marked as 1. Then we project the points in array result to each projection plane and check whether it is the same as the initial XY, YZ and ZX information. If not, then continue our search until we exhausted all possibilities. We have to take care of one edge case: if the projection planes contains no shadows, then we straight away output "Possible".


Second Problem
Div. 1 (600) - NarrowPassage2
Summary:
There are wolves of varying sizes on a 1D array. 2 adjacent wolves can be swapped if the sum of their weights are less than or equal to maxweight. Find the number of permutations achievable from the original sequence under this constraint.

Solution:
It sounds very difficult but once you know the approach, the implementation is way simpler than the first problem! First, sort all the wolves according to their sizes, and store this information in an array wolves[i]. We also have array vis[i] initialized to all 0 and variable answer initialized to 1. Then iteratively we start from the wolf with the smallest size, we only consider the wolves from this size up to the biggest size:
1. The current wolf W will always be the smallest wolf currently there is in the pack, by induction. Now this wolf can either move to the right or left, depending on the sizes of its neighbor. We only consider neighbors that has vis[i] equals to 0 (in other words, all wolves with bigger or equal sizes that are not considered yet). Then for each direction we can move this wolf only until it meets another wolf B such that weight of W and B is more than maxweight. It cannot move beyond that since no matter what we do, B cannot be swapped in any other way. There are always 2 wolves acting as B (if not, then the left end point and right end point of the array will act as such "wolf") that will define a segment, which will uniquely define the position of W in that segment. For any further swapping in the segment, we can move W back to our intended position. We count the number of all possible positions of W (including the original position) in variable pos.
2. Update answer = answer * pos, since we can have pos different permutation. Then mark vis[W] as 1.

In the end of the algorithm, answer will contain the total number of permutations possible.


Last Problem haven't tried yet.
UPDATE: just solved the problem. damn hard..... link to discussion:
SRM 638 Div. 1 Hard - CandleTimer