×

MATCH2 - EDITORIAL

Setter: Teja Vardhan Reddy
Tester: Hasan
Editorialist: Taranpreet Singh

Medium

PREREQUISITES:

Time complexity analysis, Set data structure and non-trivial 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:

• Represent ranges of consecutive positions having same values and store them in a balanced binary search tree. Calculate initial similarity naively, and for every update, update the intervals for new values, updating similarity simultaneously.
• Utilize the fact that $B$ doesn't change, preprocess to answer queries of type - count Number of positions in range $[L,R]$ such that $B[i] == C$.
• This solution works fast enough, as proved in Time complexity analysis part at the end.

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 sub-task 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, re-read 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 $Ans-x+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)}$. (zero-based 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 sub-problem, 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 l-1. 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:

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".

3.9k2387
accept rate: 22%

 1 You can solve it with SQRT Decomp - https://www.codechef.com/viewsolution/20416795 Time complexity is greater N + Q * sqrt(N) Also you can play with the size of the decomposition to obtain better times. answered 01 Oct '18, 08:20 6★inseder 350●4●8●19 accept rate: 0% 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: 1) split array in sqrt(N) blocks (smaller A and B) 2) for a block compute the sim of A and B & the map of frequencies for B 3) updates can affect 3 types of areas 3.1) a part of the block containing left 3.2) some full blocks 3.3) a part of the block containing right 4) for partial block queries just update A and in the same time compute sim 5) for full block just mark that block of having only value C and compute the new sim as being the count of C in the B of the block 6) partial update on a block having only C -> need to fill the A array (04 Oct '18, 04:58) inseder6★

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:

1. Propagate changes in the path from root to L and root to R away from root.O((log N)^2)
2. Calculate similarity in the sections between L and R. O((log N)^2)
3. Propagate changes that we just made towards root. O((log N))

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

121
accept rate: 0%

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
 0 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 218●9 accept rate: 9% 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) chinmay25★
 0 By sqrt decomposition ,how to handle updates for calculating x in similarity = similarity - x + y where x is the similarity of l to r range answered 01 Oct '18, 16:22 11●2 accept rate: 0% say we have similarity for a block calculated (for initial position, we can manually calculate). After update, two border blocks can be updated naively and middle blocks all will have same value, so, we can calculate for each block range using binary search or Merge sort tree as explained above. (01 Oct '18, 16:33) actually i am asking do we have to store array A in (range,value) manner always or we can handle updates in any other way ...(thanx ...) (01 Oct '18, 16:45) We use coordinate compression on array B. (01 Oct '18, 16:56) i used the full array but with some sort of lazy propagation(do not actually fill it until you get a partial query on that block) (04 Oct '18, 05:04) inseder6★
 0 link to my submission @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 1●1 accept rate: 0%
 0 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 1●1 accept rate: 0%
 0 why is tester's solution getting runtime error?? answered 02 Oct '18, 11:35 46●4 accept rate: 25%
 0 My Solution My Same Solution 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 32●3 accept rate: 0% 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)
 0 Can this problem be done in O(N^2) time? answered 03 Oct '18, 15:17 1 accept rate: 0%
 0 Similar code getting different verdict, can someone help me out? Code1 Code2 answered 04 Oct '18, 09:59 96●6 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,559
×1,391
×1,024
×817
×647
×145
×45
×4

question asked: 01 Oct '18, 00:27

question was seen: 1,339 times

last updated: 08 Oct '18, 06:05