PROBLEM LINK:
Setter Alei Reyes
Tester Encho Mishinev
Editorialist Abhishek Pandey
DIFFICULTY:
HARD
PREREQUISITES:
The optimal solution uses Faigle Kern algorithm from the linked paper (Read upto page 7).
But due to the unique format of this problem, the prerequisites by and large are simply:
A general Introduction to Graph Theory , BFS and DFS , Concepts on Linear Programming basic theory on Partially Ordered Sets
PROBLEM:
You are given a tree representing N soldiers. A soldier u is afraid of another soldier v if node u lies in subtree of v. There are also M generals and you also given if a general hates a soldier or not.
Now, you need to give each soldier i his salary S_i by following method
 Choose number of days D by which you will give everyone his salary. 0 \leq D \leq N^2
 For each day, chose an integer K and call K soldiers. You then decide another number R and hand each soldier R coins.
 If any general hates any of the K soldiers called, they become mad. If say, G generals are mad, their angriness increases by G*R
Find best method to pay salary such that sum of total angriness is minimized.
QUICKEXPLANATION:
Key to AC While an optimal solution is possible using the research paper linked, the general trend of making equations (the exact equation depended on Participant) and using Linear solvers to solve them dominated the top scores.
The optimal solution was to obviously apply to Faigle Kern algorithm given in this research paper. But the problem has a very special format  and that allows us to discuss a lot more than just the optimal solution.
Two of the high scoring techniques were:
 Interestingly, solving the problem without any regard to angriness of generals. This approach just decided to try to maximize the soldiers called on a single day and got \approx 7585 points.
 Some of the top scoring solutions used Linear Programming. They formulated the problem of which group to call in what order as a set of linear equations and solved them.
EXPLANATION:
The optimal solution is actually very verbosely given in the research paper, along with all the required proofs. Hence, we will not discuss a lot about that because that will make the editorial unnecessarily verbose and boring. Instead, the plan is to briefly discuss the following:
 The interpretation of constraints and test generation plan.
 Some notable observations made by topscorers.
 Discuss the optimal solution briefly.
 Analyze Contestantâs solutions
There will be no separate section for solutions  I will mention solution links along with the described approaches.
Interpretation of Constraints and Test Generation plan
This section is the first key to making observations which can make you one of the top scorers . And this applies to all approximate/challenge problems!
First note that we are given a generous 7 seconds for 50 test cases. Not bad actually! N is pretty small with a value of 128 and M is merely 16. The most interesting constraint however, is that of S. S_i \leq 100 !!! Thats very lenient because it allows a lot of approaches to open up  primarily due to the fact that now \sum S_i \leq D \leq N^2 is possible.
The next interesting thing is in the output section. It mentions that " For each valid i, let the total amount of money received by soldier i be W_i. Your answer will be considered correct if WiâSi \leq 10^{â6}"
This is the BIG hint that some sort of equation solving method is intended to yield high score  as (somehow) it allows us to give R coins where R may not be an integer. This also highlights the fact that the equations will have to deal with floating points  which makes it a wise decision to use some foolproof library instead of writing your own code to avoid loss of precision etc.
The test generation plan is very simple.
 S_i are randomly selected  hence the expected value of S_i is (1+100)/2=50.5. Hence, the expected value of \sum S_i=50.5*N=6464. The standard deviation of a uniform distribution, as proved here is \large \frac{ba}{\sqrt 12}. Using formulaâs to find standard deviation for linear transformation (because we want standard deviation for \sum S_i or N times sum of random variable S_i), we realize that standard deviation is \approx 684. Hence, by using Chebyshevâs Theorem, we can conclude that 95 \% of our data will have \sum S_i in range 6464 \pm 3*684. This means that even if we give a soldier 1 coin daily, we will be able to give everyone salary. This observation opens up possibilities of new approaches for you.
 The tree is biasedrandom. A LOT of things are given away by this. Firstly, the expected depth of such a tree is always O(LogN) , which can be proved in a similar way as proved here. You can do a lot of heuristics  based on degree of node, exploiting the âstructureâ of such random trees and what not! Why do I call it biased random? Well, there are some biases to exploit in this generation plan  like, see for how many nodes Node 1 is a candidate for being the parent. From my experience, many people would analyze the trees generated by this plan to exploit any such âcommonstructureâ in them.
 The next two constraints tell that we have both cases  where generals hate very less soldiers and where they hate majority of soldiers. You will need to handle both cases carefully to get a top score.
Some notable observations made by Top Scorers
The most important observation for this problem was the partial submodularity of the angriness function. Let us always give R=1 coins each time we call the generals. Let F(X) denote the angriness function if the set X of soldiers is called. F(X) being submodular means that:
F(A)+F(B) \geq F(A \cup B)+ F(A \cap B)
Lets understand it with an example. Say we have 2 soldiers, 1 and 2. Forget about the part that one of them would be afraid of other for now. Say we have 4 generals, 1,2,3,4. Generals 1,2,3 hate soldier 1 and Generals 2,3,4 hate soldier 2. Assume they both need to be given only 1 coin.
Now clearly, F(1) = 3, F(2)=3. Also, F(1 \cup 2)=4 and F(1 \cap 2 = \phi)=0.
A formal proof is given at the bonus corner. This proof is also necessary to convince yourself that the optimal solution using Faigle Kern algorithm is correct.
The next observation is a bit indirect  we realize that the relationship between soldiers is that of a Partially Ordered Set (POSET). To see why, just replace âfearsâ with Comparable. A soldier u is comparable to soldier v iff they have an edge between them which represents some sort of ordering or ranking. Else they are not comparable.
Now everyday, we need the list of soldiers such that each of them is incomparable to everyone else. Such a list of soldiers (or nodes in POSET) is called antichains. Pretty fancy name for a simple concept  but knowing the formal name of what you are looking for helps.
The next observation is, there is no extra overhead for calling a soldier multiple times! Hence, if you call a soldier and give him all his money at once, or call him multiple times and give him money, the angriness of generals increases by same amount, which would be G*S_i.
So does this mean brute force is optimal? Certainly not! You can always chose a set of soldiers such that most of them piss off a common General and hence optimize the overall angriness. And there are exponential possibilities on how we can find the âoptimum setâ of soldiers to call each day. This was the defining line on why same algorithm or idea got different points for various submissions.
The other observations related to Constraints and TestGeneration plan have already been discussed, and we are now ready to discuss what interesting approaches others used!
Brief Note on Optimal Solution
Before we delve into what other contestantâs did, we should definitely check out at least the basic idea of what the optimal solution was  even if its given out verbosely in the paper.
Faigle Kernâs algorithm is a greedy algorithm. The paper first defines closure of a set and uses it to define extreme points of a set. It then proceeds as follows:
 At each iteration, consider all extremepoints of the set. Find the minimum weight/value (in our case, coins to give) with respect to that point (in our case, soldier). Let this value be w_e corresponding to Node e.
 Add w_e to values (i.e. give w_e coins to all soldiers) which are extremepoints of the set.
 Remove the chosen Node e.
This is a very highview of the algorithm, because you will note I did not go into what is our âsetâ or how do we find the extremepoints of this set. That part is completely mathematical and has to be seen from the paper itself.
Analyzing Contestant's Solution
All scores mentioned in the section are from Div1 unless mentioned otherwise.
 The trivial solution of calling one soldier daily and giving him his required wage got 11.5 points in Div1. A reference solution is here.
 Some contestants optimized above by calling more than one soldier if they all pissed of the exact same set of generals. This gave them a slightly higher score than brute force. Another optimization was calling 2 soldiers whenever possible (reference solution here ).
 A majority of the solutions in Div 1 used simple BFS to score 54.7 points. What they did was to observe that soldiers at same level in the graph cannot be afraid of each other  as they cannot lie in subtree of each other! Hence, they would constantly call the entire level of soldiers and distribute money until each soldier has got his needed amount. Then theyâd proceed to the next level. Reference Solution  here
 Slight optimizations to above were possible which led to slightly more scores. One such optimization was that while processing a level, if a soldier is done, see if you can include his parent in set or not & so on.
 Then there is a distinct block of solutions getting 79.4 points. The chief difference between these solutions and previous discussed solution is that  instead of just checking soldiers at a level, this solution keeps a list of all soldiers. It then sorts the list in increasing order of S_i. It chooses the front element of the list, removes all its superiors from the list, and then makes leftover soldiers report along with first element (soldier) in the list. This solution is more optimized because it increases number of soldiers called  which means more chances of soldiers which piss common general getting called, hence more optimization. You should also refer to @david_s 's answer here as he also explained what he coded. Donât forget to hit a like there!
 The difference between this and next set of solutions was on exploitation of calling soldiers which make a common general angry. One trick that these solutions did was to replace node u with a chain of s[u] nodes and started deleting nodes from leaves. A solution which simply deletes leaves (without the chain trick) got 88.2 points as seen [here] (https://www.codechef.com/viewsolution/28951581) .
 The chain trick was more of a convenience  because with R=1 for every set of soldiers called, your sole focus is to minimize number of angry generals. One of the methods where this trick was used was to combine the BFS trick (calling soldiers at each level) with this chain trick to increase soldiers with commongenerals. Reference Answer: here .
 Another way to chose âoptimumâ or âalmostoptimumâ set of soldiers such that number of angry generals is minimized was to model this selection of soldiers as a system of linear equations. How and what insights or constraints you use to model them primarily determined the score. For example, you do not compulsorily need to model equation for the exact problem as given  you can use suitable relaxations or selfdefined additional constraints if it makes your life easier (except that its a tradeoff between quality of equations and their feasibility).
 These linear equations can be solved with Simplex or GaussJordian methods.
I will end the editorial with some cool topscoring solutions which I feel are friendly enough to understand:
 @he_____he 's solution here
 @wrong_answer_1 's solution here
 @zhouyuyang 's solution here
 @utaha 's solution here
 @nagrar0k 's solution here
 @cjy2003 's solution here
Iâd also like to invite everyone to share there approaches as well
CHEF VIJJUâS CORNER
Proof on submodularity
Assign each soldier a number, such that the i'th bit of this number is set if that soldier makes i'th general angry. Say we have two soldiers with numbers assigned as X and Y. It is easy to see that total number of angry generals if both of them are called is nothing but number of 1's in binary representation of X  Y , i.e. (X bitwiseOR Y). Its easy to see this holds true for even when there are more than 2 soldiers.
Say we have 2 sets of soldiers, A and B. We already set R=1, hence making angriness function for a day equal to number of equal generals.
Lets say F(A) = N_1,F(B)=N_2 and there are K generals common which get pissed off if soldiers from either set A or B are called.
LHS=F(A)+F(B) = N_1+N_2
Now the RHS = F(A \cup B) + F(A \cap B)
= (N_1+N_2K) + F(A \cap B)
Now, we know that F(A \cap B) can have an at most value of K, because in maximumcase, all soldiers which piss off common generals are all present in F(A \cap B). But in case any of the soldier is absent, then F(A \cap B) will be less than K. This forces RHS to be less than N_1+N_2.
Hence, proved.
A trick to conveniently represent what generals hate a soldier
Wondering what that mask thing is about in the top solutions? They chose a very well method to represent which generals are angry with a soldier! We will call this âmaskâ of soldier  a number which conveniently represents which generals hate that soldier.
Since number of generals are 16, we can take any datatype which has more than 16 bits, like int. Initialize the mask for all soldiers as 0. Now, write it out in binary form such that:
 The i'th bit of the mask is set iff the i'th general hates that soldier!
Why is it good? Because now you can use bitwise operators (AND, OR) etc. to do speedy checks. For example, the number of generals which get angry if to soldiers A and B are called is given by number of 1's in binary representation of A  B. Similarly A \& B gives us number of commongenerals pissed off by them.
Hence, this representation provides you with mechanisms to make your life, implementation easier and also save some of that time for more computation!
Setter's Notes

The relationship X is subordinate of Y is a POSET

Note that every day we chose an antichain in that POSET

The angriness function is submodular, that means that
f(A)+f(B) \geq f(A \cup B) + f(A \cap B), where f(X) is the number of angry generals if soldiers from set X are called 
The optimization problem is :
 minimise { \sum f(X)*R(X), for every antichain X}, R(X) is how much each soldier is paid
 subject to sum {R(X), for each antichain X containing x} = S_x, i.e soldier x should be paid Sx

For special kind of POSETS this optimization problem can be solved using the FaigleKern algorithm which involves
 finding a special topological sort of the tree
 solving a system of linear equations.
The problem is very technical, that is why I decided to use the challenge format.
However with the given test case generation (and definitely not the dark powers of Sauron bestowed upon me eons, eons ago), I expect many solutions that use approximate algorithms with nearoptimum scores.
Related Problems
 Red and Black Tree  Linear Programming.
 Chef and Digit Jumps  I wonât tell tag and spoil this problem for you
 SNSOCIAL  MultisourceBFS on Matrix, something you should definitely learn.
 Knight Moving  Gauss Elimination for Solving a System of Linear Equations
 Olya and Energy Drinks  01 BFS.