Tasks Details
hard
You have a deck of cards in which each card has two numbers: one on the front and one on the back. Flip some cards over so as to maximize the smallest integer that's not present on any card's front.
Task Score
100%
Correctness
100%
Performance
100%
You are playing a game with N cards. On both sides of each card there is a positive integer. The cards are laid on the table. The score of the game is the smallest positive integer that does not occur on the face-up cards. You may flip some cards over. Having flipped them, you then read the numbers facing up and recalculate the score. What is the maximum score you can achieve?
Write a function:
class Solution { public int solution(int[] A, int[] B); }
that, given two arrays of integers A and B, both of length N, describing the numbers written on both sides of the cards, facing up and down respectively, returns the maximum possible score.
For example, given A = [1, 2, 4, 3] and B = [1, 3, 2, 3], your function should return 5, as without flipping any card the smallest positive integer excluded from this sequence is 5.
Given A = [4, 2, 1, 6, 5] and B = [3, 2, 1, 7, 7], your function should return 4, as we could flip the first card so that the numbers facing up are [3, 2, 1, 6, 5] and it is impossible to have both numbers 3 and 4 facing up.
Given A = [2, 3] and B = [2, 3] your function should return 1, as no matter how the cards are flipped, the numbers facing up are [2, 3].
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..100,000];
- each element of arrays A and B is an integer within the range [1..100,000,000];
- input arrays are of equal size.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Java 21
Time spent on task 1 minutes
Notes
not defined yet
Code: 08:32:55 UTC,
java,
autosave
Code: 08:33:06 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public boolean augment(int u, List<Integer>[] graph, int[] visit, int[] match, int iteration) {
for (int v : graph[u]) {
if (visit[v] < iteration) {
visit[v] = iteration;
if (match[v] == 0 /* u is always > 0 */ || augment(match[v], graph, visit, match, iteration)) {
match[v] = u;
return true;
}
}
}
return false;
}
public boolean augmentIter(int u, List<Integer>[] graph, int[] visit, int[] match, int iteration) {
Stack<int[]> levels = new Stack<>();
levels.push(new int[] { u, 0 });// insert item u starting at neighbour 0
while (!levels.isEmpty()) {
int[] toHandle = levels.pop();
List<Integer> neighbours = graph[toHandle[0]];
while (toHandle[1] < neighbours.size() && visit[neighbours.get(toHandle[1])] == iteration) {
toHandle[1]++;
}
if (toHandle[1] < neighbours.size()) {
int v = neighbours.get(toHandle[1]);
visit[v] = iteration;
if (match[v] == 0) {
// unroll and return true;
match[v] = toHandle[0];
while (!levels.isEmpty()) {
int[] unroll = levels.pop();
int vv = unroll[1] - 1;// this was incremented before
// being added
match[neighbours.get(vv)] = unroll[0];
}
return true;
} else {
toHandle[1]++;
levels.push(toHandle);
levels.push(new int[] { match[v], 0 });
}
}
}
return false;
}
public int maxBipartite(List<Integer>[] graph) {
int[] match = new int[graph.length];
int[] visit = new int[graph.length];
for (int i = 1; i < graph.length; i++) {
if (!augmentIter(i, graph, visit, match, i)) {
return i;
}
}
return graph.length;
}
public int solution(int[] A, int B[]) {
List<Integer>[] buckets = new List[A.length + 1];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
for (int i = 0; i < A.length; i++) {
int a = Math.min(A[i], B[i]);
int b = Math.max(A[i], B[i]);
if (a > A.length)
continue;
// Add a
buckets[a].add(i);
if (b > A.length)
continue;
if (b == a)
continue;
// Add b
buckets[b].add(i);
}
return maxBipartite(buckets);
}
}
Analysis
Code: 08:33:12 UTC,
java,
verify,
result: Passed
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public boolean augment(int u, List<Integer>[] graph, int[] visit, int[] match, int iteration) {
for (int v : graph[u]) {
if (visit[v] < iteration) {
visit[v] = iteration;
if (match[v] == 0 /* u is always > 0 */ || augment(match[v], graph, visit, match, iteration)) {
match[v] = u;
return true;
}
}
}
return false;
}
public boolean augmentIter(int u, List<Integer>[] graph, int[] visit, int[] match, int iteration) {
Stack<int[]> levels = new Stack<>();
levels.push(new int[] { u, 0 });// insert item u starting at neighbour 0
while (!levels.isEmpty()) {
int[] toHandle = levels.pop();
List<Integer> neighbours = graph[toHandle[0]];
while (toHandle[1] < neighbours.size() && visit[neighbours.get(toHandle[1])] == iteration) {
toHandle[1]++;
}
if (toHandle[1] < neighbours.size()) {
int v = neighbours.get(toHandle[1]);
visit[v] = iteration;
if (match[v] == 0) {
// unroll and return true;
match[v] = toHandle[0];
while (!levels.isEmpty()) {
int[] unroll = levels.pop();
int vv = unroll[1] - 1;// this was incremented before
// being added
match[neighbours.get(vv)] = unroll[0];
}
return true;
} else {
toHandle[1]++;
levels.push(toHandle);
levels.push(new int[] { match[v], 0 });
}
}
}
return false;
}
public int maxBipartite(List<Integer>[] graph) {
int[] match = new int[graph.length];
int[] visit = new int[graph.length];
for (int i = 1; i < graph.length; i++) {
if (!augmentIter(i, graph, visit, match, i)) {
return i;
}
}
return graph.length;
}
public int solution(int[] A, int B[]) {
List<Integer>[] buckets = new List[A.length + 1];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
for (int i = 0; i < A.length; i++) {
int a = Math.min(A[i], B[i]);
int b = Math.max(A[i], B[i]);
if (a > A.length)
continue;
// Add a
buckets[a].add(i);
if (b > A.length)
continue;
if (b == a)
continue;
// Add b
buckets[b].add(i);
}
return maxBipartite(buckets);
}
}
Analysis
Code: 08:33:17 UTC,
java,
final,
score:
100
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
// you can also use imports, for example:
import java.util.*;
// you can write to stdout for debugging purposes, e.g.
// System.out.println("this is a debug message");
class Solution {
public boolean augment(int u, List<Integer>[] graph, int[] visit, int[] match, int iteration) {
for (int v : graph[u]) {
if (visit[v] < iteration) {
visit[v] = iteration;
if (match[v] == 0 /* u is always > 0 */ || augment(match[v], graph, visit, match, iteration)) {
match[v] = u;
return true;
}
}
}
return false;
}
public boolean augmentIter(int u, List<Integer>[] graph, int[] visit, int[] match, int iteration) {
Stack<int[]> levels = new Stack<>();
levels.push(new int[] { u, 0 });// insert item u starting at neighbour 0
while (!levels.isEmpty()) {
int[] toHandle = levels.pop();
List<Integer> neighbours = graph[toHandle[0]];
while (toHandle[1] < neighbours.size() && visit[neighbours.get(toHandle[1])] == iteration) {
toHandle[1]++;
}
if (toHandle[1] < neighbours.size()) {
int v = neighbours.get(toHandle[1]);
visit[v] = iteration;
if (match[v] == 0) {
// unroll and return true;
match[v] = toHandle[0];
while (!levels.isEmpty()) {
int[] unroll = levels.pop();
int vv = unroll[1] - 1;// this was incremented before
// being added
match[neighbours.get(vv)] = unroll[0];
}
return true;
} else {
toHandle[1]++;
levels.push(toHandle);
levels.push(new int[] { match[v], 0 });
}
}
}
return false;
}
public int maxBipartite(List<Integer>[] graph) {
int[] match = new int[graph.length];
int[] visit = new int[graph.length];
for (int i = 1; i < graph.length; i++) {
if (!augmentIter(i, graph, visit, match, i)) {
return i;
}
}
return graph.length;
}
public int solution(int[] A, int B[]) {
List<Integer>[] buckets = new List[A.length + 1];
for (int i = 0; i < buckets.length; i++) {
buckets[i] = new ArrayList<>();
}
for (int i = 0; i < A.length; i++) {
int a = Math.min(A[i], B[i]);
int b = Math.max(A[i], B[i]);
if (a > A.length)
continue;
// Add a
buckets[a].add(i);
if (b > A.length)
continue;
if (b == a)
continue;
// Add b
buckets[b].add(i);
}
return maxBipartite(buckets);
}
}Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.004 s
OK
4.
0.008 s
OK
5.
0.004 s
OK
6.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
5.
0.008 s
OK
6.
0.008 s
OK
7.
0.008 s
OK
8.
0.008 s
OK
9.
0.008 s
OK
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
1.
0.008 s
OK
2.
0.008 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
5.
0.008 s
OK
6.
0.008 s
OK
expand all
Correctness/performance tests
1.
0.008 s
OK
2.
0.004 s
OK
3.
0.008 s
OK
4.
0.008 s
OK
expand all
Performance tests
1.
0.012 s
OK
2.
0.016 s
OK
3.
0.012 s
OK
4.
0.012 s
OK
1.
0.012 s
OK
2.
0.008 s
OK
3.
0.016 s
OK
4.
0.012 s
OK
1.
0.732 s
OK
2.
0.776 s
OK
3.
0.868 s
OK
4.
0.864 s
OK
5.
0.876 s
OK
6.
0.880 s
OK
7.
0.888 s
OK
8.
0.884 s
OK
9.
0.860 s
OK
10.
0.912 s
OK
11.
0.916 s
OK
12.
0.688 s
OK
1.
0.440 s
OK
2.
0.544 s
OK
3.
2.112 s
OK
4.
1.496 s
OK