MATCH2 - EDITORIAL

editorial
, , , , , , ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

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

DIFFICULTY:

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. :stuck_out_tongue:

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. :smiley:

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:

Setter’s solution
Tester’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. :slight_smile:

4 Likes
2

You can solve it with SQRT Decomp - CodeChef: Practical coding for everyone
Time complexity is greater N + Q * sqrt(N)
Also you can play with the size of the decomposition to obtain better times.

1 Like
3

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 ?

1 Like
4

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

5

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 !!

6

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:


[1]

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


  [1]: https://ide.codingblocks.com/#/s/29672
7

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

1 Like
8

why is tester’s solution getting runtime error??

9

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

10

Can this problem be done in O(N^2) time?

11

Similar code getting different verdict, can someone help me out?

Code1

Code2

12

Can you explain your approach a bit more?

13

Yes, there were many square root dec submissions which passed.

14

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?

Solution Link

15

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.

16

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 …)

17

We use coordinate compression on array B.

18

@inseder Can you explain your SQRT Decomp Solution ?

19

@siddhant22 bro i am also facing same problem with similar kind of logic… in one case getting Runtime error… ur issue resolved?

20

As i know, admin is looking into this matter as this was already reported.