unofficial editorial seaco and fill matrix (BRIEFLY)

help
sept17

#1

FILL THE MATRIX:-

For 100 points u need to do it O(n) or O(n logn).The inputs are as a,b,c. So there lies three conditions
1)if a=b then c has to be 0, since the same index cannot have a difference of 1.
2) if a=b and b=a , suppose 1 2 1 then 2 1 0 , both c cannot be different since |a[J]-a*|.
3) if a and b has already been used , you need to think in such a way that the diff is same as given when its used somewhere else.

For this you can create a 1-d matrix of n length initialized to 0 everywhere, where 0 means untouched , the other values can be 1 and 2 as the diff can never be greater then 1 as mentioned in the question.
So lets solve it offline , store the queries first and sort them , while storing just check if a=b then c=0. And while storing make sure a<b , if not swap and store them.
So now iterate through the queries from top to bottom , and there will be 4 conditions.

1) visited and visited , if both have already been visited , then their difference has to be  only C else its wrong.
2)unvisited and unvisited , then make one other 1+c, 
3)visited and unvisited , in this there will be two conditions , since if visited ==2 then the unvisited will become 2-c , and if visited==1 then unvisited cannot be 0 , since its visited so it will become 1+c.
4)unvisited and visited , in this there will be two conditions , since if visited ==2 then the unvisited will become 2-c , and if visited==1 then unvisited cannot be 0 , since its visited so it will become 1+c.

In this way only the 1st condition if contradicts then “NO” else “YES”.
The link of solution.

  http://ide.geeksforgeeks.org/tVcHaf

SEREJA AND COMMANDS:-

For a 50 marks solution , you just can simply use memoization and do.
Let explain the 1st test case to make you guys more clear.

1 1 2 0
1 4 5 0
2 1 2 0
2 1 3 0
2 3 4 0

So store the queries and solve offline, start form bottom to up , and memoize how many times each command is executed rather then executing each command for increasing that will fetch you 20 points, just start form the last command and proceed as further .

1 1 2 0
1 4 5 0
2 1 2 1
2 1 3 1
2 3 4 1

In the next step when you do it will be the 2nd last command it will become 1+1 and the same value will be added to 1-3 range since if 2nd last command executes for n times then the range within it will also be executed n times .

1 1 2 2
1 4 5 2
2 1 2 3
2 1 3 2
2 3 4 1

The next step-

1 1 2 6
1 4 5 6
2 1 2 4
2 1 3 2
2 3 4 1

The next step-

1 1 2 6
1 4 5 7
2 1 2 4
2 1 3 2
2 3 4 1

the last step-

1 1 2 7
1 4 5 7
2 1 2 4
2 1 3 2
2 3 4 1

So again iterate through the queries from 1-m and then increase , this will fetch you 50 marks, since O(n^2).
For 100 marks apply the same logic just use lazy propagation to update and queries to find out how many times each command is executed.
If you donot know segment tree refer here http://se7so.blogspot.in/2012/12/segment-trees-and-lazy-propagation.html or https://www.youtube.com/watch?v=ZBHKZF5w4YU

The solution of 50 marks https://www.codechef.com/viewsolution/15228394
The solution for 100 marks using lazy trees https://www.codechef.com/viewsolution/15388053

NOT:- USE MOD PROPERLY EVERYWHERE YOU DO ADDITIONS.


#2

Nice work man :slight_smile:
Just a small suggestion : Maybe you can think of some better title.
Also please fix the link for Fill the Matrix code!


#3

Great job!!
The explanations are indeed helpful. It is extremely helpful for all those who could not solve them as well as for the ones who had to stay content with partially correct solutions.
Keep up the Good Work!!


#4

What is wrong in my seaco code? Implemented the same way you suggested for 50 marks.
https://www.codechef.com/viewsolution/15405994


#5

Why are we sorting the queries in FILLMTR?


#6

guys can we solve fill matrix by using the concept of bipartite graph?


#7

@raj97 your code for fil matrix is failing for this test case :1 5 4 1 2 0 1 5 0 3 4 0 4 5 1 suggested by @sherewillpower


#8

@anno : Correct! this approach will give ‘no’ as a output but we can fill the matrix by [1 1 2 2 1]. The reason for WA is in 3rd query we’re assigning values to both unvisited nodes. because we don’t know if we’ll need to assign values to those nodes in upcoming queries or not. So. overall it is the 1st if condition (which is evaluating both unvisited nodes) which is creating trouble.

So, we can make a slight change in this algorithm and from the 2nd query put 1 filter that if both nodes are unvisited execute it later and put it in loop until all the queries are successfully executed or there’re all unvisited nodes left in queries. By this we also don’t need to sort the queries.

For your given test case if we execute 4th query before 3rd we will get AC. :slight_smile:


#9

In SEACO while using lazy propagation , why are we not updating the node and only updating the left and right child

if(lazy[node] !=0) {


		if(a != b) {
		lazy[node*2+1] =(lazy[node*2+1]%m+ lazy[node]%m)%m; 
    			lazy[node*2+2] =(lazy[node*2+2]%m+ lazy[node]%m)%m;  
					lazy[node] = 0;
		}
}

Here according to the tutorials the tree node should be updated before the condition (a != b) but here there is no tree node.
I tried it using segment tree but got WA, Can someone point out the mistakes
https://www.codechef.com/viewsolution/15415533


#10

Thanks for explaining in simple words.But when I ran ur code in practise section, it doesn’t even give partial marks?
Here is the link for the practise session for the same https://www.codechef.com/problems/SEACO.
It simply shows TLE and terminates but according to you, it should give 50 points right? @raj79


#11

done bro as u said


#12

I think you should name it on lines of “Unofficial Editorial/Soln of SEACO &FILLMAT”.

The poor editorialist will be confused if he sees that theres a thread explaining his editorial where he in turn explained a lot of stuff. :stuck_out_tongue:


#13

ok bro done


#14

Thanks dear :slight_smile:


#15

check ur update part just add mem arrays value to the answer array


#16

so that all queries related to a index is done then we move to others , which is necessary else it will give a wrog answer since u are using visiting unvistng concept


#17

can you please give me a testcase in which the solution without sorting will fail.


#18

yes tht is what is mntioned in the editorial


#19

I am adding everywhere. Which part you are refering to? line no?


#20

can anyone explain 3rd or 4th condition ?