We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Ema's Supercomputer
  5. Discussions

Ema's Supercomputer

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 260 Discussions, By:

votes

Please Login in order to post a comment

  • ShanWei
    5 years ago+ 13 comments

    pass all test after 5 times submission...always struggling with brute force and trying to go a smart way. Finnaly, brute force wins.

    39|
    Permalink
    View more Comments..
  • gregianh
    6 years ago+ 5 comments

    Hope this could help for those who get stucked :). Sorry if my english sucks and the approach is not so optimal.

    I think it is easier to solve this problem through table. First, set the BAD cell with -1. For the sample input :

    6 6 BGBBGB GGGGGG BGBBGB GGGGGG BGBBGB BGBBGB

    will be as -1 0 -1 -1 0 -1
    0 0 0 0 0 0
    -1 0 -1 -1 0 -1
    0 0 0 0 0 0
    -1 0 -1 -1 0 -1
    -1 0 -1 -1 0 -1

    we know that it is impossible that the border has any pluses so we start from cell (1,1) until cell (row-1,col-1). In each cell we must find the distance from this cell to the blocked cell ( or border) in 4 directions : top, bottom, left, and right. Take the SMALLEST one and that will be the LENGTH of that cell to make the plus : length to the top, bottom, left, and right. That cell is the CENTER of a plus. The AREA from that plus is equal to (LENGTH*4)+1. From the sample input, the table is like :

    -1 0 -1 -1 0 -1
    0 1 0 0 1 0
    -1 0 -1 -1 0 -1
    0 1 0 0 1 0
    -1 0 -1 -1 0 -1
    -1 0 -1 -1 0 -1

    The cell with value 1 can make a plus with area of (1*4)+1=5

    And now the Bruteforce time because we don't know which combination will have the biggest product. We assume that if we take a plus, that plus will block the cell and thus can't be used to make another plus...so recalculate the LENGTH from each cell. For example we find that the first cell (1,1) has LENGTH of 1. We assume that this is our FIRST PLUS that can create the maximal product and we need to find the other pair. But it can't be overlapped by the other plus. So first we blocked the cell

    -1 -1 -1 -1 0 -1
    -1 -1 -1 0 1 0
    -1 -1 -1 -1 0 -1
    0 1 0 0 1 0
    -1 0 -1 -1 0 -1
    -1 0 -1 -1 0 -1

    The table is now not valid anymore. So after recalculate using the same approach like the first time we get :

    -1 -1 -1 -1 0 -1
    -1 -1 -1 0 1 0
    -1 -1 -1 -1 0 -1
    0 0 0 0 1 0
    -1 0 -1 -1 0 -1
    -1 0 -1 -1 0 -1

    This is the second valid table and now we just need to search which one together with the FIRST PLUS could make the maximal product. In the table there are still 2 '1', so this 2 could result both (1*4)+1=5. Before we have plus with area of 5. So the maximal Area we got from the first try is 25. There are still 3 more tries : cell (3,1) as first plus, cell (1,4) as first plus, and cell (3,4) as first plus. Repeat the step to find the second plus. In this cases no matter if the first plus is (1,1) or (1,4) or (3,1) or (3,4), all give the maximal value of 25. So the biggest product is 25.

    This approach seems to be so slow. But it can solve this problem which table has the maximal length of 12x12.

    PS : For the most complex case with table 12x12 and all cell is good, the biggest product is 221 :)

    33|
    Permalink
    View more Comments..
  • zhadyrassyn
    5 years ago+ 4 comments

    After 7 submission finally got it =) My hint: 1) do not overlap pluses 2) you have to get the MAXIMUM PRODUCT so that it means getting MAXIMUM for 1 plus and getting MAXIMUM for 2 plus may not give you MAXIMUM PRODUCT

    13|
    Permalink
    View more Comments..
  • kamal_mukhija
    6 years ago+ 4 comments

    Finally Done.

    Took lot of time.

    12|
    Permalink
    View more Comments..
  • Rys23
    5 years ago+ 7 comments

    My Java8 solution

    public class Solution {
    
        static class Plus {
            int x;
            int y;
            int len;
            int size;
            
            Plus(int x, int y) {
                this.x = x;
                this.y = y;
                this.len = 0;
                this.size = 1;
            }
            
            Plus(int x, int y, int len, int size) {
                this.x = x;
                this.y = y;
                this.len = len;
                this.size = size;
            }
            
            void grow() {
                this.len++;
                this.size += 4;
            }
            
            boolean overlaps(Plus p2, int r, int c) {
            
                if(this.x != p2.x && this.y == p2.y) {
                    if(p2.x >= this.x - this.len && 
                       p2.x <= this.x + this.len ||
                       p2.x < this.x - this.len && 
                       p2.x + p2.len >= this.x - this.len ||
                       p2.x > this.x + this.len && 
                       p2.x - p2.len <= this.x + this.len)
                        return true;                
                }
                
                if(this.y != p2.y && this.x == p2.x) {
                    if(p2.y >= this.y - this.len && 
                       p2.y <= this.y + this.len ||
                       p2.y < this.y - this.len && 
                       p2.y + p2.len >= this.y - this.len ||
                       p2.y > this.y + this.len && 
                       p2.y - p2.len <= this.y + this.len)
                        return true;
                }
                
                boolean[][] grid = new boolean[r][c];
                
                for(int i = this.x - this.len; i <= this.x + this.len; i++) 
                    grid[this.y][i] = true;
                for(int i = this.y - this.len; i <= this.y + this.len; i++)
                    grid[i][this.x] = true;
                
                for(int i = p2.x - p2.len; i <= p2.x + p2.len; i++) {
                    if(grid[p2.y][i] == true)
                        return true;          
                }
                for(int i = p2.y - p2.len; i <= p2.y + p2.len; i++) {
                    if(grid[i][p2.x] == true)
                        return true;             
                }
                return false;
            }
        } 
        
        static void findPlus(int x, int y, int r, int c, String[] grid, ArrayList<Plus> list) {
            Plus plus = new Plus(x, y);
            int s = 1;
            while(y-s >= 0 && grid[y-s].charAt(x) != 'B' &&
                  y+s < r && grid[y+s].charAt(x) != 'B' &&
                  x-s >= 0 && grid[y].charAt(x-s) != 'B' &&
                  x+s < c && grid[y].charAt(x+s) != 'B') {
                list.add(new Plus(plus.x, plus.y, plus.len, plus.size));
                plus.grow();
                s++;
            }
            list.add(plus);
        }
        
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int r = sc.nextInt();
            int c = sc.nextInt();
            sc.nextLine();
            String[] grid = new String[r];
            ArrayList<Plus> list = new ArrayList<Plus>();
            
            for(int y = 0; y < r; y++) {
                grid[y] = sc.nextLine();
            }
            
            for(int y = 0; y < r; y++) {
                for(int x = 0; x < c; x++) {
                	if(grid[y].charAt(x) != 'B')
                        findPlus(x, y, r, c, grid, list);
                }
            }        
            
            int max = 0;
            for(int i = 0; i < list.size()-1; i++) {
                Plus p1 = list.get(i);
                for(int j = i+1; j < list.size(); j++) {
                    Plus p2 = list.get(j);
                    int sum = p1.size * p2.size; 
                    if(sum > max && !p1.overlaps(p2, r, c)) {
                        max = sum;
                    }  
                }
            }
            System.out.println(max);
        }
    }
    
    11|
    Permalink
    View more Comments..
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature