Algorithm
Problem link- https://www.spoj.com/problems/KOIREP/
KOIREP - Representatives
There are N classes in a school, each with M students. There is going to be a race of 100m dash, and a representative from each class will be chosen to participate in this race. You were assigned a task to choose these representatives. Since you did not want the race to be one sided, you wanted to choose the representatives such that the difference between the ability of the best representative and the worst representative is minimal.
For example, if N = 3 and M = 4, and each class has students with following abilities:
Class 1: {12, 16, 67, 43}
Class 2: {7, 17, 68, 48}
Class 3: {14, 15, 77, 54}
it is best to choose the student with ability 16 from Class 1, 17 from Class 2, and 15 from Class 3. Thus, the difference in this case would be 17-15 = 2.
Your task is to calculate the minimal possible difference you can achieve by choosing a representative from each class.
Input
The first line of the input consists of two integers, N and M. (1<=N<=1000, 1<=M<=1000).
The next N lines will have M integers. The jth element of ith line is the ability of the jth student in ith class. The number is between 0 and 10^9, inclusive.
Output
Output the minimal difference one can achieve by choosing the representative from each class.
Example
Input: 3 4 12 16 67 43 7 17 68 48 14 15 77 54 Output: 2
Input: 4 3 10 20 30 40 50 60 70 80 90 100 110 120 Output: 70
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007LL
#define EPS 1e-9
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI 3.14159265358979323846
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
const int MAXN = 1e3+5;
int last_idx[MAXN];
int main(){
io;
int n, m;
cin >> n >> m;
vector<int> arr[n];
for(int i = 0;i < n; i++){
for(int j = 0;j < m; j++){
int foo;
cin >> foo;
arr[i].push_back(foo);
}
}
for(int i = 0;i < n; i++)
sort(arr[i].begin(), arr[i].end());
int minn_diff = INT_MAX;
while(1){
int minn = INT_MAX;
int maxx = INT_MIN;
int idx = -1;
for(int i = 0;i < n; i++){
maxx = max(maxx, arr[i][last_idx[i]]);
if(arr[i][last_idx[i]] < minn){
minn = arr[i][last_idx[i]];
idx = i;
}
}
minn_diff = min(minn_diff, maxx-minn);
last_idx[idx]++;
if(last_idx[idx] == m)
break;
}
cout << minn_diff << endl;
return 0;
}Input
12 16 67 43
7 17 68 48
14 15 77 54
Output
Demonstration
SPOJ Solution-Representatives-Solution in C, C++, Java, Python