Your problem
The problem is this: Imagine a 100,000-story building that firefighters insist on thousands of times to know how many people there are up to the top floor. This will make your program consume a lot by calculating and recalculating the totalPessoas. Each consultation would travel n floors and are q consultations in total, so the time in that case will be proportional to O(nq).
Other solutions that do not work
You could think of an approach to recalculate everything only when someone moves in and stores the result in a variable. But then there must be some test where there are thousands of changes and your program will again burst time with O(nq).
You can think about making an auxiliary array that shows the backlog of people up to each of the floors, to consult it when the firefighters arrive. But in this case, you would have to rebuild the table when there are changes from the floor where the change took place, and there must be some test where there are thousands of changes on the first floor, and the result is again O(nq).
Division and conquest
Perhaps a divide and conquer approach is the solution. If you keep a count of the number of people in the lower half of the building in a variable (let’s call x), the consultation of firefighters in the upper half will be much faster, because you will not need to recount the lower half, just use the value x). Similarly, if there is any change in the lower half of the building, you only need to recalculate the value x of the lower half of the building, without worrying about the values of the upper half.
Using this idea recursively, you subdivide each floor block in half until you get to a point where you have a single floor block. Then join the 2-in-2 blocks by adding up the number of people on each floor. Then join these larger 2-in-2 blocks also forming even larger blocks until you have a block that represents the entire building.
For a 12-story building, the result is what’s below:
Floors that don’t exist because they’re after the last one are considered zeroes. For example, the 193 of the fourth column should group 8 floors instead of 4, but the building ends before that and so what it has after is just zeroes.
How to find out how many people have up to some floor?
Okay, but how do we know how many people there are on the first nine floors, for example?
The answer is that the top 8 floors have 134 people and the 9th floor has 77. So the answer is 134 + 77 = 211 people.
And if we want the first seven floors?
The answer is that the first four are 88, the fifth and sixth together are 9 and the seventh is 24. So the answer is 88 + 9 + 24 = 121 people.
And if in a building bigger than this, we want up to the 42nd floor?
In this case you take the number of people of the first 32 floors, plus the number of people of the 8 floors of the 31st to 40th and then the number of people of the 41st together with the 42nd.
But how to know which of these blocks of different sizes to choose?
Just look at the number written in binary. For example:
9 is 1001, that is, 8 + 1. Then you take a block corresponding to 8 floors followed by a block of 1 floor.
7 is 111, that is, 4 + 2 + 1. Then you take a block corresponding to 4 floors followed by another of 2 floors and then one of 1 floor.
42 is 101010, that is, 32 + 8 + 2. Then you take a 32 storey block, an 8 storey and a 2 storey block.
In the building image, the blue building itself corresponds to blocks of size 1, the yellow row on your right the ones of size 2, then the ones of size 4, 8, 16 and so on. Thus, it is possible to know from which columns the blocks should be chosen.
Note that never two blocks of the same column are accessed in this operation.
How to change the amount of one-story residents?
This is easy, change the block corresponding to the floor and all the blocks to the right of it. The other blocks do not need to be recalculated.
Complexity of the solution.
How many blocks (each in a different column) each change or counting operation is accessed by firefighters?
In a building of 1 floor, 1 block.
In a building of 2 floors, 2 blocks.
In a building of 3 to 4 floors, 3 blocks.
In a building of 5 to 8 floors, 4 blocks.
In a building of 9 to 16 floors, 5 blocks.
In a building of 17 to 32 floors, 6 blocks.
...
In a building of 32.769 to 65.536 floors, 17 blocks.
In a building of 65.537 to 131.072 floors, 18 blocks.
This is starting to look good. In this case, any operation that requires the recount of people (be it the change or be it the firefighters) will end up consuming time proportional to 1 + log2 n. So the total complexity is O(q log2 n). whereas n is 100,000, and that 1 + log2 n is close to 18, this is clearly much better than any solution O(nq).
Organizing the solution
Now we need to see how we organize this in memory. We can use a matrix with 18 x 100,000, after all, 18 is the maximum of columns of blocks we have and 100,000 is the maximum of floors. We then declare pessoas[CAMADAS][MAX_N], where CAMADAS is 18 and MAX_N is 100,000.
The blocks are organized sequentially in each row of the matrix so:
With this logic, the block i column t is the father of blocks 2 * i and 2 * i + 1 column t - 1. This is important to build these blocks after the building is assembled:
pessoas[t][i] = pessoas[t - 1][2 * i] + pessoas[t - 1][2 * i + 1];
On the other side, the block k column t is son of the block k / 2 column t + 1 (and therefore k / 2 is the father of k). Note that this division is entire.
So, the brother of the block i in a column t any is the block i ^ 1 in that same column. That ^ 1 serves to invert the last bit of a number, transforming an even number into an odd and an odd pair.
When updating floor value k (in fact k - 1, because as you have already realized, this - 1 to start from 0), the parent block will receive the sum of the values of the children. Therefore, the expression to update a parent block in the column t from the changed value in the child k is:
pessoas[t][k / 2] = pessoas[t - 1][k] + pessoas[t - 1][k ^ 1];
For firefighters to check the number of people up to a certain floor k, for each layer t, look at the blocks k of that layer. To update the k when jumping from the layer t to the layer t + 1, just do k /= 2;. However, only the blocks that correspond to bits 1 as already explained are considered, which can be checked with k & 1, considering that the k is changing in this iteration. That is:
for (t = 0; t < CAMADAS && k > 0; t++) {
if (k & 1) totalPessoas += pessoas[t][k - 1];
k /= 2;
}
Resulting code
In the end, the result is this:
#include <stdio.h>
#define MAX_N 100000
#define CAMADAS 18
int main() {
int n, q, k, p, t, contEventos, evento, totalPessoas, i, pessoas[CAMADAS][MAX_N];
scanf("%d %d", &n, &q);
for (i = 0; i < n; i++) {
scanf("%d", &pessoas[0][i]);
}
for (; i < MAX_N; i++) {
pessoas[0][i] = 0;
}
for (t = 1; t < CAMADAS; t++) {
for (i = 0; i < MAX_N / 2; i++) {
pessoas[t][i] = pessoas[t - 1][2 * i] + pessoas[t - 1][2 * i + 1];
}
for (; i < MAX_N; i++) {
pessoas[t][i] = 0;
}
}
for (contEventos = 0; contEventos < q; contEventos++) {
scanf("%d", &evento);
scanf("%d", &k);
if (evento == 0) {
scanf("%d", &p);
k--;
pessoas[0][k] = p;
for (t = 1; t < CAMADAS; t++) {
pessoas[t][k / 2] = pessoas[t - 1][k] + pessoas[t - 1][k ^ 1];
k /= 2;
}
} else if (evento == 1) {
totalPessoas = 0;
for (t = 0; t < CAMADAS && k > 0; t++) {
if (k & 1) totalPessoas += pessoas[t][k - 1];
k /= 2;
}
printf("%d\n", totalPessoas);
}
// Para mostrar a tabela.
/*for (int y = 0; y < CAMADAS; y++) {
printf("\n|");
for (int z = 0; z < n; z++) {
printf("%d ", pessoas[y][z]);
}
printf("|\n");
}*/
}
return 0;
}
The bonds they have pessoas[0][i] = 0; and pessoas[t][i] = 0; are used to clean unused table positions to prevent pre-memory dirt/junk from interfering with the calculation.
Note that the table wastes a good amount of memory, because most of its positions are always empty even for a 100,000-story building full of people on all floors. The table has 1,800,000 positions, and it is even possible to reduce its size with some mathematical operations to 199,985 positions, which is its minimum size. However the code to do this would be much more complex and more difficult to understand and the performance gain would be negligible.
See here working on ideone.
I found this excellent approach to the problem, which had not yet occurred to me. And I suspect it was the solution that the author of the problem expected.
– Isac
Your answer was much better than I expected, congratulations. However I found the resolution somewhat confusing. You used bit operators I didn’t even know about. Analyzing with a little more time I’m sure I’ll be able to understand, but the point is, since this question was given to high school students, will not have a complex "less" solution?
– Antony Leme
@Antonyleme For high school students it is to expect more simplistic solutions like the one you had, without having time limitation. Now, to demand the optimal behavior of this from high school students is madness, insanity, insanity, cruelty. There are things here that depend on knowledge that is only acquired there by the 5th or 6th semester of a computer science degree, and that most students study only to pass the test and then forget.
– Victor Stafusa
@Victorstafusa I understand. As it is an Intervention, I imagine it is their intention to charge these things extra. Your resolution has drawn me to a few things that I will try to better understand, to perhaps gain a few extra points on some issue. Maybe it’s not so worrying, since theoretically my competitors have the same level of knowledge as me. Anyway, thank you.
– Antony Leme
@Victorstafusa, OBI’s problems are complex enough to be easily interchanged with those of the ACM-ICPC marathon. So, yes, whoever does these OBI questions is thinking about people who have at least four years of programming and training for competitive programming. That is: people who train since the 6 year of elementary school
– Jefferson Quesado