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 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.
I don't think even the solution proposed could even solve the runtime exceed problem
Write it down as comments in the programming language of your choice, anyway. Ponder how to test the results, and have that coded, too (hint: you got one implementation - confident it gives correct results?). Flesh out the "comments only" version of the proposed approach until your friendly debugger steps you through the process. Compare results. Watch your algorithm/code handling a bigger problem instance: where does it look dumb? Could it have used earlier results? \$\endgroup\$