Tasks Details
medium
Given two sequences of integers, count the minimum number of swaps (A[k], B[k]) needed to make both sequences increasing.
Task Score
88%
Correctness
81%
Performance
100%
You have two sequences A and B consisting of integers, both of length N, and you would like them to be (strictly) increasing, i.e. for each K (0 ≤ K < N − 1), A[K] < A[K + 1] and B[K] < B[K + 1]. Thus, you need to modify the sequences, but the only manipulation you can perform is to swap an arbitrary element in sequence A with the corresponding element in sequence B. That is, both elements to be exchanged must occupy the same index position within each sequence.
For example, given A = [5, 3, 7, 7, 10] and B = [1, 6, 6, 9, 9], you can swap elements at positions 1 and 3, obtaining A = [5, 6, 7, 9, 10], B = [1, 3, 6, 7, 9].
Your goal is make both sequences increasing, using the smallest number of moves.
Write a function:
def solution(A, B)
that, given two arrays A, B of length N, containing integers, returns the minimum number of swapping operations required to make the given arrays increasing. If it is impossible to achieve the goal, return −1.
For example, given:
A[0] = 5 B[0] = 1 A[1] = 3 B[1] = 6 A[2] = 7 B[2] = 6 A[3] = 7 B[3] = 9 A[4] = 10 B[4] = 9your function should return 2, as explained above.
Given:
A[0] = 5 B[0] = 2 A[1] = -3 B[1] = 6 A[2] = 6 B[2] = -5 A[3] = 4 B[3] = 1 A[4] = 8 B[4] = 0your function should return −1, since you cannot perform operations that would make the sequences become increasing.
Given:
A[0] = 1 B[0] = -2 A[1] = 5 B[1] = 0 A[2] = 6 B[2] = 2your function should return 0, since the sequences are already increasing.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [2..100,000];
- each element of arrays A and B is an integer within the range [−1,000,000,000..1,000,000,000];
- A and B have equal lengths.
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used Python
Time spent on task 4 minutes
Notes
not defined yet
Code: 16:55:45 UTC,
java,
autosave
Code: 16:56:03 UTC,
py,
autosave
def solution(A, B):
print(A)
print(B)
Z = list(zip(A,B))
if not Z: return 0
z = Z.pop()
tails = {z:0, z[::-1]:1}
for z in reversed(Z):
n_tails = {}
for a,b in tails.keys():
s = tails[(a,b)]
can_swap = z[0] < b and z[1] < a
if can_swap:
if (z[1], z[0]) not in n_tails or s+1 < n_tails[(z[1], z[0])]:
n_tails[(z[1], z[0])] = s+1
needswap = z[0] >= a or z[1] >= b
if not needswap:
if (z[0], z[1]) not in n_tails or s < n_tails[(z[0], z[1])]:
n_tails[(z[0], z[1])] = s
print(tails, "=>", n_tails)
tails = n_tails
if not tails: return -1
return min(tails.values())
Code: 16:56:37 UTC,
py,
autosave
def solution(A, B):
print(A)
print(B)
Z = list(zip(A,B))
if not Z: return 0
z = Z.pop()
tails = {z:0, z[::-1]:1}
for z in reversed(Z):
n_tails = {}
for a,b in tails.keys():
s = tails[(a,b)]
can_swap = z[0] < b and z[1] < a
if can_swap:
if (z[1], z[0]) not in n_tails or s+1 < n_tails[(z[1], z[0])]:
n_tails[(z[1], z[0])] = s+1
needswap = z[0] >= a or z[1] >= b
if not needswap:
if z not in n_tails or s < n_tails[(z[0], z[1])]:
n_tails[(z[0], z[1])] = s
print(tails, "=>", n_tails)
tails = n_tails
if not tails: return -1
return min(tails.values())
Code: 16:56:49 UTC,
py,
autosave
def solution(A, B):
print(A)
print(B)
Z = list(zip(A,B))
if not Z: return 0
z = Z.pop()
tails = {z:0, z[::-1]:1}
for z in reversed(Z):
n_tails = {}
for a,b in tails.keys():
s = tails[(a,b)]
can_swap = z[0] < b and z[1] < a
if can_swap:
if (z[1], z[0]) not in n_tails or s+1 < n_tails[(z[1], z[0])]:
n_tails[(z[1], z[0])] = s+1
needswap = z[0] >= a or z[1] >= b
if not needswap:
if z not in n_tails or s < n_tails[z]:
n_tails[z] = s
print(tails, "=>", n_tails)
tails = n_tails
if not tails: return -1
return min(tails.values())
Code: 16:57:18 UTC,
py,
autosave
def solution(A, B):
print(A)
print(B)
Z = list(zip(A,B))
if not Z: return 0
z = Z.pop()
tails = {z:0, z[::-1]:1}
for z in reversed(Z):
n_tails = {}
for a,b in tails.keys():
s = tails[(a,b)]
can_swap = z[0] < b and z[1] < a
if can_swap:
_z = z[::-1]
if (z[1], z[0]) not in n_tails or s+1 < n_tails[(z[1], z[0])]:
n_tails[(z[1], z[0])] = s+1
needswap = z[0] >= a or z[1] >= b
if not needswap:
if z not in n_tails or s < n_tails[z]:
n_tails[z] = s
print(tails, "=>", n_tails)
tails = n_tails
if not tails: return -1
return min(tails.values())
Code: 16:57:33 UTC,
py,
autosave
def solution(A, B):
print(A)
print(B)
Z = list(zip(A,B))
if not Z: return 0
z = Z.pop()
tails = {z:0, z[::-1]:1}
for z in reversed(Z):
n_tails = {}
for a,b in tails.keys():
s = tails[(a,b)]
can_swap = z[0] < b and z[1] < a
if can_swap:
_z = z[::-1]
if _z not in n_tails or s+1 < n_tails[(z[1], z[0])]:
n_tails[(z[1], z[0])] = s+1
needswap = z[0] >= a or z[1] >= b
if not needswap:
if z not in n_tails or s < n_tails[z]:
n_tails[z] = s
print(tails, "=>", n_tails)
tails = n_tails
if not tails: return -1
return min(tails.values())
Code: 16:57:53 UTC,
py,
autosave
def solution(A, B):
print(A)
print(B)
Z = list(zip(A,B))
if not Z: return 0
z = Z.pop()
tails = {z:0, z[::-1]:1} # seed tails
for z in reversed(Z):
n_tails = {}
for a,b in tails.keys():
s = tails[(a,b)]
can_swap = z[0] < b and z[1] < a
if can_swap:
_z = z[::-1]
if _z not in n_tails or s+1 < n_tails[_z)]:
n_tails[_z] = s+1
needswap = z[0] >= a or z[1] >= b
if not needswap:
if z not in n_tails or s < n_tails[z]:
n_tails[z] = s
print(tails, "=>", n_tails)
tails = n_tails
if not tails: return -1
return min(tails.values())
Code: 16:58:03 UTC,
py,
autosave
def solution(A, B):
print(A)
print(B)
Z = list(zip(A,B))
if not Z: return 0
z = Z.pop()
tails = {z:0, z[::-1]:1}
for z in reversed(Z):
n_tails = {}
for a,b in tails.keys():
s = tails[(a,b)]
can_swap = z[0] < b and z[1] < a
if can_swap:
_z = z[::-1]
if _z not in n_tails or s+1 < n_tails[_z)]:
n_tails[_z] = s+1
needswap = z[0] >= a or z[1] >= b
if not needswap:
if z not in n_tails or s < n_tails[z]:
n_tails[z] = s
print(tails, "=>", n_tails)
tails = n_tails
if not tails: return -1
return min(tails.values())
Code: 16:58:08 UTC,
py,
verify,
result: Failed
def solution(A, B):
print(A)
print(B)
Z = list(zip(A,B))
if not Z: return 0
z = Z.pop()
tails = {z:0, z[::-1]:1}
for z in reversed(Z):
n_tails = {}
for a,b in tails.keys():
s = tails[(a,b)]
can_swap = z[0] < b and z[1] < a
if can_swap:
_z = z[::-1]
if _z not in n_tails or s+1 < n_tails[_z)]:
n_tails[_z] = s+1
needswap = z[0] >= a or z[1] >= b
if not needswap:
if z not in n_tails or s < n_tails[z]:
n_tails[z] = s
print(tails, "=>", n_tails)
tails = n_tails
if not tails: return -1
return min(tails.values())
Analysis
expand all
Example tests
1.
0.048 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 139, in <module>
main()
File "exec.py", line 80, in main
sol = __import__('solution')
File "/tmp/solution.py", line 15
if _z not in n_tails or s+1 < n_tails[_z)]:
^
SyntaxError: invalid syntax
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 139, in <module>
main()
File "exec.py", line 80, in main
sol = __import__('solution')
File "/tmp/solution.py", line 15
if _z not in n_tails or s+1 < n_tails[_z)]:
^
SyntaxError: invalid syntax
1.
0.036 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Traceback (most recent call last):
File "exec.py", line 139, in <module>
main()
File "exec.py", line 80, in main
sol = __import__('solution')
File "/tmp/solution.py", line 15
if _z not in n_tails or s+1 < n_tails[_z)]:
^
SyntaxError: invalid syntax
Code: 16:58:17 UTC,
py,
verify,
result: Passed
def solution(A, B):
print(A)
print(B)
Z = list(zip(A,B))
if not Z: return 0
z = Z.pop()
tails = {z:0, z[::-1]:1}
for z in reversed(Z):
n_tails = {}
for a,b in tails.keys():
s = tails[(a,b)]
can_swap = z[0] < b and z[1] < a
if can_swap:
_z = z[::-1]
if _z not in n_tails or s+1 < n_tails[_z]:
n_tails[_z] = s+1
needswap = z[0] >= a or z[1] >= b
if not needswap:
if z not in n_tails or s < n_tails[z]:
n_tails[z] = s
print(tails, "=>", n_tails)
tails = n_tails
if not tails: return -1
return min(tails.values())
Analysis
expand all
Example tests
1.
0.036 s
OK
stdout:
[5, 3, 7, 7, 10]
[1, 6, 6, 9, 9]
{(10, 9): 0, (9, 10): 1} => {(9, 7): 1, (7, 9): 1}
{(9, 7): 1, (7, 9): 1} => {(7, 6): 1, (6, 7): 2}
{(7, 6): 1, (6, 7): 2} => {(6, 3): 2, (3, 6): 2}
{(6, 3): 2, (3, 6): 2} => {(5, 1): 2, (1, 5): 3}
1.
0.036 s
OK
stdout:
[5, -3, 6, 4, 8]
[2, 6, -5, 1, 0]
{(8, 0): 0, (0, 8): 1} => {}
1.
0.036 s
OK
stdout:
[1, 5, 6]
[-2, 0, 2]
{(6, 2): 0, (2, 6): 1} => {(5, 0): 0, (0, 5): 2}
{(5, 0): 0, (0, 5): 2} => {(1, -2): 0, (-2, 1): 3}
Code: 16:58:30 UTC,
py,
autosave
def solution(A, B):
print(A)
print(B)
Z = list(zip(A,B))
if not Z: return 0
z = Z.pop()
tails = {z:0, z[::-1]:1}
for z in reversed(Z):
n_tails = {}
for a,b in tails.keys():
s = tails[(a,b)]
can_swap = z[0] < b and z[1] < a
if can_swap:
_z = z[::-1]
if _z not in n_tails or s+1 < n_tails[_z]:
n_tails[_z] = s+1
needswap = z[0] >= a or z[1] >= b
if not needswap:
if z not in n_tails or s < n_tails[z]:
n_tails[z] = s
tails = n_tails
if not tails: return -1
return min(tails.values())
Code: 16:58:39 UTC,
py,
verify,
result: Passed
def solution(A, B):
Z = list(zip(A,B))
if not Z: return 0
z = Z.pop()
tails = {z:0, z[::-1]:1}
for z in reversed(Z):
n_tails = {}
for a,b in tails.keys():
s = tails[(a,b)]
can_swap = z[0] < b and z[1] < a
if can_swap:
_z = z[::-1]
if _z not in n_tails or s+1 < n_tails[_z]:
n_tails[_z] = s+1
needswap = z[0] >= a or z[1] >= b
if not needswap:
if z not in n_tails or s < n_tails[z]:
n_tails[z] = s
tails = n_tails
if not tails: return -1
return min(tails.values())
Analysis
Code: 16:58:53 UTC,
py,
verify,
result: Passed
def solution(A, B):
Z = list(zip(A,B))
if not Z: return 0
z = Z.pop()
tails = {z:0, z[::-1]:1}
for z in reversed(Z):
n_tails = {}
for a,b in tails.keys():
s = tails[(a,b)]
can_swap = z[0] < b and z[1] < a
if can_swap:
_z = z[::-1]
if _z not in n_tails or s+1 < n_tails[_z]:
n_tails[_z] = s+1
needswap = z[0] >= a or z[1] >= b
if not needswap:
if z not in n_tails or s < n_tails[z]:
n_tails[z] = s
tails = n_tails
if not tails: return -1
return min(tails.values())
Analysis
Code: 16:58:55 UTC,
py,
final,
score:
88
def solution(A, B):
Z = list(zip(A,B))
if not Z: return 0
z = Z.pop()
tails = {z:0, z[::-1]:1}
for z in reversed(Z):
n_tails = {}
for a,b in tails.keys():
s = tails[(a,b)]
can_swap = z[0] < b and z[1] < a
if can_swap:
_z = z[::-1]
if _z not in n_tails or s+1 < n_tails[_z]:
n_tails[_z] = s+1
needswap = z[0] >= a or z[1] >= b
if not needswap:
if z not in n_tails or s < n_tails[z]:
n_tails[z] = s
tails = n_tails
if not tails: return -1
return min(tails.values())Analysis summary
The following issues have been detected: wrong answers.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
4.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.036 s
OK
1.
0.036 s
OK
2.
0.036 s
WRONG ANSWER,
got 3 expected 2
3.
0.036 s
WRONG ANSWER,
got 4 expected 3
4.
0.036 s
OK
expand all
Correctness/performance tests
1.
0.036 s
OK
2.
0.036 s
OK
3.
0.040 s
OK
4.
0.040 s
OK
small_correctness
specific cases: swap every second element, swap only first and last element
specific cases: swap every second element, swap only first and last element
✔
OK
1.
0.036 s
OK
2.
0.036 s
OK
1.
0.368 s
OK
2.
0.360 s
OK
3.
0.364 s
OK
4.
0.364 s
OK
expand all
Performance tests
1.
0.368 s
OK
2.
0.364 s
OK
3.
0.364 s
OK
4.
0.368 s
OK
1.
0.364 s
OK
2.
0.236 s
OK
3.
0.212 s
OK
4.
0.036 s
OK