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.
  1. Prepare
  2. Algorithms
  3. Implementation
  4. Ema's Supercomputer
  5. Discussions

Ema's Supercomputer

Sort by

recency

|

326 Discussions

|

  • aliraza413063321
     + 0 comments

    Emergency Locksmith provides fast and reliable solutions when you’re locked out of your home, office, or car. Available 24/7, skilled professionals handle urgent lock repairs, key replacements, and security upgrades with precision and care. Just like Ema’s Supercomputer delivers power and efficiency in advanced computing, Emergency Locksmith ensures quick, intelligent, and effective responses to your lock emergencies, restoring safety and peace of mind when you need it most.

  • anarod_val25
     + 0 comments

    Respectfully, this problem is not "medium", it's freaking hard! (ಥ﹏ಥ)

    Heres is my c++ solutions, hope is helps someone.

    struct Plus {
    int area;
    vector<pair<int,int>> cells;
};

vector<Plus> allPlussesAt(int y, int x, const vector<string>& grid) {
    vector<Plus> result;
    if (grid[y][x] != 'G') return result;

    int arm = 0;
    int rows = grid.size(), cols = grid[0].size();

    while (y-arm >= 0 && y+arm < rows &&
           x-arm >= 0 && x+arm < cols &&
           grid[y-arm][x] == 'G' &&
           grid[y+arm][x] == 'G' &&
           grid[y][x-arm] == 'G' &&
           grid[y][x+arm] == 'G') {
        
        vector<pair<int,int>> cells;
        cells.push_back({y,x});
        for (int k=1; k<=arm; k++) {
            cells.push_back({y-k,x});
            cells.push_back({y+k,x});
            cells.push_back({y,x-k});
            cells.push_back({y,x+k});
        }
        
        result.push_back({1 + 4*arm, cells});
        arm++;
    }

    return result;
}

vector<Plus> allPlusses(const vector<string>& grid) {
    vector<Plus> plusses;
    for (int y=0; y<grid.size(); y++) {
        for (int x=0; x<grid[0].size(); x++) {
            auto p = allPlussesAt(y, x, grid);
            plusses.insert(plusses.end(), p.begin(), p.end());
        }
    }
    return plusses;
}

bool overlap(const Plus& a, const Plus& b) {
    for (auto &cellA : a.cells) {
        for (auto &cellB : b.cells) {
            if (cellA == cellB) return true;
        }
    }
    return false;
}

int maxPlusAreaAt(int y, int x, const vector<string>& grid) {
    if (grid[y][x] != 'G') return 0;

    int arm = 0;
    int rows = grid.size(), cols = grid[0].size();

    while (y-arm >= 0 && y+arm < rows &&
           x-arm >= 0 && x+arm < cols &&
           grid[y-arm][x] == 'G' &&
           grid[y+arm][x] == 'G' &&
           grid[y][x-arm] == 'G' &&
           grid[y][x+arm] == 'G') {
        arm++;
    }
    arm--; 
    
    return 1 + 4*arm;
}

int twoPluses(vector<string> grid) {
    vector<Plus> plusses = allPlusses(grid);

    int best = 0;
    for (int i=0; i<plusses.size(); i++) {
        for (int j=i+1; j<plusses.size(); j++) {
            if (!overlap(plusses[i], plusses[j])) {
                best = max(best, plusses[i].area * plusses[j].area);
            }
        }
    }

    return best;
}

  • saminazubair93
     + 0 comments

    MY SOLUTION IN PHP

      $totalrow = count($grid);
    
    $columnArr = array();
    $allIndex = array();

    for ($i=0; $i <$totalrow ; $i++) { 
         $arr = str_split($grid[$i]);
         $columnArr[]  = $arr;
    }
    $columnLength = count($columnArr[0]);


    for ($i=1; $i < $totalrow-1; $i++) { 

        for ($j=1; $j <$columnLength-1 ; $j++) { 
            $rowis = $i+1;
            $columnIs = $j+1;
            
            $down = $totalrow-$rowis;
            $up = $totalrow - ($down +1);
            $right = $columnLength - ($columnIs);
            $left = $columnLength - ($right+1);
            $min = min($down,$up,$right,$left);
            
            
            for ($k=$min; $k >0 ; $k--) { 
                
                 $totalValue = 0;
                 $flag = 0;
                 $indexArr = array();
                 $innerArr = array();
                 for ($l=0; $l <$k; $l++) { 
                     
                     
                      $val = $l+1;
                      $newupRow = $rowis -$val-1;
                      $newDownRow = $rowis+$val-1;
                     
                      $columnUpValue = $columnArr[$newupRow][$columnIs-1];
                     

                      $columnDownvalue = $columnArr[$newDownRow][$columnIs-1];
                     

                     
                      $colLeft = ($columnIs-1)-($l+1);
                       $columnLeftValue = $columnArr[$rowis-1][$colLeft];
                      

                       $colRight = ($columnIs-1)+($l+1);
                        $columnRightValue = $columnArr[$rowis-1][$colRight];
                     

                       if($columnUpValue === 'G' && $columnDownvalue === 'G' && $columnLeftValue === 'G' && $columnRightValue === 'G' && $columnArr[$i][$j] === 'G' && $l === 0 )
                        {
                            $flag = 1;
                            $totalValue+= 4;
                       
                         $innerArr[] =$newupRow.','.$columnIs-1;
                         $innerArr[] =$newDownRow.','.$columnIs-1;
                         $innerArr[] =($rowis-1).','.$colLeft;
                         $innerArr[] =($rowis-1).','.$colRight;
                         $innerArr[] =$i.','.$j;

                        }
                        else if($columnUpValue === 'G' && $columnDownvalue === 'G' && $columnLeftValue === 'G' && $columnRightValue === 'G'  && $columnArr[$i][$j] === 'G' && $flag === 1 )
                        {
                            $flag = 1;
                            $totalValue+= 4;
                        
                        $innerArr[] =$newupRow.','.$columnIs-1;
                         $innerArr[] =$newDownRow.','.$columnIs-1;
                         $innerArr[] =($rowis-1).','.$colLeft;
                         $innerArr[] =($rowis-1).','.$colRight;
                       
                       
                        }
                         else
                        {
                            break;
                        }

                       if(count($innerArr)>0)
                       {
                            $indexArr[] = $innerArr;

                       } 


                 }
                
                
                   if(count($indexArr)>0)
                       {
                            $allIndex[] = $indexArr;

                       } 
                  
                


            }
            
        }

        
    }


 
    

$result = array();
foreach ($allIndex as $outer) {
    foreach ($outer as $inner) {
        $result[] = $inner;
    }
}
    

    $unique = [];
foreach ($result as $sub) {
    $temp = $sub;
    sort($temp);                
    $key = json_encode($temp);  
    $unique[$key] = $sub;    
}


$result = array_values($unique);


$resultLen = count($result);

$ans = 0;
if ($resultLen == 1) {
    $ans = count($result[0]);
}
else
{
    $productArray = [];
for ($i=0; $i < $resultLen-1; $i++) { 
    
    $first = $result[$i];
    $firstLen = count($first);
    
     for ($j=$i+1; $j < $resultLen ; $j++) { 
        $second = $result[$j];
        $secondLen = count($second);

        $common = array_intersect($first, $second);

        if (!empty($common)) {
            $productArray[] = max($firstLen,$secondLen);
          
        } else {
            $secondLen = count($second);
            $productArray[] = $firstLen*$secondLen;
           
        }

     }
}

$ans = count($productArray) > 0 ? max($productArray) : 1;

}

return $ans;

  • wifivop476
     + 0 comments

    If you fail only a few cases, consider smaller size pluses with the same center, as they might not overlapse while the biggest one does. Also, you might be curious about how much pearls are worth when selecting decorative elements for your design.

  • shashikanth8639
     + 0 comments

    Since the input size is very small, we can use brute force approach:

    TLDR:

    1. for each G point, traverse in all four directions setp by step (ex: at step 2 you visit all the points which are at dist. 2 in all directions) till all the points in the step are valid G points and collect them at each step

    2. sort them based on len in desc order, then check for all the combinations of such non overlapping plus points and find the max aread

    CODE

    def twoPluses(grid):
    # Write your code here
    n,m = len(grid), len(grid[0])
    g_points = []
    pluses = []
    
    for i in range(n):
        for j in range(m):
            if grid[i][j] == 'G': 
                g_points.append((i, j))
                pluses.append({(i, j)})
    
    def getPluses(i, j):
        cur_plus = {(i, j)}                
        for k in range(1, min(n-i, m-j, i+1, j+1)):
            points = ((i-k, j), (i+k, j), (i, j-k), (i, j+k))
            for x,y in points:
                if grid[x][y] != 'G': 
                    return
            cur_plus.update(points)
            pluses.append(cur_plus.copy())
    
    for i,j in g_points:
        getPluses(i, j)
                    
    pluses.sort(key=len, reverse=True) 
    
    def getRes(pluses):
        res = -1
        for i in range(len(pluses)):
            for j in range(i+1, len(pluses)):
                if len(pluses[i].intersection(pluses[j])) == 0:
                    res = max(res, len(pluses[i])*len(pluses[j]))
        return res
				`
    
    return getRes(pluses)

    Initial thoughts:

    Approach 1:

    1. start at each G point

    2. traverse in all four directions at once (mark G to say -1 to identify as visited, so that there won't be any intersection with others)

    3. now we have lenghts of all such pluses

    4. find the top two and do product. Either sort the lenghts array or use heap and maintain only top two

    Flaws with this approach:

    Future G point, might need the current one (as it can be in the plus path of future G) since we are marking as -1, this will be ignored and we might loose the longest plus

    Approach 2:

    Okay, so what if we try to find the pluses that can be formed from each G point? find the top two such set of points without any intersection

    1. find all the G points

    2. from each G point, traverse in all the directions, collect all the points

    3. sort the collection of points based on length, find top two with zero intersection and do a product of it

    Flaws:

    x = max(side of plus you can reach in all 4 directions), area = 4*x +1 ex: x=2, area = 4*2+1 = 9 say pluses of x=2 & x=3 are next to each other with one overlapping G point, then maxArea = area(3)*1 (as there is no other plus points) = 13 but if we somehow make x=3 to take only two G's in all directions? then maxArea = area(x=2)*area(x=2) = 81

    Approach 3:

    So now instead of considering only the points in the max plus path of each g point, consider all the plus points for each length.

    Ex: for x=3, we will have in total of 4 collections points while going thorugh the directions, i.e start from x = 0 --> x=1 --> x=2 --> x=3 for a given G point

    Now for x=2 & x=3 points, we have 0,1,2 & 0,1,2,3 lengths of collection points for each G point. Now sort the collection of plus points, find max among all the given pairs (not just top two non intersection points, as 2x1 & 3x2 can have intersection, then top two aread will become 1x1 * 3x2, but max is 2x1 *2X2)