### noobinho's blog

By noobinho, history, 11 months ago, , I want a list of balanced binary search trees so that I can answer queries for insert, delete and median in each tree. Based on this post I coded the following:

struct Tree{
multiset<int> ms;
multiset<int>::iterator med_it;
int med_idx;
};

int Ceil(int a, int b){
return (a+1)/b;
}

void initializeTree(Tree (&tree), int el){
(tree.ms).insert(el);
(tree.med_it) = (tree.ms).begin();
(tree.med_idx) = 1;
}

void TreeInsert(Tree (&tree), int el){
(tree.ms).insert(el);

if(el < *(tree.med_it)) (tree.med_idx)++;

int idx = Ceil((tree.ms).size(),2);

if(tree.med_idx < idx) (tree.med_it)++;
else if(tree.med_idx > idx) (tree.med_it)--;

tree.med_idx = idx;
}

void TreeDelete(Tree (&tree), int el){
multiset<int>::iterator aux;

int idx = Ceil((int)(tree.ms).size() - 1,2);

if(el == *(tree.med_it)){
aux = (tree.med_it);

if((tree.med_idx) == idx) aux++;
else aux--;

(tree.ms).erase((tree.med_it));
(tree.med_it) = aux;
}
else{
aux = (tree.ms).find(el);
(tree.ms).erase(aux);

if(el < *(tree.med_it)) (tree.med_idx)--;

if((tree.med_idx) < idx) (tree.med_it)++;
else if((tree.med_idx) > idx) (tree.med_it)--;
}

(tree.med_idx) = idx;
}

int TreeMerge(Tree (&tree1), Tree (&tree2)){
multiset<int>::iterator it;

if((tree1.ms).size() >= (tree2.ms).size()){
for(it = (tree2.ms).begin(); it != (tree2.ms).end(); it++) TreeInsert(tree1, *it);
return 1;
}
else{
for(it = (tree1.ms).begin(); it != (tree1.ms).end(); it++) TreeInsert(tree2, *it);
return 2;
}
}


I tested all the functions and they seem to work well. But then I created a list L to be my list and inserted some trees on it to test the functions on the members of the list. The following code shows that:

Tree tree1, tree2;

initializeTree(tree1,9);
initializeTree(tree2,4);

list<Tree> L;

L.push_back(tree1);
L.push_back(tree2);


Then I acessed the members of the list with list::iterator as shown in the code below:

list<Tree>::iterator L_cur = L.begin(), L_next = L.begin();
L_next++;


So I applied the functions to *L_cur and *L_next and the med_it pointer got some bug. For example, when running the code below:

int merge = TreeMerge(*L_cur,*L_next);


When I access the content of the L_cur and L_next pointers all seems to work as expected except for the med_it pointer of the tree in L_cur, which continues pointing to 9 instead of 4.

When I run the same function with two Tree objects it seems to work well, as shown in the code below:

Tree tree1, tree2;

initializeTree(tree1,9);
initializeTree(tree2,4);

int merge = TreeMerge(tree1,tree2);


Why it occurs?

By noobinho, history, 2 years ago, , I'm trying to solve this problem: http://acm.timus.ru/problem.aspx?space=1&num=1421. I created a graph in which the source vertex is 0 and the sink vertex is 2n + 1. Vertices from 1 to n are the banks and vertices from n+1 to 2n are the enterprises. After the necessary connections have been made, I ran the O(V³) algorithm to find the maxflow of the graph and construct the demanded matrix A. I stored the sum of the lines of the matrix in the array r and the sum of the columns in the array col. If some of those sums are different from some of the elements in the arrays sr or sc or if some element of the matrix A is negative it prints "NO". It gives WA#19. Code: https://ideone.com/i9l3zW. Someone could help me, please?

By noobinho, history, 2 years ago, , I'm trying to solve this problem: http://acm.timus.ru/problem.aspx?space=1&num=1455. In short, it gives a dictionary consisting of 'n' words (1 <= n <= 100). Each word consists of from 1 to 100 small latin letters. It's demanded to find an expression which can be formed by at least two different sequences of words from the dictionary. The expression should not be more than 20000 characters long. If the problem has several solutions, you may output any of them. Any help would be appreciated. Thanks in advance.

By noobinho, history, 2 years ago, , I'm trying to solve this problem: http://acm.timus.ru/problem.aspx?space=1&num=1458. It gives a n x n matrix (2 <= n <= 1000), with n always even, with all entries 0-1. We can change the matrix with operations with the format op(i,j), which turns on all the zeros and turns off all the ones in the ith horizontal and in the jth vertical. It's demanded to find the minimum number of operations (and output these operations) that we can apply to the matrix to get a matrix with all entries 0 or a matrix with all entries 1. I found a closed way to turn on or turn off a unique entry of the matrix using (2*n-1) operations and used it in my algorithm in the following way: I count the number of ones in the matrix. If it's less than (n*n)/2, I turn off all the ones of the matrix to get a matrix with all entries 0. Else, I turn on all the zeros to get a matrix with all entries 1 (code: https://ideone.com/e.js/XU3rHF ), but it gives TLE. So, I would like to know what I can do to improve the complexity of the algorithm (at this moment, I think it's O(n³), which is not enough for 2 <= n <= 1000). Thanks in advance.

By noobinho, history, 2 years ago, , By noobinho, history, 2 years ago, , 