1052 - Bit Compressor

[morris821028]

My AC input & output

Code: Select all

32 27
10000010011110011
3 3
11
2 2
11
2 1
10
15 9
0110000100100
11 7
0101010011
2 1
01
9 3
00011000
15 5
100010000001000
12 4
101000010100
20 10
110100000010011010
13 7
011001001000
18 8
100101001000010000
14 4
10101000000001
0 0

Code: Select all

Case #1: NO
Case #2: YES
Case #3: YES
Case #4: YES
Case #5: NO
Case #6: NO
Case #7: YES
Case #8: YES
Case #9: NO
Case #10: YES
Case #11: NO
Case #12: YES
Case #13: NO
Case #14: YES

[red_apricot]

This one seems to be a nice backtracking problem, and this is my code. Anyone has an idea on why it gets WA?

Code: Select all

/*
 * 1052. Bit Compressor
 * m: the length of the original message
 * n: the number of 1's in the original message
 */
#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
enum { NO, YES, NOT_UNIQUE };
typedef unsigned long long u64;
typedef long long i64;

i64 ts,m,n;
char buff[1<<21];

int f( char *s, i64 m, i64 n ) {
    int i,j,k,t,success_01 = 0,ii = -1,jj,
                success_02 = 0,
                status;
    i64 ax;

    if ( !*s ) {
        if ( !m && !n )
            return YES;
        return NO;
    }

    if ( n < 0 || m < 0 )
        return NO;

    if ( !m ) 
        return NO;

    if ( !n ) {
        for ( k = 0, i = 0; s[i] == '0' && k < m; ++i, ++k );
        if ( s[i] == '1' )
            return NO;
        if ( k == m && s[m] )
            return NO;
        assert( !s[i] );
        return k == m ? YES:NO;
    }

    for ( i = 0; s[i]; i = j ) {
        for ( j = i; s[j] == '0'; ++j );
        if ( !s[j] ) break ;
        for ( t = j, k = 1; s[++j] == '1' && ++k; );
        if ( k >= 3 ) {
            ii = t, jj = j-1;
            assert( jj-ii+1 == k );
            break ;
        }
    }

    if ( ii != -1 ) {
        for ( k = t = 0, i = 0; i < ii; t += (int)(s[i++]-'0'), ++k );
        for ( ax = s[i=ii]-'0', j = i+1; s[j]; ++j ) {
            ax <<= 1, ax += ((i64)(s[j]-'0'));
            if ( s[j+1] == '1' )
                continue ;
            if ( ax > (j-i+1) ) {
                if ( NOT_UNIQUE == (status = f(s+j+1,m-k-ax,n-t-ax)) )
                    return NOT_UNIQUE;
                if ( status == YES && (++success_01) >= 2 )
                    return NOT_UNIQUE;
            }
        }
        return success_01==1?YES:NO;
    }

    assert( ii == -1 );
    for ( k = t = 0, i = 0; s[i]; t += (int)(s[i++]-'0'), ++k )
        if ( (ax = s[i]-'0') && !(i >= 1 && s[i-1] == '1') ) {
            for ( j = i+1; s[j]; ++j ) {
                ax <<= 1, ax += (i64)(s[j]-'0');
                if ( s[j+1] == '1' )
                    continue ;
                if ( (j-i+1) < ax ) {
                    if ( NOT_UNIQUE == (status = f(s+j+1,m-k-ax,n-t-ax)) )
                        return NOT_UNIQUE;
                    if ( status == YES && (++success_01) >= 2 )
                        return NOT_UNIQUE;
                }
            }
        }

    if ( n == t && m == k ) 
        return !success_01 ? YES:NOT_UNIQUE;

    return success_01==1?YES:NO;

}

int main() {
    int res,i,j,k;
#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
#endif
    while ( 2 == scanf("%lld %lld",&m,&n) && (m||n) ) {
        scanf("%s",buff), printf("Case #%lld: ",++ts);
        for ( i = 0; !isdigit(buff[i]); ++i );
        for ( k = i; buff[k] && isdigit(buff[k]); ++k );
        buff[k] = '\0';
        if ( NO == (res = f(buff+i,m,n)) ) 
            puts("NO");
        else if ( res == NOT_UNIQUE )
            puts("NOT UNIQUE");
        else puts("YES");
    }
    return 0;
}

[brianfry713]

Try running your code on the sample input.

[red_apricot]

I got AC -- had to resort to memoisation... I changed the above code to handle cases both sample and found above, but still it was WA. Thanks.

[Hikari9]

I'm confused. Why is the answer for this test case NO? Can't the last two bits be decompressed into 111?

Code: Select all

32 27
10000010011110011
00

[Hikari9]

Oh, my bad. Apparently, one can't compress "11" into "10"

[metaphysis]

Test data generator.

Code: Select all

#include <bits/stdc++.h>

using namespace std;

int main(int argc, char *argv[])
{
    srand(time(NULL));
    
    for (int cs = 1; cs <= 1000; cs++)
    {
        int L = rand() % 200 + 1, N = rand() % L + 1;
        cout << L << ' ' << N << '\n';
        int T = rand() % 40 + 1;
        for (int i = 1; i <= T; i++)
            cout << (rand() % 2);
        cout << '\n';
    }
    cout << "0 0\n";

    return 0;
}

[metaphysis]

Before trying to solve it, please make sure you have comprehended the constraint in description completely:
"Replace any maximal sequence of n 1’s with the binary version of n whenever it shortens the length of the message."