10537 - The Toll! Revisited

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

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

10537 - The Toll! Revisited

Post by windows2k » Tue Jul 29, 2003 6:09 am

Why I always get Time Limit Exceed
It only 52 nodes in a graph,and I uses shortest path to solve it.
if n=0, what output we should do ?

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland

Post by cyfra » Tue Jul 29, 2003 1:00 pm

Hi!

Hmm.. your method is good. I also did it with Dijkstra for finding the shortest pathes... (and got AC in less then 1sec)

But I think that there are 2 things that can cause TLE...

1.) Check how long your function for visiting cities works. ( the function, that counts the minimal number of cash you need to have before entering the city, so that you can leave it with known amount of cash)

2.) Don't forget that the final answer can be greater than 2^31 ...

I hope it will help you

Good Luck :wink:

inkfish
New poster
Posts: 7
Joined: Wed Jul 30, 2003 9:04 am

Post by inkfish » Wed Jul 30, 2003 9:13 am

Help!
[cpp]

#include <stdio.h>

// A-Z: 0-25
// a-z: 30-55
long long maxvalue;
bool link[60][60];
long long cost[60];
long long v;

int parent[60];
int isin[60];
int scr,tar;

int convert_1(char ch)
{
if(ch>='a' && ch<='z') return (ch-'a'+30);
return (ch-'A');
}

char convert_2(int x)
{
if(x<30) return (char)('A'+x);
return (char)('a'+x-30);
}

long long pre(long long x,int id)
{
long long k,b;

if(id<30){
k=x/19;
b=x%19;
if(b) return 20*k+b+1; return 20*k;
}else return x+1;
}

void dp()
{
long long temp;
long long minv;
int minid;
int i;

for(i=0;i<60;i++){
cost=maxvalue; parent=-1; isin=0;
}

cost[tar]=v;
isin[tar]=1;
for(i=0;i<60;i++){
temp=pre(v,tar);
if(link[tar]){
if(temp<cost){
cost=temp;
parent=tar;
}
}
}

while(1){
minv=maxvalue;
minid=-1;
for(i=0;i<60;i++)
if(!isin && cost<minv){
minv=cost;
minid=i;
}
if(minid==-1) break; /* I got WA, and if i delete this ,it will be TLE ,*/
isin[minid]=1;
for(i=0;i<60;i++){
temp=pre(cost[minid],minid);
if(link[i][minid]){
if(temp<cost[i]){
cost[i]=temp;
parent[i]=minid;
}else{
if(temp==cost[i] && parent[i]>minid) parent[i]=minid;
}
}
}
if(minid==scr) break;
}
}

void print(int cases)
{
int temp;

printf("Case %d:\n",cases);
printf("%lld\n",cost[scr]);
printf("%c",convert_2(scr));
temp=scr;
while(1){
temp=parent[temp];
printf("-%c",convert_2(temp));
if(temp==tar) break;
}
printf("\n");
}

int main()
{
char str[10];
long long n;
int cases=0;
char ch1,ch2;
int i,j;
int v1,v2;
// freopen("test.txt","r",stdin);
while(1){
scanf("%lld",&n);
if(n==-1) break;
cases++;

maxvalue=10000000;
maxvalue*=10000000;
for(i=0;i<60;i++)
for(j=0;j<60;j++) link[i][j]=0;
for(i=0;i<n;i++){
scanf("%s",str);
ch1=str[0];
scanf("%s",str);
ch2=str[0];
v1=convert_1(ch1);
v2=convert_1(ch2);
link[v1][v2]=1;
link[v2][v1]=1;
}
scanf("%lld",&v);
scanf("%s",str);
ch1=str[0];
scanf("%s",str);
ch2=str[0];
scr=convert_1(ch1);
tar=convert_1(ch2);

dp();
print(cases);
}
return 0;
}
[/cpp]

inkfish
New poster
Posts: 7
Joined: Wed Jul 30, 2003 9:04 am

Post by inkfish » Wed Jul 30, 2003 9:19 am

I get Ac now
my last program was wrong when there is just one node.

ne0
New poster
Posts: 2
Joined: Fri Aug 01, 2003 12:17 am
Contact:

Post by ne0 » Fri Aug 01, 2003 12:36 am

Dear all,

I think, I've read all the notes and every thing seems okay, but i still get WA :(
Can someone help me please?
I would be thankful :)

here is my code:
[cpp]
#include<iostream>
#include<string.h>

#define INFINITE 2E14
#define int long long
#define CEIL(x) ((x)==(int)(x)?(x):(int)(x)+1)
#define MIN(x,y) ((x)<(y)?(x):(y))
#define CODE(x) ((x)<='Z'?(x)-'A':(x)-'a'+26)
#define DECODE(x) ((char)(x<26?x+'A':x-26+'a'))
#define INC(x,c) ((c)<26?CEIL((x)*20/19.0):(x)+1)
#define DEC(x,c) ((c)<26?(x)-CEIL(x/20.0):(x)-1)

using namespace std;

int src,tgt,m;
int graph[52][52];
int dist[52];
int mark[52];

void dijkstra()
{
for(int i=0;i<52;i++)
mark=0,dist=INFINITE;

dist[tgt]=m;
for(;;)
{
int mindex=-1;
for(int i=0;i<52;i++)
if(!mark&&(mindex==-1||dist<dist[mindex]))
mindex=i;
if(mindex==-1||dist[mindex]>=INFINITE||mindex==src)
break;
mark[mindex]=1;
for(int i=0;i<52;i++)
if(!mark&&graph[mindex])
dist=MIN(dist,INC(dist[mindex],mindex));
}
}

main()
{
int N=0;
while(cin>>m,m+1)
{
memset(graph,0,sizeof graph);
char c1,c2;
while(m--)
{
cin>>c1>>c2;
graph[CODE(c1)][CODE(c2)]=1;
}
cin>>m>>c1>>c2;
src=CODE(c1);tgt=CODE(c2);
if(m)
dijkstra();
else
cout<<"Case "<<++N<<":"<<endl;

cout<<dist[src]<<endl;
cout<<DECODE(src);
do
{
int i;
for(i=0;i<52;i++)
if(graph[src]&&dist==DEC(dist[src],i))
break;
if(i==52)
break;
src=i;
cout<<'-'<<((char)DECODE(src));
}while(src!=tgt);
cout<<endl;
}
return 0;
}
[/cpp]

ne0
New poster
Posts: 2
Joined: Fri Aug 01, 2003 12:17 am
Contact:

sorry

Post by ne0 » Fri Aug 01, 2003 12:48 am

sorry, in the main function:
[cpp]
src=CODE(c1);tgt=CODE(c2);
if(m)
dijkstra();
else
cout<<"Case "<<++N<<":"<<endl
[/cpp]
must be:
[cpp]
src=CODE(c1);tgt=CODE(c2);
dijkstra();
cout<<"Case "<<++N<<":"<<endl;
[/cpp]

but it's still WA

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

10537 - Toll! Revisited - I/O

Post by UFP2161 » Thu Aug 14, 2003 2:04 am

Could someone post some input/outputs for this? Thanks in advance!

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

Post by Faizur » Sun Aug 17, 2003 12:02 pm

how can i solve this kind of problems?? using single source shortest path algo..can anyone explain a bit.

User avatar
UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 » Wed Aug 20, 2003 8:00 am

You can use single source shortest path. It's just not "normal", since you don't have any fixed weights, so you're recreating them backwards as you leave a town/village until you hit your starting destination.

Anyways, I pretty much verified that my number of items that I must start with is correct (checked it with some code I found online, assuming it's right too). Which probably also means my path is correct. So, I don't know anymore.

Regardless of what the description says, are there things like p = 0? or there isn't a connection between starting and destination cities?

I just don't know what other border cases to try!

Faizur
New poster
Posts: 39
Joined: Fri Jun 06, 2003 3:04 pm

Post by Faizur » Wed Aug 20, 2003 1:13 pm

Where can i find thes codes pls.

carneiro
Learning poster
Posts: 54
Joined: Sun May 18, 2003 1:19 am
Location: Rio de Janeiro, Brazil
Contact:

Post by carneiro » Sun Aug 31, 2003 5:26 am

How does the input with n = 0 looks like ?

Code: Select all

0
23 A A
or something else ?

And what's the expected output for that ?

my (WA) program outputs this :

Code: Select all

Case 1:
23
A
[]s
Mauricio Oliveira Carneiro

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Mon Sep 01, 2003 1:35 pm

it schould be



Case 1:
23
A-A :lol:

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

Post by little joey » Mon Sep 01, 2003 4:03 pm

Well, that isn't funny at all!

The problem statement clearly says:
Actually, the path contains all the city/village names that Sindbad sees along his journey. Two consecutive city/village names in the path are separated by a hyphen.
In the example you give, Sindbad sees only one city, so the path length should be one and the correct output should be:

Case 1:
23
A

The path A-A would implicate that Sindbad leaves the town, changes his mind and reenters again, in which case he should pay toll, and the correct answer would be:

Case 1:
25
A-A

There would be no consecutive towns inbetween which to place a hyphen if he doesn't leave and reenter.

Still got WA any which way, so there must be something else I missed...

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Sep 01, 2003 11:54 pm

To clear up the confusion:
My AC program answers "A" as the path for such a test case (which I definitely agree is the correct interpretation), so if miras is AC with his/hers interpretation, there can't be any such test cases.

These test cases are proably too easy, but anyway:

Code: Select all

4
A b
A B
b c
B c
18 A c
4
A b
A B
b c
B c
19 A c
Output:

Code: Select all

Case 1:
20
A-B-c
Case 2:
21
A-b-c

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Tue Sep 02, 2003 3:57 am

The following output format is OK: (When source and dest are same)

Case 1:
23
A

and there are such cases in the judge data.

Post Reply

Return to “Volume 105 (10500-10599)”