Help needed in Binary Matrix CF 884F

help
codeforces
disjoint-set

#1

Hello, I am facing WA in test 7 in problem Binary Matrix. Here’s my submission. Can anyone tell me what is wrong in my solution, or provide helpful test cases?


#2

@taran_1407

ur code gives output 4 for this test case : :

3 16

9CFD

E9A7

9BAF

answer should be 3

hope this helps , as i don’t know java so i cant figure out the bug …


#3

##Kept test case simple for u to debug it easily…
##Saw and understood you code…

Test case :-

10 4
B
9
D
5
D
B
9
D
5
7

1011
1001
1101
0101
1101
1011
1001
1101
0101
0111

Expected Output: 1

##Your output : 2
You have logical error probably…


#4

Can Anyone help??


#5

@vivek_1998299 @vijju123 @swetankmodi

anyone??


#6

will reply error soon… I guess its related to conflicting roots or something of that type… let me check it thoroughly…
I made this test case after reading your logic…


#7

try this one too ::

10 24

174094

882455

171152

761423

221685

761892

795431

233411

387427

793198


#8

##GOT ERROR
check set after
2 4
D
5

i.e.
1101
0101

so after D
set[0-3] becomes :
0012

and then you will assign
4567 to set[4-7] for 5

now for union query
union(set,3,7)

You will do find(3)
set[3]=find(set[3)) = find(2)
find(2)
set[2]=find(set[2))= find(0)
set[0]=0

so basically all will point to zero i.e set[0-3]=0000 … which was not intended… it should remain 0012 no matter what you do…


#9

as I said earlier it’s about conflicting and wrong assignment of value to root… Due to uniq function…


#10

Thanks a lot for test case, let me try debugging. Will ping here if can’t debug.


#11

Thanks for test cases, man.


#12

sure… welcome :slight_smile: