## 11179 - Bit Stream

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

### 11179 - Bit Stream

I couldn't find any solution without brute forcing over all the chunks.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Find an efficient way to deal with long sequences of chunks consisting of only 0's or only 1's.
(Hint: some ideas behind problem 11149 could help here.)

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
Can somebody give me some test cases? I am getting wa. My code works well in my own small cases. Please help.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
I am still wa. Here are some of the small cases that I have tried:

Code: Select all

``````1 5 100 2 0 1 0
1 5 100 2 0 0 1 0
2 5 100 2 0 0 1 0
2 5 100 2 1 0 1 0
1 5 100 2 1 0 1 0
0``````

Code: Select all

``````Bitstream 1: Compression OK
Bitstream 2: Compression OK
Bitstream 3: Invalid Length
Bitstream 4: Invalid Length
Bitstream 5: Invalid Checksum``````
I think they are correct. It is hard to check big cases by myself.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:
Just generate testcases that can be solved by a bruteforce program, so you can check the correctness of your efficient program. That's basically what I did to check my efficient program.

My AC program says your output are all correct.

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
I followed your advice and write a brute force program, but it gives the same results for my cases as my wa solution. Can you see if my brute force code is correct? It will also be great if you can send me your brute force code.

Code: Select all

``````var
L, n, m, C, sum, check_digit, chunk_value : qword;
b, i, j, tcase, num_chunks, digit : longint;
position, start : int64;
chunk_length : array[1..100008] of longint;
begin
tcase := 0;
while (not eof) do begin
if (L = 0) then break;
inc(tcase);
read(b, n, m, C);
num_chunks := 1;
sum := chunk_length[1];
repeat
inc(num_chunks);
sum := sum + chunk_length[num_chunks];
until chunk_length[num_chunks] = 0;
if (L <> sum) then
writeln('Bitstream ',tcase,': Invalid Length')
else begin
n := n mod m;
digit := 0;
chunk_value := 0;
check_digit := 0;
start := -1;
for i := 1 to num_chunks-1 do begin
for j := 1 to chunk_length[i] do begin
chunk_value := chunk_value + chunk_value + digit;
start := start + 1;
position := start mod b;
if (position = b-1) then begin
check_digit := ((check_digit*n) mod m+chunk_value mod m) mod m;
chunk_value := 0;
end;
end;
digit := 1-digit;
end;
if (padding) then begin
position := start mod b;
for i := 1 to (b-1)-position do
chunk_value := chunk_value + chunk_value; (* Append zeros *)
check_digit := ((check_digit*n) mod m+chunk_value mod m) mod m;
end;
if (check_digit = C) then
writeln('Bitstream ',tcase,': Compression OK')
else
writeln('Bitstream ',tcase,': Invalid Checksum');
end;
end;
end.``````

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
Probably no one here wants to read pascal codes. Anyway, I would really appreciate if someone can send me a working brute force solution by private message, so that I can see if I have made any fundamental misunderstanding of the problem statement. Thank you.

Erik
Learning poster
Posts: 67
Joined: Fri Jul 01, 2005 11:29 am
Location: Germany
Contact:
Hi,

your code looks ok to me. Does it give same result as your program for high chunk lenghts?
Compression OK should be output for

Code: Select all

``````640000 32 1234567890 1987654320 1671853665
320000 320000 0``````
Cu, Erik

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
Erik wrote:Hi,

your code looks ok to me. Does it give same result as your program for high chunk lenghts?
Compression OK should be output for

Code: Select all

``````640000 32 1234567890 1987654320 1671853665
320000 320000 0``````
Cu, Erik
Doesn't the input says that chunk length <= 100000? Anyway, I get the correct result for both my brute force program and my efficient program. Still I am getting wa. Shall I just give up?

tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm
I have finally got accepted. Special thanks to windows2k.

tanaeem
New poster
Posts: 26
Joined: Mon Mar 12, 2007 6:58 pm
Location: BUET
Contact:

### Getting WA

Can someone help with some tricky test cases.
I find my soln gives same result as brutforce in small cases.

christephan
New poster
Posts: 5
Joined: Fri Jan 25, 2008 9:27 pm
400000 5 1234567890 1987654320 1336952641
100000 100000 100000 100000 0

399990 5 1234567890 1987654320 1911114481
99999 99998 99997 99996 0

400000 5 4294967289 4294967295 110362555
100000 100000 100000 100000 0

All compressed OK.