Codefest

Problem 4: Cuboid

Time limit: 2 secs

A cube has been placed in first octant of a 3-D system(x,y,z>=0) such that its edges are parallel to x, y and z axis with one corner of the cube lying at (0,0,0). Every point (i, j, k), where all i, j and k are integers, that lies inside the cube is allocated an integer each as shown in figure:

Consider a cuboid inside the cube. Let A(x1,y1,z1) and B(x2,y2,z2) be end points of one of diagonals of this cuboid. Find the sum of all integers that are inside this cuboid.

Input:

First line of the input contains the length N of a side of the cube.
This follows N, (NxN) matrices representing N planes in the increasing order of x as shown in diagram. The elements in the matrix denote the integer allocated to that coordinate. For each matrix, there are N lines with N elements on each line. These matrices are separated by a single line.
Next line will contain the number of cuboids, 'T' for which the sum of integers is to be calculated.
Next T lines contain six values in order x1 y1 z1 x2 y2 z2 on each line signifying the coordinates (x1,y1,z1) and (x2,y2,z2),the end points of the main diagonal of the cuboid.

Output:

Output contains of T lines. On each line, output the required sum for the corresponding cuboid.

Constraints:

0<N<15
0<T<25
Integers lying on every co-ordinate(i, j, k) are greater than -200 and less than 200

Sample Input:

(The following sample input corresponds to the above image.)

3
6 7 8
1 2 3
4 5 9

1 2 3
4 5 6
7 8 9

3 6 7
2 4 1
9 8 5
2
2 2 2 0 0 0
1 1 1 2 2 0

Sample Output:

135
46

Score:

USE OF FUNCTIONS IN "math.h" IS NOT ALLOWED
B : Number of square brackets [ ]
C : Number of non-whitespace characters
T = 50000/(B*5000 + C)

Solution:

The aim of the problem is proper use of arrays with the help of pointers. The complexity increases as the dimension of the array becomes large.
The problem can be solved by 3-d arrays. As there is constraint on square brackets, problem can be solved using pointers. For example, A[i][j][k] can be represented through pointers as *(*(*(A+i)+j)+k).
For finding the summation of a cuboid, the minimum and maximum of i, j and k is evaluated individual. Then three nested loops can be used be calculate the sum.

Reference:5.9 Pointers vs Multidimensional Arrays, Dennis Ritchie

Code:

int max(int a, int b)
{
	return a>b?a:b;
}

int min(int a, int b)
{
	return a<b?a:b;
}

main()
{
	int l,b,h;
	int ***A;
	scanf("%d",&l);
	int i,j,k;
	b = l;
	h = l;
	
	A = (int ***)malloc( sizeof(int *) * h);
	for(i=0; i<h; i++)
	{
		*(A + i) = (int **)malloc(sizeof(int *) *l);
		for(j=0; j<l; j++)
			*(*(A + i) + j) = (int *)malloc(sizeof(int) * b);
	}
	
	
	
	for(i=0; i<h; i++)
		for(k=l-1; k>=0; k--)
			for(j=0; j<l; j++)
				scanf("%d",(*(*(A + i) + j) + k) );

	
	int x1, y1, z1, x2, y2, z2;
	int tx1, ty1, tz1, tx2, ty2, tz2;
	int t;
	scanf("%d", &t);
	while(t--)
	{
	
		scanf("%d%d%d%d%d%d", &tx1, &ty1, &tz1, &tx2, &ty2, &tz2);
		x2 = max(tx1, tx2);
		x1 = min(tx1, tx2);
		y1 = min(ty1, ty2);
		y2 = max(ty1, ty2);
		z1 = min(tz1, tz2);
		z2 = max(tz1, tz2);
	
		int sum=0;
	
		for(i=x1; i<=x2; i++)
		{
			for(k=z1; k<=z2; k++)
			{
				for(j=y1; j<=y2; j++)
				{
					sum += *(*(*(A + i) + j) + k);
				}
			}
		}
		printf("%d\n", sum);
	}
}

Check the Best Solutions