11179 - Bit Stream

[sunny]

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

[mf]

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]

Can somebody give me some test cases? I am getting wa. My code works well in my own small cases. Please help.

[tobby]

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]

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]

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]

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]

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]

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]

I have finally got accepted. Special thanks to windows2k.

[tanaeem]

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

[christephan]

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.