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

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

11179 - Bit Stream

Post by sunny » Wed Feb 28, 2007 9:36 pm

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:

Post by mf » Wed Feb 28, 2007 9:57 pm

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

Post by tobby » Thu Mar 08, 2007 8:38 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

Post by tobby » Fri Mar 09, 2007 4:13 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:

Post by sclo » Sat Mar 10, 2007 2:32 am

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

Post by tobby » Sat Mar 10, 2007 4:25 am

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;
  padding : boolean;
begin
  tcase := 0;
  while (not eof) do begin
    read(L);
    if (L = 0) then break;
    inc(tcase);
    read(b, n, m, C);
    num_chunks := 1;
    read(chunk_length[1]);
    sum := chunk_length[1];
    repeat
      inc(num_chunks);
      read(chunk_length[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;
      padding := false;
      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;
          padding := true;
          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;
            padding := false;
          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

Post by tobby » Mon Mar 12, 2007 4:30 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:

Post by Erik » Tue Mar 13, 2007 7:23 pm

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

Post by tobby » Wed Mar 14, 2007 1:01 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

Post by tobby » Mon Mar 19, 2007 2:01 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

Post by tanaeem » Mon Dec 31, 2007 10:09 am

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

Post by christephan » Fri Jan 25, 2008 9:29 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.

Post Reply

Return to “Volume 111 (11100-11199)”