wolfsniper2388
Wrong answer in buddy system bitmap
0
/ \
0 1
/ \ / \
1 0 1 1
/\ / \ /
1 1 1 0 1
Error clearing bit from 3 for 3
Output: 0 0 1 0 0 0 1 0 1 1 0 0
Expected: 0 0 0 0 0 0 1 0 1 1 0 0
Error clearing bit from 4 for 2
Output: 0 0 1 1 0 0 1 1 1 1 0 0
Expected: 0 0 0 1 0 0 1 1 1 1 0 0
Error clearing bit from 5 for 1
Output: 0 0 1 1 0 0 1 1 1 1 0 0
Expected: 0 0 0 1 0 0 1 1 1 1 0 0
For example clearing 3 for 3, the tree should be like
0
/ \
0 0
/ \ / \
0 0 0 1
/\ / \ /
0 1 1 0 0
But your program gives
0
/ \
0 1
/ \ / \
0 0 0 1
/\ / \ /
0 1 1 0 0
where A[2] isn't updated.
And I don't understand why you only use one variable x, shouldn't it be a different variable inside the while loop since x is for for x in range(pos, min(n+1, pos+length)):?
I think clear_bit may look something like
void clear_bit (vector<int>& A, int offset, int length) {
if (A.empty() || offset < 0 || offset > A.size() || length <= 0)
return;
for (int i = offset; i < offset + length; i++) {
if (A[i] == 0)
continue;
A[i] = 0;
int x = i;
while (x < A.size()) {
if (2 * x + 1 < A.size() && A[2 * x + 1] == 1)
A[2 * x + 1] = 0;
x = 2 * x + 1;
}
x = i;
while (x > 0) {
if (A[(x - 1) / 2] == 0)
break;
A[(x - 1) / 2] = 0;
x = (x - 1) / 2;
}
}
}
These following three test cases are giving incorrect answer < after clearing bit from 3 for 3 A is: [0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0] < after clearing bit from 4 for 2 A is: [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0] < after clearing bit from 5 for 1 A is: [0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0]
The correct answer (valid bitmap) should be,
after clearing bit from 3 for 3 A is: [0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0] after clearing bit from 4 for 2 A is: [0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0] after clearing bit from 5 for 1 A is: [0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0]
