Los_Angelos_Laycurse's blog

any hint about 100453C — Rectangles and Connected Regions?
By Los_Angelos_Laycurse, 10 years ago, In English

Link:http://codeforces.net/gym/100453 C

what I can think out is to use unsigned long long bit mask compression and brute force for every rectangle.. complexity is total area of query rectangle divide 64,this approach possibly can pass,but it is not so beautiful.

can anyone give me some hint on better ideas(not brute force)?

  • Vote: I like it
  • +18
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
10 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I have came up an method,but a little complex: first,floodfill to get all connected blocks in the whole matrix. for each query,if the rectangle have three or more connected blocks then sure answer is zero.if this cases is judged,then remain cases that is invalid(not smaller than 3) is some connected blocks is connected in the whole matrix but disconnected in the rectangle,these blocks must be connected with outside part of the rectangle.

Then we can easily judges all 0s and all 1s of the rectangle(the answer is 1), then the main problem is judge if the rectangle has both 0s and 1s,and all of them are connected with outside part of the rectangle.

for each 0 and 1,for example 0,count the number of node of 0 denote N,and number of edges connected them denote E, and the number of 2*2 smaller rectangle that contain all 0s denote M, this number M is the least number of edges we must delete to cancell all circles to form a forest,if this forest is a tree(N==E-M+1),then it is valid for 0s (some 1s are enclosed by some 0s in this rectangle is judged before,i.e. this case the number of connected blocks >=3 in the whole matrix), same method to check 1s

Hope there are better approaches.

→ Reply