Wet Boxes problem: counting points on a triangular grid As a solution to the B. Wet Boxes problem :


  B. Wet Boxes
  
  Bob works in a warehouse which contains a large pile of boxes. The
  position of a box can be described with a pair of integers (x, y).
  Each box either stands on the ground (y = 0) or stands on top of two
  boxes with positions (x, y - 1) and (x + 1, y - 1) (see the figure).
  
  Sometimes the contents of a box leak out and the box gets wet. When a
  box becomes wet, so do the two boxes below it. Given a list of boxes
  that leak in succession, help Bob count how many dry boxes became wet
  after each leak. Don't include boxes that were already wet.


My solution is :

#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;

static int count;


typedef struct {
    int x;
    int y;
}Box;


Box* push(Box* memptr, int x, int y){
    int i;
    for (i = 0; i &lt; count; i++){
        if ((memptr[i].x == x) &amp;&amp; (memptr[i].y == y))
            return memptr;
    }
    count++;
    if (count == 1)
        memptr = (Box*)malloc(sizeof(Box));
    else
        memptr = (Box*)realloc(memptr, sizeof(Box) * count);
    memptr[count - 1].x = x;
    memptr[count - 1].y = y;

    return memptr;
}

Box* find_wet_boxes(Box* memptr, int x, int y){
    if ((x * y) &lt; 0)
        return memptr;
    else {
        memptr = push(memptr, x, y);
        find_wet_boxes(memptr, x, y - 1);
        return find_wet_boxes(memptr, x + 1, y - 1);
    }
}

int main(){
    Box* memptr = NULL;
    // int i;
    memptr = find_wet_boxes(memptr, 1, 3);
    // memptr = find_wet_boxes(memptr, 3, 2);
    // memptr = find_wet_boxes(memptr, 0, 6);
    // memptr = find_wet_boxes(memptr, 1, 1);
    printf("count = %d\n", count);
    return 0;
}


This works fine for each individual box co-ordinates but when I try to run for all the 4 co-ordinates, it gives me time limit exceed error during submission. (Coordinates may be as large as 109.  There may be up to 105 leaking boxes.  Time limit is 0.7 seconds.) Clearly my algorithm is not good enough. Can someone please give me a better solution for this?

If it the answer is too broad and there could be many solution, then I expect at least one of them which will at least pass the runtime limit test

Possible Solution:


  So, a single leaked box covers a smaller triangle of boxes. In short,
  we maintain a set that contains the vertices of such triangles that
  have not been covered by any other triangle yet. When a box leaks
  (i.e., a new triangle is added), we find the vertices of the triangles
  that are inside the new one, and subtract the area that was first
  covered by this box and is inside the new triangle. Then we can remove
  them from the set and insert the new triangle vertex in the set. This
  results in \$O(n\ \log n)\$ solution (for each new triangle, there can be
  also two vertices that are not inside the new triangle, but overlap
  with it: these vertices remain in the set, but that does not change
  the complexity).


This is the possible solution as quoted by someone but I don't understand how to implement it or will that actually solve the problem.
It's been a while since I have worked in C, so a language-specific review would not be so accurate. The only thing I can say in that aspect is that you should put curly bracket even in single-command body ifs as the code gets more readable and less error prone.

Taking a look at the problem and at your solution I think that you're overcomplicating it. You are allocating memory for each box and working with it when you actually don't need them. All you need is a square matrix - to be more precise, a lower triangular matrix - of ints (in this case).

The idea is the following:


Represent the boxes' status via the matrix \$A\$. If the box in the position \$(x, y)\$ is wet then \$A_{x,y} = 1\$, otherwise \$A_{x,y} = 0\$. So, initially, every item in the matrix is \$0\$.
When the box in position \$(x, y)\$ leaks you just set all the appropriate cells of \$A\$ to \$1\$ and count the number of cells whose value has changed from \$0\$ to \$1\$.
Return the value of the counter for each case.


In pseudo-code (I'm not so practical in C), it becomes something like the following:

int[,] A = new int[7,7];

void initialize_matrix(){
    for(int i = 0; i &lt; 7, i++){
        for(int j = 0; j &lt; 7; j++){
            A[i, j] = 0;
        }
    }
}

int count_wet_boxes(int x, int y){
    int counter = 0;

    for(int i = x; i &gt;= 0; i--){
        for(int j = 0; (i + j) &lt;= (x + y); j++){
            if(A[i, j] == 0){
                A[i, j] = 1;
                counter++;
            }
        }
    }

    return counter;
}

int main(){
    initialize_matrix();

    // the rest of the logic goes here
}


You can also try to ask in the Mathematics SE site if there is a formula you can use.

Let me know if anything's unclear.