SAKTAN - Editorial

PROBLEM LINK:

Div 1
Div 2
Practice

Author: Abhinav Jain
Tester: Hanlin Ren
Editorialist: Hanlin Ren

DIFFICULTY:

SIMPLE

PREREQUISITES:

Math

PROBLEM:

Given an N\times M matrix filled with zeroes initially, and Q operations. Each operation (X_i, Y_i) means to add 1 to the row x and also to the column y. (Note that 1 is added twice to the cell (X_i, Y_i).) The task is to compute the number of cells with odd values after all Q operations.

QUICK EXPLANATION:

Rows and columns are independent. Suppose there are r rows added an odd number of times, and c columns added an odd number of times. Then the answer is rM+cN-2rc.

EXPLANATION:

Subtask 1

Since T,N,M,Q\le 300 in this subtask, a straightforward solution with complexity O(T((N+M)Q+NM)) can pass. We simply implement every query, and each query takes O(N+M) time. After then we use O(NM) time to count the number of odd cells.

Subtask 2

In this subtask, N\cdot M\le 10^6 and Q\le 10^6. For each row x (1\le x\le N), let A[x] be the number of operations on it. Then A[x] is simply the number of i's such that X_i=x. For each column y (1\le y\le M), let B[y] be the number of operations on it, thus similarly B[y] is the number of i's such that Y_i=y. We can compute A[x] and B[y] by the following pseudocode:

Initially A[x]=B[y]=0 for every x, y;
for i = 1 to Q
    A[X[i]] += 1
    B[Y[i]] += 1

The value at cell (x,y) is simply A[x]+B[y], since it’s added by this many operations. We can iterate through the matrix to find the number of odd cells:

ans = 0
for x = 1 to N
    for y = 1 to M
        val = A[x] + B[y]
        if val % 2 == 1 then ans += 1

This takes O(Q+MN) time per test case.

Subtask 3

Actually, we don’t need to spend O(MN) time to count the number of odd cells. Suppose there are r rows operated an odd number of times (i.e. A[x] is odd, where x is the row index). Suppose there are c columns operated an odd number of times (i.e. B[y] is odd, where y is the column index). Then the answer is r\cdot M+c\cdot N-2r\cdot c.

Proof

Consider the following diagram, where the first r rows and first c columns are operated an odd number of times. Let’s count the number of odd cells row by row.

  • In the i_1-th row where i_1\le r, the cells not in the first c columns are odd. (Because if you don’t do column operations at all, every number is odd. If you did an odd number of column operations, the corresponding cell becomes even.) There are r such rows, each row has (M-c) odd cells.
  • In the i_2-th row where i_2>r, the cells in the first c columns are odd. There are N-r such rows, each row has c odd cells.

Therefore, there are r(M-c)+c(N-r)=r\cdot M+c\cdot N-2r\cdot c odd cells.

Alternatively, the odd cells are exactly those in the shaded area. It’s also easy to see that there are r(M-c)+c(N-r) odd cells.

The time complexity is, therefore, O(M+N+Q).

ALTERNATE EXPLANATION:

Please feel free to share your approach :slight_smile:

SOLUTIONS:

Setter's Solution
// Author : Abhinav Jain
// Institution: Jaypee Institute of information Technology
// AC COde
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define cases int testcases;cin>>testcases; while(testcases--)
int Row[100005],Col[100005];
int32_t main()
{
    cases
    {
        int n,m,q,x,y;
        cin>>n>>m>>q;
        for(int i=1;i<=n;i++)
        {
                Row[i]=0;
        }
        for(int i=1;i<=m;i++)
        {
                Col[i]=0;
        }
        
        /*n=3 m=4
        00 01 02 03
        10 11 12 13
        20 21 22 23
        */
        while(q--)
        {
            cin>>x>>y;
            Row[x]++;
            Col[y]++;
            Row[x]%=2;Col[y]%=2;
        }
        int a=0,b=0,c=0,d=0;
        for(int i=1;i<=n;i++)
        {
            if(Row[i]==1) a++;
            else b++;
        }
        for(int i=1;i<=m;i++)
        {
            if(Col[i]==1)c++;else d++;
        }
        int res= (a*d + b*c);
        cout<<res<<endl;
    }
    return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void gi(int &x) {char ch = getchar(); x = 0; while (ch < '0' || ch > '9') ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();}
void pi(ll x) {if (x > 9) pi(x / 10); putchar(x % 10 + 48);}

int n, m, q, row[100200], col[100200];

void doit() {
  int i, j, r, c;
  gi(n); gi(m); gi(q);
  for (i = 1; i <= n; i++) row[i] = 0;
  for (j = 1; j <= m; j++) col[j] = 0;
  while (q--) {
    gi(i); gi(j);
    row[i] ^= 1; col[j] ^= 1;
  }
  for (i = 1, r = 0; i <= n; i++) if (row[i]) r++;
  for (j = 1, c = 0; j <= m; j++) if (col[j]) c++;
  pi(1ll * r * m + 1ll * n * c - 2ll * r * c); putchar('\n');
}

int main() {int t; gi(t); while (t--) doit(); return 0;}
5 Likes

Since 1 is added to all the cells of a row or a column, rather than maintaining the whole matrix, we can just manage two arrays. One for all rows and one for all columns. If 1 is to be added to i^{th} row, then I will do row[i-1]++, assuming 0 based index. Same for columns. At the end, we can reconstruct the whole matrix by taking a cross product of these two arrays. The value M_{ij} = row[i-1] + col[j-1]. So we can run two nested loops to check all the cells and find odd values. But this approach is too slow for the subtask 3. To complete subtask 3, you need to observe that odd + odd = even and even + even = even. Hence if row[i] and col[j] are both odd or even, then that cell can never have odd value. So we need to just count odd and even values in both arrays and multiply them i.e. total_odd_values = odd_row_values * even_col_values + even_row_values * odd_col_values.

16 Likes
  • 1 . Did the same!

I used the same approach of storing rows and columns separately in a 1D array. In the end i iterated over all the rows and checked the even or odd number of elements respectively.
Here’s the simple code

#include<bits/stdc++.h>
#define vll vector
#define ll long long
#define mp make_pair
#define pb push_back
#define mod 1000000007
using namespace std;
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); //fast I/O
ll t;cin>>t;
while(t–)
{
ll n,m,q;cin>>n>>m>>q;
vll rows(n,0);
vll cols(m,0);
while(q–)
{
ll r,q;cin>>r>>q;
rows[r-1]++;
cols[q-1]++;
}
ll odd_cnt=0,i,temp,j,odd_col=0;
for(i=0;i<m;i++)
{
if(cols[i]%2)
odd_col++;
}
ll even_col=m-odd_col;
for(i=0;i<n;i++)
{
if(rows[i]%2)
{
odd_cnt+=even_col;
}
else
{
odd_cnt+=odd_col;
}
}
cout<<odd_cnt<<"\n";
}
return 0;
}

This is my soln-my soln
While upsolving I came up with this soln. It’s same as setter’s soln but still last test case isn’t passing . Any help will be highly appreciated.

@anon55818992
This is not the link to your solution. Please click on ‘My Submissions’ option on the problem page and give the link.

Can we use multidimensional array for the same ?

Here is my approach to the problem: CodeChef: Practical coding for everyone

1 Like

how did you think about it ?
i mean it never occured to me

2 Likes

This is my solution with time complexity O(M+N+Q)
https://www.codechef.com/viewsolution/27326221

Edit : it’s actually O(M+N+Q) if we count memset()

Bro i followed your approach but its failing the subtask 3. Please check my code.
https://www.codechef.com/viewsolution/27387509

Bro my approach is similar to yours but its failing the subtask 3. Please check my code.https://www.codechef.com/viewsolution/27387509

can any one please tell me why one is giving wa while other ac in third subtask
https://www.codechef.com/viewsolution/27165726
https://www.codechef.com/viewsolution/27215864

https://www.codechef.com/viewsolution/27203538
my approach same as above…

@zzz11
difference is just you have defined variables of counting in long long and i have in int. But this should not make difference because final answer is in long in my code

I hope this will Help You alot :
Just Go Through this

And Subscribe my channel Hello World Please.

2 Likes

That’s some nice work bro. Keep it up!

Same problem, @manunem
https://www.codechef.com/viewsolution/27469993
Figured what the fix is?

@anon76214830

I have modified your solution and it got accepted. Check it out here

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

Since you have declared vars as ints and result may not fit into an ‘int’ for sub task 3, I have changed it to ‘long long’ and it got accepted. I havent changed the logic though

I also had the same problem. Figured out from your comment. Multiplying int with int results in int. So, despite storing in long, we have already allowed it to overflow because multiplication in done in int.

1 Like