n the computer science class at the school in Byteland, the teacher handed out t

Question

n the computer science class at the school in Byteland, the teacher handed out the following assignment as homework:

"For an integer n, let bn denote the bit parity of the binary representation of n, i.e. bn=0 if n has an even number of ones when written down in the binary system, and bn=1 otherwise. The numbers bn, for n >=0, form an infinite sequence of bits (zeros and ones). Given a sequence c=(c0, ..., cp-1) of p bits, find the first occurrence of sequence c as a subsequence of b (i.e., the smallest value of index k such that for all i between 0 and p-1, we have ci = bi+k)."

And the teacher gave his students several short sequences c, asking them to provide the answers next day. Most, as expected, wrote programs to solve the task. Only Johnny computed the results by hand, claiming (quite correctly) that it was quicker that way. The teacher, slightly exasperated, decided to teach Johnny a lesson, and prepared a harder assignment, just for him.

"Given a sequence c=(c0, ..., cp-1) of p bits, for each s between 0 and p-1, compute the first occurrence of the prefix (c0, ..., cs) of sequence c as a subsequence of b."

And to be doubly sure that Johnny does his homework using a computer, the teacher gave him some really long sequences to deal with. Now, Johnny is in a bit of a spot, because he has never bothered to learn to program. Please help him out!

The first line of input contains a positive integer t < 10, describing the number of tests. Exactly t test cases follow.

Each test case is given in two lines. The first line contains integer p (1<=p<=106, the length of sequence k). The next line contains exactly p space-separated numbers (0 or 1), denoting successive elements of sequence c.

For each test case, print a line containing exactly p space-separated numbers, corresponding to the indexes of the first occurrence of successive prefixes of c as subsequences of b. All indexes are numbered starting from zero. If there is no such occurrence, output -1.

Explanation:

The first 16 elements of b are:
0 1 1 0 1 0 0 1 1 0 0 1 0 1 1 0

The prefix '1' first appears in b at index 1,

The prefix '1 0' first appears in b at index 2,

The prefixes '1 0 0' and '1 0 0 1' first appear in b at index 4,

... and so on.

There are no occurences of '1 0 0 1 0 1 1 1' in sequence b.

Explanation / Answer

#include <iostream>

#include <stdlib.h>

#include <stdio.h>

using namespace std;

int radix[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000 };

inline void print_number(int num, char*& p)

{

if ( num < 0 ) { *p++ = '-'; num = -num; }

int count = 1;

while ( radix[count] <= num ) count ++;

for ( int i = count - 1 ; i >= 0 ; i -- )

{

int digit = num / radix[i];

*p++ = digit + '0';

num -= radix[i] * digit;

}

}

inline void read_number(int& num, char*&p)

{

num = 0;

while ( (unsigned char)(*p - '0') > 9 ) p ++;

while ( (unsigned char)(*p - '0') <= 9 ) num = num * 10 + *p++ - '0';

}

#define MAX_P (1<<20)

char c[MAX_P];

char b[MAX_P*8];

int idx[MAX_P];

char line[MAX_P*8];

void solve()

{

// input

int p;

scanf("%d", &p);

gets(line);

gets(line);

char* s = line;

for ( int i = 0; i < p ; i ++ )

{

int num;

read_number(num, s);

c[i] = num;

}

int pow2 = 1;

while ( pow2 < p ) pow2 <<= 1;

pow2 <<= 3;

b[0] = 0;

for ( int i = 1; i < pow2; i<<=1 )

{

int n = i;

for ( int k = n ; k < (n << 1); k ++ )

b[k] = b[k-n]^1;

}

int start = 0;

int match = 0;

for ( int l = 1; l <= p ; l ++ )

{

if ( idx[l-2] == -1 ) { idx[l-1] = -1; continue; }

int i, j;

for ( i = start ; i < (pow2>>1) ; i ++ )

{

for ( j = 0; j < l ; j ++ )

{

if ( c[j] != b[i+j] ) break;

if ( j == l-1 )

{

idx[l-1] = i;

start = i+1;

l++;

if ( l > p ) break;

}

}

if ( l > p ) break;

}

if ( i == (pow2>>1) )

idx[l-1] = -1;

if ( start == 3*(pow2>>3) ) start = 5*(pow2>>3);

}

// output

s = line;

for ( int i = 0; i < p ; i ++ )

{

print_number(idx[i], s); *s++ = ' ';

}

*s = 0;

printf("%s ", line);

}

int main(int argc, char* argv[])

{

int t;

scanf("%d", &t);

for ( int i = 0 ; i < t ; i ++ )

solve();

return 0;

}

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.