10543  Traveling Politician
Moderator: Board moderators

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
10543  Traveling Politician
During the online contest, my Pascal program kept on crashing because of dirty input. I spent a lot of time on this, and gave up the whole contest out of pure frustration
Now I'm testing again, but my little program, that does nothing else than reading the input, keeps on crashing too:
[pascal]program test;
var
mink,roads,cities:integer;
c1,c2,r:integer;
begin
repeat
read(cities,roads,mink);
if ((cities=0) and (roads=0) and (mink=0)) then break;
for r:=1 to roads do begin
read(c1,c2);
end;
until false;
while true do continue;
end.[/pascal]
It should loop forever after succesfully reading the input, giving TLE, but it halts after 0.002 seconds, which means it can't handle the input file. I tried readln instead of read, but with the same result.
Can anybody, preferably one of the problemsetters, tell me what's going on?
Now I'm testing again, but my little program, that does nothing else than reading the input, keeps on crashing too:
[pascal]program test;
var
mink,roads,cities:integer;
c1,c2,r:integer;
begin
repeat
read(cities,roads,mink);
if ((cities=0) and (roads=0) and (mink=0)) then break;
for r:=1 to roads do begin
read(c1,c2);
end;
until false;
while true do continue;
end.[/pascal]
It should loop forever after succesfully reading the input, giving TLE, but it halts after 0.002 seconds, which means it can't handle the input file. I tried readln instead of read, but with the same result.
Can anybody, preferably one of the problemsetters, tell me what's going on?

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Further investigation (lots and lots of submissions..) let me to the conclusion that the input contains a lower ascii character (ascii 25), which disturbs the readln function.
What should we do with it? Ignore it? Consider it white space? Consider it a newline?
Please fix this problem.
I tried to circumvent it, but still get WA.
Is it correct that some city numbers are outside the range (0..n1)? This is what I conclude...
What should we do with it? Ignore it? Consider it white space? Consider it a newline?
Please fix this problem.
I tried to circumvent it, but still get WA.
Is it correct that some city numbers are outside the range (0..n1)? This is what I conclude...
I don't have any check for out of range cities in my (AC) code, so that shouldn't be the problem.
I did some experimenting, and when reading strings with scanf and the %s flag, ascii 25 (End of Medium, EM) is considered nonwhitespace and part of the string.
But when only reading integers (as my solution does), EM is quite naturally considered a nondigit, and will therefore work like EOF.
I did some experimenting, and when reading strings with scanf and the %s flag, ascii 25 (End of Medium, EM) is considered nonwhitespace and part of the string.
But when only reading integers (as my solution does), EM is quite naturally considered a nondigit, and will therefore work like EOF.

 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm
Thanks Larry and Per for your replies. I finally figured it out and got AC.
I now use my own buffered input, considering every nonnumeric character as whitespace and reading integers one at the time. This is what I use:
[pascal]program test;
var
inputbuffer:string;
bufpos,buflen:integer;
procedure myread(var i:integer);
label reload;
begin
reload:
while (bufpos>buflen) do begin
readln(inputbuffer);
buflen:=length(inputbuffer);
bufpos:=1;
end;
while ((bufpos<=buflen) and not (inputbuffer[bufpos] in ['0'..'9']))
do inc (bufpos);
if (bufpos>buflen) then goto reload;
i:=0;
while ((bufpos<=buflen) and (inputbuffer[bufpos] in ['0'..'9'])) do begin
i:=10*i+ord(inputbuffer[bufpos])ord('0');
inc (bufpos);
end;
end;
var
mink,roads,cities:integer;
c1,c2,r:integer;
begin
buflen:=0;
bufpos:=1;
repeat
myread(cities);
myread(roads);
myread(mink);
if ((cities=0) and (roads=0) and (mink=0)) then break;
for r:=1 to roads do begin
myread(c1);
myread(c2);
end;
until false;
end.[/pascal]
Some processing logic should be added to get accepted though...
I truely believe the problemsetters didn't add the rubbish in the input on purpose, and I'm sure they didn't notice it because their C/C++ programs handled it correctly, but it realy spoiled the contest for this old Pascal programmer. I wonder how many Pascal programs got AC during the contest. I bet it's zero...
I now use my own buffered input, considering every nonnumeric character as whitespace and reading integers one at the time. This is what I use:
[pascal]program test;
var
inputbuffer:string;
bufpos,buflen:integer;
procedure myread(var i:integer);
label reload;
begin
reload:
while (bufpos>buflen) do begin
readln(inputbuffer);
buflen:=length(inputbuffer);
bufpos:=1;
end;
while ((bufpos<=buflen) and not (inputbuffer[bufpos] in ['0'..'9']))
do inc (bufpos);
if (bufpos>buflen) then goto reload;
i:=0;
while ((bufpos<=buflen) and (inputbuffer[bufpos] in ['0'..'9'])) do begin
i:=10*i+ord(inputbuffer[bufpos])ord('0');
inc (bufpos);
end;
end;
var
mink,roads,cities:integer;
c1,c2,r:integer;
begin
buflen:=0;
bufpos:=1;
repeat
myread(cities);
myread(roads);
myread(mink);
if ((cities=0) and (roads=0) and (mink=0)) then break;
for r:=1 to roads do begin
myread(c1);
myread(c2);
end;
until false;
end.[/pascal]
Some processing logic should be added to get accepted though...
I truely believe the problemsetters didn't add the rubbish in the input on purpose, and I'm sure they didn't notice it because their C/C++ programs handled it correctly, but it realy spoiled the contest for this old Pascal programmer. I wonder how many Pascal programs got AC during the contest. I bet it's zero...

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut

 New poster
 Posts: 17
 Joined: Fri Aug 01, 2003 4:55 pm
 Location: Beijing, China
try this
Code: Select all
int BFS()
{
int i;
taker=putter=0;
node t,temp;
t.id=0;
t.dis=1;
enq(t);
while ( taker!=putter)
{
t=deq();
if ( t.dis>20) return 25;
//if ( (t.dis>=k) && t.id==(n1) ) return t.dis;
for(i=0;i<n;i++)
if(adj[t.id][i]==1 && i!=t.id )
{
temp.id=i;
temp.dis=t.dis+1;
if(mark[i] == temp.dis)
continue;
else
mark[i] = temp.dis;
if ( (i==(n1)) && temp.dis>=k && temp.dis<=20) return temp.dis;
enq(temp);
}
}
return 25;
}
Last edited by sharklu2000 on Tue Aug 26, 2003 8:46 pm, edited 1 time in total.

 Experienced poster
 Posts: 187
 Joined: Wed Dec 11, 2002 2:03 pm
 Location: Mount Papandayan, Garut
shamim.. no need to make your queue bigger. you've just need to mark whether the road has been in the queue or not, at same depth. that's better than make bigger the size of your queue.
for example :
queue : 1 2
1 adjacent to 3 5 7
2 adjacent to 4 5 6
if you expand 2 after 1, when you reach 5, you know that there is 5 in your queue, so you need not to enqueue 5 again.
hope this helps.
for example :
queue : 1 2
1 adjacent to 3 5 7
2 adjacent to 4 5 6
if you expand 2 after 1, when you reach 5, you know that there is 5 in your queue, so you need not to enqueue 5 again.
hope this helps.
Kalo mau kaya, buat apa sekolah?
10543 WA Why?
Here is my code in Pascal
[pascal]
const maxn=52;
var a:array [0..maxn,0..maxn] of boolean;
c:array [0..maxn,1..22] of boolean;
m,n,i,j,k,p,q:integer;
Begin
readln(n,m,k);
while n>0 do
begin
fillchar(a,sizeof(a),0);
fillchar(c,sizeof(c),0);
for i:=1 to m do
begin
readln(p,q);
if p<>q then a[p,q]:=true;
end;
c[0,1]:=true;
i:=1;
while (i<20)and((c[n1,i]=false)or(i<k)) do
begin
inc(i);
for j:=0 to n1 do
for p:=0 to n1 do
if (a[j,p] and c[j,i1])
then c[p,i]:=true;
end;
if c[n1,i]=true then writeln(i)
else writeln('LOSER');
readln(n,m,k);
end;
End.
[/pascal]
Help, please.
[pascal]
const maxn=52;
var a:array [0..maxn,0..maxn] of boolean;
c:array [0..maxn,1..22] of boolean;
m,n,i,j,k,p,q:integer;
Begin
readln(n,m,k);
while n>0 do
begin
fillchar(a,sizeof(a),0);
fillchar(c,sizeof(c),0);
for i:=1 to m do
begin
readln(p,q);
if p<>q then a[p,q]:=true;
end;
c[0,1]:=true;
i:=1;
while (i<20)and((c[n1,i]=false)or(i<k)) do
begin
inc(i);
for j:=0 to n1 do
for p:=0 to n1 do
if (a[j,p] and c[j,i1])
then c[p,i]:=true;
end;
if c[n1,i]=true then writeln(i)
else writeln('LOSER');
readln(n,m,k);
end;
End.
[/pascal]
Help, please.
10543  Traveling Politician
I m getting Wa in this problem . I used BFS to solve this Problem and it works for all the Sample Cases and Inputs I have made. Is There any Bad inputs for This Problem ??.
If so, PLZ help me !!.
Some Inputs with Outputs will be better for me to check my fault.
If so, PLZ help me !!.
Some Inputs with Outputs will be better for me to check my fault.
Fixed Length All Pair
Try to use fixed length all pair shortest path algorithm for this problem. It will be easy then bfs.(From Corman).
10543 (Funny JUDGE)
I submit the solution of this problem for 15 times . I use BFS (without coloring the vertex). In my first solution I get TLE. Then I use cicular queue and got WA. My Qsize was 4000000. I edit my solution for more than 10 times but I got WA again and again. But finally I chainge my Qsize and reduce it to 1000000. After the editing it is strainge that I got AC with less time.
What I think, there might have somekind of bug in JUDGE SOLUTION. May be the solver use less Qsize and in some case for big Graph the content of Q is overwritten. Wrong judge solution is always creates problem. If the solution have some problem like this it should take care by the problemsetter.
If someone interested I can send my solution by mail. My mail address is:
anm_rajib@hotmail.com
What I think, there might have somekind of bug in JUDGE SOLUTION. May be the solver use less Qsize and in some case for big Graph the content of Q is overwritten. Wrong judge solution is always creates problem. If the solution have some problem like this it should take care by the problemsetter.
If someone interested I can send my solution by mail. My mail address is:
anm_rajib@hotmail.com