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

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

Post by Martin Macko » Sun Aug 06, 2006 7:55 am

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
Location: Calgary, Canada

Post by Darko » Sun Aug 06, 2006 7:58 am

Nice catch! Thanks for that.

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

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

Post by Martin Macko » Sun Aug 06, 2006 7:58 am

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.

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

Post by Martin Macko » Sun Aug 06, 2006 8:01 am

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 8)

temper_3243
Experienced poster
Posts: 105
Joined: Wed May 25, 2005 7:23 am

Post by temper_3243 » Sun Aug 06, 2006 9:17 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

Post by miras » Sun Aug 06, 2006 9:28 am

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]
Remember Never Give Up
Regrads
Miras

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

I 've found my bug :)

Post by nymo » Sun Aug 06, 2006 9:58 am

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

Post by Ecou » Wed Aug 09, 2006 11:51 pm

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

Post by Observer » Thu Aug 10, 2006 3:10 am

miras wrote: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!! :evil: 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

User avatar
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

Post by Martin Macko » Thu Aug 10, 2006 8:24 am

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

Post by Ecou » Thu Aug 10, 2006 9:37 am

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

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

Re: Didn't help

Post by Martin Macko » Thu Aug 10, 2006 9:53 am

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

Post by Observer » Thu Aug 10, 2006 10:37 am

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.

Post by Ecou » Thu Aug 10, 2006 12:47 pm

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

Post by asif_rahman0 » Thu Aug 10, 2006 9:16 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

Post Reply

Return to “Volume 110 (11000-11099)”