452 - Project Scheduling

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

Moderator: Board moderators

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Location: Dhaka, Bangladesh
Contact:

452 - Project Scheduling

Post by Solaris » Mon Aug 23, 2004 7:43 pm

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.
Where's the "Any" key?

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Tue Aug 24, 2004 11:59 am

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
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)

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Sun May 08, 2005 7:51 am

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...

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon May 22, 2006 3:25 pm

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.

branka.j
New poster
Posts: 1
Joined: Tue Mar 03, 2009 4:28 pm

Re: 452, Why WA

Post by branka.j » Tue Mar 03, 2009 4:38 pm

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.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 452, Why WA

Post by Sedefcho » Tue Mar 03, 2009 7:09 pm

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.

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

Re: 452, Why WA

Post by mak(cse_DU) » Mon Apr 26, 2010 6:57 pm

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.
Mak
Help me PLZ!!

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 452, Why WA

Post by Shafaet_du » Mon Aug 29, 2011 9:51 pm

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

skiranc
New poster
Posts: 2
Joined: Wed Jun 26, 2013 3:03 am

Re: 452, Why WA

Post by skiranc » Wed Jun 26, 2013 9:30 am

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.
Last edited by skiranc on Wed Jun 26, 2013 10:57 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 452, Why WA

Post by brianfry713 » Wed Jun 26, 2013 10:37 am

don't read from a file.
print a newline at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

skiranc
New poster
Posts: 2
Joined: Wed Jun 26, 2013 3:03 am

Re: 452, Why WA

Post by skiranc » Wed Jun 26, 2013 10:57 am

Wow, I can't believe it was so simple.

Thank you!

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 452, Why WA

Post by @ce » Thu Jun 27, 2013 9:23 pm

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 452, Why WA

Post by brianfry713 » Thu Jun 27, 2013 11:40 pm

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
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!

User avatar
@ce
Learning poster
Posts: 71
Joined: Mon May 28, 2012 8:46 am
Location: Ranchi, India

Re: 452, Why WA

Post by @ce » Fri Jun 28, 2013 12:34 pm

@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...
-@ce

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 452, Why WA

Post by brianfry713 » Fri Jun 28, 2013 11:38 pm

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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 4 (400-499)”