452 - Project Scheduling
Moderator: Board moderators
-
- Learning poster
- Posts: 99
- Joined: Sun Apr 06, 2003 5:53 am
- Location: Dhaka, Bangladesh
- Contact:
452 - Project Scheduling
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.
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.
Where's the "Any" key?
-
- Guru
- Posts: 834
- Joined: Wed May 29, 2002 4:11 pm
- Location: Wroclaw, Poland
- Contact:
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![:-)](./images/smilies/icon_smile.gif)
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
If anyone should help us and post some critical IO or proof that this approach isn't good - we would be greatful
![:-)](./images/smilies/icon_smile.gif)
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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)
Born from ashes - restarting counter of problems (800+ solved problems)
-
- A great helper
- Posts: 281
- Joined: Tue Sep 10, 2002 5:14 am
- Location: Mountain View, CA, USA
- Contact:
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.
If only I had as much free time as I did in college...
I think they have repeated lines in the input.
For example:
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.
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 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
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.
I also need to know if the graph includes a cycle what do I get on system output?
Thank you.
Re: 452, Why WA
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.
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.
-
- Learning poster
- Posts: 72
- Joined: Tue May 30, 2006 5:57 pm
- Location: bangladesh
Re: 452, Why WA
The graph must be a DAG.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.
SO there have no circle.
There can be multiple starting node.
There can be Multiple DAG in a case.
Mak
Help me PLZ!!
Help me PLZ!!
-
- Experienced poster
- Posts: 147
- Joined: Mon Jun 07, 2010 11:43 am
- Location: University Of Dhaka,Bangladesh
- Contact:
Re: 452, Why WA
try this case:
output from my ac code:
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]
Code: Select all
34
UVa stats: http://felix-halim.net/uva/hunting.php?id=63448
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
My blog on programming: http://www.shafaetsplanet.com/planetcoding/
Re: 452, Why WA
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.
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.
Last edited by skiranc on Wed Jun 26, 2013 10:57 am, edited 1 time in total.
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 452, Why WA
don't read from a file.
print a newline at the end of the last line.
print a newline at the end of the last line.
Check input and AC output for thousands of problems on uDebug!
Re: 452, Why WA
Wow, I can't believe it was so simple.
Thank you!
Thank you!
Re: 452, Why WA
Getting WA...plzz help
Code: Select all
AC
Last edited by @ce on Sat Jun 29, 2013 6:58 am, edited 2 times in total.
-@ce
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 452, Why WA
Input:
AC output:
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
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
Last edited by brianfry713 on Fri Jun 28, 2013 11:26 pm, edited 2 times in total.
Check input and AC output for thousands of problems on uDebug!
Re: 452, Why WA
@brianfry713....for the test case
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...
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...
Code: Select all
A 74
B 55
C 51 A
D 33
E 48 B C D
F 34 B C
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
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...
-@ce
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 452, Why WA
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: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.
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
@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.
Check input and AC output for thousands of problems on uDebug!