CONSADD - Editorial

editorial
, , , ,
4

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
5

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

6

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
7

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

1 Like
8

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

2 Likes
9

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
10

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

11

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?

12

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

13

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

14

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

15

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

16

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

1 Like
17

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

1 Like
18

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.

19

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

21

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

22

This is correct and a O(RCX) solution should fail. But mine’s passed solution. Weak test cases?

23
  1. Can anyone explain why coloring is mentioned in the prerequisites?
  2. What is meant by Graph-coloring in the question?
  3. How does the concept of Graph-coloring/coloring is used here?
24

The solution just arbitrarily convert it into a condensed matrix and then graph problem. Didn’t find it intuitive at all. Is this some standard technique, any resources to read up on it?