noobinho's blog

By noobinho, history, 3 years 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?

• +8

By noobinho, history, 4 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?

• -6

By noobinho, history, 4 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.

• -7

By noobinho, history, 4 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.

• 0

By noobinho, history, 4 years ago,

I'm trying to do this problem: http://acm.timus.ru/problem.aspx?space=1&num=1416. It consists in a simple, undirected and weighted graph for which is demanded to calculate the second minimum total cost: a cost of a configuration (different than the minimum-spanning-tree) which connects all vertex and has the smallest cost not less than the cost given by the minimum-spanning-tree. If there isn't such a configuration it's demanded to indicate that. I did the following code: https://ideone.com/e.js/y4CcBz. It generates the minimum-spanning-tree with Kruskal and tries to eliminate the edges of this tree one by one from the bigger to the smallest. For each edge eliminated, it tries to connect the edges that weren't in the minimum-spanning-tree, one by one, from the bigger to the smallest, and verifies with a DFS if the resulting graph has only one connected component. If so, it stops. Else, it reconnects the edge of the minimum-spanning-tree and goes to the next iteration. Since my approach gives wrong answer, I want to know what is wrong with it and what is the correct approach. Thanks in advance.

• 0

By noobinho, history, 4 years ago,

I'm trying to solve the problem: http://acm.timus.ru/problem.aspx?space=1&num=1439. It consists basically in m (1 <= m <= 10^5) queries in an ordered set which can be of two types: 1) eliminate an element of the ordered set (the number of elements eliminated is at most 10^4); 2) find the kth element of the ordered set. The ordered set can have at most n elements (1 <= n <= 10^9).The elements are {1,2,...,n} at the beginning. I tryed to code a dynamic segment tree to solve in O(m*logn) of time, as follows:https://ideone.com/e.js/jLFIMv. However, it gave MLE. So, I want to know what I can do to improve the memory used. Thanks in advance

• 0