PROBLEM LINK:Practice Setter: Teja Vardhan Reddy DIFFICULTY:Medium PREREQUISITES:Time complexity analysis, Set data structure and nontrivial implementation skills. Merge sort Tree or binary search and value compression. PROBLEM:Given two array $A$ and $B$, define similarity of two arrays as number of positions i such that $A[i] == B[i]$. Perform $Q$ range updates and print similarity of arrays after each update. Range update assign every element of $A$ in range $[L, R]$ to $C$. Queries are online. i.e. we have to answer queries in same order as input. SUPER QUICK EXPLANATION:
EXPLANATION:This problem has a relatively simple solution if comparing with usual second hardest problem, but proving that the solution runs with time is not trivial, earning this problem spot of second hardest problem. Time complexity of solution will be analysed at the end, so please have patience, when i make any assumption. :P So, Solution for first subtask is simple, perform updates naively, and calculate similarity every time, giving $O(N^2)$ time complexity, too slow to pass final sub task. First of all, Notice a fact that suppose we have similarity already calculated before ith query $[L,R]$. We can see, that similar positions change only in range of update, since at all other positions, both arrays remain unchanged. This way, If we can calculate the change in similarity cause due to current update within update range, we can calculate answer. Let us represent the array A in a different format. Create tuple of type $(l,r,c)$ representing that elements of $A$ in range $[l, r]$ have value $c$, and store it in a set, ordered by left end of range (right end will also work, with changes in implementation. Now, From this point, dont worry about complexity till i mention myself. :D Talking about updates first, Perform update in manner, suppose update range is $[L, R]$. Give a thought about how will $A$ look like after update. Some ranges which coincide with update range, would be modified, and ranges lying completely inside update range would be deleted and one new range would be inserted. Got this much? Right. If not, reread because next paragraph won't make sense without this. Now, updating answer. Suppose before update, we had $x$ positions in update range which were similar to array $B$. Current answer gets reduced by $x$. Also suppose, that after update, $y$ positions in update range are similar. Answer increases by $y$. So, After every update, Answer becomes $Ansx+y$. Let's calculate $y$ first. We know, after update, all elements in update range in array $A$ will be $c$. So, $y$ is same as Number of positions in array $B$ within update range, which have value $c$. This problem is well known, and can be solved using binary search, Merge sort tree (though slower). This problem will be explained soon. Suppose we are using Merge sort tree. So, now that we have calculated $y$, all that remains is to calculate $x$. Let us represent $x$ as a summation in terms of ranges completely and partially covered in range. For every range $(l,r,c)$ completely inside update range, we know all elements in range have value $c$. So, we query to Merge sort Tree, to tell us number of positions in range $(l,r)$ in array $B$ having value $c$. This is same as problem above. But we need to handle boundary ranges carefully, make new range for each border. Suppose we have array $A$ initially 1 1 2 1 2. So, its represent is set ${(0,1,1),(2,2,2), (3,3,1), (4,4,2)}$. (zerobased indexing). Say update is [1,3] to 4 We Final array after update should look like ${(0,0,1), (1,3,4), (4,4,2)}$. Another case to be handled carefully is when a range fully covers the update range itself. This all is implementation stuff, so, will depend more on how you handle cases. Refer setter solution for implementation. But, we still need to solve subproblem, Given a permanent array, count number of elements in range l to r, with value $c$. It can be solved using two methods, one faster, other slower but simpler. Binary search and Merge sort tree. Binary search idea involve compressing the values in array first, make a sorted vector corresponding to each value in array which stores every position of value in $B$, and for every query $(l,r,c)$, if there doesn't exist vector for value $c$, there isn't any position in $B$ which have $c$ as value. Otherwise we can see that number of elements in range l to r is same as number of values in range from start to r less number of elements in range start to l1. This can be easily done using binary search, and gives $O(logN)$ (or even faster, exactly, O(log(no of elements in vector)). Using merge sort tree, we maintain a map on every segment (total $N*logN$ maps it become). It is very simple to query, just like segment tree, as explained here and here too. So, we have solved the problem. Implementation is messy, but worth a try. I know you all are shouting at me saying that this solution would be inefficient, rest assured, this time i have a proof to proudly claim that this is efficient enough, let's discuss it. TIME COMPLEXITY ANALYSIS:First of all, set, at any point, cannot have more than $N$ ranges. That happens when no two consecutive values are same. Second thing, Let us find maximum number of insertions possible. We see, that we can alter at most three ranges, (one for l to r), and two boundary conditions. This way, We can insert at max 3 ranges, resulting in maximum $N+3*Q$ insertions, which is linear in respect of $N+Q$. Finally, Total number of deletions can never be more than initial ranges plus inserted ranges, thus deletions also are of linear complexity. Every insertion and deletion takes only $O(LogN)$ time (binary search on $B$), so, this solution has overall complexity $O((N+Q)*logN)$. Preprocessing on $B$ takes $O(NlogN)$ time only, and thus, is dominated by queries. AUTHOR'S AND TESTER'S SOLUTIONS:Setter's solution Until above links are not working, feel free to refer solution here. EDIT: Found an interesting problem here. Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)
This question is marked "community wiki".
asked 01 Oct '18, 00:27

You can solve it with SQRT Decomp  https://www.codechef.com/viewsolution/20416795 answered 01 Oct '18, 08:20
Yes, there were many square root dec submissions which passed.
(01 Oct '18, 12:34)
@inseder Can you explain your SQRT Decomp Solution ?
(01 Oct '18, 23:23)
1
@tihorsharma123 here you go:
(04 Oct '18, 04:58)

I too have used segment tree with lazy propagation and binary search(in a sorted array of pairs of (B[i],i)) for similarity. The complexity is O(N(log N)^2). Algorithm:Maintain Segment Tree for similarity. In each query:
My code passes all given tests except one. I have used random tests but could not find any test in which it fails. Could someone find the bug in code or flaw in the algorithm or a test in which it fails. Link to Code Thanks answered 02 Oct '18, 04:27
I have used Segment tree and Lazy Propagation approach but I am getting TLE. Can u please tell me what improvement can be done as it is also having same time complexity. I think clearing the map everytime is resulting in TLE, How can I improve that?
(01 Oct '18, 13:25)
@siddhant22 bro i am also facing same problem with similar kind of logic.. in one case getting Runtime error.. ur issue resolved?
(02 Oct '18, 15:06)
Not Yet... Got a very different result after resubmission(https://www.codechef.com/viewsolution/20436261) with minor changes. The one test that was not passed earlier is passed now but other cases now have Wrong answer. So, it seems like my code has some undefined behaviour(maybe something like segmentation fault that is not detected). Also, another resubmission(https://www.codechef.com/viewsolution/20436365) with additional conditions 'and'ed in assert converts the SIGABRT in my original submission to a WA which is also weird.
(03 Oct '18, 01:07)
@boost_insane : 1)both build and update are recursive. You can try making it with loops instead for saving function call overhead. 2)(minor effect) change line 80 to: tree[right] = tree[pos]  tree[left];
(03 Oct '18, 06:35)
@siddhant22 There is surely some problem with the input file of this problem changing the input format is resulting in different outputs, If you get the answer correct do comment your correct solution link.
(03 Oct '18, 13:06)
@siddhant22 @boost_insane i think issue resolved now.. my same solution now got AC .. try to resubmit your solutions
(08 Oct '18, 06:04)
showing 5 of 6
show all

I know it would be an overkill, but I was wondering if this problem could be solved using Segment Tree and Lazy Propagation ? I haven't coded it yet, I just want to know if its a valid approach or not ? answered 01 Oct '18, 11:47
Can you explain your approach a bit more?
(01 Oct '18, 12:33)
Here's my solution with seg tree + lazy propagation  https://www.codechef.com/viewsolution/20402757
(03 Oct '18, 17:52)

@taran_1407 could you plz tell the fault in my logic? or , can anyone plz tell why i am getting TLE ??? I'm using segment tree with lazy updates and Binary Search to look for similarities !! Thanks in advance !! answered 01 Oct '18, 19:01

I'm having some trouble in calculating x. I can't seem to understand how to calculate the value of x in less than O(N). Link to my code: Code I have commented the portion (in the main function) where I'm having a problem with "TODO: " Can someone please help me out with this? Thank you. answered 02 Oct '18, 01:01

why is tester's solution getting runtime error?? answered 02 Oct '18, 11:35

The above solution have same code. but Their submission time is different. Until Yesterday the solution which was giving 100 pts is now Showing Runtime Error for one subtask. @admin @taran_1407 @teja349. Please look into this matter. Same Code gives two different out comes how???? Testers Solution it gives Runtime Error Setters Solution it gives TLE answered 02 Oct '18, 15:02
As i know, admin is looking into this matter as this was already reported.
(02 Oct '18, 17:59)
@huzaifa242 bro same problem i am facing...same solution submitted in giving diff time giving differt output behaviour with runtime errro... different different attemp with exact same line of code giving different output
(02 Oct '18, 20:19)

answered 04 Oct '18, 09:59
