10543 - Traveling Politician

[little joey]

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?

[little joey]

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..n-1)? This is what I conclude...

[Per]

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 non-whitespace and part of the string.

But when only reading integers (as my solution does), EM is quite naturally considered a non-digit, and will therefore work like EOF.

[Larry]

Ya, I used scanf with %d, and experienced no problems...

[little joey]

Thanks Larry and Per for your replies. I finally figured it out and got AC.

I now use my own buffered input, considering every non-numeric 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...

[shamim]

CUT

[titid_gede]

i;ve check your code. it seems ok. but do you think your queue is enough? while expanston, it is possible that there exist same roads at that level (depth). it makes your queue bubble. i added mark to your program, and it got AC.

[shamim]

CUT

[sharklu2000]

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==(n-1) ) 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==(n-1)) && temp.dis>=k && temp.dis<=20) return temp.dis; 
         enq(temp); 
      } 
   } 
   return 25; 
} 

[titid_gede]

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.

[Kimi]

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[n-1,i]=false)or(i<k)) do
begin
inc(i);
for j:=0 to n-1 do
for p:=0 to n-1 do
if (a[j,p] and c[j,i-1])
then c[p,i]:=true;
end;

if c[n-1,i]=true then writeln(i)
else writeln('LOSER');

readln(n,m,k);
end;

End.
[/pascal]
Help, please.

[kamrul]

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.

[rasel04]

Try to use fixed length all pair shortest path algorithm for this problem. It will be easy then bfs.(From Corman).

[sohel]

I solved it using BFS without colouring.

The difference is enque a node if and only if its length is less than 20 and when the queue becomes empty output "LOSER";
Simple isn't it!!

[Rajib]

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 Q-size was 4000000. I edit my solution for more than 10 times but I got WA again and again. But finally I chainge my Q-size 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 Q-size 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