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) ?
I just inserted a clock function around my
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
I have the same problem :s too much recursion
Yeah. I solved this by turn recursion to loops
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.
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’