fork download
copy 
  1. from collections import defaultdict
  2. import bisect
  3.  
  4.  
  5. def fix_array(a):
  6. 	n = len(a)
  7. 	freq_a = defaultdict(int)
  8. 	for x in a:
  9. 		freq_a[x] += 1
  10.  
  11. 	if all(a[i-1] <= a[i] for i in range(1, n)):
  12. 		return 0
  13.  
  14. 	if all(a[i-1] >= a[i] for i in range(1, n)):
  15. 		return n - max(freq_a.values())
  16.  
  17. 	left_side = []
  18. 	right_side = []
  19. 	inside = []
  20. 	min_pivot, max_pivot = sorted([a[0], a[n-1]])
  21. 	for x in a:
  22. 		if x < min_pivot:
  23. 			left_side.append(x)
  24. 		elif x > max_pivot:
  25. 			right_side.append(x)
  26. 		else:
  27. 			inside.append(x)
  28.  
  29. 	idx_list_dict = defaultdict(list)
  30. 	for i in range(len(inside)):
  31. 		idx_list_dict[inside[i]].append(i)
  32.  
  33. 	unique_inside = sorted(set(inside))
  34.  
  35. 	cnt_correct_pos_left = [0 for x in unique_inside]
  36. 	cnt_correct_pos_right = [freq_a[x] for x in unique_inside]
  37.  
  38. 	for i in range(len(unique_inside)-2, -1, -1):
  39. 		x = unique_inside[i]
  40. 		next_x = unique_inside[i+1]
  41. 		l_i, r_i = idx_list_dict[x][0], idx_list_dict[x][-1]
  42. 		l_i1, r_i1 = idx_list_dict[next_x][0], idx_list_dict[next_x][-1]
  43.  
  44. 		if r_i < l_i1:
  45. 			cnt_correct_pos_right[i] = freq_a[x] + cnt_correct_pos_right[i+1]
  46. 		elif l_i1 < r_i < r_i1:
  47. 			# cnt_correct_pos_right[i] = freq_a[x] + sum(1 for j in idx_list_dict[next_x] if r_i < j)
  48. 			cnt_correct_pos_right[i] = freq_a[x] + len(idx_list_dict[next_x]) - bisect.bisect(idx_list_dict[next_x], r_i)
  49. 		else:
  50. 			cnt_correct_pos_right[i] = freq_a[x]
  51.  
  52. 	for i in range(len(unique_inside)-1):
  53. 		x = unique_inside[i]
  54. 		next_x = unique_inside[i+1]
  55. 		l_i, r_i = idx_list_dict[x][0], idx_list_dict[x][-1]
  56. 		l_i1, r_i1 = idx_list_dict[next_x][0], idx_list_dict[next_x][-1]
  57.  
  58. 		if r_i < l_i1:
  59. 			cnt_correct_pos_left[i+1] = cnt_correct_pos_left[i] + freq_a[x]
  60. 		elif l_i < l_i1 < r_i:
  61. 			# cnt_correct_pos_left[i+1] = cnt_correct_pos_left[i] + sum(1 for j in idx_list_dict[x] if j < l_i1)
  62. 			cnt_correct_pos_left[i+1] = cnt_correct_pos_left[i] + bisect.bisect(idx_list_dict[x], l_i1)
  63. 		else:
  64. 			cnt_correct_pos_left[i+1] = 0
  65.  
  66. 	# print(*zip(unique_inside, cnt_correct_pos_left, cnt_correct_pos_right))
  67. 	min_cnt_incorrect_pos = min(
  68. 		len(inside) - cnt_left - cnt_right
  69. 		for cnt_left, cnt_right in zip(cnt_correct_pos_left, cnt_correct_pos_right)
  70. 	)
  71. 	# min_cnt_incorrect_pos = min(count_incorrect_positions(unique_idx) for unique_idx in range(len(unique_inside)))
  72. 	return len(left_side) + min_cnt_incorrect_pos + len(right_side)
  73.  
  74.  
  75. if __name__ == '__main__':
  76. 	test_cases = [
  77. 		[1, 3, 2, 4, 5],
  78. 		[2, 1, 4, 6, 3, 5],
  79. 		[5, 1, 3, 6, 4, 2],
  80. 		[1, 5, 2],
  81. 		[2, 1, 4, 3, 2],
  82. 		[3, 2, 5, 2, 2, 1],
  83. 		[2, 5, 4, 3, 4, 4, 4, 4, 3, 6],
  84. 		[2, 5, 4, 3, 4, 4, 4, 5, 3, 6],
  85. 		[2, 5, 4, 3, 4, 4, 3, 4, 5, 6],
  86. 	]
  87. 	for arr in test_cases:
  88. 		print(arr, fix_array(arr))
Success #stdin #stdout 0.02s 9036KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[1, 3, 2, 4, 5] 2
[2, 1, 4, 6, 3, 5] 4
[5, 1, 3, 6, 4, 2] 4
[1, 5, 2] 1
[2, 1, 4, 3, 2] 3
[3, 2, 5, 2, 2, 1] 3
[2, 5, 4, 3, 4, 4, 4, 4, 3, 6] 5
[2, 5, 4, 3, 4, 4, 4, 5, 3, 6] 5
[2, 5, 4, 3, 4, 4, 3, 4, 5, 6] 5
https://ideone.com/NNeWCp
Fixing Array - O(n log n)
language:
Python 3 (python  3.9.5)
created:
2 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!