10544 - Numbering the Paths

[Whinii F.]

Hi. I constantly tackled this problem in the contest and received LOTs of WAs.

I assumed the graph as a DAG and there are no additional spaces in the input.
Anyone could point out any flaws or critical inputs? The following is my algorithm:

Initially for all vertices with out-degree 0, give them count 1, and mark the all other vertices with count 0.

And repeat the following process while there is a vertex V with outdegree 0, for all its parents (vertices who has edges targetted to V), remove the edge between the parents and V. And increase each the parents' counts by (count of V).

So count of a vertex means how many ways are there starting from that vertex. I think it will produce same result with using DP with memoization.

So, after doing that for all paths, follow the path vertex-by-vertex. And for every vertex on the path: Add up all counts of vertices which the current vertex has edges to, and is less than the next vertex on the path.
(for example, if current vertex is A and A has edges to C, D, and E, and the next vertex on the path is E, counts of C and D are summed up)

(The summation of the counts) + 1 will be the number of the path..

I was very confident about it but I'm really confused. Any suggestions would help.

Thanks in advance,

[Per]

I just managed to get this problem AC after ~5 tries. Do you handle this input correctly (this was my problem)?

Code: Select all

3 3
AB
AC
AB
1
AC

(Output is 2.)

Since it took me a while (a far too long while!) to realize the above, I made my code handle weird spacing in input (e.g. having an edge like "A B"). But I don't really think that's needed.

[kmhasan]

Well, I admit that I made it a bit difficult to understand just to make sure that it is not so obvious. But I guess repeated reading could reveal all the hidden information.

Yes the graph is a DAG. And I myself use memoization from the starting vertex of the path to solve the problem.

But there's no dirty input (i.e., spaces) so far as I'm concerned.

[Whinii F.]

Per:
Yes, my program handles the case correctly since count of B and C are both 1. When I process A, count of B is added to the whole sum. How did you interprete the problem? Something special?
BTW, congratulations for your 900 problem

kmhasan:
... Well, is my English not good enough? I don't see what you mean.. I read the statement again and again, and still desperate. Any clue will be helpful.

Thanks anyway~

[Per]

Thanks
I solved it pretty much the way you did (though top-down with memoization like kmhasan instead of bottom-up), so if you've got that part right, I don't know. You could try my input file, I'll send it to you via PM (it's a bit too long to post).[/code]

[kmhasan]

Whinii, I didn't say that your english is not good. I just said that I had tried not to be straight forward.

What I meant is that the required information can be derived from the problem statement. Let me clarify what I meant:

The number of nodes were given in the problem statement. It said that the road intersections (vertices) were labeled with upper case english letters (26).

The given graph would be a DAG. KB3 does not want to look stupid and he specifically asked his mayor to build a road network that does not allow him to come to the same place again that he has visited on a path. And the return trip with the chopper has to be ignored, so that makes the graph a DAG.

The paths are all maximal paths. KB3 does not stop until he reaches a road intersection from where he cannot go anywhere.

The enumeration of the paths would be done alphabetically. And the numbering of the paths are to be done for the maximal paths that start with the starting vertex of the given path.

So from where I see, every bit of information is there, but maybe not in a helpful manner. Could you be a bit specific about the part that was not apparent from the problem statement? I really won't want to set a problem statement where the required information is missing. Perhaps you could help.

Thanks.

[Whinii F.]

Per:
Thank you for being so kind! My program passed all your test inputs. After that I changed my counting routine to a top-down approach with memoization and got ACCEPTED at once. Was my approach wrong or was it my code?

Tomal:
Well, I didn't say your problem statement was confusing. I could well derive everything you intended. I was confused because of the WA, and was wondering there is something extreme hidden behind the problem statement. And I now found out that my interpretation was not wrong but my program.

Thanks all! I'm really gonna think about what is wrong with my previous code.

[prilmeie]

I have found all troubles in my code using this sample input:

Code: Select all

3
7 15
CB
FE
DA
GA
AB
DC
AF
GB
AE
GA
AC
CE
GF
GC
CF
9
DCFE
GCE
GAB
CFE
AFE
CB
GB
DAB
DAFE
5 6
AB
AC
BC
CD
CE
ED
3
ABCD
ACD
CD
3 3
AB
AC
AB
1
AC

The output should be:

Code: Select all

DCFE: 9
GCE: 9
GAB: 1
CFE: 3
AFE: 6
CB: 1
GB: 7
DAB: 1
DAFE: 6
ABCD: 1
ACD: 3
CD: 1
AC: 2

[carneiro]

kmhasan,

My problem is ACCEPTED but I'd like to bring something into discussion here

From what I understand of the problem statement, if i have two edges AB, that means I have 2 different ways to get to B, from A. That said, different paths should receive different numbers.

As any ordering algorithm, draws are solved by random assignment, and that's exactly what my program did.

Now, if that's not what you intended when you put two different edges to between the same vertices, I think there should be either an explanation on what to do in that situation, or, if you decide not to explain, it should be left in the standard way (random assignment) which would force you to build a special judge for the problem.

I got WA with my first "standard" solution. Then, I supposed the problem was not clear about that point, and that you most likely wouldn't have made a special judge for that, so I simply DIDN'T add an edge that already existed, and got accepted.

Do you aggree with me ? Or do you have another point of view?

[kmhasan]

I agree with you. It should have been clearly stated. I should not argue,

"... So for a given track, there can be multiple paths that have the same number"

indicates that. It had to be much more specific.

Perhaps that could be one reason why Whinii's program failed. Maybe it was related to increasing degree of the vertices. And it would be the obvious problem for adjacency list representations.

I would update either the problem statement or the input file very shortly. Thanks a lot for pointing it out. The fault was on my side.

[Whinii F.]

Oh! Yes! That was why. My program got Accepted when I ignored already existing paths.

[Lijiganjun]

I think my code is right,but it got WA,please help me !3x!
I use dynamic to solve it,and assumed if there is only one letter,the number is zero.
#include<string.h>
#include<iostream.h>

int t,n,m,q;
char s[30],o[30],g[26][27];
long sum[26];

void get(int v)
{
int i;

if (sum[v]>0) return;
if (g[v][0]==0) {sum[v]=1;return;}
for (i=1;i<=g[v][0];i++)
{
get(g[v]);
sum[v]+=sum[g[v]];
}
}

void solve(char *s)
{
long label;
int i,j,v,t;

t=strlen(s);
for (i=0;i<t;i++) s-='A';
label=0;
for (i=0;i<t-1;i++)
{
j=1;
while (g[s][j]<s[i+1])
{
v=g[s][j];
get(v);
label+=sum[v];
j++;
}
}
cout<<o<<": "<<++label<<endl;
}

void sort(char *a)
{
char i,j,k;

for (i=1;i<a[0];i++)
{
k=i;
for (j=i+1;j<=a[0];j++)
if (a[k]>a[j]) k=j;
j=a;a=a[k];a[k]=j;
}
}

void main()
{
int i,j,k;
char a,b;

cin>>t;
for (i=0;i<t;i++)
{
memset(sum,0,sizeof(sum));
memset(g,0,sizeof(g));
cin>>n>>m;
for (j=0;j<m;j++)
{
cin>>a>>b;
a-='A';b-='A';
g[a][++g[a][0]]=b;
}
for (j=0;j<n;j++) sort(g[j]);
cin>>q;
for (j=0;j<q;j++)
{
cin>>s;
if (strlen(s)==1)
{
cout<<s<<": 0\n";
continue;
}
memcpy(o,s,sizeof(s));
solve(s);
}
}
}



[cpp]

[Lijiganjun]

Please give me some advice ,ok? otherwise ,some test cases.3X!

[zprian]

I always got WA for this problem and I don't know where my mistake.
I prove for a this input...

Code: Select all

5
26 325 
AB
AC
AD
AE
AF
AG
AH
AI
AJ
AK
AL
AM
AN
AO
AP
AQ
AR
AS
AT
AU
AV
AW
AX
AY
AZ
BC
BD
BE
BF
BG
BH
BI
BJ
BK
BL
BM
BN
BO
BP
BQ
BR
BS
BT
BU
BV
BW
BX
BY
BZ
CD
CE
CF
CG
CH
CI
CJ
CK
CL
CM
CN
CO
CP
CQ
CR
CS
CT
CU
CV
CW
CX
CY
CZ
DE
DF
DG
DH
DI
DJ
DK
DL
DM
DN
DO
DP
DQ
DR
DS
DT
DU
DV
DW
DX
DY
DZ
EF
EG
EH
EI
EJ
EK
EL
EM
EN
EO
EP
EQ
ER
ES
ET
EU
EV
EW
EX
EY
EZ
FG
FH
FI
FJ
FK
FL
FM
FN
FO
FP
FQ
FR
FS
FT
FU
FV
FW
FX
FY
FZ
GH
GI
GJ
GK
GL
GM
GN
GO
GP
GQ
GR
GS
GT
GU
GV
GW
GX
GY
GZ
HI
HJ
HK
HL
HM
HN
HO
HP
HQ
HR
HS
HT
HU
HV
HW
HX
HY
HZ
IJ
IK
IL
IM
IN
IO
IP
IQ
IR
IS
IT
IU
IV
IW
IX
IY
IZ
JK
JL
JM
JN
JO
JP
JQ
JR
JS
JT
JU
JV
JW
JX
JY
JZ
KL
KM
KN
KO
KP
KQ
KR
KS
KT
KU
KV
KW
KX
KY
KZ
LM
LN
LO
LP
LQ
LR
LS
LT
LU
LV
LW
LX
LY
LZ
MN
MO
MP
MQ
MR
MS
MT
MU
MV
MW
MX
MY
MZ
NO
NP
NQ
NR
NS
NT
NU
NV
NW
NX
NY
NZ
OP
OQ
OR
OS
OT
OU
OV
OW
OX
OY
OZ
PQ
PR
PS
PT
PU
PV
PW
PX
PY
PZ
QR
QS
QT
QU
QV
QW
QX
QY
QZ
RS
RT
RU
RV
RW
RX
RY
RZ
ST
SU
SV
SW
SX
SY
SZ
TU
TV
TW
TX
TY
TZ
UV
UW
UX
UY
UZ
VW
VX
VY
VZ
WX
WY
WZ
XY
XZ
YZ
11
GYZ
XYZ
WXYZ
TXZ
SUZ
OZ
OYZ
LOZ
IYZ
GYZ
AZ
7 15 
CB 
FE 
DA 
GA 
AB 
DC 
AF 
GB 
AE 
GA 
AC 
CE 
GF 
GC 
CF 
9 
DCFE 
GCE 
GAB 
CFE 
AFE 
CB 
GB 
DAB 
DAFE 
5 6 
AB 
AC 
BC 
CD 
CE 
ED 
3 
ABCD 
ACD 
CD 
3 3 
AB 
AC 
AB 
1 
AC

and run well... can give me some input??

[brunokbcao]

But, if you use an simple matricce multiplication, what happens!?