Tuesday, January 4, 2011

TopCoder - SRM 144 DIV 1 - BinaryCode - decode

problem statement

The problem sounds a little bit tricky at first but the test cases show you what you have to do. At first, when you assume about the first element of source to be '0' or '1', you can find the rest of them easily. But while doing this you have to take care about what you are pushing back into source, if it is some characters other than '0' or '1' the answer for this assumption is "NONE", and at the end I try to rebuild q from my result and see whether this q is equal to the given q or not? Why? Cause source[q.size()] must be equal to '0' because it's outside the string. There is one other way to do this, that while you are constructing source from given q, check whether source[q.size()] is equal to '0' or not, and there is no need to rebuild q from source.

This function returns the i-th element of string s, if i is out of range returns 0
int f( string &s, int i )
{
    if(i < 0 || i >= s.size() )
        return 0;
    return s[i]-'0';
}

This function checks whether the source that I've decoded is valid or not, by checking whether it has characters other than '0' and '1' or not, and checking that if I build q from s, is it equal to the given q or not?
bool valid( string &s, string &q )
{
    for(int i = 0; i < s.size(); i ++)
        if( s[i] != '0' && s[i] != '1' )
            return false;
      
    string t(q.size(), '0');
    for(int i = 0; i < s.size(); i ++)
        t[i] = f(s, i-1) + f(s, i) + f(s, i+1) + '0';
     
    if( q != t )
        return false;
               
    return true;
}

No comments:

Post a Comment