Why is this divide and conquer algorithm inefficient?

Question

I was solving one of the problem in USACO 2007 Open Silver:

Description

Farmer John has taken his cows on a trip to the city! As the sun sets, the cows gaze at the city horizon and observe the beautiful silhouettes formed by the rectangular buildings.

The entire horizon is represented by a number line with \$N (1 ≤ N ≤ 40,000\$) buildings. Building \$i\$'s silhouette has a base that spans locations \$Ai\$ through \$Bi\$ along the horizon \1ドル ≤ Ai < Bi ≤ 1,000,000,000\$ and has height \$Hi\$ (\1ドル ≤ Hi ≤ 1,000,000,000\$).

Determine the area, in square units, of the aggregate silhouette formed by all \$N\$ buildings.

Input

• Line 1: A single integer: N
• Lines 2...N+1: Input line i+1 describes building \$i\$ with three space-separated integers: \$Ai\,ドル \$Bi\,ドル and \$Hi\$.

Output

Line 1: The total area, in square units, of the silhouettes formed by all \$N\$ buildings

Sample Input

4
2 5 1
9 10 4
6 8 2
4 6 3

Sample Output

16

I used a divide-and-conquer algorithm to solve this problem, but failed. The feedback of the online judgement system is Time Limit Exceeded. Could you help me to make my code more efficient, readable, and clear?

#include <stdio.h>
#include <malloc.h>
#define INF 10000000000
enum {MAX = 2, DIM = 3};
typedef struct Outline Outline;
struct Outline {
 int pos;
 int height;
};
/* merge two outlines of buildings */
Outline *mergebuilding(Outline *a, Outline *b, int num)
{
 int a_move = 0;
 int b_move = 0;
 int r_count = 0;
 int r_move = 0;
 int pre = -1;
 int x = 0;
 int y = 0;
 Outline *r = (Outline *) malloc(MAX * num * (sizeof(Outline)) + sizeof(Outline));
 while (a[a_move].pos < INF || b[b_move].pos < INF) {
 r[r_move].pos = (a[a_move].pos <= b[b_move].pos) ? a[a_move].pos : b[b_move].pos;
 if (r[r_move].pos == a[a_move].pos) {
 x = a[a_move].height;
 a_move++;
 }
 if (r[r_move].pos == b[b_move].pos) {
 y = b[b_move].height;
 b_move++;
 }
 r[r_move].height = (x >= y) ? x : y;
 if (r[r_move].height != pre) {
 pre = r[r_move].height;
 r[r_move+1] = r[r_move];
 r_move++; 
 } 
 }
 r[r_move].pos = INF;
 return r;
}
/* divide-and-conquer */
Outline *recursive(Outline **p, int low, int high)
{
 /*
 Recursively divide the set of buildings into two parts 
 until one block, then merge two blocks from the bottom to the top. 
 */
 Outline *part1, *part2, *merge;
 int mid;
 if (low == high) 
 return p[low];
 mid = (low + high) / 2;
 part1 = recursive(p, low, mid);
 part2 = recursive(p, mid+1, high);
 merge = mergebuilding(part1, part2, low+high+1);
 free(part1);
 free(part2);
 return merge;
}
int main()
{ 
 int **bul;
 int num;
 Outline **p, *cp;
 scanf("%d", &num);
 bul = (int **) malloc(num * sizeof(int));
 p = (Outline **) malloc(num * sizeof(Outline));
 for (int i = 0; i < num; i++) {
 bul[i] = (int *) malloc(DIM * sizeof(int));
 p[i] = (Outline *) malloc(DIM * sizeof(Outline));
 scanf("%d %d %d", &bul[i][0], &bul[i][1], &bul[i][2]);
 p[i][0].pos = bul[i][0];
 p[i][0].height = bul[i][2];
 p[i][1].pos = bul[i][1];
 p[i][1].height = 0;
 p[i][2].pos = INF;
 free(bul[i]);
 }
 free(bul);
 cp = recursive(p, 0, num-1);
 free(p);
 int temp, square;
 square = 0;
 for (int i = 0; cp[i].pos < INF; i++) {
 temp = (cp[i+1].pos - cp[i].pos) * cp[i].height;
 square += temp;
 }
 printf("%d\n", square);
 free(cp);
 return 0;
}

• Michael Zedeler: Is this algorithm complexity O(n log n)? I'm thinking that using radix sort, it should be possible to get it down to O(n).

Answer 1

I don't know for sure why your program is running out of time (since I know nothing about the target platform), but my guess is that it's either item (1) or (2) in the list below. These errors lead to undefined behaviour, and then, well, anything could happen (that's what undefined means), including an infinite loop.

1. This line computes the wrong size for the allocation:

   bul = (int **) malloc(num * sizeof(int));
   

   You want an array of num pointers to integers but you are allocating space for num integers. So this will only work if an integer is the same size as a pointer. On my platform/compiler (x86-64/Clang) an integer is 4 bytes long but a pointer is 8 bytes long so this computes a size that is too small, and then the loop writes off the end of the array, which results in undefined behaviour. (On my platform this causes the program to crash with a segmentation fault.)

   You need to write:

   bul = malloc(num * sizeof(int *));
   

   or:

   bul = malloc(num * sizeof *bul);
   

   instead. Note that there's no need to cast the result of malloc() since the function returns void * and that type is convertible to any object pointer type without a cast.

2. The total area might be close to 10¹⁸ units. For example if the input was

   1
   1 1000000000 1000000000
   

   then your program would need to output

   999999999000000000
   

   and yet you are accumulating the area in the variable square, which is an int. Is int large enough on the target platform/compiler to store a number of this size? It certainly isn't on mine (x86-64/Clang) where INT_MAX is 2147483647.

   This means that your program causes integer overflow, which yields undefined behaviour. (John Regehr has a good explanation here.)

   On my platform (with item (1) above fixed) this bug causes mergebuilding() to run off the end of the array in an infinite loop (because the comparison with INF goes wrong) and this eventually hits unmapped memory and crashes with a segmentation fault.

   I'm surprised that you didn't spot this at compilation time. I get these warnings from Clang:

   cr26938.c:46:21: warning: implicit conversion from 'long' to 'int' changes value
    from 10000000000 to 1410065408 [-Wconstant-conversion]
    r[r_move].pos = INF;
    ~ ^~~
   cr26938.c:4:13: note: expanded from macro 'INF'
   #define INF 10000000000
    ^~~~~~~~~~~
   

   And these from gcc:

   cr26938.c: In function ‘mergebuilding’:
   cr26938.c:26: warning: comparison is always true due to limited range of data type
   cr26938.c:26: warning: comparison is always true due to limited range of data type
   cr26938.c:46: warning: overflow in implicit constant conversion
   

   Perhaps you can say what compiler you are using?

   You need to use a type that's large enough on the target platform to store numbers of the required size. If the target platform conforms to C99, then you can

   #include <stdint.h>
   

   and then use int64_t, which is guaranteed by the standard to be a signed integer type with exactly 64 bits. But if the target platform does not conform to C99, then, well, I guess you need to read the compiler manual to find out what type is big enough (but probably long or long long would work).

3. You write

   #include <malloc.h>
   

   which is non-standard: in Standard C, malloc() is declared in stdlib.h. Unless your platform is really non-standard, I'd stick with stdlib.h.

4. What is the role of the bul array? You only ever use one element at a time, and then only to read some numbers which you immediately copy out again. Why not read the input into variables on the stack instead? Perhaps like this:

   for (int i = 0; i < num; i++) {
    int a, b, h;
    scanf("%d %d %d", &a, &b, &h);
   

5. You don't check the return values of the functions you call. malloc() returns NULL if it can't allocate, and scanf() returns the number of input items assigned, which might be less than the number of format specifiers if there was an error. I know this is only a simple program that doesn't require much in the way of error handling, but it's still an opportunity for you to practice your skills. And it doesn't have to be burdensome: you can write

   if (p[i] == NULL) error("out of memory");
   if (scanf("%d %d %d", &a, &b, &h) != 3) error("malformed input");
   

   with error() defined like this:

   void error(const char *message) {
    fprintf(stderr, "%s\n", message);
    abort();
   }
   

• fishiwhj: Sorry for the late reply, the compiler I'm using is VS 2010. I have already corrected these mistakes but still running out of time. I guess this algorithm may not be suitable to the problem. BTW, here is the link for the online judgement system.