PROBLEM LINK:
Setter- Arjun Arul _/\_
Tester- Multiple
Editorialist- Abhishek Pandey
DIFFICULTY:
MEDIUM
PRE-REQUISITES:
Greedy, DFS, Data Structures (like vectors).
PROBLEM:
Some employees of ICPC (i.e. Intensely Corrupt Private Company) avail services of Hawala Trader. Given that Hawala Traders follow “close knit” relationship while serving client, what is the minimum number of arrests you have to make to bring down all Hawala Traders? Arresting 1 employee brings down all Hawala Traders whose services he avails.
QUICK EXPLANATION:
Its not hard to deduce that the question is hinting at a greedy approach. Indeed, we see that, starting from leaves, its better to greedily arrest the parent node among nodes served by a Hawala Trader. However, this question is a test of your implementation and analyzing skills, and patience along with carefulness is required to solve this question without penalties.
EXPLANATION:
The correct thinking direction + Why is Close-Knit relation relevant-
What are your first thoughts on reading the question?
A good portion of people might get confused that “What is actually the significance of close knit relation? What is the relevance of this tree? Can I not find intersection of set as in, without given tree and close knit relations?”
Well, finding minimum number of sets to union so that they contain each element is a NP- complete as described here. This means, that the key to solve this question is somewhere hidden in this close-knit relation, which the setter has emphasized a lot.
Indeed, the key to solve this question is analyzing what the close knit relation means. Lets see how-
Deducing greedy from Close-Knit Relation-
Lets say we have a Node A which has multiple children. Now, if a Hawala Trader is serving one of its children, then its serving the immediate parent, i.e. Node A as well. What if there are multiple children being served by different Hawala Traders? Yes, they all will be serving the immediate parent, i.e Node A as well!!
Now, we have to minimize arrests. I think its pretty obvious by now, that its better to arrest Node A, (which is being commonly served by all Hawala Traders serving his children) than to arrest each of Node A's child individually.
Mathematically speaking, the close knit relation guarantees that if a node is being served, then its immediate parent (say Node A) is being served as well. By above examples, we saw that this means a parent can be served by multiple Hawala traders, and is equivalent to “Common element occuring in the given sets (i.e. Common client served by these Hawala Traders)”
You see that we can make a neat observation from this.
Observation 1- For a particular Hawala Trader, its always better to arrest the parent node he is serving.
However, this doesn’t mean that you just randomly traverse the tree and arrest all the parents you see! Its just equivalent to randomly arresting nodes hoping to minimize arrests, except that we have reduced the number of candidates to be considered.
So, how do we go about it? How to use greedy properly ?
Strategy to be used while applying Greedy-
I will illustrate one example. Lets say we have three Nodes A,B,C such that A is parent of B, and Node B is parent of C.
Lets say 1 Hawala Trader is serving Node A (and thus Node B as well due to close-knit relation), and another is serving Node C and hence B.
If we start from top of tree, then our algorithm goes as follow-
Note- Parent w.r.t. Trader = Parent among all nodes served by that Trader.
Start at Node A.
Node A is parent w.r.t Trader serving Node A and Node B. Hence, Arrest A.
Arrive at Node B.
Node B is parent w.r.t. Trader serving Node B and Node C. Hence Arrest B.
Total Arrest =2.
But in this case, one can intuitively see that a single arrest is enough. What if we start from the leaf, i.e. Node C ?
Start at Node C.
Node C is child w.r.t Trader serving Node B and C. Hence, Dont arrest.
Arrive at Node B.
Node B is Parent w.r.t Trader serving Node B and C. Hence, arrest B. Note that the Trader
serving Node A and Node B also gets taken down because we arrested Node B.
Arrive at Node A.
The trader serving him is already taken down. No need of any arrest.
Total Arrests=1.
We make another crucial observation.
Observation 2- Its always better to start from leaves and arrest parent nodes w.r.t. a Hawala Trader, because chances are this will let us skip arresting the grandparent node!
See this image for details-
Final step towards AC-
Code it and Submit it 
What? Dont look at me like that! Thats pretty much it about the logic part and explanation.
Speaking seriously, recall that I said that this question is a test of your implementation and analyzing skills, rather than logical thinking. There is a good (over 80%) chance that despite reading this editorial, understanding the logic, you will get WA and/or TLE. And thats not because of “insufficient explanation” or because anythings wrong with the editorial. The reason for those WAs and TLEs will be that you think you did exactly what the editorial said, but actually on some analysis you will see that what you coded/implemented is not what the editorial says, and will yourself say that “Damn its wrong!!”
I will not include it in “official” part of Editorial as their thorough analysis will make it verbose and boring to people who already solved it. Those parts are included in Chef Vijju’s Corner (since its optional and hence “unofficial” part of editorial) for whosoever is facing problem.
Please give an attempt to the problem before reading Chef Vijju’s corner or the Editorialist’s Solution, so that you appreciate and hence learn to the fullest what I have to offer!!
One Precaution to take-
Note that for this problem, constraints are QUITE big. Hardware level optimizations make a difference. Please optimize your code as much as you can!!
Editorialist’s Solution:
Iterative Solution
Recursive Solution
TimeComplexity=O(Nlog_2N)
CHEF VIJJU’S CORNER
1.Before giving out details of WA and TLE, let me give out one practice problem for interested people who bothered to read the first line here :D. Hawala Arrest gave you a flavour of greedy+trees. What can be better? DP+ TREES YEAH!!. TWOCOINS is an excellent problem by the same setter, and you will thoroughly enjoy it, even though getting AC in this can be a pain.
2.Discussing various tricky points of implementation for various verdicts-
WA:
The most common mistake people do is not appreciating what I said in observation 1. You should see that, I had been very specific about something there. Let me re-quote observation 1-
Observation 1- For a particular Hawala Trader, its always better to arrest the parent node he is serving.
Does it ring a bell? What I presume most people must have done is-
if Node A is parent w.r.t Trader i.
Check ALL the traders serving him, if any is not taken down, arrest A.
If A is arrested, take down ALL hawala Traders associated with A.
This algorithm is wrong, and not what I mentioned in Editorial. Why?
Instead of spoon-feeding everything to you guys, I want to make your intuition realize it yourself, so bear with me for a few lines, things will be really clear soon.
The first step for finding why a particular algorithm is wrong, is to see a similar correct algorithm and compare the two. The correct algorithm for arresting traders is-
if Node A is parent w.r.t Trader i.
Check ONLY the traders w.r.t. which Node A is parent, if any is not taken down, arrest A.
If A is arrested, take down ALL hawala Traders associated with A.
Why is that so that second algorithm is correct while first is incorrect? We are ,in fact, checking fewer traders in second algorithm, how is that minimizing arrests? I will make it clear with a neat picture.
I have been very specific in saying that Arrest a Node only if its a parent w.r.t to the trader (who obviously isnt arrested yet).
If you are still getting WA, then probably there is something else wrong as well. You should try asking at discuss or here at editorial. (Please give only code link)
TLE:
MANY, MANY ,MANY things can cause you TLE despite correct algorithm
- The input is HUGE. PLEASE use Fast I/O methods. For reference, using simple
cinin C++ to read input gave TLE in codeforces contest for N={10}^{6} and Time Limit of 2seconds. For JAVA, DONT USE SCANNER for input, its really slow. Google some Fast I/O template and use it. - The data on which we have to operate is huge as well. Try to optimize your code on hardware level as much as you can. The Time limit of 5 seconds seems lenient, but remember that time taken increases exponentially. Possibly your unoptimized code is taking somewhere ~5-6~ seconds to execute and getting TLE. Optimize where ever possible.
Besides above 2 points, a very common implementation error led to TLE as well. Note that I said to optimize code where ever possible.
An implementation which gets TLE is-
For (every Trader from 1 to K)
if Node A is parent w.r.t. trader i- Add him to list Check_Node (it is a list of Nodes to be checked.)
else Dont add.
For (All Nodes in the list)
Check them as described in second algorithm in above section (Section for WA)
Why does this get TLE? Think in terms of number of operation.
Lets say a Node A has {10}^{4} children (A lot of children I must say). Assume each child is being served by 1 Hawala Trader. This makes it that, Node A is being served by {10}^{4} Hawala Traders.
For each of these traders, the above algorithm will add Node A to check list, meaning, Node A is being added to check list {10}^{4} times. Obviously,checking Node A once is enough. Note that for checking, the correct algorithm (which I mentioned in above section labelled “WA”) will check all the Traders for which Node A is parent (in this case, Node A is parent of all {10}^{4} nodes.)
This means that for Node A we will check each of its {10}^{4} traders. Node A will get checked {10}^{4} times. So total operations are {10}^{8} , for a single node. Since N,K\le{10}^{6}, we can have 100 nodes similar to Node A. So this increases total operations from {10}^{8} to {10}^{10} . Hence, TLE.
3.Thats all folks, this time :D. After doing this question, you will see how the setter cleverly invented a logic-wise simple question, but so cunning and tricky in implementation! @arjunarul is one of my favorite problem setters because of this, his questions are bound to push you to your maximum limit. Very few problem setters have this skill. Kudos to him
(PS: In case you dont believe-
.png)
_FZheUK7.png)