Hackerearth May Circuits — Tom and Jerry Love matrices

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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

#include <iostream>
#include <bits/stdc++.h>
using namespace std; 

#define MAX     1000
#define pb       push_back
#define ppb      pop_back
#define FOR(i,s,e)      for(int i=s; i<=e; i++) 
#define RFOR(i,s,e)     for(int i=e; i>=s; i--)
#define lli     long long int
#define mod       1000000007
#define ppc     __builtin_popcount
#define ppcll     __builtin_popcountll
#define gs      getline(cin, s);
#define c_yes   std::cout << "YES" << std::endl;
#define c_no   std::cout << "NO" << std::endl;
#define ALL(x)      x.begin() , x.end()
typedef   pair<int, int> pi;
typedef   std::vector<int> vi;
typedef   std::vector<vector<int>> vvi;
typedef   std::vector<lli> vlli;
typedef   std::vector<char> vc;
typedef   std::vector<string> vs;
typedef   std::vector<pi> vpi;
typedef   priority_queue<int> max_heap_int;
typedef   priority_queue<string> max_heap_string;
typedef   priority_queue<int, vi, greater<int>> min_heap_int;


// class Timer { private: chrono::time_point <chrono::steady_clock> Begin, End; public: Timer () : Begin(), End ()
// { Begin = chrono::steady_clock::now(); } ~Timer () { End = chrono::steady_clock::now();
// cout << "\nDuration: " << ((chrono::duration <double>)(End - Begin)).count() << "s\n"; } } t;

lli row , col , x, q;
vector<pair<lli , lli>> deleted;

lli getCount(lli n) {
    lli c = min(col , n-1);
    return c*(c+1)/2;
}

//If the number is in the range that has been deleted then decrease the count of this number
lli getDeletedCount(lli val) {
    
    lli cnt = 0;
    for(auto &k : deleted) {
        if(k.first > val) continue;
        else if(val >= k.second) cnt += k.second - k.first + 1;
        else if(val >= k.first and val < k.second)  cnt += val - k.first + 1;
    }
    return cnt;
}

lli query(lli k) {
    lli low = 2 , high = row+col , sumOfTwoNumbers = row + col + 2 , middle = (low+high) >> 1 ;
    
    bool even = false;
    if((row+col) % 2) even = false;
    else even = true;
    
    while(low <= high) {
        lli mid = (low+high) >> 1;
        lli currentCount;
        
        if(mid <= middle) 
            currentCount = getCount(mid);
        else 
        {
            if(!even)
                currentCount = 2 * getCount(middle) - getCount(sumOfTwoNumbers - mid - 1);
            else 
                currentCount = 2 * getCount(middle-1) - getCount(sumOfTwoNumbers - mid - 1) + min(middle-1 , col);
        }
        
        currentCount -= getDeletedCount(mid);
        
        if(currentCount == k ) return mid;
        else if(k < currentCount) high = mid-1;
        else low = mid+1;
    }
    
    return low;
}
void solve(){  
    
    
    cin >> row >> col >> x >> q;
    
    while(q--) {
        int type;
        lli a , b , c;
        cin >> type;
        
        if(type == 1 || type == 2) {      //type 1 | 2 queries
            cin >> a >> b >> c;
            deleted.pb({a+b , a+c});
        }
        else {                  //type 3 queries
            cin >> a;
            
            lli qa ;
            qa = query(a);
            
            // Answer can not be greater than N+M
            if(qa > (row + col)) {
                cout << "-1\n";
            }
            else 
                cout<< qa + x << "\n";  
        }
    }
    
} 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    solve();
	
	return 0;
}

nikhil_vaibhav_17's blog