You are given a sorted two-dimensional integer array arr of size r * c, where all the numbers are in non-decreasing order from left to right and top to bottom. I.e. arr[i][j] Show Check if a given number x exists in arr or not. Given an arr, you have to answer q such queries. Example OneInput: arr = [[1, 2, 3, 12], [4, 5, 6, 45], [7, 8, 9, 78]], queries = [6, 7, 23] Output: [“present”, “present”, “not present”] Given number x=6 is present at arr[1][2] and x=7 is present at arr[2][0]. Hence, "present" returned for them, while x=23 is not present in arr, hence "not present" returned Example TwoInput: arr = [[3, 4], [5, 10]], queries = [12, 32] Output: [“not present”, “not present”] Given number x=12 and x=32 are not present in arr. Hence, "not present" returned for both of the queries. NotesInput Parameters: There are two arguments, arr and x, denoting input 2D array and a number to be searched as mentioned in problem statement respectively Output: Return string "present" if x is present in arr, string "not present" otherwise. Constraints:• 1 • 1 • 1 • -10^9 • -10^9 SolutionWe provided three solutions. 1) brute_force_solution.javaA naive approach would be to iterate over the entire input array arr to check if x is present or not. Time Complexity:O(r*c*q) where r denotes number of rows of arr, c denotes number of columns of arr and q denotes number of queries. As we are iterating over entire array for each query, time complexity will be O(r*c) (for each query) and as there are q queries so total time complexity will be O(r*c*q). Auxiliary Space Used:O(1). As we are not storing anything extra. Space Complexity:O(r*c) where r denotes number of rows of arr and c denotes number of columns of arr. To store input, it would take O(r*c), auxiliary space used is O(1). So, total space complexity will be O(r*c). 2) optimal_solution.java1) Start with top right element arr[0][c-1] 2) Loop: compare this element arr[i][j] with x -> If arr[i][j] == x, then return "present" -> If arr[i][j] < x then move to next row (i.e. arr[i+1][j]) -> If arr[i][j] > x then move to column to its left (i.e. arr[i][j-1]) 3) repeat the steps in #2 till you find element and return "present" OR if out of bound of matrix then break and return "not present" Let say x is not present in the first i-1 rows. Let's say in i-th row, arr[i][j] is the largest number smaller than or equal to x. -> If it is equal to x, then problem solved, directly return “present”. -> If arr[i][j] < x, it can be implied that x cannot be present at arr[l][m], i < l and j < m as array is row wise and column wise sorted (ascending). So, moving on to the next row, i+1-th row, we can start checking from j-th column (i.e. arr[i+1][j]). -> If arr[i][j] > x, means element x can be present in the left side of column jth as row and column are sorted in ascending order. So, we start checking it with arr[i][j-1]. Time Complexity:O((r+c)*q) where r denotes number of rows of arr, c denotes number of columns of arr and q denotes number of queries. As for each query maximum iteration over array can be of O(r+c) and as there can be q queries so, total complexity will be O((r+c)*q). Auxiliary Space Used:O(1). As we are not storing anything extra. Space Complexity:O(r*c) where r denotes number of rows of arr and c denotes number of columns of arr. To store input, it would take O(r*c), auxiliary space used is O(1). So, total space complexity will be O(r*c).
Given an array, "A" of integers and you have also defined the new array"B"as a concatenation of array"A" for an infinite number of times. For example,if the given array"A"is[1,2,3]then,infinite array“B”is[1,2,3,1,2,3,1,2,3 ........ Now you are given q queries, each query consists of two integers"L" and"R"(1-based indexing). Your task is to find the sum of the subarray from index"L" to"R"(both inclusive)in the infinite array "B" for each query. Note: The value of the sum can be very large,return the answer as modulus 10^9+7.Input Format The first line of input contains a single integer T, representing the number of test cases or queries to be run. Then the test cases follow. The first line of each test case contains a single integer N, denoting the size of the array"A". The second line of each test case contains N single space-separated integers, elements of the array"A". The third line of each test case contains a single integer Q, denoting the number of queries. Then each of the Q lines of each test case contains two single space-separated integers L, and R denote the left and the right index of the infinite array"B" whose sum is to be returned.I have come up with an approach that doesn't think is the optimal solution for this. I have used two pointer approach in this. #include <iostream> #include <vector> vector<int> sumInRanges(vector<int> &arr, int n, vector<vector<long long>> &queries, int q) { // Write your code here vector<int> res; for(int i = 0; i < q; i++){ int sum = 0; int start = queries[i][0]; int end = queries[i][1]; while( start <= end ){ if(start < arr.size()){ sum += arr[start - 1]; } else{ int mod = start % arr.size(); sum += arr[mod - 1]; } } res.push_back(sum); } return res; }
So I gave the on-campus Google hiring test yesterday and when I saw the 2 problems I had to solve in an hour, I was really excited since they looked doable. However, things took a turn when I actually started to think about optimizations. Anyways, here goes : We have an array A of N elements. We will be asked Q queries. each query is in the form of a single integer, X, and we have to tell whether there exists an index i in the array such that the bitwise AND of A[i] and X equals 0. If such an index exists print YES, otherwise print NO. Constraints : 1<=N<=1e5, 1<=Q<=1e5, 1<=A[i]<=1e5 We have a binary string S of length N, and we have to find the number of substrings(that is, a contiguous range i to j) in which the frequency of 1 is strictly greater than the frequency of 0. Constraints : 1<=N<=1e6; I have spent a lot of time on them but could not come up with an optimal approach for either. I realize that the 2nd problem can be solved in O(NlogN) in a similar fashion in which we solve LIS in NlogN time, But other than that, I am clueless about both problems. Any help will be appreciated, Thanks!
Mo’s algorithm is a generic idea. It applies to the following class of problems:
For the sake of brevity we will denote Func([L, R]) as the value of Func on subarray Arr[L..R].
Here we have Func([L, R]) = Arr[L] + Arr[L + 1] + ... + Arr[R]. Mo’s algorithm provides a way to answer all queries in O((N + Q) * sqrt(N) * F) time with at least O(Q) additional memory. Meaning of F is explained below. The algorithm is applicable if all following conditions are met:
Due to constraints on array immutability and queries being known, Mo’s algorithm is inapplicable most of the time. Thus, knowing the method can help you on rare occasions. But. Due to property #3, the algorithm can solve problems that are unsolvable otherwise. If the problem was meant to be solved using Mo’s algorithm, then you can be 90% sure that it can not be accepted without knowing it. Since the approach is not well-known, in situations where technique is appropriate, you will easily overcome majority of competitors. Basic overviewWe have Q queries to answer. Suppose we answer them in order they are asked in the following manner: for i = 0..Q-1: L, R = query #i for j = L..R: do some work to compute Func([L, R])This can take Ω(N * Q) time. If N and Q are of order 105, then this would lead to time limit exceeded. But what if we answer queries in different order? Can we do better then? Definition #1: Notation
We will describe Mo’s algorithm, and then prove its running time. The approach works as follows:
Time complexityLet’s view Arr as a union of disjoint segments of size BLOCK_SIZE, which we will call “blocks”. Take a look at the picture for better understanding:  Let K be the index of last block. Then there are K + 1 blocks, because we number them from zero. Notice than K’th block can have less than BLOCK_SIZE elements. Proposition #1: K = O(sqrt(N)). Proof: If sqrt(N) * sqrt(N) = N (which may be false due to our definition of sqrt(N)), then K = sqrt(N) - 1, because we have K + 1 blocks, each of size sqrt(N). Otherwise, K = sqrt(N), because we need one additional block to store N - sqrt(N) * sqrt(N) elements.UPD 19 june 2017: As pointed out in the comments, this does not hold for small values of N. Alternative proof (less intuitive, more formal): we need the smallest K such that K * sqrt(N) ≥ N - when this is true, our space is sufficient to hold all N elements. If we divide by sqrt(N), we get K ≥ N / sqrt(N). sqrt(N) is either real_sqrt(N) (the one without truncating value after decimal point) or real_sqrt(N) - 1. So K ≥ N / (real_sqrt(N) - 1). So, K = N / (real_sqrt(N) - 1) + 1 suffices. Let's look at the difference between this value and real_sqrt(N). Denote this difference as x: N / (real_sqrt(N) - 1) + 1 - real_sqrt(N) ≥ x. Put everything under common denominator: (N + real_sqrt(N) - 1 - N + real_sqrt(N)) / (real_sqrt(N) - 1) ≥ x. This means that (2 * real_sqrt(N) - 1) / (real_sqrt(N) - 1) ≥ x. As N approaches infinity, the bound on the right approaches 2. So, for very large N, x ≤ 2. Otherwise, it is bounded by a constant (you can find it, for example, by taking the first 1000 values of N and taking maximum value of the bound). So K - real_sqrt(N) ≤ constant, which implies K = O(sqrt(N)). Proposition #2: Block #r is a segment [r * BLOCK_SIZE, min(N - 1, (r + 1) * BLOCK_SIZE - 1)]. Proof (by induction): For block #0 statement is true — it is a segment [0, BLOCK_SIZE - 1], containing BLOCK_SIZE elements. Suppose first T ≤ K blocks satisfy the above statement. Then the last of those blocks is a segment [(T - 1) * BLOCK_SIZE, T * BLOCK_SIZE - 1].Then we form the next, T+1’th block. First element of this block will have array index T * BLOCK_SIZE. We have at most BLOCK_SIZE elements to add to block (there may be less if T + 1 = K + 1). So the last index in T+1’th block will be min(N - 1, (T + 1) * BLOCK_SIZE - 1). Corollary #1: Two indices i and j belong to same block #r if and only if i⁄BLOCK_SIZE = j⁄BLOCK_SIZE = r. Definition #2: Proposition #3: Corollary #2: When we are processing queries following Mo’s order, we firstly process all queries from Q0, then all queries from Q1, and so on, up to QK. Theorem #1:Mo_right changes its value O(N * sqrt(N)) times throughout the run of Mo’s algorithm.
There are no more cases when mo_right changes. Overall, we have O(N * sqrt(N)) + O(N * sqrt(N)) = O(N * sqrt(N)) changes of mo_right. Corollary #3: All mo_right changes combined take O(N * sqrt(N) * F) time (because each change is done in O(F) time). Theorem #2:Mo_left changes its value O(Q * sqrt(N)) times throughout the run of Mo’s algorithm.
There are no more cases when mo_left changes. Overall, we have O(sqrt(N) * Q) + O(N) = O(sqrt(N) * Q) changes of mo_left. Corollary #4: All mo_left changes combined take O(Q * sqrt(N) * F) time (because each change is done in O(F) time). Corollary #5: Time complexity of Mo’s algorithm is O((N + Q) * sqrt(N) * F). Example problemLet’s look at an example problem (idea taken from here):
Constraints are N ≤ 105, Q ≤ 105.
First two properties obviously hold. The third property depends on the time bound — O(F). Surely, we can compute V([L + 1, R]) from scratch in Ω(R - L) = Ω(N) in the worst case. But looking at complexity of Mo’s algorithm, you can deduce that this will surely time out, because we multiply O(F) with O((Q + N) * sqrt(N)). Typically, you want O(F) to be O(1) or O(log(n)). Choosing a way to achieve appropriate time bound O(F) is programmer’s main concern when solving problems using Mo’s algorithm. I will describe a way to achieve O(F) = O(1) for this problem. current answer = V([mo_left, mo_right]) =∑i=0..99 count'(i)2 * i current answer = ∑i=0..99 cnt[i]2 * i. Suppose we want to change mo_right to mo_right + 1. It means we want to add number p = Arr[mo_right + 1] into consideration. But we also want to retain current_answer and cnt’s properties. Maintaining cnt is easy: just increase cnt[p] by 1. It is a bit trickier to deal with current_answer. We know (from the definitions) that current_answer contains summand cnt[p]2 * p before addition. Let’s subtract this value from the answer. Then, after we perform addition to cnt, add again cnt[p]2 * p to the answer (make no mistake: this time it will contain updated value of cnt[p]). Both updates take O(1) time. All other transitions (mo_left to mo_left + 1, mo_left to mo_left - 1 and mo_right to mo_right - 1) can be done in the same way, so we have O(F) = O(1). You can refer to the code below for clarity. Now let’s look into detail on one sample test case: Queries (0-indexed): [0, 8], [2, 5], [2, 11], [16, 17], [13, 14], [1, 17], [17, 17] The algorithm works as follows: Firstly, set BLOCK_SIZE = sqrt(18) = 4. Notice that we have 5 blocks: [0, 3], [4, 7], [8, 11], [12, 15], [16, 17]. The last block contains less than BLOCK_SIZE elements. Then, set mo_left = 0, mo_right = -1, current_answer = 0, cnt = [0, 0, 0, 0, 0, 0] (I will use only first 6 elements out of 100 for the sake of simplicity). Then sort queries. The Mo’s order will be: Now, when everything is set up, we can answer queries:
Now the important part comes: we must output answers not in order we’ve achieved them, but in order they were asked. Output: 27 6 47 8 9 122 2 ImplementationHere is the C++ implementation for the above problem: #include <bits/stdc++.h> using namespace std; int N, Q; // Variables, that hold current "state" of computation long long current_answer; long long cnt[100]; // Array to store answers (because the order we achieve them is messed up) long long answers[100500]; int BLOCK_SIZE; int arr[100500]; // We will represent each query as three numbers: L, R, idx. Idx is // the position (in original order) of this query. pair< pair<int, int>, int> queries[100500]; // Essential part of Mo's algorithm: comparator, which we will // use with std::sort. It is a function, which must return True // if query x must come earlier than query y, and False otherwise. inline bool mo_cmp(const pair< pair<int, int>, int> &x, const pair< pair<int, int>, int> &y) { int block_x = x.first.first / BLOCK_SIZE; int block_y = y.first.first / BLOCK_SIZE; if(block_x != block_y) return block_x < block_y; return x.first.second < y.first.second; } // When adding a number, we first nullify it's effect on current // answer, then update cnt array, then account for it's effect again. inline void add(int x) { current_answer -= cnt[x] * cnt[x] * x; cnt[x]++; current_answer += cnt[x] * cnt[x] * x; } // Removing is much like adding. inline void remove(int x) { current_answer -= cnt[x] * cnt[x] * x; cnt[x]--; current_answer += cnt[x] * cnt[x] * x; } int main() { cin.sync_with_stdio(false); cin >> N >> Q; BLOCK_SIZE = static_cast<int>(sqrt(N)); // Read input array for(int i = 0; i < N; i++) cin >> arr[i]; // Read input queries, which are 0-indexed. Store each query's // original position. We will use it when printing answer. for(int i = 0; i < Q; i++) { cin >> queries[i].first.first >> queries[i].first.second; queries[i].second = i; } // Sort queries using Mo's special comparator we defined. sort(queries, queries + Q, mo_cmp); // Set up current segment [mo_left, mo_right]. int mo_left = 0, mo_right = -1; for(int i = 0; i < Q; i++) { // [left, right] is what query we must answer now. int left = queries[i].first.first; int right = queries[i].first.second; // Usual part of applying Mo's algorithm: moving mo_left // and mo_right. while(mo_right < right) { mo_right++; add(arr[mo_right]); } while(mo_right > right) { remove(arr[mo_right]); mo_right--; } while(mo_left < left) { remove(arr[mo_left]); mo_left++; } while(mo_left > left) { mo_left--; add(arr[mo_left]); } // Store the answer into required position. answers[queries[i].second] = current_answer; } // We output answers *after* we process all queries. for(int i = 0; i < Q; i++) cout << answers[i] << "\n"; return 0; }Same solution without global variables (the way I like to implement it): #include <bits/stdc++.h> using std::vector; using std::tuple; /* * Take out adding\removing logic into separate class. * It provides functions to add and remove numbers from * our structure, while maintaining cnt[] and current_answer. * */ struct Mo { static constexpr int MAX_VALUE = 1005000; vector<long long> cnt; long long current_answer; void process(int number, int delta) { current_answer -= cnt[number] * cnt[number] * number; cnt[number] += delta; current_answer += cnt[number] * cnt[number] * number; } public: Mo() { cnt = vector<long long>(MAX_VALUE, 0); current_answer = 0; } long long get_answer() const { return current_answer; } void add(int number) { process(number, 1); } void remove(int number) { process(number, -1); } }; int main() { int N, Q, BLOCK_SIZE; std::cin.sync_with_stdio(false); std::cin >> N >> Q; BLOCK_SIZE = static_cast<int>(sqrt(N)); // No global variables, everything inside. vector<int> arr(N); vector<long long> answers(Q); vector< tuple<int, int, int> > queries; queries.reserve(Q); for(int i = 0; i < N; i++) std::cin >> arr[i]; for(int i = 0; i < Q; i++) { int le, rg; std::cin >> le >> rg; queries.emplace_back(le, rg, i); } // Comparator as a lambda-function, which catches BLOCK_SIZE // from the above definition. auto mo_cmp = [BLOCK_SIZE](const tuple<int, int, int> &x, const tuple<int, int, int> &y) -> bool { int block_x = std::get<0>(x) / BLOCK_SIZE; int block_y = std::get<0>(y) / BLOCK_SIZE; if(block_x != block_y) return block_x < block_y; return std::get<1>(x) < std::get<1>(y); }; std::sort(queries.begin(), queries.end(), mo_cmp); Mo solver; int mo_left = 0, mo_right = -1; // Usual Mo's algorithm stuff. for(const auto &q: queries) { int left, right, answer_idx; std::tie(left, right, answer_idx) = q; while(mo_right < right) { mo_right++; solver.add(arr[mo_right]); } while(mo_right > right) { solver.remove(arr[mo_right]); mo_right--; } while(mo_left < left) { solver.remove(arr[mo_left]); mo_left++; } while(mo_left > left) { mo_left--; solver.add(arr[mo_left]); } answers[answer_idx] = solver.get_answer(); } for(int i = 0; i < Q; i++) std::cout << answers[i] << "\n"; return 0; }Practice problemsIn case you want to try out implementing Mo’s technique for yourself, check out these problems:
|
You are given an array a of size n you are asked q queries there will be two types of queries
zusammenhängende Posts
Urheberrechte © © 2024 wiewird Inc.
