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:
class Solution { public int solution(int[] A, 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: 04:41:49 UTC,
java,
autosave
Code: 04:42:08 UTC,
cs,
autosave
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A, int[] B, int F) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
}
}
Code: 04:42:16 UTC,
cs,
verify,
result: Failed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A, int[] B, int F) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
int[] A = { 9, 4, 10, 2, 8, 5 };
int[] B = { 5, 4, 11, 9, 9, 9 };
int N = A.Length;
int BE = N - F;
Dictionary<int, int> frontend = new Dictionary<int, int>();
Dictionary<int, int> backend = new Dictionary<int, int>();
Dictionary<int, int> neutral = new Dictionary<int, int>();
for (int i = 0; i < N; i++)
{
if (A[i] > B[i])
{
frontend.Add(i, A[i]-B[i]);
}
else if (B[i] > A[i])
{
backend.Add(i, B[i]-A[i]);
}
else
{
neutral.Add(i, 0);
}
}
bool[] tmp = new bool[N];
int sum = 0;
foreach (var item in frontend.OrderByDescending(x => x.Value))
{
if (F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = true;
F--;
}
}
foreach (var item in backend.OrderByDescending(x => x.Value))
{
if (BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = true;
BE--;
}
}
if (F > 0)
{
foreach (var item in neutral)
{
if (tmp[item.Key] == false && F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = false;
F--;
}
}
}
if (F > 0)
{
foreach (var item in backend)
{
if (tmp[item.Key] == false && F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = false;
F--;
}
}
}
if (BE > 0)
{
foreach (var item in neutral)
{
if (tmp[item.Key] == false && BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = false;
BE--;
}
}
}
if (BE > 0)
{
foreach (var item in frontend)
{
if (tmp[item.Key] == false && BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = false;
BE--;
}
}
}
return sum;
}
}
Analysis
Compile error
Compilation failed: 2 error(s), 0 warnings Solution.cs(11,16): error CS0128: A local variable named `A' is already defined in this scope Solution.cs(12,19): error CS0128: A local variable named `B' is already defined in this scope
Code: 04:42:29 UTC,
cs,
autosave
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113
using System;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A, int[] B, int F) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
int N = A.Length;
int BE = N - F;
Dictionary<int, int> frontend = new Dictionary<int, int>();
Dictionary<int, int> backend = new Dictionary<int, int>();
Dictionary<int, int> neutral = new Dictionary<int, int>();
for (int i = 0; i < N; i++)
{
if (A[i] > B[i])
{
frontend.Add(i, A[i]-B[i]);
}
else if (B[i] > A[i])
{
backend.Add(i, B[i]-A[i]);
}
else
{
neutral.Add(i, 0);
}
}
bool[] tmp = new bool[N];
int sum = 0;
foreach (var item in frontend.OrderByDescending(x => x.Value))
{
if (F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = true;
F--;
}
}
foreach (var item in backend.OrderByDescending(x => x.Value))
{
if (BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = true;
BE--;
}
}
if (F > 0)
{
foreach (var item in neutral)
{
if (tmp[item.Key] == false && F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = false;
F--;
}
}
}
if (F > 0)
{
foreach (var item in backend)
{
if (tmp[item.Key] == false && F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = false;
F--;
}
}
}
if (BE > 0)
{
foreach (var item in neutral)
{
if (tmp[item.Key] == false && BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = false;
BE--;
}
}
}
if (BE > 0)
{
foreach (var item in frontend)
{
if (tmp[item.Key] == false && BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = false;
BE--;
}
}
}
return sum;
}
}
Code: 04:42:36 UTC,
cs,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115
using System;
using System.Collections.Generic;
using System.Linq;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A, int[] B, int F) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
int N = A.Length;
int BE = N - F;
Dictionary<int, int> frontend = new Dictionary<int, int>();
Dictionary<int, int> backend = new Dictionary<int, int>();
Dictionary<int, int> neutral = new Dictionary<int, int>();
for (int i = 0; i < N; i++)
{
if (A[i] > B[i])
{
frontend.Add(i, A[i]-B[i]);
}
else if (B[i] > A[i])
{
backend.Add(i, B[i]-A[i]);
}
else
{
neutral.Add(i, 0);
}
}
bool[] tmp = new bool[N];
int sum = 0;
foreach (var item in frontend.OrderByDescending(x => x.Value))
{
if (F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = true;
F--;
}
}
foreach (var item in backend.OrderByDescending(x => x.Value))
{
if (BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = true;
BE--;
}
}
if (F > 0)
{
foreach (var item in neutral)
{
if (tmp[item.Key] == false && F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = false;
F--;
}
}
}
if (F > 0)
{
foreach (var item in backend)
{
if (tmp[item.Key] == false && F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = false;
F--;
}
}
}
if (BE > 0)
{
foreach (var item in neutral)
{
if (tmp[item.Key] == false && BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = false;
BE--;
}
}
}
if (BE > 0)
{
foreach (var item in frontend)
{
if (tmp[item.Key] == false && BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = false;
BE--;
}
}
}
return sum;
}
}
Analysis
Code: 04:42:40 UTC,
cs,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115
using System;
using System.Collections.Generic;
using System.Linq;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A, int[] B, int F) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
int N = A.Length;
int BE = N - F;
Dictionary<int, int> frontend = new Dictionary<int, int>();
Dictionary<int, int> backend = new Dictionary<int, int>();
Dictionary<int, int> neutral = new Dictionary<int, int>();
for (int i = 0; i < N; i++)
{
if (A[i] > B[i])
{
frontend.Add(i, A[i]-B[i]);
}
else if (B[i] > A[i])
{
backend.Add(i, B[i]-A[i]);
}
else
{
neutral.Add(i, 0);
}
}
bool[] tmp = new bool[N];
int sum = 0;
foreach (var item in frontend.OrderByDescending(x => x.Value))
{
if (F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = true;
F--;
}
}
foreach (var item in backend.OrderByDescending(x => x.Value))
{
if (BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = true;
BE--;
}
}
if (F > 0)
{
foreach (var item in neutral)
{
if (tmp[item.Key] == false && F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = false;
F--;
}
}
}
if (F > 0)
{
foreach (var item in backend)
{
if (tmp[item.Key] == false && F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = false;
F--;
}
}
}
if (BE > 0)
{
foreach (var item in neutral)
{
if (tmp[item.Key] == false && BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = false;
BE--;
}
}
}
if (BE > 0)
{
foreach (var item in frontend)
{
if (tmp[item.Key] == false && BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = false;
BE--;
}
}
}
return sum;
}
}
Analysis
Code: 04:42:43 UTC,
cs,
final,
score:
100
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115
using System;
using System.Collections.Generic;
using System.Linq;
// you can also use other imports, for example:
// using System.Collections.Generic;
// you can write to stdout for debugging purposes, e.g.
// Console.WriteLine("this is a debug message");
class Solution {
public int solution(int[] A, int[] B, int F) {
// write your code in C# 6.0 with .NET 4.5 (Mono)
int N = A.Length;
int BE = N - F;
Dictionary<int, int> frontend = new Dictionary<int, int>();
Dictionary<int, int> backend = new Dictionary<int, int>();
Dictionary<int, int> neutral = new Dictionary<int, int>();
for (int i = 0; i < N; i++)
{
if (A[i] > B[i])
{
frontend.Add(i, A[i]-B[i]);
}
else if (B[i] > A[i])
{
backend.Add(i, B[i]-A[i]);
}
else
{
neutral.Add(i, 0);
}
}
bool[] tmp = new bool[N];
int sum = 0;
foreach (var item in frontend.OrderByDescending(x => x.Value))
{
if (F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = true;
F--;
}
}
foreach (var item in backend.OrderByDescending(x => x.Value))
{
if (BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = true;
BE--;
}
}
if (F > 0)
{
foreach (var item in neutral)
{
if (tmp[item.Key] == false && F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = false;
F--;
}
}
}
if (F > 0)
{
foreach (var item in backend)
{
if (tmp[item.Key] == false && F > 0)
{
sum = sum + A[item.Key];
tmp[item.Key] = false;
F--;
}
}
}
if (BE > 0)
{
foreach (var item in neutral)
{
if (tmp[item.Key] == false && BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = false;
BE--;
}
}
}
if (BE > 0)
{
foreach (var item in frontend)
{
if (tmp[item.Key] == false && BE > 0)
{
sum = sum + B[item.Key];
tmp[item.Key] = false;
BE--;
}
}
}
return sum;
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N*log(N)) or O(N)
expand all
Correctness tests
1.
0.028 s
OK
2.
0.028 s
OK
3.
0.028 s
OK
4.
0.028 s
OK
1.
0.028 s
OK
2.
0.028 s
OK
1.
0.032 s
OK
2.
0.032 s
OK
3.
0.028 s
OK
1.
0.028 s
OK
2.
0.032 s
OK
3.
0.032 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.032 s
OK
2.
0.032 s
OK
3.
0.028 s
OK
expand all
Correctness/performance tests
1.
0.032 s
OK
2.
0.028 s
OK
3.
0.028 s
OK
1.
0.032 s
OK
2.
0.032 s
OK
3.
0.028 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.032 s
OK
2.
0.028 s
OK
3.
0.028 s
OK
expand all
Performance tests
1.
0.216 s
OK
2.
0.216 s
OK
3.
0.220 s
OK
1.
0.220 s
OK
2.
0.224 s
OK
3.
0.244 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.208 s
OK
2.
0.216 s
OK
3.
0.224 s
OK
1.
0.172 s
OK
2.
0.176 s
OK
3.
0.176 s
OK