Skip to Content
CTRL K

Into Blocks

Editorial oficial 

Explicación

Lo clave a notar aquí es que si tenemos dos números de esta forma:

[1,⋯ ,2,⋯ ,1,⋯ ,2] [1, \cdots, 2, \cdots, 1, \cdots, 2]

donde sus rangos activos se intersectan, entonces tienen que ser el mismo valor.

El algoritmo consiste entonces en partir el arreglo en todos los segmentos “independientes”, en los que ningún número del arreglo original queda partido en varios segmentos. Lo hacemos calculando primero todos los rangos de valores y ordenándolos por posición de inicio.

Por ejemplo, si nuestro arreglo inicial era

[3,3,1,3,1,4,2,4,2] [3, 3, 1, 3, 1, 4, 2, 4, 2]

los segmentos serían los primeros cinco y los últimos cuatro elementos del arreglo.

Para cada segmento, su dificultad es su longitud menos el número de veces que aparece el valor más frecuente. En otras palabras, la mejor estrategia es cambiar todos los valores del segmento al valor que ya aparece más veces.

La dificultad total es la suma de las dificultades de todos los segmentos, ya que no se afectan entre sí.

Implementación

Complejidad temporal: O(nlog⁡n)\mathcal{O}(n \log n)

#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
int main() {
	int len;
	int query_num;  // no se usa
	std::cin >> len >> query_num;
 
	std::map<int, vector<int>> inds;
	for (int i = 0; i < len; i++) {
		int val;
		std::cin >> val;
		inds[val].push_back(i);
	}
 
	vector<vector<int>> ranges;
	for (const auto &[v, i] : inds) {
		ranges.push_back({i[0], i.back(), (int)i.size()});
	}
	std::sort(ranges.begin(), ranges.end());
 
	int difficulty = 0;
	int start = ranges[0][0];
	int end = ranges[0][1];
	int most_common = 0;
	for (const vector<int> &r : ranges) {
		if (r[0] > end) {
			difficulty += end - start + 1 - most_common;
			start = r[0];
			end = r[1];
			most_common = r[2];
		} else {
			end = std::max(end, r[1]);
			most_common = std::max(most_common, r[2]);
		}
	}
	difficulty += end - start + 1 - most_common;
 
	cout << difficulty << endl;
}
import java.io.*;
import java.util.*;
 
public class IntoBlocks {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer initial = new StringTokenizer(read.readLine());
		int len = Integer.parseInt(initial.nextToken());
 
		StringTokenizer arrST = new StringTokenizer(read.readLine());
		Map<Integer, List<Integer>> inds = new HashMap<>();
		for (int i = 0; i < len; i++) {
			int val = Integer.parseInt(arrST.nextToken());
			if (!inds.containsKey(val)) { inds.put(val, new ArrayList<>()); }
			inds.get(val).add(i);
		}
 
		int[][] ranges = new int[inds.size()][3];
		int at = 0;
		for (List<Integer> i : inds.values()) {
			ranges[at++] = new int[] {i.get(0), i.get(i.size() - 1), i.size()};
		}
		Arrays.sort(ranges, Comparator.comparingInt(r -> r[0]));
 
		int difficulty = 0;
		int start = ranges[0][0];
		int end = ranges[0][1];
		int mostCommon = 0;
		for (int[] r : ranges) {
			if (r[0] > end) {
				difficulty += end - start + 1 - mostCommon;
				start = r[0];
				end = r[1];
				mostCommon = r[2];
			} else {
				end = Math.max(end, r[1]);
				mostCommon = Math.max(mostCommon, r[2]);
			}
		}
		difficulty += end - start + 1 - mostCommon;
 
		System.out.println(difficulty);
	}
}
len_, _ = [int(i) for i in input().split()]
 
inds = {}
arr = [int(i) for i in input().split()]
for i in range(len_):
	if arr[i] not in inds:
		inds[arr[i]] = []
	inds[arr[i]].append(i)
 
ranges = []
for i in inds.values():
	ranges.append((i[0], i[-1], len(i)))
ranges.sort()
 
difficulty = 0
start = ranges[0][0]
end = ranges[0][1]
most_common = 0
for r in ranges:
	if r[0] > end:
		difficulty += end - start + 1 - most_common
		start = r[0]
		end = r[1]
		most_common = r[2]
	else:
		end = max(end, r[1])
		most_common = max(most_common, r[2])
difficulty += end - start + 1 - most_common
 
print(difficulty)
Fundamentos