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

|

307 Discussions

|

  • alex_k5
     + 0 comments

    def twoPluses(grid):

    pl = []
result = 0
for i,j in product(range(len(grid)), range(len(grid[0]))):
    if grid[i][j] == 'G':
        pl2 = set()
        for k in range(0, len(grid)//2+1):
            if j-k<0 or j+k>len(grid[0])-1 or i-k<0 or i+k>len(grid)-1:
                break
            if grid[i][j-k] == grid[i][j+k] == grid[i-k][j] == grid[i+k][j] == 'G':
                pl2.update(((i,j-k),(i,j+k,),(i-k,j),(i+k,j)))
                pl.append(pl2.copy())
            else:
                break
for i in combinations(pl, 2):
    if not i[0] & i[1]:
        result = max(result, len(i[0])*len(i[1]))

return result

  • logan_schultheis
     + 0 comments

    Python3 solution:

    def twoPluses(grid):
    m, n = len(grid), len(grid[0])
    sets = []
    good = {(i,j) for (i,j) in product(range(m), range(n)) if grid[i][j] == "G"}
    for (i, j) in good:
        cur_set = {(i,j)}
        sets.append(cur_set)
        left, right = (i, j - 1), (i, j + 1)
        up, down = (i + 1, j), (i - 1, j)
        while True:
            if left not in good or right not in good:
                break
            if up not in good or down not in good:
                break
            for d in [left, right, up, down]:
                cur_set.add(d)
            sets.append(cur_set.copy())
            left, right = (left[0], left[1] - 1), (right[0], right[1] + 1)
            up, down  = (up[0] + 1, up[1]), (down[0] - 1, down[1])
    
    mx = 0    
    for c1, c2 in product(sets, sets):
        if not c1.intersection(c2):
            sz = len(c1) * len(c2)
            if sz > mx:
                mx = sz
    return mx

  • dhihanlaksanaaj1
     + 0 comments

    swift its long but solve all the test cases

    func calculatePossibleIndex(maxIndex: Int, median: Int, index: Int) -> Int {
    let factor = (index + median) / median
    let res = abs((((factor * median - median) * 2) - index) - (maxIndex % 2) * index / median)
    
    return res
}

func twoPluses(grid: [String]) -> Int {
    // Write your code here
    let grids: [[UInt8]] = grid.map{ [UInt8]($0.utf8) }
    let hIndexCount: Int = grids.first!.count - 1
    let vIndexCount: Int = grids.count - 1
    let hIndexMedian: Int = (hIndexCount / 2) + (hIndexCount % 2)
    let vIndexMedian: Int = (vIndexCount / 2) + (vIndexCount % 2)
    
    var isVerticalValid: Bool = false
    var isHorizontalValid: Bool = false
    var totalGridFound: [Int] = [Int]()
    var coordinates: [[Int]] = [[Int]]()
    var isNeedToCreateCoorBatch: Bool = true
    var possibleIndexes: [Int] = [Int]()
    var offset: Int = 0
    
    for vIndex in 1 ... vIndexCount - 1 {
        let vPossibleIndex: Int = calculatePossibleIndex(maxIndex: vIndexCount, median: vIndexMedian, index: vIndex)
        possibleIndexes.append(vPossibleIndex == 0 ? vIndex : vPossibleIndex)
        
        for hIndex in 1 ... hIndexCount - 1 {
                
            if grids[vIndex][hIndex] == 71 {
                possibleIndexes.append(calculatePossibleIndex(maxIndex: hIndexCount, median: hIndexMedian, index: hIndex) )
                offset = possibleIndexes.min()!
                
                while(offset >= 1) {
                    let minVIndex: Int = vIndex - offset
                    let maxVIndex: Int = vIndex + offset
                    let minHIndex: Int = hIndex - offset
                    let maxHIndex: Int = hIndex + offset
                        
                    // check vertical validity
                    for vIndexPossible in minVIndex ... maxVIndex { 
                        let multiplier: Int = hIndex > 9 ? 100 : 10                   
                        let coor: Int = vIndexPossible * multiplier + hIndex
                        if isNeedToCreateCoorBatch {
                            coordinates.append([coor])
                            isNeedToCreateCoorBatch = false   
                        } else {
                            coordinates[coordinates.count - 1].append(coor)
                        }
                        
                        if grids[vIndexPossible][hIndex] != 71 { break }

                        if vIndexPossible == maxVIndex {
                            isVerticalValid = true
                        }
                    }
                        
                    if !isVerticalValid { 
                        coordinates.popLast()
                        isNeedToCreateCoorBatch = true
                        offset -= 1
                        continue 
                    }
                    
                    // check horizontal validity
                    for hIndexPossible in minHIndex ... maxHIndex {
                        if hIndexPossible == hIndex { continue }
                        
                        let multiplier: Int = hIndexPossible > 9 ? 100 : 10
                        let coor: Int = vIndex * multiplier + hIndexPossible
                        coordinates[coordinates.count - 1].append(coor)
                        
                        if grids[vIndex][hIndexPossible] != 71 { break }
                                                
                        if hIndexPossible == maxHIndex {
                            isHorizontalValid = true
                        }   
                    }
                    
                    if isVerticalValid && isHorizontalValid {                        
                        totalGridFound.append(offset * 4 + 1)
                    } else {
                        coordinates.popLast()
                    }
                    
                    isNeedToCreateCoorBatch = true
                    offset -= 1
                }
                
                possibleIndexes.popLast()
                isVerticalValid = false
                isHorizontalValid = false    
            }
        }
        possibleIndexes.removeAll()
    }
    
    var highest: Int = 0
    var container: [Int] = [Int]()
        
    if totalGridFound.count == 0 {
        return 1
    }
    
    for index1 in 0 ... totalGridFound.count - 1 {
        for index2 in index1 ... totalGridFound.count - 1 {
            let candidates: [Int] = [totalGridFound[index1], totalGridFound[index2]]
            let total: Int = candidates.reduce(1) { $0 * $1 }
            if total > highest {
                container.append(contentsOf: coordinates[index1])
                container.append(contentsOf: coordinates[index2])
                let initialCount: Int = container.count
                container = Array(Set(container))
                if initialCount == container.count {
                    highest = total
                } 
                
                if initialCount != container.count && candidates.max()! > highest {
                    highest = candidates.max()!
                }
                container.removeAll()
            }
        }
    }
    
    return highest
}

  • jmcparland
     + 0 comments

    Haskell

    module Main where

import Control.Monad (replicateM)
import qualified Data.Map  as M
import qualified Data.Set  as S

type Center = (Int, Int)
type Radius = Int
type Plus = (Center, Radius)

goodcoords :: [[Bool]] -> S.Set Center
goodcoords = S.fromList . concat . zipWith (\i -> map (\(j, b) -> (i, j)) . filter snd . zip [0 ..]) [0 ..]

allplusses :: S.Set Center -> [Plus]
allplusses good = concatMap plusseshere goodList
  where
    goodList = S.toList good
    plusseshere :: Center -> [Plus]
    plusseshere c = go 0
      where
        go r =
          if all (\(dx, dy) -> S.member (fst c + dx, snd c + dy) good) [(0, r), (0, -r), (r, 0), (-r, 0)]
            then (c, r) : go (r + 1)
            else []

plusintersect :: Plus -> Plus -> Bool
plusintersect ((x1, y1), s1) ((x2, y2), s2) = do
  let set1 = S.fromList [(x1 + dx, y1 + dy) | (dx, dy) <- [(0, r) | r <- [-s1 .. s1]] ++ [(r, 0) | r <- [-s1 .. s1]]]
      set2 = S.fromList [(x2 + dx, y2 + dy) | (dx, dy) <- [(0, r) | r <- [-s2 .. s2]] ++ [(r, 0) | r <- [-s2 .. s2]]]
  not $ S.null $ S.intersection set1 set2

runmax :: [Plus] -> Int
runmax ps = go ps 0
  where
    go :: [Plus] -> Int -> Int
    go [] m = m
    go (p@(_, pr) : ps) m = do
      let qrs = [qr | q@(_, qr) <- ps, not (plusintersect p q)]
      case qrs of
        [] -> go ps m
        _ -> go ps (max m ((4 * pr + 1) * (4 * maximum qrs + 1)))

solve :: [[Bool]] -> Int
solve = runmax . allplusses . goodcoords

main :: IO ()
main = do
  [n, m] <- map read . words <$> getLine :: IO [Int]
  grid <- replicateM n $ do map (== 'G') <$> getLine
  print $ solve grid

  • mikesboyle
     + 0 comments

    I started out thinking I could simply go through each good cell and compute the biggest plus I could make with that cell as its center. While doing this, I tracked the largest two areas seen, then finally returned the product of those two values.

    This doesn't work for two reasons:

    1. We cannot count two pluses if they have overlapping cells
    2. We have to consider not only the LARGEST plus you can make from a given center, but any possible smaller sized plus.

    The second case might happen if you have a 9-area plus and a 13-area plus that overlap. But inside the 13-area plus is a smaller 9-area plus that doesn't overlap with the other 9-area plus. Those two pluses might turn out to be the two largest ones in the grid.

    So the approach looks more like this:

    1. Create a pluses array to hold all of the pluses you find.
    2. For each good cell, try to make pluses of size 1, 5, 9, 13, 17, ... etc. using that cell as the center. Each time you find a plus, copy its cell coordinates into a set and save that set in pluses.
    3. You now have a large array of pluses, each one represented as a set of coordinates.
    4. Set a value for the maximum product found so far to zero.
    5. Iterate through every possible pair of pluses. If the product of their lengths is greater than the maximum found so far, check if the pluses are overlapping. (In Python, you can check if two sets overlap by finding their intersection; if they overlap, len(set1 & set2) > 0.) If they don't overlap, update the maximum product found so far.