Tasks Details
medium
1.
DreamTeam
Divide developers into two teams to maximize their total contribution.
Task Score
100%
Correctness
100%
Performance
100%
A company has employed N developers (numbered from 0 to N−1) and wants to divide them into two teams. The first is a front-end team with F developers. The second is a back-end team with N−F developers. If the K-th developer is assigned to the front-end team then their contribution is A[K], and if they are assigned to the back-end team then their contribution is B[K]. What is the maximum sum of contributions the company can achieve?
Write a function:
int solution(vector<int> &A, vector<int> &B, int F);
that, given two arrays A, B (consisting of N integers each) and the integer F, returns the maximum sum of contributions the company can achieve.
Examples:
1. Given A = [4, 2, 1], B = [2, 5, 3] and F = 2, the function should return 10. There should be two front-end developers and one back-end developer. The 0th and 2nd developers should be assigned to the front-end team (with contributions 4 and 1) and the 1st developer should be assigned to the back-end team (with contribution 5).
2. Given A = [7, 1, 4, 4], B = [5, 3, 4, 3] and F = 2, the function should return 18. The 0th and 3rd developers should be assigned to the front-end team and the 1st and 2nd developers should be assigned to the back-end team.
3. Given A = [5, 5, 5], B = [5, 5, 5] and F = 1, the function should return 15. The 0th developer can be assigned to the front-end team and the 1st and 2nd developers can be assigned to the back-end team.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..200,000];
- arrays A and B have equal lengths;
- each element of array A is an integer within the range [0..1,000];
- F is an integer within the range [0..N].
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used C++
Time spent on task 1 minutes
Notes
not defined yet
Code: 17:46:12 UTC,
java,
autosave
Code: 17:46:15 UTC,
cpp,
autosave
Code: 17:46:22 UTC,
cpp,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<bits/stdc++.h>
typedef struct node{
int a;
int b;
}node;
bool comp(node a, node b){
int d1 = abs(a.a - a.b);
int d2 = abs(b.a - b.b);
if(d1 > d2){
return true;
}
if(d1 == d2)
return true;
return false;
}
int solution(vector<int> &A, vector<int> &B, int F) {
int n = A.size();
node * arr = new node[n + 2];
for(int i=0; i<n; i++){
arr[i].a = A[i];
arr[i].b = B[i];
}
sort(arr, arr + n, comp);
int res = 0;
int cnta = 0, cntb = 0;
for(int i=0; i<n; i++){
if(arr[i].a >= arr[i].b){
if(cnta < F){
res += arr[i].a;
cnta++;
}
else{
res += arr[i].b;
cntb++;
}
}
else{
if(cntb < n - F){
res += arr[i].b;
cntb++;
}
else{
res += arr[i].a;
cnta++;
}
}
}
return res;
}
Code: 17:46:33 UTC,
cpp,
autosave
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<bits/stdc++.h>
typedef struct node{
int a;
int b;
}node;
bool comp(node a, node b){
int d1 = abs(a.a - a.b);
int d2 = abs(b.a - b.b);
if(d1 > d2){
return true;
}
if(d1 == d2)
return false;
return false;
}
int solution(vector<int> &A, vector<int> &B, int F) {
int n = A.size();
node * arr = new node[n + 2];
for(int i=0; i<n; i++){
arr[i].a = A[i];
arr[i].b = B[i];
}
sort(arr, arr + n, comp);
int res = 0;
int cnta = 0, cntb = 0;
for(int i=0; i<n; i++){
if(arr[i].a >= arr[i].b){
if(cnta < F){
res += arr[i].a;
cnta++;
}
else{
res += arr[i].b;
cntb++;
}
}
else{
if(cntb < n - F){
res += arr[i].b;
cntb++;
}
else{
res += arr[i].a;
cnta++;
}
}
}
return res;
}
Code: 17:46:37 UTC,
cpp,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<bits/stdc++.h>
typedef struct node{
int a;
int b;
}node;
bool comp(node a, node b){
int d1 = abs(a.a - a.b);
int d2 = abs(b.a - b.b);
if(d1 > d2){
return true;
}
if(d1 == d2)
return false;
return false;
}
int solution(vector<int> &A, vector<int> &B, int F) {
int n = A.size();
node * arr = new node[n + 2];
for(int i=0; i<n; i++){
arr[i].a = A[i];
arr[i].b = B[i];
}
sort(arr, arr + n, comp);
int res = 0;
int cnta = 0, cntb = 0;
for(int i=0; i<n; i++){
if(arr[i].a >= arr[i].b){
if(cnta < F){
res += arr[i].a;
cnta++;
}
else{
res += arr[i].b;
cntb++;
}
}
else{
if(cntb < n - F){
res += arr[i].b;
cntb++;
}
else{
res += arr[i].a;
cnta++;
}
}
}
return res;
}
Analysis
Code: 17:46:44 UTC,
cpp,
verify,
result: Passed
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<bits/stdc++.h>
typedef struct node{
int a;
int b;
}node;
bool comp(node a, node b){
int d1 = abs(a.a - a.b);
int d2 = abs(b.a - b.b);
if(d1 > d2){
return true;
}
if(d1 == d2)
return false;
return false;
}
int solution(vector<int> &A, vector<int> &B, int F) {
int n = A.size();
node * arr = new node[n + 2];
for(int i=0; i<n; i++){
arr[i].a = A[i];
arr[i].b = B[i];
}
sort(arr, arr + n, comp);
int res = 0;
int cnta = 0, cntb = 0;
for(int i=0; i<n; i++){
if(arr[i].a >= arr[i].b){
if(cnta < F){
res += arr[i].a;
cnta++;
}
else{
res += arr[i].b;
cntb++;
}
}
else{
if(cntb < n - F){
res += arr[i].b;
cntb++;
}
else{
res += arr[i].a;
cnta++;
}
}
}
return res;
}
Analysis
Code: 17:46:49 UTC,
cpp,
final,
score:
100
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556
// you can use includes, for example:
// #include <algorithm>
// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;
#include<bits/stdc++.h>
typedef struct node{
int a;
int b;
}node;
bool comp(node a, node b){
int d1 = abs(a.a - a.b);
int d2 = abs(b.a - b.b);
if(d1 > d2){
return true;
}
if(d1 == d2)
return false;
return false;
}
int solution(vector<int> &A, vector<int> &B, int F) {
int n = A.size();
node * arr = new node[n + 2];
for(int i=0; i<n; i++){
arr[i].a = A[i];
arr[i].b = B[i];
}
sort(arr, arr + n, comp);
int res = 0;
int cnta = 0, cntb = 0;
for(int i=0; i<n; i++){
if(arr[i].a >= arr[i].b){
if(cnta < F){
res += arr[i].a;
cnta++;
}
else{
res += arr[i].b;
cntb++;
}
}
else{
if(cntb < n - F){
res += arr[i].b;
cntb++;
}
else{
res += arr[i].a;
cnta++;
}
}
}
return res;
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N)) or O(N)
expand all
Correctness tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
4.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
small_bigger_and_smaller_differences
N = 20. Some developers have small difference between A[i] and B[i].
N = 20. Some developers have small difference between A[i] and B[i].
✔
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
expand all
Correctness/performance tests
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
medium_bigger_and_smaller_differences
N = 300. Some developers have small difference between A[i] and B[i].
N = 300. Some developers have small difference between A[i] and B[i].
✔
OK
1.
0.001 s
OK
2.
0.001 s
OK
3.
0.001 s
OK
expand all
Performance tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.032 s
OK
2.
0.032 s
OK
3.
0.032 s
OK
large_bigger_and_smaller_differences
N = 200,000. Some developers have small difference between A[i] and B[i].
N = 200,000. Some developers have small difference between A[i] and B[i].
✔
OK
1.
0.032 s
OK
2.
0.032 s
OK
3.
0.032 s
OK
1.
0.024 s
OK
2.
0.024 s
OK
3.
0.024 s
OK