Автор, розробник, автор розбору: Ілля Пермяков
Побачимо, що суму усіх чисел в матриці можна виразити як r_1 + r_2, або c_1 + c_2. Якщо ці дві суми не збігаються, то відповіді не існує, в іншому випадку можна завжди побудувати відповідь наступним чином:
Нехай x = T_{1,1}. Тоді:
T_{1, 2} = r_1 - x.
T_{2, 1} = c_1 - x.
T_{2, 2} = r_2 - T_{2, 1} = r_2 - c_1 + x.
Для того щоб усі елементи були невід'ємними, має виконуватись наступне:
T_{1, 1} \geq 0 \Rightarrow x \geq 0.
T_{1, 2} \geq 0 \Rightarrow r_1 - x \geq 0.
T_{2, 1} \geq 0 \Rightarrow c_1 - x \geq 0.
T_{2, 2} \geq 0 \Rightarrow r_2 - c_1 + x \geq 0.
Звідси видно, що для відновлення рішення, можна встановити x = min(r_1, c_1, r_2 - c_1), а потім, за допомогою , відновити усі інші елементи матриці.