## 11063 - B2-Sequence

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

Moderator: Board moderators

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Darko wrote: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":
work() wrote:............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
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Nice catch! Thanks for that.

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

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
nymo wrote: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
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Darko wrote: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
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am
does there exist an algorithm less than o(n^2) for this problem .

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
Hi guys...

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

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;

begin
niemoge:=false;
for a:=0 to 40000 do sum[a]:=false;

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);
end;
end.
``````
thanks.. [/code][/list]
Remember Never Give Up
Miras

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### I 've found my bug :)

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

Ecou
New poster
Posts: 10
Joined: Wed Aug 09, 2006 11:47 pm

### Also WA, need help

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

Code: Select all

``````// resolved
}
``````
Last edited by Ecou on Fri Aug 11, 2006 10:56 am, edited 1 time in total.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
miras wrote:Hi guys...

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

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:
Then you can get Accepted!! Probably there are invalid cases where number of elements != N...
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: Also WA, need help

Ecou wrote:Also getting WA, can't see the problem in this. The 2 examples work:
Try to use a bigger buffer for read lines.
Ecou's main() wrote:int main(int argc, char** argv) {
..char input[600];........<-- Set it to something about 10000.
..int n, casenum = 1;
.....
}

Ecou
New poster
Posts: 10
Joined: Wed Aug 09, 2006 11:47 pm

### Didn't help

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

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

### Re: Didn't help

Ecou wrote: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
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
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.
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Ecou
New poster
Posts: 10
Joined: Wed Aug 09, 2006 11:47 pm

### Thanks, that did it.

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

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm
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