Wet Boxes problem: counting points on a triangular grid

Question

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 <stdio.h>
#include <stdlib.h>

static int count;


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


Box* push(Box* memptr, int x, int y){
    int i;
    for (i = 0; i < count; i++){
        if ((memptr[i].x == x) && (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) < 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 10⁹. There may be up to 10⁵ 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.

Answer 1

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:

1. 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\$.
2. 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\$.
3. 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 < 7, i++){
        for(int j = 0; j < 7; j++){
            A[i, j] = 0;
        }
    }
}

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

    for(int i = x; i >= 0; i--){
        for(int j = 0; (i + j) <= (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.

Answer 2

Each box is on a triangular grid... but actually, what is described by the coordinate system is a grid like this:

x
xx
xxx
xxxx

So what I'd do is instead make a single array that describes the lowest dry box in a column. Because if a box gets wet then so does the box beneath and the box beneath that...

So if box 2,10 becomes wet, then we say i = x and put ((y-(i-x))+1) in the column if it is higher than the value already there. Add the difference to the sum variable whilst changing the array.

0, 0, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0

pseudo

int sum = 0;
for(int i = x; ; i++){
  int dryBoxHeight = ((y-(i-x))+1);
  if (dryBoxHeight < 0 || array[i] >= dryBoxHeight){
     break;
  }
  sum += dryBoxHeight - array[i];
  array[i] = dryBoxHeight;
}

Then next, you get box 0,4 wet...

So column 0, we put 5, and 5-0 = 5, so 5 to sum

5, 0, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 & sum = 5

Column 1, we put 4, and 4 - 0 = 4, so add 4 to sum

5, 4, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 & sum = 9

And column 2 we stop because 11 beats 3.

The only problem with this approach is that you need to be able to have a sparse array, otherwise you run into memory issues.

This solution is \$O(n)\$.

Answer 3

It looks like I have solved it:

#include <iostream>
#include <vector>
#include <algorithm>

int counter = 0;
std::vector<std::vector<int>> boxes;
void prune_boxes(int x, int y){
 if (y < 0)
   return;
 else{
   if (boxes[x][y] == 0){
     boxes[x][y] = 1;
     counter++;
   }
   prune_boxes(x, y - 1);
   prune_boxes(x + 1, y - 1);
 }
}



int main(){
  int wetBoxes;
  std::cin >> wetBoxes;
  std::vector<int> coordinatesX;
  std::vector<int> coordinatesY;
  int input;
  for (int i = 0; i < wetBoxes; i++){
    std::cin >> input;
    coordinatesX.push_back(input);
    std::cin >> input;
    coordinatesY.push_back(input);
  }

  int greatestX = *max_element(coordinatesX.begin(), coordinatesX.end());
  int greatestY = *max_element(coordinatesY.begin(), coordinatesY.end());

  int Y =  greatestY + 1;
  int X =  greatestX + greatestY + 1;
  boxes.resize(X);
  for (int i = 0; i < X; i++){
    for (int j = 0; j < Y; j++){
      boxes[i].push_back(0);
    }
  }

  for(int i = 0; i < wetBoxes; i++){
    prune_boxes(coordinatesX[i], coordinatesY[i]);
    std::cout << counter << std::endl;
    counter = 0;
  }
  return 0;
}

The only thing that has changed from the accepted answer is the fact that I am not storing each points as there is no need for it. Instead, I am maintaining a LUT as mentioned by @Gentian Kasa with all the values to be zero. Each time I visit them, I put 1, and if any cell is already 1, I would not increment the counter. If it is not 1, I would increment the counter. Although the actual tricky part was to select the row and column size of the matrix.

If out of all the points my greatest X-coordinate is 6 and greatest Y-coordinate is 12, then at each level my Y is decremented by 1 and X is incremented by 1 and if Y goes negative, I return from the function. Now this means I don't need a matrix whose height needs more than maximum Y + 1 (because it is always decremented) and I don't need a matrix whose breath needs more than maximum X + maximum Y + 1 (because X can increment only until the time Y can decrement).

Note: The performance is improved because every time I am not searching is that point is already included or not like in the previous solution. Accessing a member of any 2D array to check if it is 1 or 0 is constant time.

Moreover, the previous solution can pose a buffer overflow because I did x * y, without understanding that x never goes negative, only y does.

Edit 2: For number of points given as 1, the solution can be found in \$O(1)\$..This is how For n = 1 and the given point (x, y), the count value seems to be calculated by

count = ( (y + 1) (y + 2) ) / 2)

This is because it comes out to be sum of y + 1 natural numbers.

Plus the above solution can be improved further. The understanding is that if a box is already visited so does the 2 boxes below it and similar for those 4 boxes even below it. Hence there is no need for prunig those boxes further whose parent is already visited and hence can reduce the recursion calls by a lot for more than one points Hence the improved prune_boxes will be like this.

void prune_boxes(int x, int y){
     if (y < 0)
       return;
     else{
       if (boxes[x][y] == 0){
         boxes[x][y] = 1;
         counter++;
         prune_boxes(x, y - 1);
         prune_boxes(x + 1, y - 1);
       }else{
         return;
       }
     }
    }