Modification of Flood fill ???

[rish123y]

The basic floodfill algorithm finds the largest connected area having only a single value.
But instead of binary 2D array, input is a matrix of n*m with numbers;
an island is defined by 2 numbers.

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

ans :-

1 1 2 . .
. 1 2 . .
. 2 1 . .
. . 1 2 1

for island defined by 1 and 2.


. . 2 . .
. . 2 5 2
. . . 5 .
. . . 2 .

for island defined by 2 and 5

find max area of island.
The numbers in array are from 1 to 4*1e6;
size of matrix is max. 2*1e3;

Problem :-
https://www.codechef.com/JUNE18B/problems/TWOFL

[icy1]

tricky, since the two flower combinations are not known.

I wonder if it'd help to store it all in a structure that keeps track of neighbor values (e.g. 0 if no neighbor)

struct Flower
{
    unsigned int north, east, south, west;
};

not sure what I'd want to store all the flowers in, though.

[closed account 3UohqMoL]

I think a set of pairs will work along with mapping them in right places.

[tpb]

This is kind of an interesting problem. Does anyone have any good ideas?

The size of the matrix goes up to 1000 x 1000 (or possibly 2000 x 2000).
And there can be up to 1,000,000 different values (or possibly 4,000,000).

[closed account 3UohqMoL]

The problem says the area should be sideways connected but for the area to be connected it must also be connected downwards to the same values.Am i correct??

If i am then we can store the pair of each value with the numbar that appers max no. of times in a row and at last output that count it will be very simple but i think that the column too has to be connected

[unstoppable13]

@lastchance please see this problem

[unstoppable13]

@Wasp have you solved this problem?

[ashishyadav]

can anyone provide me some test cases that i can use for checking my code?
my code giving right answer for all the test cases that i used bt it give wrong amswer on submission

[unstoppable13]

@kashish
2 6
1 1 1 2 2 2
2 2 2 1 1 1
what is your output for this?

4 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

and what is for this?

[ashishyadav]

@unstoppable13

12 and 20

[rish123y]

******* Matrix size 50*50 , 100*100, 100*100*****
Test File 1 :- https://justpaste.it/43ico
Ans = 2
Test File 2 :- https://justpaste.it/496hv
Ans= 10000
Test File 3 :- https://justpaste.it/6js0o
Ans = 199
*********Matrix size 10*10 ---3 test in 1 file
https://justpaste.it/6666z
Ans are in the file

[rish123y]

@Wasp
I tried finding all unique pairs that exist in the matrix using a set in a traversal
and the a Floodfill for each of these pairs but it gives TLE on 3 cases

Sub-Task	Task #	Result
(time)
1	0	AC   (0.010000)
1	1	AC   (0.000000)
1	2	AC   (0.490000)
1	3	AC   (0.000000)
1	4	AC   (0.000000)
Subtask Score: 20.00%	Result - AC
2	5	AC  (0.270000)
2	6	AC  (0.080000)
2	7	TLE (4.010000)
2	8	AC   (3.380000)
2	9	AC   (0.200000)
Subtask Score: 0.00%	Result - TLE
3	10	AC  (1.040000)
3	11	AC  (0.310000)
3	12	TLE (4.010000)
3	13	TLE (4.010000)
3	14	AC   (0.760000)
Subtask Score: 0.00%	Result - TLE

[suchandra]

@rish
Well does that mean?

like flowers till lets say 1...7
u compute all possible combinations says [1,2]=x
[1,3]=x
.
.
.
.
[7,6]=x

and find maximum of that?

[closed account 3UohqMoL]

@rish123y Well done can u share your code so that i we can optimise it for other subtasks.
I also got 20 pts but i traversed all the matrix and didnt used flood will i think ur code can be optimised a little bit

[unstoppable13]

@rishi123y can you give me code or link for floodfill algorithm to find length of longest component of a number?

[ashishyadav]

modify this for the above problem

https://www.geeksforgeeks.org/find-length-largest-region-boolean-matrix/

[unstoppable13]

Got AC :-)

Sub-Task		Task #		Result
(time)	
1		0		AC
(0.000000)	
1		1		AC
(0.000000)	
1		2		AC
(0.610000)	
1		3		AC
(0.010000)	
1		4		AC
(0.000000)	
Subtask Score: 20.00%		Result - AC	
2		5		AC
(0.700000)	
2		6		AC
(0.060000)	
2		7		AC
(3.900000)	
2		8		AC
(3.480000)	
2		9		AC
(0.400000)	
Subtask Score: 20.00%		Result - AC
3		10		AC
(2.750000)	
3		11		AC
(0.270000)	
3		12		AC
(3.010000)	
3		13		AC
(3.210000)	
3		14		AC
(1.600000)	
Subtask Score: 60.00%		Result - AC	
		Total Score = 100.00%

[hyfun]

@unstoppable how do u get that i was facing problem as @rishi123y

[closed account 3UohqMoL]

@unstoppable can you share your code or algo please what modifications should i do or what approach you followed

[closed account 3UohqMoL]

Sub-Task Task # Result
(time)
1 1 AC
(0.020000)
1 2 AC
(0.020000)
Subtask Score: 5.00% Result - AC
2 3 AC
(0.010000)
2 4 AC
(0.000000)
Subtask Score: 15.00% Result - AC
3 5 AC
(0.010000)
3 6 AC
(0.020000)
Subtask Score: 20.00% Result - AC
4 7 AC
(0.060000)
4 8 AC
(0.060000)
4 9 AC
(0.050000)
4 10 AC
(0.060000)
4 11 AC
(0.060000)
Subtask Score: 60.00% Result - AC
Total Score = 100.00%

Yes Got it.