QMAXTRIX - Editorial

editorial
, , ,
1

PROBLEM LINK

Practice
Contest

Panel Members

Problem Setter: Amit Pandey
Problem Tester: Pushkar Mishra
Editorialist: Prateek Gupta
Contest Admin: Praveen Dhinwa and Pushkar Mishra
Russian Translator: Sergey Kulik
Mandarin Translator: Hu Zecong
Vietnamese Translator: VNOI Team
Language Verifier: Rahul Arora

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Basic Programming, Logic

PROBLEM:

Given a binary matrix having 1s and 0s. Each ithrow of the matrix contains 1s only in the given contiguous range [l[i], r[i]]. For each query, you need to find the sum of the matrix modulo 2 if some given xth row and yth column are supposedly removed from the matrix. Also, each query does not modify the state of the matrix after its been processed.

EXPLANATION:

Let initialSum be the sum of the original matrix.
Let rowSum[i] and colSum[i] denote the sum of the elements of ith row and column respectively in the original matrix.
Let A[i][j] denote the value at cell (i,j) formed by intersection of ith row and ith column.

For each query, the sum of the final matrix for each query(x,y) will be equal to initialSum - rowSum[x] - colSum[y] + A[x][y]

initialSum of the matrix can be calculated as summation of r[i] - l[i] + 1 for each i \mathcal\in [1,N].
rowSum[x] is already the number of ones in the ith row i.e r[x] - l[x] + 1.
A[x][y] is 1 if and only if j \mathcal\in [l[x],r[x]].
Only task now left is to calculate colSum[y].

Solution for Subtask 1:
To calculate the value of colSum[y], we need to find out how many rows have y \mathcal\in [l[i],r[i]] for each i from [1,N].
For this, we can iterate each row and find out. This approach will take \mathcal{O}(N) per query which is infact slow for Subtask 2 to pass.

Solution for Subtask 2:
We can calculate the values of colSum[y] before hand for all y \mathcal\in [1,N]. For each rowSum[i], we basically have to increase colSum[j] += 1 where j \mathcal\in [l[i],r[i]].
In other words, we can do a range update in the following manner :-

for ( int i = 1; i <= N; i++ ) colSum[l[i]]++, colSum[r[i]+1]--;

We can then do a cumulative sum to compute individual values for each column.

for ( int i = 1; i <= N; i++ ) colSum[i] += colSum[i-1];

How do above range updates work?

When you have to increase a particular range[i,j] in the empty array with 1, you increase A[i] += 1, meaning you have increased all the numbers from i uptill infinity to 1. That’s because when you take the cumulative sum after doing the update at position i, you see all values having index than or equal to i are now 1. But, in your case ,you want them to be increased uptill index j only. Hence, to counter balance the effect caused, you do A[j+1] -= 1 and then take the cumulative sum. If you see now, all the values in range$[i,j]$ are increased to 1 while rest of them remain 1.

We now have all the necessary parameters that we need to answer each query in a constant number of operations.

COMPLEXITY

Overall Complexity for the solution to pass all the subtasks is \mathcal{O}(N) precomputation and then \mathcal{O}(1) per query. For details on the implementation, please have a look at the solutions below.

SOLUTIONS:

1 Like
2

I solved it using BiT. Computing rows in O(n) and cols in O(nlogn) (using BiT) for pre computation. And then O(1) per query. Though I was unable to get AC during contest :’( :’(. Did a very very silly mistake :’(. Here’s my solution.

3

I solved this using binary search to calculate colSum and rest same: https://www.codechef.com/viewsolution/8841488 though not memory optimized.
Complexity: O(nlogn)

4

i am answering each query in order of (1) still i am getting TLE in 2 Sibtask

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

    public class Matr {

  public static void main(String[] args) throws NumberFormatException,
		IOException {
	InputStreamReader or = new InputStreamReader(System.in);
	BufferedReader br = new BufferedReader(or);

	// Scanner sc = new Scanner(System.in);
	StringBuffer sb = new StringBuffer();
	int n = Integer.parseInt(br.readLine());
	int mat[][] = new int[n][3];
	long sum = 0;
	for (int i = 0; i < mat.length; i++) {
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s, " ");

		int a = Integer.parseInt(st.nextToken());
		int b = Integer.parseInt(st.nextToken());
		mat[i][0] = --a;
		mat[i][1] = --b;
		mat[i][2] = b - a + 1;
		sum += b - a + 1;

	}
	// System.out.println(sum);
	/*
	 * 1 1 1 0 0 0 0 0 0 0 1 0 0 1 1 1
	 */
	int arr[] = new int[n];
	for (int j = 0; j < mat.length; j++) {
		for (int j2 = mat[j][0]; j2 <= mat[j][1]; j2++) {
			arr[j2] += 1;

		}

	}

	/*
	 * for (int i = 0; i < arr.length; i++) { System.out.print
	 * (arr[i]+"  ");
	 * 
	 * } System.out.println();
	 */

	int q = Integer.parseInt(br.readLine());
	while (q-- > 0) {
		long tem = sum;
		// String s[]=br.readLine().split(" ");
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s, " ");

		int x = Integer.parseInt(st.nextToken());
		int y = Integer.parseInt(st.nextToken());
		x--;
		y--;
		tem -= mat[x][2];

		tem -= arr[y];
		if (y >= mat[x][0] && y <= mat[x][1])
			tem++;
		// System.out.println("tem "+tem);
		if (tem % 2 == 0)
			sb.append("E\n");
		// System.out.println("E");
		else
			// System.out.println("O");
			sb.append("O\n");

	}
	System.out.println(sb);

}

}

5

Why are we doing r[i]+1 in colSum[r[i]+1]--; ?

6

Solution with exactly the same approach :slight_smile:

https://www.codechef.com/viewsolution/8841244

3 Likes
7

because after doing this for each row and taking the prefix sum at the end, we’re left with “coloumn’wise” sum for each i till n in O(n) time.

8

Silly mistakes hurt a lot. But BiT was not really needed when you’ve a much simpler and efficient technique for this thing. :stuck_out_tongue:

9

@shibli786 …u r getting tle bcoz

 int arr[] = new int[n];

for (int j = 0; j < mat.length; j++) {
    for (int j2 = mat[j][0]; j2 <= mat[j][1]; j2++) {
        arr[j2] += 1;

    }

}

for the y co-ordinate it goes O(N^2)…Read the editorials for precomputation

1 Like
10

got it …thanks bro!!

11

Can someone please tell me the correctness of the method used to calculate colSum

12

yea,realized it later :stuck_out_tongue:

13

What is the problem with this??
link text

14

Your solution seems to just ignore that single element at specified column and row. However you have to ignore the entire row and the entire column (not just the common element)

15

very nice algorithm used to calculate colsum[n].

my solution

1 Like