PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Allen
Testers: Abhinav Sharma, Venkata Nikhil Medam
Editorialist: Nishank Suresh
DIFFICULTY:
2923
PREREQUISITES:
Greedy algorithms, observation
PROBLEM:
There are N events and M participants competing in them. The j-th participant scored A_{i, j} in the i-th event.
For a fixed subset S of events, its differentiation is defined as follows:
- First, the score of the j-th participant is s_j = \sum_{x \in S} A_{x, j}
- Then, the differentiation is \max_{i=1}^M (\sum_{j=1}^M |s_i - s_j|)
Find the maximum possible differentiation across all possible subsets of events.
EXPLANATION:
First, let us analyze the formula for differentiation. Say a set S of events has been fixed, and we compute the scores s_1, s_2, \ldots, s_M. Without loss of generality, s_1 \leq s_2 \leq \ldots \leq s_M.
What is the differentiation in this case?
Answer
It is either (s_1 - s_1) + (s_2 - s_1) + \ldots + (s_M - s_1) or (s_M - s_1) + (s_M - s_2) + \ldots + (s_M - s_M). That is, if X = s_1 + s_2 + \ldots + s_M, then the differentiation is the larger of X - M\cdot s_1 and M\cdot s_M - X.
This tells us the following: given any subset, its differentiation is decided by either its largest score or its smallest score.
Now we have something else to work with. Instead of fixing the subset of events chosen, let us fix the person with minimum score, and calculate the maximum possible differentiation that can be achieved with this person as the minimum. Similarly, we can compute the maximum possible differentiation assuming the person has the highest score. Knowing these two values for everyone, the final answer is simply the maximum of all of them.
So, fix a person j. We want to compute the maximum possible differentiation assuming this person has the minimum score (the case where they have the maximum score can be computed similarly). This can be done as follows:
How?
Recall that the formula for differentiation when s_j is the minimum, is \sum_{i=1}^M s_i - M\cdot s_j.
Each s_i is simply the sum of scores of person i in all chosen events. So, rewriting the above sum in terms of the set S of chosen events, it can be seen to be
So, each event x contributes a value of \sum_{i=1}^M (A_{x, i} - M\cdot A_{x, j}) to the overall summation — note that this value depends only on x and j.
We want to maximize the sum, and as seen above the events can be chosen (or not chosen) independently. So, we simply compute the value of \sum_{i=1}^M (A_{x, i} - M\cdot A_{x, j}) for each event, and add it to the answer if it is positive.
Implementing the above solution as-is will result in a runtime of \mathcal{O}(N\cdot M^2). However, it can be optimized to \mathcal{O}(N\cdot M) by simply precomputing the value of C_i = A_{i, 1} + A_{i, 2} + \ldots + A_{i, M}, and then looking this up instead of constantly recomputing it.
Something to think about
You might notice that we started off the above solution by assuming that s_j was the smallest score. However, we never really enforced that condition anywhere afterwards, and simply took events as and when they contributed positively to the overall answer without actually checking if s_j was the minimum.
Does ignoring that condition during calculation actually affect the answer in any way?
TIME COMPLEXITY:
\mathcal{O}(N \cdot M) per test case.
CODE:
Setter (C++)
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#define FR(i, b) for (int i = 0; i < int(b); i++)
#define FOR(i, a, b) for (int i = int(a); i < int(b); i++)
#define all(x) begin(x), end(x)
#define sz(x) int((x).size())
using ll = long long;
using namespace std;
void solve() {
int n, m;
cin >> n >> m;
vector<vector<ll>> a(n, vector<ll>(m, 0));
vector<ll> tot(n, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> a[i][j];
tot[i] += a[i][j];
}
for (int j = 0; j < m; j++) {
a[i][j] = m*a[i][j] - tot[i];
}
}
ll res = 0;
for (int j = 0; j < m; j++) {
ll mn = 0, mx = 0;
for (int i = 0; i < n ; i++) {
if (a[i][j] < 0) {
mn -= a[i][j];
}
if (a[i][j] > 0) {
mx += a[i][j];
}
}
res = max(res, max(mn, mx));
}
cout << res << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int T;
cin >> T;
FOR(t, 1, T+1) {
solve();
}
return 0;
}
Tester (nikhil_medam, C++)
// Tester: Nikhil_Medam
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define int long long
const int N = 1e5 + 5;
int t, n, m;
int32_t main() {
cin >> t;
while(t--) {
cin >> n >> m;
int a[m][n], b[m][n], tot[n] = {0};
for(int j = 0; j < n; j++) {
for(int i = 0; i < m; i++) {
cin >> a[i][j];
tot[j] += a[i][j];
}
}
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
b[i][j] = m * a[i][j] - tot[j];
}
}
int ans = 0;
for(int i = 0; i < m; i++) {
int pos_sum = 0, neg_sum = 0;
for(int j = 0; j < n; j++) {
if(b[i][j] >= 0) {
pos_sum += b[i][j];
}
else {
neg_sum -= b[i][j];
}
}
ans = max(ans, max(pos_sum, neg_sum));
}
cout << ans << endl;
}
return 0;
}
Editorialist (Python)
for _ in range(int(input())):
n, m = map(int, input().split())
a = []
totscore = [0]*n
for i in range(n):
b = list(map(int, input().split()))
a.append(b)
totscore[i] = sum(b)
ans = 0
for j in range(m):
# Fix j as the minimum/maximum
mxscore, mnscore = 0, 0
for i in range(n):
val = m*a[i][j] - totscore[i]
mxscore += val * (val > 0)
mnscore -= val * (val < 0)
ans = max(ans, mxscore)
ans = max(ans, mnscore)
print(ans)