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

-
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.
-
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

-
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: :)
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
Post
by Ecou » Wed Aug 09, 2006 11:51 pm
Also getting WA, can't see the problem in this. The 2 examples work:
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
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
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
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
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.
-
Martin Macko
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
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 : -)
which should be treated as two sets of input.
P.S. I don't think the judge input contains tabs or trailing spaces.
-
Ecou
- New poster
- Posts: 10
- Joined: Wed Aug 09, 2006 11:47 pm
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