3
\$\begingroup\$

Due to severe code-evolution i will repost this question here! The original can be found here : Kattis Challenge - Animal Classification

I'm new to competitive programming and C++ in general. I have solved the Kattis Animal Classification challenge. We are given two classification trees, each represented using nested parentheses. For example, ((3,(1,(5,2))),4) and (((5,1),(2,3)),4) represent the trees

   ╱╲                   ╱╲
  ╱╲ 4                 ╱╲ 4
 ╱ ╱╲                 ╱  ╲
3 1 ╱╲               ╱╲  ╱╲
   5  2             5 1  2 3

The challenge is to report the fact that there are 7 subgroups in common between the two trees (namely {1}, {2}, {3}, {4}, {5}, {1,2,3,5}, and {1,2,3,4,5}).

My approach is to parse the strings into trees in linear time. After that i recursively traverse up the subtrees, reporting the elements along the way. If i'm at a leaf i create a singleton set and add it into the wanted superset, if i'm at a junction i take the union of the sets left and right and add it into the superset. The process of computing the subsets takes a long time and i'm not quite sure why, since in a complete binary tree it's a O(Nlog(N)) operation. The code does not finish on the test cases and i would love some helpful advice. Thank you in advance!

Code can be found here :

#include <iostream>
#include <list>
#include <algorithm>
#include <string>
#include <unordered_set>

using namespace std; 


struct hashX{
  size_t operator()(const unordered_set<int> &x) const{
    int sum = 0;
    for(int element: x){sum = sum+element;}
    return hash<int>()(sum);
  }
};

class node{
    public:
        struct node *left,*right;
        int data;
        bool isleaf;
};

void make_tree(string s, struct node **root){
    //the stack will hold the node hierarchy, the last element will be the current parent node.
    list<node*> stack;
    struct node *newnode,*current,*previous, *previousprevious;
    int i = 0;
    while(i < s.size()){
        // if we see ( we create a new node and push it back as the current parent onto the stack
        if(s[i] == '('){
            newnode = new node();
            newnode->data = -1;
            newnode->left = NULL;
            newnode->right= NULL;
            newnode->isleaf= false;
            stack.push_back(newnode);
        }
        // if we see a digit we parse it, create a leaf and push it onto the stack
        else if(isdigit(s[i])){
            //parse the whole number
            string tmp = "";
            while( isdigit(s[i]) ){
                tmp += s[i];
                i++;
                }
            int int_tmp = stoi(tmp);
            i--;
            //create a leaf node and push it onto the stack
            newnode = new node();
            newnode->data = int_tmp;
            newnode->left = NULL;
            newnode->right= NULL;
            newnode->isleaf= true;
            stack.push_back(newnode);
        }
        // if we see ) the current node is finished and the right child of the previous previous node, the previous node is the left child .. see (a, (b, c))  root = ( ..... ) .. left child = a, right child = (b, c)
        else if(s[i] == ')'){
            current = new node();
            current = stack.back();
            stack.pop_back();
            previous = new node();
            previous = stack.back();
            stack.pop_back();
            previousprevious = new node();
            previousprevious = stack.back();
            stack.pop_back();
            previousprevious->right = previous;
            previousprevious->left = current;
            stack.push_back(previousprevious);
        }
        i++;
    }
    *root = stack.front();
}

unordered_set<int> get_sets(node *T, unordered_set<unordered_set<int>, hashX> &subsets){
    //if we encounter a leaf node we add the singleton set of its data to the subsets
    if(T->isleaf){
            unordered_set<int> subset;
        subset.insert(T->data);
            subsets.insert(subset);
        return subset;
    }
    //else we join the subsets of its children, and add it to the subsets
        else{
        node *left = T->left;
        node *right = T->right;
        unordered_set<int> x = get_sets(left, subsets);
        unordered_set<int> y = get_sets(right, subsets);
        for(int i: x){
            y.insert(i);
        }
        subsets.insert(y);
        return y;
    }
}

int main(){
    int n;
    cin >> n;
    //input stuff
    string inputA, inputB;
    cin >> inputA; 
    cin >> inputB;
    //construct the trees
    struct node *TreeA, *TreeB;
    make_tree(inputA, &TreeA);
    make_tree(inputB, &TreeB);
    //get the subsets
    unordered_set<unordered_set<int>, hashX> setsA;
    unordered_set<unordered_set<int>, hashX> setsB;
    get_sets(TreeA, setsA);
    get_sets(TreeB, setsB);
    //compute the size of the intersection
    int result = count_if(setsB.begin(), setsB.end(), [&](unordered_set<int> subsetofB) {return setsA.find(subsetofB) != setsA.end();});
    cout << result;
}

Update1:

I profiled a bit and it seems that almost all of the time is taken by the

y.insert(x.begin(), x.end());
subsets.insert(y);

part of the get_sets function.

Update2:

the problem with y.insert(x.begin(), x.end()) is that this insertion is linear in the number of inserted elements, which leads to quadratic complexity in the worst case. If we first find the smaller set of both and add it to the larger set we gain NlogN complexity. So thats one problem solved. There is still the problem that the subsets.insert(y) takes much to long! Any Ideas?

\$\endgroup\$
  • 1
    \$\begingroup\$ First, I don't have the answer to your question, but I've solved several competitive problems and know some tricks. First, you need to think out of the box, forget what you're supposed to answer and concentrate in what the solution is. Do you really need to generate all the subsets to know if they are matching. I'm almost sure, you don't need to. \$\endgroup\$ – fernando.reyes Sep 21 '16 at 22:27
  • \$\begingroup\$ At least in the case that both trees are the same, i would need all the sets, i think. But maybe there is some reduction i have overlooked thus far! \$\endgroup\$ – M.Hoffmann Sep 21 '16 at 22:31
  • \$\begingroup\$ Let me propose you something and you do it if you think it is reasonable. You assign each element a binary place, and each group will be represented by just a number. Then you compare if the numbers in a list are contained in the other list, and there you go. Managing a list of numbers will take less resources and less time than creating trees and subsets. \$\endgroup\$ – fernando.reyes Sep 21 '16 at 22:35
  • \$\begingroup\$ Im sorry, i dont understand. It would be nice to have a way that maps the subgroups to numbers in a one to one way, that would certainly solve the problem. But im not sure how that should be done. \$\endgroup\$ – M.Hoffmann Sep 22 '16 at 6:45
1
\$\begingroup\$

A binary representation of your subsets would be like this:

long set1 = 0;
set1 = set1 | 1 << 5 | 1 << 3; // This would be 101000
std::cout << "set1: " << set1 << endl;
long set2 = 0;
set2 = set2 | 1 << 1 | 1 << 3; // this would be 001010
std::cout << "set2: " << set2 << endl;

This way in the end you'll have just a list of numbers, and the comparison will be very fast. In the part of the 1 << 5 you add each element of the subset to the binary representation.

\$\endgroup\$
  • \$\begingroup\$ Thats cool, but one problem is to be solved, namely if the tree degenerates into basically a linked list then the binary representation would be 10**5 digits long. So the numbers might get large, but i think thats very smart, one could take this number modulo the number of all sets maybe ( there will be n-1 sets ). I have to think about that. Very nice idea, thank you! \$\endgroup\$ – M.Hoffmann Sep 22 '16 at 18:21
  • \$\begingroup\$ I tried hashing this representation by doing for(auto i: subset){ subsethash = (subsethash + 2**i)%largePrime; } subsets.push_back(subsethash); This works on the smaller test sets but fails on the larger ones. \$\endgroup\$ – M.Hoffmann Sep 23 '16 at 10:36
  • \$\begingroup\$ I solved it by producing two numbers with different primes and counting the same tuples.. that worked very well, thank you so much! \$\endgroup\$ – M.Hoffmann Sep 23 '16 at 14:14
1
\$\begingroup\$

Some small remarks:

  1. Do not use namespace std It is considered bad practice and doesnt save you anything

  2. A class with only public members is not really usefull, you might use a struct for that. Also you have open coded the constructor of the node:

    if(s[i] == '('){
        newnode = new node();
        newnode->data = -1;
        newnode->left = NULL;
        newnode->right= NULL;
        newnode->isleaf= false;
        stack.push_back(newnode);
    }
    

    Instead define a proper constructor.

  3. Sort include headers alphabetically, that makes things much easier.

  4. Nested single line statements are (at least for me) bad pratice.

    for(int element: x){sum = sum+element;}
    

    At a first glance it is hard to discriminate what is the condition and what is the following code

    Also separate controll flow instructions with a whitespace so one can easily discriminate them from functions

    for (int element : x) {
        sum += element;
    }
    
\$\endgroup\$
  • \$\begingroup\$ You are right, node should have been a struct! Isn't namespace std okay in competitive programming scripts? \$\endgroup\$ – M.Hoffmann Sep 22 '16 at 7:59
  • 1
    \$\begingroup\$ I would say no. The reason is that if you dont use it here you will not use it somewhere else. And once you are accustomed to using std:: whenever necessary you can use it in those scripts too. Its not like it will cost you a significant amount of time. \$\endgroup\$ – miscco Sep 22 '16 at 8:03
  • \$\begingroup\$ Okay i can understand that! \$\endgroup\$ – M.Hoffmann Sep 22 '16 at 8:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.