I used Java and saved all sets, each of which contains indices of the same lake. When finding the area of the lake given a cell, I simply searched the set the cell is in and returned the size of the set. When constructing the sets, I tracked flooded and to-flood cells. I did not encounter issues with the approach.
Iām having issue on C# for the validation of the large tests
Actually the code below timeouts.
If I canāt increment an integer 1 000 000 times I donāt really know how Iām supposed to read a 1000 x 1000 table, any clues ?
for (int i = 0; i < H; i++)
{
//if (i % 10 == 0)
//Console.Error.WriteLine(i + ā/ā +H);
string row = Console.ReadLine();
var cpt = 0;
for (int j = 0; j < row.Count(); j++)
{
}
}
The default code does not timeout for any test-cases. And the puzzle is solvable in C# too.
row.Length is better than row.Count btw.
Thank you I had overlooked that
Much easier when parsing the input in n^2 than n^3 
Hey coders !
Just for my information, how long does your implementation takes for #9 test (large map, large lake) ?
My classical flood algorithm in JavaScript took 64ms Iām sure compiled langages are even better, but Iād like to know.
I just inserted a clock function around my main() function
Reading the input and everything took 53.386002 ms in C++
Iām processing the map into āstart, endā pairs on input to detect runs. This makes the subsequent searches much easier, as well as drastically reducing the memory footprint for the larger tests. I havenāt timed it, but it should be quite fast.
Unfortunately, even though my code passes all of the IDE tests (including the āall lakeā test), it consistently fails the āNo landā test on submission. Is that likely to be a validator bug?
The whole program takes 3.855 ms in Lua (according to a call to os.clock() right at the end).
Taking 53ms in C++ suggests a very suboptimal algorithmā¦
Doing it in C# and getting 80%. I fail the cases with 100+ tiles on a 1000x1000 board because I get a File Not Found exceptionā¦ could not load file or assembly āSystemā. Sounds like a bug (maybe a different exception is getting masked or something) but I wanted to ask about it here before posting on the bugs forum. Has anyone seen this before?
ā¦and trying the same code one day later, it all worked. Definitely a bug, but I guess a temporary one.
It seems need solved with the Loops, because with recursion I got always 80%,and have stack overflows at last test 
1 Like
I have the same problem :s too much recursion
Yeah. I solved this by turn recursion to loops
1 Like
Thank you ! I I have just ended it with loop. I never had rewritten a recursive algorithm to an iterative one, itās a good exercice.
1 Like
Agree. Itās a good exercice.
This a great problem ! It made me learn a lot about the performance considerations related to data structure (Set, List, Array) and optimization of the flood algorithm.
Iām using Scala (would be similar in Java) and tuning the code with jvisualvm really helped me identify performance bottlenecks such as :
- computing hashes to insert a point in a Set (which is not required)
- concatenation time of Arrays (Vector in Scala)
Unfortunately, even though my code passes all of the IDE tests (including the āall lakeā test), it consistently fails the āNo landā test on submission.
I have the same problem here. How is this āNo landā test even looks like? I guess itās some weird input and not even related to the actual algorithm, but validator doesnāt give enough feedback to figure it out.
No land? There is only water.
How is that different from āAll area is a lakeā which I pass?
Maybe they differ in size. Are you saving the value you calculate for a lake? Maybe the no Land Test just test a bunch of points, all in the same lake, and your algorithm is recalculating it and receiving TLE.
Edit: Just saw your post was from Mar 30. Well hope it helps someone anyways n_nā