Hackerearth May Circuits — Tom and Jerry Love matrices

Revision en2, by nikhil_vaibhav_17, 2021-05-23 12:45:05

Here I want to share my approach towards the problem of May Circuits — Tom and Jerry Love Matrices. Also also I want to ask for help to optimize this.

Worst Case Complexity : O(QLogN)

This gave me TLE in 3 test files but passed all other test files.

Approach : Binary Search

Each cell in matrix has value i+j+X . Since X is common to all we can add this value at the end.

Now there are values in range 2 to N+M and each value has a certain frequency. If you observe carefully , each number num in the range 2 to (N+M)/2 + 1 has frequency equal to min(num-1 , no_of_columns). After that the frequency of remaining numbers can be calculated using the frequency of already calculated numbers. You can observe that in a range of continuous numbers, if we use two pointer like approach , the sum of numbers in the start and end is same.

Eg: [ 2,3,4,5,6,7 ] the sum of 2+7 = 3+6 = 4+5. So we can use this to calculate frequency of numbers in second half.

While making delete range queries , you don't have to actually delete the range but just keep the track of values to be deleted. For eg: if a delete query is delete column 2 to 6 in a row 4 , then value range to be deleted is (4+2) to (4+6).

While searching for a value we can simply perform binary search in the range from 2 to (N+M).

Worst Case When there are all print operations in the queries.

Any help regarding optimizing this is welcome.

Note: It may be a little bit difficult to understand code.

Code

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English nikhil_vaibhav_17 2021-05-23 12:45:05 16
en1 English nikhil_vaibhav_17 2021-05-23 12:44:18 5134 Initial revision (published)