JOIN
 Select a Forum     Round Tables New Member Discussions News Discussions Algorithm Matches Marathon Matches NASA Tournament Lab TopCoder Cookbook High School Matches Sponsor Discussions Development Forums Design Forums Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings View: Flat (newest first)  | Threaded  | Tree Forums Algorithm Matches SRM 212 LargestCircle
 LargestCircle | Reply After wrecking my brains trying to solve this problem for a while, I decided to try out the solution outlined in the editorialBut this approach doesn't seem to work for me, can anybody please point out the bug in this code:```public int radius(String[] grid) { int height = grid.length; int width = grid[0].length(); int maxRadius = Math.min(height/2, width/2); for (int r = maxRadius; r >= 1; r--) for (int cx = r; cx >= width - r; cx--) for (int cy = r; cy >= height - r; cy--) for (int x = 0; x < height; x++) for (int y = 0; y < width; y++) { int c1 = Math.abs(cx - x); int c2 = Math.abs(cx - x - 1); int c3 = Math.abs(cy - y); int c4 = Math.abs(cy - y - 1); int min = Math.min(c1,c2)*Math.min(c1,c2) + Math.min(c3,c4)*Math.min(c3,c4); int max = Math.max(c1,c2)*Math.max(c1,c2) + Math.max(c3,c4)*Math.max(c3,c4); if (min < r && max > r) continue; if (grid[x].charAt(y) == '#') return r; } return 0; } ```Any kind of help will be greatly appreciated.
 Re: LargestCircle (response to post by shalinmangar) | Reply This looks wrong to me:``` for (int cx = r; cx >= width - r; cx--) for (int cy = r; cy >= height - r; cy--) ```if r<=min(floor(width/2),floor(height/2))then r<=width/2and width-r >= r, so you should increment cx, not decrement:``` for (int cx = r; cx <= width - r; cx++) for (int cy = r; cy <= height - r; cy++) ```Haven't looked at the remainder of the solution...
 Re: LargestCircle (response to post by shalinmangar) | Reply ```if (min < r && max > r) ```should be```if (min >= r*r || max <= r*r ) ```
 Re: LargestCircle (response to post by shalinmangar) | Reply Seven years later! :Dfor new users like me :)```class LargestCircle { public: int radius(vector ); };   int LargestCircle::radius(vector grid) { int height = grid.size(); int width = grid[0].length(); int maxRadius = min(height/2, width/2); bool flag;   for(int r = maxRadius; r >= 1; r--) { for(int cx = r; cx <= height - r; cx++) { for(int cy = r; cy <= width - r; cy++) { flag = 1; for(int x = 0; x < height; x++) { for(int y = 0; y < width; y++) { int c1 = abs(cx - x); int c2 = abs(cx - x - 1); int c3 = abs(cy - y); int c4 = abs(cy - y - 1); int m1 = min(c1,c2)*min(c1,c2) + min(c3,c4)*min(c3,c4); int m2 = max(c1,c2)*max(c1,c2) + max(c3,c4)*max(c3,c4); if (m1 >= r*r || m2 <= r*r) continue; if (grid[x][y] == '#') { flag = 0; goto A; } } } if(flag == 1) return r; A:; } } } return 0; } ```
 Re: LargestCircle (response to post by ImanAkbari) | Reply Another five years later!I was able to solve this problem, not in O(n^^4) time, but in just above O(n) time. Please see my solution on my github site and provide feedback:https://github.com/stevenlinzer/InterviewPracticeThank you.
 Forums Algorithm Matches SRM 212 LargestCircle