Блог

Я работаю над задачей HackerRank, которая заключается в нахождении наибольшей суммы элементов в верхнем левом квадранте матрицы 2N x 2N после обращения строк и столбцов. Например, если матрица равна

 M = [
  112  42   83   119
  56   125  56   49
  15   78   101  43
  62   98   114  108
];
  

тогда наибольшая сумма, которая может быть сформирована из обращения строк и столбцов, 119 114 56 125 = 414 после получения матрицы

 M' = [
   119  114  42   112
   56   125  101  49
   15   78   56   43
   62   98   83   108
];
  

из изменения столбца 2, а затем строки 0.

Я не нашел простого решения, но я пришел к некоторым фактам, которые могут быть полезны:

• Не возможно получить какую-либо конфигурацию из обращения строк и столбцов. Следовательно, ответом не может быть простая сортировка всех элементов и суммирование верхнего NxN из них.
• Кроме того, невозможно переместить любой 1 элемент в любую другую позицию. Например, единственными возможными местами перемещения элемента в (N-1,N-1) являются (0,N-1), (N-1,0), (0,0).
• Требуется 1 обращение строки, чтобы получить элемент из верхнего правого или нижнего левого квадранта в верхний левый квадрант, и 2 обращения, чтобы получить элемент из нижнего правого квадранта в верхний левый квадрант.
• Невозможно придумать решение, которое просто просматривает каждый элемент в верхнем левом квадранте и проверяет, может ли он быть заменен более крупным элементом в диапазоне элементов, которые могут быть перемещены на его место (например, M[0,1]=42 может быть заменен на M[0,2]=83 или M[3,2]=114 или M[3,1]=98 ), потому что вы должны также учитывать другие элементы, которые перетаскиваются в процессе.

Кроме этих фактов, я не могу придумать ничего, что помогло бы мне построить простое решение. Есть ли какой-либо очевидный факт, который я упускаю? Я не спал за полночь, думая об этом прошлой ночью. 🙂

Давайте развиваем ваше наблюдение о том, что элемент (N - 1, N - 1) может находиться только в (0, 0) , (N - 1, 0) или (0, N - 1) позиции.

• Рассмотрим (r, c) элемент. Можно заметить, что она может находиться только в одной из следующих четырех позиций: (r, c), (N - r - 1, c), (r, N - c - 1) или (N - 1 - r, N - 1 - c)

• Можно показать, что всегда существует последовательность операций, которая помещает наибольшее из четырех чисел, расположенных в вершинах описанного выше прямоугольника, в верхний левый квадрант без изменения остальной его части (чтобы доказать это, можно просто рассмотреть все случаи и предоставить явную конструкцию для этого. Это довольно длинно, но просто, поэтому я не буду публиковать это здесь).

• Эти два наблюдения дают следующее решение:

   int sum = 0;
  for (int i = 0; i < n / 2; i  )
      for (int j = 0; j < n / 2; j  )
          sum  = max(a[i][j], a[i][n - j - 1], a[n - i - 1][j], a[n - i - 1][n - j - 1]); 
    

найдите максимальное значение суммы значений ячеек в верхнем левом квадранте для квадратной матрицы.

Ключевым моментом здесь является то, что каждая ячейка в квадратной матрице может быть заменена только на 3 другие ячейки (путем обращения строки или столбца — путем транспонирования матрицы, обращения строки вспять и затем повторного транспонирования), следовательно, чтобы вычислить (без изменения матрицы) максимальное значение верхнего левого квадранта, нам нужно только вычислить максимально возможное значение для каждой ячейки в верхнем левом квадранте.

1. В (двойном) цикле ‘for’:

• сканирование ячеек верхнего левого квадранта,
• для каждой ячейки, сравнивая ее значение с другими 3-мя доступными для замены значениями.
• использование ‘//’ для получения int (‘/’ даст значение с плавающей точкой)

2. В следующем коде ‘Sum = ..’:

• Мы можем добавить значение текущей ячейки [i, j] (из верхнего левого квадранта) к сумме,
• или добавьте другое значение ячейки для любой ячейки, которую можно заменить на [i, j] внутри матрицы.
• Любая ячейка в квадратной матрице может быть заменена только на 3 другие ячейки,
• следовательно, мы выбираем максимальное значение между самой ячейкой и остальными 3.

 def maxSum(mat):
    R = C = len(mat)
    Sum = 0

    for i in range(0, R // 2):
        for j in range(0, C // 2):
            r1, r2 = i, R - i - 1
            c1, c2 = j, C - j - 1

            Sum  = max(mat[r1][c1], mat[r1][c2],
                       mat[r2][c1], mat[r2][c2])

    return Sum


# Testing
if __name__ == "__main__":
    mat = [[112, 42, 83, 119],
           [56, 125, 56, 49],
           [15, 78, 101, 43],
           [62, 98, 114, 108]]

    print(maxSum(mat))  # 414
    exit()
  

В случаях, когда на ум не приходит никаких сокращений, всегда можно делегировать. Не только для пользователей stackoverflow, но и для центрального процессора. Т.е. поиск методом перебора. Для этой маленькой матрицы работает грубая сила — учитывая глубину 4, этого уже более чем достаточно, и учитывая, что коэффициент ветвления дерева равен (2 * N) где N — количество строк и столбцов соответственно. (N строк могут быть обращены вспять и N столбцов.)

Здесь, для матрицы 4×4 в вопросе, соответствующее решение:

 let data = 
    let values = 
        [|
            112;  42 ;  83;   119;
            56 ;  125;  56;   49;
            15 ;  78 ;  101;  43;
            62 ;  98 ;  114;  108
        |]
    Array2D.init 4 4 (fun r c -> values.[4 * r   c])

let upperQuadrantSum (m : int[,]) = 
    [ for r in 0..1 do for c in 0..1 do yield (r,c) ]
    |> List.sumBy (fun (r,c) -> m.[r,c])

let reverseRow row (m : int[,])  =
    Array2D.init 4 4 (fun r c -> if r = row then m.[r,3-c] else m.[r,c])
let reverseCol col (m : int[,]) =
    Array2D.init 4 4 (fun r c -> if c = col then m.[3-r,c] else m.[r,c])

let possibleActions = 
    [   reverseRow 0; reverseRow 1; reverseRow 2; reverseRow 3; 
        reverseCol 0; reverseCol 1; reverseCol 2; reverseCol 3; 
    ]

let maximize metric maxDepth m0 =
    let rec search depth m =
        let value = metric m
        if depth = maxDepth 
        then value
        else
            possibleActions 
            |> List.map (fun a -> let m1 = a m in max (metric m1) (search (depth 1) m1))
            |> List.max
            |> fun msearch -> max value msearch
    search 0 m0

let solve = maximize upperQuadrantSum
  

В fsi выдача:

решите 7 данных;;
значение: int = 414

Конечно, как указано в другом ответе, как только на ум приходит оптимизация, неплохо иметь решение методом перебора, чтобы убедиться, что оба дают одинаковый результат:

 let inline solve1 m = 
    let n = Array2D.length1 m
    let candidates r c =
        [ r,c ; n-1-r,c ; r,n-1-c ; n-1-r,n-1-c ]
    [
        for r in 0..n/2-1 do
            for c in 0..n/2-1 do
                yield (candidates r c |> List.map (fun (r,c) -> m.[r,c]) |> List.max)
    ] |> List.sum

solve1 data
  

Извините, что не пишу код на C #, но файл .fsx и fsi намного проще, чем создать другое приложение на C #…

СМЕХОТВОРНО! Я много раз терпел неудачу в этой задаче, пытаясь придумать алгоритм для решения всех путей к решению (своего рода хитрые инструкции). Вот мой способ решить эту проблему:

 #Turn it into numpy for maximum pleasure
matrix=np.array(matrix)

#Measure its leangth
l=len(matrix)
ml=int(l/2)

#Move throught the four "corners" or "the-only-four-places-where-you-can-find-the-maximum-of-each-quadrant's-element"
max_vals = 
    [
        max(
            matrix[i,j],
            matrix[i,-(j 1)], 
            matrix[-(i 1),j],
            matrix[-(i 1),-(j 1)]
        )
        for j in range(ml)
        for i in range(ml)
    ]

#Return the sum of values
sum(max_vals)