11063 - B2-Sequence

[Martin Macko]

I just recoded this in C and it worked. Here's my Java solution that I couldn't get accepted (I have no idea what's wrong - a few people got it in Java today):

Trace the wollowing part of your code for sequence "1 2 -1000":

............for (int i = 0; i < n; i++) {
...............if (b[i] > 10000 || (i < n - 1 && b[i] >= b[i + 1])) {
..................ok = false;
..................break;
...............}
...............for (int j = i; j < n; j++) {
..................int sum = b[i] + b[j];
..................if (seen[sum]) { ...........<-- here you access seen[-999] for i=0 and j=2 as b[2] is not checked for being negative yet.
.....................ok = false;
.....................break;
..................}
..................seen[sum] = true;
...............}
...............if (!ok)
..................break;
............}

[Darko]

Nice catch! Thanks for that.

The worst part is - I do exactly the same thing in C and it gets AC

[Martin Macko]

I checked the followings:
i. number[0] is >= 1 else not a B2-seq
ii. number [i + 1] > number else not a B2-seq
iii. using a boolean array checking for uniqueness

I must be missing something, too. But what is that?

Yes, you are right, but make sure you check i. and ii. before checking iii. to make sure you don't access negative indicies of the array.

[Martin Macko]

Nice catch! Thanks for that.

The worst part is - I do exactly the same thing in C and it gets AC

Lucky man you haven't overwrited any important data in the variables stored in the memory just before that array

[temper_3243]

does there exist an algorithm less than o(n^2) for this problem .

[miras]

Hi guys...

I spend nearly 2 hours sitting at H problem... and I couldn't find out what is wrong...

PLEASE... tell me
Here is my pascal code

Code: Select all

program hhh;
var sum:array[0..40000] of boolean;
    tab:array[1..200] of longint;
    b,a,n,numb:longint;
    niemoge:boolean;


procedure read_data;
 begin
 niemoge:=false;
 readln(n);
  for a:=0 to 40000 do sum[a]:=false;
  for a:=1 to n do read(tab[a]); readln; readln;

 for a:=2 to n do if (tab[a]<=tab[a-1]) then niemoge:=true;
 if tab[1]<1 then niemoge:=true;

if niemoge=false then
begin
  for a:=1 to n do
   for b:=a to n do
    if (sum[tab[a]+tab[b]]=false) then sum[tab[a]+tab[b]]:=true else
    niemoge:=true;
end;

    write('Case #',numb,': It is');
 if niemoge=false then writeln(' a B2-Sequence.') else
 writeln(' not a B2-Sequence.');
 writeln;
 end;




begin
while not eof do
begin
inc(numb);
read_data;
end;
end.

thanks.. [/code][/list]

[nymo]

Hi martin macko, thanks for assuring... I rechecked again and found the error, it was a misplaced break statement... thanks for everything

[Ecou]

Also getting WA, can't see the problem in this. The 2 examples work:

Code: Select all

// resolved
}

[Observer]

Hi guys...

I spend nearly 2 hours sitting at H problem... and I couldn't find out what is wrong...

PLEASE... tell me
Here is my pascal code

Code: Select all

...

thanks.. [/code][/list]

I strongly believe that the judge is wrong!!!!

miras, make the following to changes to your above code:
1. write "read(n)" instead of "readln(n)";
2. write "while not eof and eoln do readln" instead of "readln; readln;".
Then you can get Accepted!! Probably there are invalid cases where number of elements != N...

[Martin Macko]

Also getting WA, can't see the problem in this. The 2 examples work:

Try to use a bigger buffer for read lines.

int main(int argc, char** argv) {
..char input[600];........<-- Set it to something about 10000.
..int n, casenum = 1;
.....
}

[Ecou]

That did not help, still WA. and <=100 5 digit numbers should have fitted easily.

[Martin Macko]

That did not help, still WA. and <=100 5 digit numbers should have fitted easily.

Yes, but possibly the numbers could be separated by more than just one space... or even by some other whitespace such as tabs.

I don't see any error in your code. Maybe you could try to change the way you are reading the input. Try to read it by scanf() directly instead of using gets(). Write something like the following:

while (scanf("%d ", &n)==1)
{
........for (i=0; i<n; i++) scanf("%d ", &p[i]);
...........
}

[Observer]

Yes, do NOT read line by line. Try to read number by number. The judge input file is probably incorrect.

I guess there are cases like: (this is just my guess : -)

Code: Select all

2
1 3 2 1 3

which should be treated as two sets of input.

P.S. I don't think the judge input contains tabs or trailing spaces.

[Ecou]

Thanks a lot. A little more tolerance with the input and it worked.

[asif_rahman0]

Can someone check the following Input/output:

Code: Select all

4
1 2 3 3
4
15 16 17 18
4
-5 0 5 9
6
1 9 19 0 45 70
6
1 9 19 45 70 150
5
15 16 -1 17 18
4
2 2 2 3
4
2 2 2 2
4
1 9 18 36
5
1 9 10 18 36

Output:

Code: Select all

Case #1: It is not a B2-Sequence.
Case #2: It is a B2-Sequence.
Case #3: It is not a B2-Sequence.
Case #4: It is not a B2-Sequence.
Case #5: It is a B2-Sequence.
Case #6: It is not a B2-Sequence.
Case #7: It is not a B2-Sequence.
Case #8: It is not a B2-Sequence.
Case #9: It is a B2-Sequence.
Case #10: It is not a B2-Sequence.

thnx
rabbi