Solutions to the problem CHEFARMY are awarded points even if not optimum. I tried a simple solution to earn myself some points, based on the following observations:
- The structure of the army is a tree.
- Whether a soldier hated by a general is paid a bit at a time or all at once, the total anger of the general is the same.
- If several soldiers hated by a general are paid at the same time, the total anger of the general is less than if they are paid separately.
- As the army is small, an N-cubed algorithm is good enough.
The method is then
-
Build a tree of the army by command structure.
-
Evaluate the time entered and left each node on a recursive traverse of the tree by depth-first search, to enable rapid evaluation of whether any soldier is a superior of another (ancestor in the tree).
-
Loop until no more soldiers are to be paid:
Sort the soldiers still to be paid into order of increasing amount owed.
Compare every soldier in this array against every other soldier. If any is a superior of another in the list, remove the subordinate from the list (one of the rules is that a soldier and a superior cannot be paid at the same time).
Pay all the soldiers remaining in the array the least amount owed.
Update the amount owed to each soldier.
This approach in CodeChef: Practical coding for everyone earned me 79 points, without the need to take into account the information about who hates whom. I found this problem considerably easier than others which I failed to solve but which were solved by hundreds of people, although I have no idea how to get 100 points here.