PROBLEM LINK:
Setter: nitjchapter
Tester: nitjchapter
Editorialist: nitjchapter
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
Chef likes playing with matrices. He has a matrix X of size n∗m, which is initialized to 0 (i.e. for each 0≤i<n,0≤j<m,X[i][j]=0).
Chef’s mommy has a list of size s that contains special indices. For each special index [a,b] (assume 0-based indexing), she wants Chef to perform the following operations:
- Increment the value of all the cells on row a.
- Increment the value of all the cells on column b.
After performing s operations, Mommy wants to know the total number of cells that store an odd value.
Since Chef has to go out to play with his friends, he asks for your help. Can you complete this task for Chef?
QUICK EXPLANATION:
Since it can be observed from constraints, we cannot create a 2D matrix with 10^4 rows and 10^4 columns. But in this problem, we do not need to create the matrix.
We will store the rows and columns as they occur in the list of indices as for a row that is incremented an odd number of times, all its cells will be incremented an odd number of times(similarly for columns).
In the end, we need to subtract those cells from our calculation that have occurred 2 times.
EXPLANATION:
We will maintain two vectors row and col to know whether the row and column has been incremented even number of times or odd. 0 denotes even and 1 denotes odd.
Initialize row and col vector to 0(denoting even(0) occurrence initially)
For each index [r,c] from the list of indices,
If row[r]==0, set row[r] = 1 else set row[r] = 0
If col[c]==0, set col[c] = 1 else set col[c] = 0
By doing this we have stored all the rows and columns that have an odd occurrence. All the cells of such rows will contribute to the answer except the intersection points for a particular row and column(as it will be incremented 2 times- one for row and one for column).
Hence, we need to remove those cells from the answer.
The count of those cells is basically (no_of_odd_rows)*(no_of_odd_columns)*2 (as they were counted two times).
Thus, after calculating the number of odd rows and columns from the row and col vector,
If no_of_odd_rows = nr and no_of_odd_columns = nc, the required answer will be-
Ans = nr * m + nc * n -2*(nr * nc)
TIME COMPLEXITY:
The time complexity is O(n+m+s) ,where
n = no. of rows, m = no. of columns, s = size of list of indices
Editorialist’s Solution
#include <bits/stdc++.h>
using namespace std;
int oddCells(int m, int n, vector<vector<int>>& indices) {
vector<int>row(m);
vector<int>col(n);
int a = indices.size();
for(int i = 0;i < a;i++){
row[indices[i][0]] = row[indices[i][0]]==0?1:0;
col[indices[i][1]] = col[indices[i][1]]==0?1:0;
}
int cnt_row = 0;
int cnt_col = 0;
for(int i = 0;i < m;i++){
if(row[i]){
cnt_row++;
}
}
for(int i = 0;i < n;i++){
if(col[i]){
cnt_col++;
}
}
return cnt_row*(n-cnt_col) + cnt_col*(m-cnt_row);
}
int main() {
// your code goes here
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int r,c;
cin>>r>>c;
int q;
cin>>q;
vector<vector<int>>v(q,vector<int>(2));
for(int i = 0;i < q;i++){
cin>>v[i][0]>>v[i][1];
}
cout<<oddCells(r,c,v);
return 0;
}