10543 - Traveling Politician

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

Moderator: Board moderators

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

10543 - Traveling Politician

Post by 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 :evil:

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
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by 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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

Ya, I used scanf with %d, and experienced no problems...
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by 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
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

10543

Post by shamim »

CUT
Last edited by shamim on Tue Oct 14, 2003 8:56 am, edited 2 times in total.
titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by 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.
Kalo mau kaya, buat apa sekolah?
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Resolved

Post by shamim »

CUT
Last edited by shamim on Tue Oct 14, 2003 8:55 am, edited 1 time in total.
sharklu2000
New poster
Posts: 17
Joined: Fri Aug 01, 2003 4:55 pm
Location: Beijing, China

Post by 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; 
} 
Last edited by sharklu2000 on Tue Aug 26, 2003 8:46 pm, edited 1 time in total.
titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by 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.
Kalo mau kaya, buat apa sekolah?
Kimi
New poster
Posts: 4
Joined: Sat Oct 18, 2003 4:08 am
Location: Shanghai, China
Contact:

10543 WA Why?

Post by 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
New poster
Posts: 9
Joined: Sat Aug 24, 2002 11:21 am
Location: Dhaka, Bangladesh

10543 - Traveling Politician

Post by kamrul »

I m getting Wa in this problem :oops: . 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
New poster
Posts: 9
Joined: Sun Dec 07, 2003 4:52 am

Fixed Length All Pair

Post by rasel04 »

Try to use fixed length all pair shortest path algorithm for this problem. It will be easy then bfs.(From Corman).
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by 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
New poster
Posts: 28
Joined: Tue Nov 04, 2003 6:45 am
Location: Bangladesh

10543 (Funny JUDGE)

Post by Rajib »

I submit the solution of this problem for 15 times :evil: . 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 :P 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
Post Reply

Return to “Volume 105 (10500-10599)”