It is a kind request to @vijju123 to please upload the editorial of ARMY OF ME and some problems related to it. It’s very difficult to understand other coders solution…
Please upload asap
Thanks
2 Likes
Hi,
Due to my personal life issues some editorials are delayed. I will upload setters notes n status soon - but not possible immediately. Mail me if you urgently need, I will respond on priority.
2 Likes
Your email id please.
Since my (the official) solution is very different than that of the others, I’ll share it :
First we have to establish a few lemmas :
Lemma 1 : If two intersecting subarrays are good then their union is also good.
Lemma 2 : If two intersecting subarrays are good then their common subarray is also good.
Now let’s try to solve another problem : We are given queries of form (x, y) and we have to divide the subarray (x, y) into minimum number of consecutive good subarrays. For example if subarray (x, y) looks like (4, 3, 1, 8, 9, 7) then the answer would be 3 : (4, 3) (1) (8, 9, 7). To solve this problem we have to realize that we should take the biggest good subarray we can from the start of (x, y) and then solve the problem for the rest of it (some sort of greedy algorithm). The reason is deducted from the Lemmas introduced above. Knowing all this, we are left with this greedy problem. To solve it we have to define an array right_i : The maximum index where subarray [i, right_i] is good. Similarly define left_i. Now we can answer a query like this : while right_x <= y, we take subarray [x, right_x] and assign x = right_x + 1. This is correct since we should act greedy as described earlier. So now we have right_x > y. We can do the same thing from the end of the array, i.e while left_y >= x we take this subarray [left_y, y] and assign y = left_y - 1. Now if x > y then the problem is solved. Otherwise we know that left_y < x <= y < right_x. Considering lemma 2 we deduct that subarray [x, y] is actually also good so we can take the whole subarray as one piece. This solution solves the problem but it’s slow. We can speed it up via binary lifting; Instead of taking good subarrays one by one, we can take them in goups of 2^i resulting in O(log(N)) method.
Lemma 3 : The maximum good subsegment is among the subsegments in the partition. This follows from lemma 1.
We can keep track of the maximum subsegments in the binary lifting and so our original problem is solved in an online fashion in O((N + Q) \times log(N)) without the use of any persistent structure.
3 Likes
Just to add, google this: fast algorithms counting intersections of two permutations" and you’ll find a research paper on a generalization of this problem. Though its not very practical to implement it has some very good ideas which are of help here too
Hey a 7 star coder @tmwilliamlin is putting a lot of effort in making video editorials about how to solve the problems . Here is the link to the video editorial discuss page of Army of Me Problem. Do check it out. 
7 Likes
Could you please explain the binary lifting part… means how to calculate left[i] and right[i] efficiently??