Page 1 of 2

452 - Project Scheduling

Posted: Mon Aug 23, 2004 7:43 pm
by Solaris
Haven't found any topic about this problem. It must be one of the easier ones. but still I could not find any solution to this problem.

For this problem,
I assume that there will not be any circle in the given graph and there will atleast be one node which will not have any preceding node (I call it starting node). I run DFS() from all the starting nodes and update the costs of the tasks/nodes connected to it.

Where is my mistake. anyone plzzzzzzzzzz help.

Posted: Tue Aug 24, 2004 11:59 am
by Dominik Michniewski
I faced with the same problem as you. I think that your method is good - I can't imagine any case which could causes failure of such algorithm.

If anyone should help us and post some critical IO or proof that this approach isn't good - we would be greatful :-)

I test my program with cases where exist more than one separate graph in input and so on, but I still got WA.

Best regards
DM

Posted: Sun May 08, 2005 7:51 am
by Abednego
Wow. This problem has a crazy amount of input! I did a very lazy topological sort using Floyd-Warshall, and it timed out, even though it's a O(n^3) algorithm with n=26. Then I replaced all the instances of getline() with gets() and used a O(n^2) insertion sort instead of Floyd-Warshall and got accepted in 8.6 seconds. Unbelievable! I wonder what the size of the input file is. It must be at least 10 MB.

Posted: Mon May 22, 2006 3:25 pm
by Sedefcho
I think they have repeated lines in the input.

For example:

Code: Select all

1

A 5
A 5
A 5
.... ( the line A 5 is repeated 2000 times for example ... ) 
B 3 A
D 2 A
C 2 B
F 2 CE
E 4 DC
E 4 DC
E 4 DC
.... (the line E 4 DC is repeated another 3000 times ... )
I got ACC in about 0.4 sec.
I don't think the input is so hard.
I don't know for sure of course.

Here is a small advice. What I do is...
Well... When I see a line starting with the char 'A' and
I've had already in the same test case a line starting with 'A'
('A' is just an example) I just ignore this second
occurrence of the 'A'-line.


So I don't think the input contains something like
...
A 4 BC
A 4 DE
...
because such an input would screw up my logic.

Good luck.

Re: 452, Why WA

Posted: Tue Mar 03, 2009 4:38 pm
by branka.j
I have a problem with example 452. I get a runtime error. Can someone tell me what should I look for at input and output?

I also need to know if the graph includes a cycle what do I get on system output?

Thank you.

Re: 452, Why WA

Posted: Tue Mar 03, 2009 7:09 pm
by Sedefcho
Most of the times RE means you are accessing memory
which your program did not acquire first. For example
you may be trying to access element i=1001 of an array
having len=1000 elements.

Re: 452, Why WA

Posted: Mon Apr 26, 2010 6:57 pm
by mak(cse_DU)
Solaris wrote: For this problem,
I assume that there will not be any circle in the given graph and there will atleast be one node which will not have any preceding node (I call it starting node). I run DFS() from all the starting nodes and update the costs of the tasks/nodes connected to it.

Where is my mistake. anyone plzzzzzzzzzz help.
The graph must be a DAG.
SO there have no circle.
There can be multiple starting node.
There can be Multiple DAG in a case.

Re: 452, Why WA

Posted: Mon Aug 29, 2011 9:51 pm
by Shafaet_du
try this case:

Code: Select all

[b]1

A 2
C 3
B 5 AC
D 10 B
H 13 GF
E 11 B
G 12
F 2 DE
I 10
J 20 I
[/b]
output from my ac code:

Code: Select all

34

Re: 452, Why WA

Posted: Wed Jun 26, 2013 9:30 am
by skiranc
Could someone please provide some test cases/help me debug?

I tried a few of my own but I keep getting WA...I'm not sure what the issue is. My code works for all cases above.
I tried using bellman ford initially and now i'm using dfs, but I can't get either AC.

Edit: Got AC

Thank you in advance.

Re: 452, Why WA

Posted: Wed Jun 26, 2013 10:37 am
by brianfry713
don't read from a file.
print a newline at the end of the last line.

Re: 452, Why WA

Posted: Wed Jun 26, 2013 10:57 am
by skiranc
Wow, I can't believe it was so simple.

Thank you!

Re: 452, Why WA

Posted: Thu Jun 27, 2013 9:23 pm
by @ce
Getting WA...plzz help

Code: Select all

AC

Re: 452, Why WA

Posted: Thu Jun 27, 2013 11:40 pm
by brianfry713
Input:

Code: Select all

100

A 52
B 98 A
C 68 A
D 97
E 9 C
F 37 CDE
G 69 DEF
H 42 E
I 5 CEGH
J 60 BFGI
K 76 CEFGHJ
L 55 ABFHK
M 33 BCDEHJ
N 96 ABCDEFIM
O 33 ABCHIN
P 98 BCGHJLN
Q 11 BEFHKLOP
R 91 ABCDFHIJKMNQ
S 13 CDEKLM
T 57 CDEFLPQS
U 13 ABCFGHIJLMNPQST
V 5 ACFGHJPQRST
W 2 BCDFGHKOQRSTUV
X 93 CDEGJKMOPQRT
Y 94 ABCEHJMPQRSUW
Z 92 BEHILNOPQRTUY

A 76
B 30
C 70
D 34 BC
E 52 ACD
F 82 CDE
G 9 AF
H 99 ACDFG
I 53 ABDEFG
J 2 DH
K 37 AEGHJ
L 14 ADEFHJK
M 6 ADEFGIJL
N 85 BJ
O 79 BGIKLMN
P 9 ACKLNO
Q 83 ACDEHIJLNP
R 9 BCEIJMOPQ
S 14 BCDEJMOR
T 6 BCEFGHKLMQ
U 67 EHIJLNOPQST
V 39 IJKLMNQRSU

A 2
B 37
C 16
D 43 ABC
E 20 AB
F 29 ABC
G 36 ADEF

A 35
B 20
C 72
D 70 BC
E 2 BCD
F 90 ABC
G 77 EF
H 98 BCEF
I 47 ABE
J 7 DHI
K 76 ADFHJ
L 13 ADEFGHK
M 8 ADFI
N 83 ABDFHJL

A 79
B 57
C 87
D 48 AC
E 8 D
F 67 AD
G 90 ACDF
H 54 DFG
I 90 ABDEFGH
J 84 BGHI
K 50 BDEGHI
L 94 ACEGJK
M 63 ABCFGHIK
N 91 ABFKLM
O 77 AEGHL
P 42 HMNO
Q 76 BCEFGIKLNO
R 71 AFIJKQ
S 78 ADEMNOPQR
T 47 DEFGHIJ
U 24 GHIJLMNT
V 93 BDEGHJKLOQSU
W 69 ACFHIKLMORT
X 7 ACEFGIJLMNORSTU
Y 49 CDFGILMNORSTUWX
Z 30 ABCDEGHLMOPSTUVWXY

A 80
B 73 A
C 77 A
D 96 B
E 31 BCD
F 93 CD
G 77 ABDF
H 86 ABDEF
I 33 BCFGH
J 8 ABCEF
K 2 ADFGHJ
L 71 BDEIJK
M 3 DGJL
N 67 BHJL
O 86 BDEGK
P 17 ACFJKLMO
Q 98 EGHJMNOP
R 31 BCHIJKLMNOPQ
S 59 ABCEGHKLMNQ
T 42 ACDEJKLPQR
U 88 ACEFHJMNOR
V 52 ABCDHOPST
W 9 FJKLNORSUV
X 50 CEGHIJKLMNPQRW
Y 54 CDEGHKMOQSUVW

A 48
B 88 A
C 14 AB
D 92 ABC
E 86 ABC
F 93 ADE
G 22 ABDEF
H 15 ACEFG
I 41 ABDEFH
J 3 ACE
K 74 BDJ
L 2 ACDEHIK
M 89 ABCEFIJ
N 97 EGIKLM
O 41 ABFGJN
P 18 ABCDEFGHIJLN
Q 49 BCDIJKLP
R 47 AEFGIJKLMOP
S 60 ACDEHJKLPR
T 34 DEFHJKLQ
U 42 ABCFHKNOPRT
V 65 CFGKLMOPS
W 17 BDFHKNOPQRSTUV
X 45 CDEGNPVW

A 59
B 79 A
C 8
D 5
E 29 AD
F 13 ABCD
G 83 ACDF
H 61 DEG

A 85
B 89 A
C 35 A
D 18 ABC
E 40 D
F 27 AB
G 91 ACDEF
H 67 D

A 58
B 88
C 93
D 37 B
E 55 AD
F 19 ABD
G 93 DE

A 64
B 40 A
C 52
D 32 ABC
E 44 ACD
F 22 D
G 17 ACD
H 51 BCFG
I 98 ACG
J 81 ACDH
K 70 AG
L 89 ABCGH
M 8 IKL
N 86 ADHIJKL
O 16 ACFIM
P 17 EFHLMO
Q 60 ABCDIKLN
R 98 BCEHJKNP
S 59 ACEGHKOPR
T 3 DEGORS

A 21
B 35
C 92
D 9 A

A 30
B 75 A
C 69 B
D 10 AC
E 23 BD
F 71 BD
G 95 ACF
H 98 CDE

A 13
B 79
C 44
D 49
E 96 ACD

A 3
B 44 A
C 21
D 71
E 30 ABD
F 20 AD
G 65 CEF
H 86 ACDEG
I 41 ABCEGH
J 6 ADI
K 87 EGJ
L 5 ABCDEGJK
M 24 AGHIJKL
N 75 ABCDFGHM
O 16 BCDFGIKMN
P 61 CDEIJLNO
Q 24 AFHILMNOP
R 1 BCEFJLNQ

A 47
B 14 A
C 22 AB
D 6 A
E 0 AB
F 72 B
G 2 CEF
H 35 DE
I 16 BEH
J 74
K 99 ACFHI
L 48 ACEFHK
M 74 CFGJK
N 47 CDFGHJLM
O 35 BGIJKLM
P 76 EGIO
Q 71 CHIJN
R 95 BGJNP
S 35 ACEGHKLMP
T 97 CDHJKLPQ

A 75
B 78
C 76 A
D 48 B
E 87 A
F 76 CDE
G 68 DE
H 7 ABDE
I 96 CEH
J 64 CDEH
K 22 BFHIJ
L 37 ABCK
M 64 ACHIKL
N 68 ABFGIJLM
O 96 ABCDEHJKLN
P 81 AGHIJMO

A 89
B 66 A
C 55 AB
D 57 B
E 56 AC
F 1 AD
G 65 ABDEF
H 43 CE
I 50 AF
J 79 BCEFG
K 57 ABDEH
L 1 BEG
M 62 ACEFJL
N 2 BEFGHIJM
O 34 BEGHILMN
P 25 GHIKLMN
Q 9 ABGLMNOP
R 75 ABCDEFGHLP
S 88 IJKMQR
T 9 CEHIKLNOR
U 2 BCDFGHLOPT
V 64 ABDGJLNPRSU
W 32 ABGHMNQSTUV
X 53 ACIJLMPRS
Y 57 ADHJMOQRT
Z 29 ABEFGILNQSTUWX

A 91
B 30
C 27 B
D 64 B
E 33 AD
F 94 C
G 83 BEF
H 17 ABEF
I 51 EFH
J 61 BCDEF
K 19 DEGHI
L 87 CDJ
M 83 CDFHI
N 75 BCDEJM
O 9 BCEFGHKLMN
P 33 ACEFGIJO
Q 25 ADHLMNO
R 57 CDEFHIKL
S 47 CDFGKNPQ
T 86 ABCIMNQR
U 35 GHIJKQ
V 11 DGLMOPQR
W 74 BCFJNOPQRTV
X 95 CDFGKNOQSW
Y 78 AEFGHILNORVWX

A 16
B 31
C 38
D 19 AC

A 65

A 99
B 94 A
C 61 AB
D 56 B
E 41 ABCD
F 18 A
G 72 AC
H 8 ACDE
I 78 BCDF
J 90 BEFI
K 21 CEFGHIJ
L 53 ADEFHIK
M 92 BCDEGJKL
N 76 CDFGIK
O 94 ACDGIJKLM
P 22 DGHIJLNO
Q 22 BCEFGHLMO
R 7 ABCDHJKLNP
S 72 ABCEFGJKOPR
T 69 EFILMNPR
U 82 CJKNPQR
V 39 FJ
W 13 BCDGHIKLNOQRSTU
X 44 AEJKOPQRTUV
Y 6 ABCFHJKLMNOQTV

A 46
B 73
C 33 A
D 38 C
E 8 ABCD
F 6 AE
G 96 AF
H 96 DE
I 33 CDFG
J 88 ABCDEGH
K 79 ABCEFH
L 77 BDHJK
M 19 CGHIL
N 33 H
O 39 ABEFGIJKMN
P 37 CEFGHKN

A 72
B 38
C 85 AB
D 24 A
E 58 ABC
F 37 BD
G 49 CD
H 54 ACD
I 38 FG
J 69 ADEFHI
K 63 CEFGJ
L 20 FIJK
M 29 DFHIKL

A 2
B 71 A

A 12
B 38
C 42 B

A 99
B 53 A
C 22
D 51 C
E 15 D
F 99 CE
G 68 ABDF
H 6 ACE

A 79
B 15 A
C 73 B
D 73 C

A 57
B 22 A
C 84
D 45 C
E 1 CD
F 34 BCDE
G 60 DEF
H 44 CEF
I 29 BCF
J 49 AFI
K 90 BCEFG
L 52 CDGH
M 72 FGIL
N 12 AJK
O 8 EGHMN
P 62 BEHKLMN
Q 77 ACEFGIJK
R 35 FINQ
S 28 CGJNQ
T 54 CFIKLNPQ
U 9 FHKMPQST
V 23 CEGHIJLMOQTU

A 90
B 77 A

A 45
B 92 A
C 64 A
D 58 C
E 95 AB
F 31 ABCE
G 38 AE
H 46 CFG
I 12 ADEFH
J 30 ACFGHI
K 95 CGH
L 38 BFGJK
M 44 ACEGJK
N 41 ABDEFGHIJKLM
O 70 ACEFGHJN
P 60 BCEFGNO
Q 96 BCEFGIJKMP
R 5 ABCEFGHIJKNOPQ
S 69 CDEHIKNPQR
T 90 DGHIJLM
U 25 ABCDEGIMOPQR
V 20 ABCDEGHJLQSU
W 89 ABCHJLMOQSUV

A 46

A 89
B 72 A
C 99 A
D 40 AB
E 69 ABD
F 30 ABCD
G 22 CF
H 8 EF
I 82 BCFGH
J 44 CDEGH
K 59 H
L 49 DIJ
M 37 BEGJ
N 42 BCEHK
O 21 BCDFKN
P 72 BDFIJLM
Q 48 BEFIKLO
R 61 ACFIJKMNPQ
S 44 EKLNOPQR
T 61 ABDIJKLQ
U 62 ABCEGKLRT
V 14 BEFGHIJMOPQSU
W 19 BCGHIJLMNQTV
X 34 CFGHIJMNOSTU
Y 59 ACDGILPQSUX
Z 48 ABCEFGHKLMRUVWXY

A 21
B 59
C 22 B
D 59 AB

A 77

A 25
B 95 A
C 0 AB
D 26 ABC
E 65 D
F 97 ABDE
G 93 AF
H 67 AEG
I 40 DEG
J 67 BDFH

A 90
B 48 A
C 9 A
D 53 ABC
E 89 BC
F 90 ACDE
G 49 DE
H 38 ABDF
I 32 DE
J 94 BDFGHI
K 31 BFGI

A 6
B 7
C 62 B
D 30 A
E 81 AC
F 85 BCDE
G 36 AB
H 94 ABE
I 27 BCE
J 34 ACEH
K 15 ACDEGHJ
L 44 ABCEHJK
M 42 BDFGHJ
N 55 ABDE
O 97 ABDGHLMN
P 95 AEFGHIKL
Q 89 ABELM
R 36 ABCFJMOP
S 6 DGHJKOPQ
T 38 ACEFHIJKLMNOQR
U 8 ABCEGHIJKPT
V 83 ACEFGIJLQRSTU
W 29 ABEJLMNSUV

A 37
B 66 A
C 65 A
D 78 ABC
E 45 ABCD
F 21 AE
G 79 ABCDF
H 88 BCEG
I 29 CEGH
J 46 EI
K 35 ACDIJ
L 61 ABEFK
M 43 ABDEHI
N 84 EGHJLM
O 61 DEFGIJN
P 96 BIJMN
Q 86 AEGHIKLO
R 66 ABEGKLO
S 3 ACEFGKNOQ
T 40 FMNOPS
U 37 BDEFHJKLMNOPST
V 72 BDFGKLMRST
W 18 ABCFHMOSTU
X 41 DEFHJKLMOR
Y 8 ACEFHKLMNOSX

A 51
B 45 A
C 9 AB
D 88 ABC
E 57 B
F 75 AE
G 10 ABCDEF
H 23 EG
I 59 BD
J 77 ACHI
K 94 CEHI
L 16 BCFGH
M 88 ADEH
N 97 BEFJK
O 62 EFLM
P 57 AHLMO
Q 41 BFIJNOP
R 99 ACDFIJLMNOQ
S 31 ACDEHJKP
T 74 CDIJKPQS
U 25 ADGJM
V 75 ACDFGHLNORST
W 81 CIKLMNU
X 5 ABCHIKLMNPTUW

A 14
B 10
C 29 AB
D 34
E 79 CD
F 17 CDE
G 23 CDE
H 19 ACDE
I 40 ABDGH
J 75 ABFGHI
K 32 BDFHJ
L 91 EJK
M 89 ABDFIJK
N 53 EHL
O 41 ABEJL
P 80 BDN
Q 17 BDGJKLMNO
R 54 ABDEGHIJMNOPQ
S 42 ABCGHKOP
T 85 ADFHJKMOP
U 92 CFGHIJKLMNPS
V 8 CGJPQSU
W 24 DEHLMORSUV
X 66 CEFGHIJKLOUW
Y 13 BFIJLNQSTW

A 37
B 60 A
C 31
D 13 AC
E 1 ABD
F 10 C
G 35 A
H 16 ABCDFG
I 77 CFG
J 64 DHI
K 76 BFG
L 85 ABEGJ
M 2 ABCEGH

A 87
B 24 A
C 77
D 44 AC
E 6 C
F 48 ABCD
G 25 EF
H 22 ACDEF
I 47 ABGH
J 13 AE
K 68 BCEFG
L 22 HIJ
M 67 ABCDEFHIJKL
N 84 CDEFGHIJKLM
O 83 BCGILMN
P 46 EFGLNO
Q 11 FGJLO
R 80 CDFIJLNO
S 21 ABDEFHILOPR
T 76 DFLMNOPS

A 79
B 83
C 70 A
D 99 C
E 26 B
F 59 ACD

A 58
B 82
C 47 AB
D 51
E 85 D
F 52 BC
G 38 ACF
H 28 EG
I 90 ABF
J 50 CDEFGI
K 19 BGIJ
L 18 ACGHJK
M 3 BGHJKL
N 17 CDEFGHIJL
O 11 ABEFHKLM
P 61 BCGIK
Q 59 ABEFIJKLN
R 60 ACDEFGHJNOPQ
S 55 BDFHIKLOP
T 60 ABEHLNOP
U 19 ACFGIJMNOQRST
V 53 BDFGHIJLNPS
W 53 ABDEGIJKLOQSTV
X 42 CEFHKLMNPQRSVW
Y 12 CDJOSTWX
Z 57 BCDEFGHKNOPQRSTVY

A 12
B 79
C 39
D 33 B
E 7 BD
F 20 BCDE
G 36 CF
H 61 ABCEF
I 4 CG
J 65 AF
K 69 ACEGHI
L 29 ADGH
M 36 FK
N 81 ABFIJKL
O 22 ACFJM
P 99 ABDEGHJLO

A 55
B 27
C 3 B
D 90 BC
E 27 ABC
F 96 ACE
G 98 ABE
H 48 BCEF
I 69 AEGH
J 44 CDI
K 84 EGHI
L 31 BCDFGHJK
M 70 BEHK
N 61 ADFGIM
O 91 BCEIJM
P 71 CIKNO
Q 20 ACDFGO
R 54 CFHKLMN
S 73 BEFHIKLMNOR
T 89 CGHJLMNOPQS
U 18 ACEFGHIJLMNOPQST
V 74 ACEFGKMOQS
W 48 BCDHJKLNPQRSUV
X 38 ABDEHJKNPQSW
Y 35 ACDEIPQRSTVWX
Z 57 BCFGOSXY

A 57
B 48
C 56
D 3 A
E 28 A
F 52 CE
G 23
H 49 ABDG
I 2 ABCDE
J 34 CDG

A 20
B 42 A

A 87
B 2 A
C 32 B
D 84 ABC
E 8
F 36 ABC
G 1 B
H 2 ACEF
I 49 ABEG
J 35 ABEH
K 72 ADJ
L 32 ABDEFGI
M 78 CDGIJK
N 51 ACDHJLM
O 93 ABCDFGHJMN
P 59 ABCIJMO
Q 76 ABCEFGIJLNOP
R 92 BCEFGMO
S 83 ABCDGHJLMOQ
T 10 BEHIKOPRS
U 48 ADEFMORT
V 67 ABCEFMNOQRTU
W 30 ABCDEGJLMNPQTV
X 38 BCDEFGHKLNOQTUVW
Y 54 AFGLMNOPQSTUX
Z 46 CEFGHJLPRTWY

A 22

A 38
B 71 A
C 95 A
D 89 B

A 1
B 29
C 99
D 53 AB
E 11 BCD
F 65 CD
G 10 BC
H 52 C
I 16 ABCG

A 8
B 46 A
C 48
D 10 B
E 49 C
F 78 D
G 60 B
H 17 BE
I 15 BH
J 17 BCGHI
K 15 ABCDEGIJ
L 4 BCDFGK
M 8 BFGHIJ
N 70 ABFGHKM
O 90 CGIKM
P 79 ABEIKLMNO
Q 61 ABEFGHJMNO
R 56 ABCEGHIJKOPQ
S 87 DGILNQ
T 74 ABCFHJMS
U 32 ADGIJMNPT
V 71 BEJKMPRSTU
W 65 BEJKMNOQRSU
X 39 ACEIJLNOPQTV

A 94
B 19 A
C 35 B
D 26 BC
E 54 BD
F 48 ABC
G 67 ABCDEF
H 9 ABCDG
I 62 BCDG
J 69 ADFH
K 45 BCDEGIJ

A 63
B 26 A

A 35

A 30
B 76 A
C 51 B
D 26 ABC
E 19 BD
F 69 AE
G 32 ABCE
H 8 BCDEG
I 68 DEGH
J 79 BEF
K 11 BFGH
L 0 ADFGHJK

A 71
B 43
C 94 A
D 5

A 89
B 60
C 18 A
D 42 ABC
E 23 B
F 20 ABC
G 68 ACDEF
H 22 CF
I 16 BDEH
J 10 CDEFG
K 50 ABCDEFI
L 82 CEHJK
M 90 CEFHIJ
N 63 BCDEFGHJL
O 69 ABDEGHIKMN
P 62 DEIJLMNO
Q 16 EGHIJLMNOP
R 17 GHIMOP
S 37 AEFKLMNOQR
T 30 ACDGIMPQR
U 53 CDEGHLMNPQR
V 60 CDFILMNPST
W 28 BCDEGHMOPSU

A 47
B 52
C 15 AB
D 17 BC
E 7 AC

A 28
B 42 A
C 58 A
D 9 AC
E 98 ACD
F 33 ABCE
G 66 CDEF
H 3 BCF
I 66 BCDEG
J 49 BDF
K 7 BCDEJ
L 50 ABCHIJK
M 48 ABDEFGIK
N 26 AEGIJLM
O 93 DEFGKLM
P 36 ADIKO
Q 49 ABFGHLMOP
R 48 ADEHIMNOQ
S 93 ABEJKLMNO
T 30 ADGHIJKQRS

A 53
B 8
C 62 AB
D 97 A
E 82 A
F 4 BCDE
G 90 ABDF
H 54 ACDEF
I 80 ADFG
J 94 ACEG
K 41 ACEFGJ
L 36 ADEGJK

A 60
B 15 A
C 67 B
D 85 BC
E 63 A

A 11
B 17
C 8 AB
D 75 B
E 76 BC

A 87
B 4 A
C 17 A
D 37 B
E 97 ABD
F 62 ABD
G 49 AF
H 31 B
I 86 ACG
J 67 ABCDFI
K 82 BDF
L 84 BCEFIK
M 86 ACEFHIJK
N 63 ADGIJK
O 0 ACEGHIKMN
P 20 ACHILNO
Q 52 BCFGHJKLO
R 46 CGHKLMN
S 84 FGHJM
T 20 BCHLMOP
U 50 BFHIJKLPQT
V 78 CEGJLMNQR
W 75 ABCFHJLMNQSV

A 46
B 77
C 51 AB
D 39 A
E 16
F 20 BDE
G 63 ABCEF
H 40 DFG
I 39 CDFG
J 48 ACDGH
K 8 ABCDEFGI
L 13 ABCHK
M 69 ACEHJL
N 88 ABDEIL
O 64 CDFIN
P 51 BDEFHIJKM
Q 25 BDEGHIKL
R 19 ABHILP
S 81 CDEFHIKMOQR
T 18 ACDEGHJKMOPQS
U 20 ADEGHIKMOQRST
V 40 BCNOPRT

A 30
B 7
C 36 B
D 27 ABC
E 33 ACD
F 84 BE
G 71 AB
H 63 BCDFG
I 31 BCDGH
J 73 ABCEGHI
K 33 ABCFGHI
L 57 DEGHIJ

A 24
B 80
C 70 AB
D 0 C
E 94 BCD
F 69 BE
G 40 BDF
H 44 DEF
I 80 ABCEF
J 87 ADGI

A 50
B 49
C 94 AB
D 15
E 55 BD
F 53 ABCD
G 18 ACD
H 66 AB
I 43 ACDEFH
J 71 DE
K 27 BFHI
L 73 CDEFG
M 79 BEFHIJKL
N 88 BCEHIKM
O 63 ABCEHJKLN
P 96 ABIJKL

A 27
B 31
C 17 B
D 23 ABC
E 78 BC
F 27 CE
G 43 CEF
H 76 ABCE

A 47
B 11 A
C 20 AB
D 64 ABC
E 21 D
F 26 BC
G 70 BCDEF
H 97 ABCEFG
I 60 AG
J 75 AEHI
K 54 ACEGHIJ
L 82 CEFIJK
M 15 ABDEHIL
N 81 ABIK
O 59 ABDFGHIJKN
P 85 DGHIJLMN
Q 38 BCDGHIKMOP

A 75
B 46 A
C 39 A
D 90 B
E 49
F 93 ACDE

A 23
B 91
C 17
D 96 ABC
E 79 AD
F 5 AC

A 16
B 1
C 69 A
D 47 B
E 23 ABD
F 87 ABD
G 76 ABC
H 47 BCDF
I 54 CG
J 13 B
K 56 DG
L 82 CDFGHIK
M 78 ABCDEFGHIJL
N 40 IJ
O 29 AEFGHM
P 32 LO
Q 55 BCEGIJLOP
R 42 ABDFGIKLMO
S 91 ADEFKLMPQ
T 20 BCFGMNPS
U 23 BDFGLMOPQRST
V 95 BDFGMNU
W 43 ABCHIKLMNOQRSTU
X 32 FGKLNORST
Y 44 ACEFHIMNRS
Z 35 ABCDFIKNPQXY

A 99
B 51 A
C 83 B
D 76 A
E 21 AD
F 86 CE
G 48 BF
H 19 ADEFG
I 34 BCG
J 11 ACEH
K 30 CDEFIJ
L 74 ABCFHI
M 67 AL
N 89 ABEIM
O 73 ABCFGIJM
P 48 CGJKNO
Q 41 CEGHM
R 56 ADEGIMQ
S 45 ABEFHJKMNR
T 64 GIJKNPRS
U 18 CGILOPQS
V 2 AFILOQRS
W 84 CDEGHKRSV
X 4 BDEGHKMNOPQRTUW

A 58
B 80
C 50 AB
D 7 ABC
E 4 BD
F 53 CDE
G 74 CD
H 69 AG
I 52 ACFG
J 90 ACGI
K 50 ABCDFGIJ
L 45 ABCEGH
M 99 ACDEFIJK
N 66 BDGHIJKLM
O 92 BDHJN
P 59 BCDIJKLN
Q 40 ABEFIJL
R 69 ACDFGHIOPQ
S 45 CEGJLNOR
T 41 ADGHIOPQ
U 75 BCDEHJKNORST
V 51 ADEFHIJNORST

A 35
B 81
C 42 AB
D 3 ABC
E 87 A
F 33 BE
G 43 ACDE
H 55 ABD

A 40
B 11
C 97 B
D 53 AB
E 73 BCD
F 70 CE
G 74 ABCDF
H 94 BEF
I 45 BDFH
J 24 DGHI
K 33 BEFHIJ
L 80 CEGHIK
M 43 CGHIKL
N 34 ACEFHIL
O 31 FGHIMN
P 55 BJKLO
Q 79 BEFKMOP
R 73 CFGHKMNOQ

A 83
B 86 A
C 18 B
D 23 C
E 81 C
F 3 CDE
G 37 ABF
H 8 ACDFG
I 17 BDG
J 94 AEFG
K 49 EFGIJ
L 15 BEFIK
M 15 BEJK
N 44 BCDGIK
O 79 ABCEHIN
P 91 BCDHILM

A 17
B 41 A
C 85
D 3 BC
E 14 ABC
F 21 BDE
G 82 BF
H 66 CDE
I 57 ACGH
J 35 BGI
K 79 BCFGHJ

A 12
B 34 A
C 69 B
D 69 A
E 99 B
F 55 ABE
G 11 ACEF
H 21 ACD

A 27
B 35
C 84 A
D 37 A
E 18 AD
F 69 BC
G 88 ABE
H 48 AG
I 88 ADGH
J 53 BDEGH
K 88 AB
L 72 BDFGHK
M 31 BFIJKL
N 63 ABEJL
O 43 AFGHKMN
P 23 CDFIKLO
Q 55 FGHIKMO
R 84 BCDFGKLMOP
S 65 CDEFHKMNQ
T 69 EFGJLMRS
U 97 BILMOQT
V 17 ADEFGJLMNPQ
W 29 ADEFJKLSTU
X 34 ACFJNPRTUW

A 98
B 85

A 72
B 91 A

A 1
B 79
C 81
D 91 AB
E 83 BCD
F 83 BDE
G 33 ABDEF
H 20 BCDEF
I 33 BCFH
J 98 ABCGHI
K 56 ACDEGI
L 32 CDEFH
M 9 ADFGJK
N 4 ABCEFHI
O 87 ABK
P 13 BDHILNO
Q 74 EGHIJLMO
R 41 ABCFGIM
S 35 ABFHP
T 62 ADHIKMPRS
U 90 AHLRST
V 3 ABCDEPRSU
W 9 BCHJKLOQRTUV

A 53
B 90 A
C 61 AB
D 52 B
E 16 AD
F 49 DE

A 47
B 15
C 84 B
D 0 AC
E 69 A
F 19 ABCD
G 75 AF
H 15 ADFG
I 43 ACEGH
J 68 CDEFHI
K 82 ACEFGI
L 47 BCDEGJ
M 64 BEFGJK
N 83 ABCEFGL

A 61
B 65 A
C 77

A 88
B 92
C 79
D 69 AB
E 58 BC
F 38 C
G 68 BC
H 4 F
I 59 H
J 96 BCDFG
K 90 CEFHI
L 12 EGHJK
M 69 BCHJL
N 98 ABCEFGIJK
O 92 CDGIJKM
P 96 CEFGHJ

A 56
B 22
C 54 A
D 45 AB
E 26 ABD
F 12
G 99 ACDF
H 26 AD
I 24 ADFGH
J 27 ABCDEF
K 39 CEFHIJ
L 13 ACDGHI
M 86 ABDEGHJ
N 93 ABFGIJL
O 63 CEJKLMN
P 75 DGHIJN
Q 19 ACFIJMNOP
R 23 ACDEGIJQ
S 96 DGIMNQR
T 84 BCDGKNPQ
U 68 ADEFGHNQRT
V 13 ABFNPQRTU
W 44 ABDGIKLMNOPRSUV
X 57 ADHIJKLNQRSVW
Y 49 ADFHIJMNOSX

A 98
B 55 A
C 49 A
D 96 AC
E 93 ABC
F 74 ACE
G 38 ACDF
H 96 AEFG
I 81 ABCGH
J 23 BCDEFGI
K 39 BFJ
L 42 CDFHIJK
M 62 BCDHJ
N 83 ADEGHIJKM

A 27
B 94
C 41 B
D 39 BC
E 86 ABD
F 31 ACDE
G 44 ABC
H 9 ADG
I 69 ABCG
J 59 BCDEGI
K 14 ABHI

A 74
B 55
C 51 A
D 33
E 48 BCD
F 34 BC

A 80
B 68 A
C 13 AB
D 18 A
E 15 D
F 29 ABDE
G 15 ACDF
H 32 DEF
I 66 ABFH
J 4 ACDEFGI
K 12 BCFHI
L 11 ABEFGHJK
M 76 CDEGK
N 46 ACGIJK

A 36
B 17
C 12
D 93 AC
E 18 BCD
F 55 AD
G 12 AE
H 64 BDEG
I 21 BCDEFG
J 95 CEG
K 35 ABCDEHI
L 74 ACFHIJK
M 87 EFL
N 77 BFGJLM
O 9 ACEFGH
P 24 ABCDFGHJKLNO
Q 45 BFGIJMP
R 31 ACELMO
S 73 ACDEGHJLNO
T 76 EFGHKMNOQRS

A 39
B 76
C 80
D 79 C
E 25 CD
F 63 AD
G 37 ABCE
H 58 CEG
I 91 ABCDFG

A 14
B 95 A
C 94 B
D 31 B
E 46 D
F 23 B
G 95 AF
H 41 CDEF
I 78 ACDH
J 75 ABDEFI
K 64 ABCFHJ
L 9 ACIJK
M 48 CDFJKL

A 75
B 53 A
C 53
D 14 AC
E 15 BCD
F 97 BC
G 16 BF
H 51 AB
I 46 BDGH
J 39 BDEGH
K 53 ADEFGHIJ
L 3 CEFGI

A 45
AC output:

Code: Select all

824

733

116

439

1053

885

874

295

323

273

544

92

350

145

592

521

633

787

744

57

65

837

450

425

73

80

255

240

496

167

905

46

745

118

77

535

449

628

931

683

748

298

684

307

673

426

922

137

62

1010

22

198

164

615

418

89

35

350

165

617

84

664

415

227

101

683

557

411

480

500

202

679

304

266

722

774

849

181

808

574

373

211

745

98

163

744

260

449

126

443

748

703

319

173

363

645

313

518

340

45

Re: 452, Why WA

Posted: Fri Jun 28, 2013 12:34 pm
by @ce
@brianfry713....for the test case

Code: Select all

A 74
B 55
C 51 A
D 33
E 48 B C D
F 34 B C
Your answer is 159, but...
Critical path for A = A(74) = 74
Critical path for B = B(55) = 55
Critical path for C = A(74) + C(51) = 125
Critical path for D = D(33) = 33
Critical path for E = max(B(55),C(125)) + E(48) = 173
Critical path for F = max(B(55),C(125)) + F(34) = 159
Project completion time = 173(E)

Another test case...

Code: Select all

A 2
B 37
C 16
D 43 A B C
E 20 A B
F 29 A B C
G 36 A D E F
Your answer is 81, but...
Critical path for A = A(2) = 2
Critical path for B = B(37) = 37
Critical path for C = C(16) = 16
Critical path for D = max(A(2),B(37),C(16)) + D(43) = 80
Critical path for E = max(A(2),B(37)) + E(20) = 57
Critical path for F = max(A(2),B(37),C(16)) + F(29) = 66
Critical path for F = max(A(2),D(80),E(57),F(66)) + G(36) =116
Project completion time = 116(G)

Please explain...i think i am not understanding the question...

Re: 452, Why WA

Posted: Fri Jun 28, 2013 11:38 pm
by brianfry713
My input was invalid, it shouldn't have had spaces between the letters at the end of a line. I edited it in my previous post.

AKJ88, for this input:

Code: Select all

1

A 2
B 37
C 16
D 43 ABC
E 20 AB
F 29 ABC
G 36 ADEF
Your code at https://ideone.com/1R33VS is printing 81, the correct answer is 116, the critical path is B->D->G.

@ce, your output for the two cases you posted is correct, however now your code doesn't work because there should not be spaces between the letters at the end of a line. Check my updated I/O or post updated code if you're still having trouble.