CONSADD - Editorial

Practice
Div-3 Contest
Div-2 Contest
Div-1 Contest

Author: Divyam Singal
Tester: Felipe Mota
Editorialist: Divyam Singal

DIFFICULTY:

Easy-Medium

PREREQUISITES:

Math, Colorings

PROBLEM:

You are given two matrices A and B, each of size R \times C. You are also given an integer X. You may perform the following operation on A any number of times:

  • Choose an integer v.
  • Choose X consecutive elements of A, either in the same row or in the same column.
  • Add v to each of the chosen elements of A.

Determine whether it is possible to change A to B in a finite number of operations.

QUICK EXPLANATION:

We will first convert the matrix B=0, and so A = A-B. We can change the set of our available operations to:

  • Add v on 1 \times X or X \times 1 which is in the top-left square X \times X.
  • Do +v and -v in two cells in the same row/column on distance exactly X.

Now we can create an X \times X matrix A', where A'_{i,j} contains the sum of all cells having row number i remainder modulo X and having column number j remainder modulo X. Now the problem is converted into modified problem where R=C=X.

We will build a bipartite graph where left part is rows and right part is columns and the edge between two vertices is a cell on intersection of that row and column. We are given numbers on edges and we have to put numbers on vertices such that for each edge, the number on the edge is equal to sum of numbers in its ends.

Let us suppose there is a solution. For any number v we can do +v to all vertices in the left part, and -v to all vertices in the right part and get another valid solution. So we can choose any vertex and make it 0. Now we know all the numbers in the other part and, eventually, all the numbers.

EXPLANATION:

We will first convert the matrix B=0, and so A = A-B, as absolute values in the matrix A and B doesn’t matter, only difference matters.

We will first consider the case where R=C=X.

We will think of this problem as a bipartite graph. The left vertices will represent the rows and the right vertices will represent the columns. The edge between the left and right vertices is a cell on the intersection of that row and column. Now the problem converts to:

We are given some numbers on edges and we have to put numbers on vertices such that for each edge, the number on the edge is equal to sum of numbers on its ends i.e the two vertices.

Now let us suppose there is a solution to this problem. For any number v we can do +v to all vertices in the left part, and -v to all vertices in the right part and get another valid solution. This is due to the fact that the sum of vertices in the left and right part still remains the same, as +v-v=0. This gives us the freedom to choose any vertex and make it 0. This will help us find all the numbers on the other part of the vertex and eventually we can find all the numbers.

Now let us move onto the general case. We will try to convert it into the case where R=C=X.

We can change the set of our available operations to:

  • Add v on 1 \times X or X \times 1 which is in the top-left square X \times X.
  • Do +v and -v in two cells in the same row/column on distance exactly X.

As to why we can do so, we can add +v to X consecutive rows/columns and then add -v to X consecutive rows/columns, shifted by one cell. This will effectively make a change of +v and -v in two cells in the same row/column separated by a distance of X. This is the second operation.

And to make changes in the cells with (i,j), where i \leq R and j \leq C, we need the first operation.

By doing such a modification we can convert A to another matrix A' of size X \times X. Here A'_{i,j} contains the sum of all cells having index of row =i remainder modulo X and having index of column =j remainder modulo X.

Now we can proceed to solve the this reduced problem as above approach for R=C=X.

Time complexity is O(RC).

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ll long long
#define vll vector<ll>
#define ld long double
#define pll pair<ll,ll>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define oset tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
#define osetll tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update>
#define ook order_of_key
#define fbo find_by_order
const int MOD=1000000007; //998244353
long long int inverse(long long int i){
    if(i==1) return 1;
    return (MOD - ((MOD/i)*inverse(MOD%i))%MOD+MOD)%MOD;
}
ll POW(ll a,ll b)
{
    if(b==0) return 1;
    if(b==1) return a%MOD;
    ll temp=POW(a,b/2);
    if(b%2==0) return (temp*temp)%MOD;
    else return (((temp*temp)%MOD)*a)%MOD;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t;
    cin>>t;
    for(int i=0;i<t;i++)
    {
        ll r,c,x;
        cin>>r>>c>>x;
        ll a[r][c],b[r][c];
        ll a1[x][x];
        for(int i=0;i<x;i++)
        {
            for(int j=0;j<x;j++)
            {
                a1[i][j]=0;
            }
        }
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                cin>>a[i][j];
            }
        }
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                cin>>b[i][j];
            }
        }
        for(int i=0;i<r;i++)
        {
            for(int j=0;j<c;j++)
            {
                a1[i%x][j%x]+=a[i][j];
                a1[i%x][j%x]-=b[i][j];
            }
        }
        ll flag=0;
        for(int i=1;i<x;i++)
        {
            ll temp=a1[i][0]-a1[0][0];
            for(int j=1;j<x;j++)
            {
                if(temp!=a1[i][j]-a1[0][j])
                {
                    flag=1;
                }
            }
        }
        if(flag==0) cout<<"Yes";
        else cout<<"No";
        cout<<"\n";
    }
}
Tester's Solution
7 Likes

Tester’s solution is not visible

4 Likes

I have done something different. First of all i make all the rows elements equal to corrospondig elements of B except X-1 elements in each row, then I have done for the remaining elements column wise .And after that checked remaining elements if they are equal to B’s element then answer is YES else NO here is the link to my code Consecutive Adding

2 Likes

This problem is very Simple. Just make the element value equal to the corresponding one by substracting or adding the remaining value and also applying the the same operation to the consecutive X element No matter if the value are distorted. If the consecutive right is not possible do the consecutives in the downward direction. And at the end if the matrix is equal the answer then it is yes else no. The main logic is the subtraction and addition is a multiple of X and the values at the edge are suppose to be made equal taken from the right consecutives or the downwards no other way. So No matter which direction you take. Ultimately it will be in equilibrium. Solution

3 Likes

Can we say testcases were easy as I also do the same brute forcing , Changing every element of a to b and corresponding elements. But I have done it in linear time.
Isn’t it the solution time complexity will be o(10^6*500)
My submission: CodeChef: Practical coding for everyone

I have found a tutorial here

The tutorial is not mine but I found the explanation quite detailed and close to what a non-talented person thinks.

Thanks

1 Like

Wait, how did 1.2 seconds pass? Time limit is 1secs, right?

1 Like

I didn’t understood the solution/editorial can anyone help me to understand it?

2 Likes

I too found a simple, brute force method similar to vijinking. There are 2 steps.

  1. Evaluate the total of differences between corresponding elements. If this is not a multiple of X, there is no solution possible.
  2. Work through the matrix directly, roughly as described above.

My solution is at CodeChef: Practical coding for everyone which passed in under half the time allowed. There is no need for anything more complicated.

2 Likes

I USED DIFFERENT APPROACH HERE
FIRST I TAKE A ROW
THEN IN EACH ROW I COMPARED EACH EELEMENT WITH CORRESPONDING ELEMENT IN B
IF IT IS DIFFERENT THEN I CHECK IT IS POSSIBLE TO TAKE THE X CONSECTIVE ELEMENTS FROM THAT ELEMENT TO LAST ELEMENT IN ROW IF IT IS THEN I DO OPERATIONS AND IF NOT THEN I SIMPLY NOT DO ANYTHING
AND DID SAME FOR COLUMNS
AND THEN FINAL CHECK A BECOMES B OR NOT

Can anyone explain why my code https://www.codechef.com/viewsolution/43874444 does not give TLE? According to me, the time complexity is O(R*C*X) which should give TLE. Am I missing something?

Codechef (unlike, for example, Codeforces) allows language dependent multipliers for the time limits. See Updated: Announcing Variable Time Limits Based on Programming Language | CodeChef

yeah, but his code is in CPP and the multiplier for that should be 1, which doesn’t make any sense.

My solution was, I think, simpler than the one given in the editorial. As with the editorial solution I start by creating a matrix of the differences, Conceptually I then set every element to zero using the provided operation except the bottom right X-1 by X-1 square, and then test whether the elements in this square are equal. One can do this by working from top to bottom and from left to right adding the remaining difference to each element of A, and to the next X-1 elements of the row or column containing A. It is easy to show that it makes no difference whether one adds to the row or the column (except, of course, for the last X-1 rows and columns, where one has no choice).

Doing this naively, however, would be O(RCX), so would probably be too slow. One can, however, show that, if all previous cells have been set to zero using horizontal operations, the remainder in a cell is only dependent on the elements in the row with the same index mod X.

This reduces the problem to O(RC), and gives what turns out to be a very neat solution in Python. See CodeChef: Practical coding for everyone

This is the solution in the comment you referenced, it looks like Python to me!

can you please elaborate this line a little bit( in detail )

1 Like

Oh, damnit. On a quick look, it looked cpp to me. Thank you!

1 Like

Hi thanks for the editorial, I understood most of the part except the assumption part

You said you assumed there is a solution for that bipartite graph.

How to find out whether it is possible to have a solution or not ?

This is where you will get the no case.

why shoud it be TLE?
since r,x and c are of order 10^3 and and x might be even less for many testcases, so in worst case 10^9 operations which would definitely give TLE if it included too many complex operations like multiply ,divide or modulo
But 10^9 add or subtract simple operations can easily run under 1 second

here is my solution, basically I made c - x columns of r rows equal by doing row operations and then did the same for the remaining columns by column operation.
https://www.codechef.com/viewsolution/43894400