### nikhil_vaibhav_17's blog

By nikhil_vaibhav_17, history, 2 years ago,

I need help understanding where I am going wrong with this solution. Possibly I am doing wrong with modular operations.

This is the problem of recent Codeforces Round #778 , Problem D — Potion Brewing Class

1654D - Урок зельеварения

My piece of code
By nikhil_vaibhav_17, history, 3 years ago,

Hello Everyone,

I have been stuck at a question for quite some time. I came up with an approach but that's not working for me. Maybe the idea can be correct and implementation can be wrong. So I need some help with an approach. I will add necessary piece of code for showing my approach.

The question is exactly the same and has no typing errors.

Question
My Approach
Main computation part

I just want to know what can be a good approach for this and I will try to implement this on my own.

By nikhil_vaibhav_17, history, 3 years ago,

Hello Everyone,

I am currently learning about sparse table. So after learning basics , I tried to implement it on my own. I thought that it should but I am not able to figure out why it is not working.

So I built table sparse[N][26] , sparse[i][j] gives minimum of the range (i , i + pow(2,j) — 1). Now the problem is :

For a given query range [L , R] , the length of range is R — L + 1. We can represent it as a sum of powers of two so I run a loop for iterating bits and if a bit is set , I made a jump of length pow(2,j) from L. It did not worked for all test cases.

Then I learnt about idempotency and then solved the problem using it. But I want to know why the previous approach is not working.

Precomputation code
QueryCode

By nikhil_vaibhav_17, history, 3 years ago,

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