506 - System Dependencies

[dh3014]

I need correct output for following test data:
--
DEPEND A B C
DEPEND B D E G
DEPEND C G E K
DEPEND K Z
DEPEND E S
INSTALL A
LIST
REMOVE A
LIST
INSTALL B
INSTALL C
INSTALL A
REMOVE A
INSTALL K
LIST
REMOVE C
REMOVE A
INSTALL A
LIST
INSTALL C
REMOVE A
LIST
END

--
following are my program's output
--
DEPEND A B C
DEPEND B D E G
DEPEND C G E K
DEPEND K Z
DEPEND E S
INSTALL A
Installing Z
Installing K
Installing S
Installing E
Installing G
Installing C
Installing D
Installing B
Installing A
LIST
Z
K
S
E
G
C
D
B
A
REMOVE A
Removing A
Removing C
Removing K
Removing Z
Removing B
Removing G
Removing E
Removing S
Removing D
LIST
INSTALL B
Installing G
Installing S
Installing E
Installing D
Installing B
INSTALL C
Installing Z
Installing K
Installing C
INSTALL A
Installing A
REMOVE A
Removing A
INSTALL K
K is already installed.
LIST
G
S
E
D
B
Z
K
C
REMOVE C
Removing C
Removing K
Removing Z
REMOVE A
A is not installed.
INSTALL A
Installing Z
Installing K
Installing C
Installing A
LIST
G
S
E
D
B
Z
K
C
A
INSTALL C
C is already installed.
REMOVE A
Removing A
Removing C
Removing K
Removing Z
LIST
G
S
E
D
B
END
--

I think I did look at the problem description very carefully and several times. but after submit my problem, I got Runtime Error, I think it's because I don't allocate enough memory to restore each item's data. After I fixed it, I got Wrong Answer now... I tried several times but it didn't work, now I want to know...when we installing or removing some components, would their display order make the difference though it's a special judge problem?
Thanks anyway.

[wyvmak]

i checked the output, the order is a bit different, but it looks ok. as it's claimed as a special judge problem, unless the judge program itself has problem.

maybe test your program on cases on components cannot be removed.

in installing A, my output would be:
INSTALL A
Installing D
Installing S
Installing E
Installing G
Installing B
Installing Z
Installing K
Installing C
Installing A

[..]

I got many WA on this, going to be crazy
Can anyone provide some tricky case?

[little joey]

Well, I got many, many WAs too, and still see no way out of it.

The thing that worries me most is the phrase

Likewise, a component, not explicitly installed, can be explicitly removed in response to a command (if it is not needed to support other components)

I cannot think of a situation where a component that is not explicitly installed, that is not needed by other components, can be still installed. It should be already removed when the components that depended on it where removed. Can anybody explain?

[..]

Hi, I got it accepted.
I never think about the case you say, I think you are correct. There is no such situation.
I got accepted after correcting my "LIST" order.

[little joey]

Congrats!
Been waisting the whole morning on this problem, and still no success...

Are there any catches concerning the list-order? My program produces exactly the same output for the sample cases as is given.
For the input

Code: Select all

INSTALL A
INSTALL B
REMOVE A
INSTALL A
LIST
END

my program gives

Code: Select all

INSTALL A
   Installing A
INSTALL B
   Installing B
REMOVE A
   Removing A
INSTALL A
   Installing A
LIST
   B
   A
END

which should be correct, according to the description. Or should the list-order be reversed?

[..]

You are correct on that output.

Input:

Code: Select all

DEPEND A C B
DEPEND B C
INSTALL A
LIST
REMOVE A
END


Output:

Code: Select all

DEPEND A C B
DEPEND B C
INSTALL A
   Installing C
   Installing B
   Installing A
LIST
   C
   B
   A
REMOVE A
   Removing A
   Removing B
   Removing C
END


[little joey]

That's exactly my output.
I give up on this problem.

[Caesum]

I had a similar experience on this problem some time ago, I can match all of the examples that have been given on the boards but unfortunately I am also WA on it

[little joey]

Well, it's maddening. There should be something that almost everybody is overlooking. I have confirmed that command words can also occur as component names, but I am almost certain my program handles them correctly.

Code: Select all

DEPEND REMOVE INSTALL DEPEND END LIST
INSTALL REMOVE
INSTALL END
LIST
END

should give

Code: Select all

DEPEND REMOVE INSTALL DEPEND END LIST
INSTALL REMOVE
   Installing INSTALL
   Installing DEPEND
   Installing END
   Installing LIST
   Installing REMOVE
INSTALL END
   END is already installed.
LIST
   INSTALL
   DEPEND
   END
   LIST
   REMOVE
END

and not

Code: Select all

DEPEND REMOVE INSTALL DEPEND END LIST
INSTALL REMOVE
   Installing INSTALL
   Installing REMOVE
INSTALL END
   Installing LIST
   Installing END
LIST
   INSTALL
   REMOVE
   LIST
   END
END

I also considered some exotic cases, but still on the wrong track.

[Caesum]

What about the following ?

DEPEND A B C
DEPEND B D E G
DEPEND C G E K
DEPEND K Z
DEPEND E S
INSTALL A
LIST
REMOVE A
LIST
INSTALL B
INSTALL C
INSTALL A
REMOVE A
INSTALL K
LIST
REMOVE C
REMOVE A
INSTALL A
LIST
INSTALL C
REMOVE A
LIST
END

My WA program gives

DEPEND A B C
DEPEND B D E G
DEPEND C G E K
DEPEND K Z
DEPEND E S
INSTALL A
Installing D
Installing S
Installing E
Installing G
Installing B
Installing Z
Installing K
Installing C
Installing A
LIST
D
S
E
G
B
Z
K
C
A
REMOVE A
Removing A
Removing B
Removing D
Removing C
Removing E
Removing S
Removing G
Removing K
Removing Z
LIST
INSTALL B
Installing D
Installing S
Installing E
Installing G
Installing B
INSTALL C
Installing Z
Installing K
Installing C
INSTALL A
Installing A
REMOVE A
Removing A
INSTALL K
K is already installed.
LIST
D
S
E
G
B
Z
K
C
REMOVE C
Removing C
Removing K
Removing Z
REMOVE A
A is not installed.
INSTALL A
Installing Z
Installing K
Installing C
Installing A
LIST
D
S
E
G
B
Z
K
C
A
INSTALL C
C is already installed.
REMOVE A
Removing A
Removing C
Removing K
Removing Z
LIST
D
S
E
G
B
END

[little joey]

Exactly the same, line by line. I also tried 'crossing dependences' involving multiple levels and mixed levels, but al the answers seem sensible. Did several checks on the input, but found no flaws.

[..]

Just want to remind you two, do you handle that arbitrarily space may exist before and after the name of modules?

[Caesum]

Well for something like

DEPEND.....A....B
INSTALL....A....
LIST......
REMOVE....B....
REMOVE.........A....
END

(I have replaced spaces by dots)
My program gives:

DEPEND.....A....B
INSTALL....A....
Installing B
Installing A
LIST......
B
A
REMOVE....B....
B is still needed.
REMOVE.........A....
Removing A
Removing B
END

[little joey]

2.5 months later I got AC, while looking at it all over again.

Just one hint for those still struggeling: look at my memory consumption...