Sleepy Cow Sorting

Pista

Solo hay una salida correcta.

Solución en video

Nota: La solución en video puede no ser la misma que las otras soluciones. Código en C++.

Solución 1

Explicación

Para obtener el número de vacas $K$ que no están en la posición correcta, restamos de $N$ la longitud del sufijo más largo del arreglo que ya está ordenado. Esto tiene sentido porque el problema asume que las vacas se mueven una por una a la parte ordenada de la fila. Una vez que una vaca llega a su lugar correcto en la sección ya ordenada, se queda allí y no causa más problemas. Al centrarnos en el sufijo ordenado más largo, estamos identificando las vacas que ya están en el lugar correcto y no necesitan moverse más. Esto maximiza el número de vacas que están “listas” y minimiza el número de vacas $(K)$ que aún necesitan reordenarse.

Luego, para cada una de estas vacas no ordenadas, calculamos cuántos pasos necesita dar para llegar a su posición correcta. Para esto, consideramos dos cosas:

Contar cuántas vacas en la sección ordenada tienen un número menor que la vaca en la que nos estamos enfocando. Estas vacas están en el camino y hay que saltarlas. Para hacer este conteo eficiente, usamos un Árbol de Segmentos, que nos permite hallar rápidamente cuántas vacas más pequeñas hay adelante sin revisar cada una de forma individual.
Contar cuántas vacas en la sección no ordenada están a la derecha de la vaca actual, ya que también bloquean su camino.

Al sumar estos dos números —las vacas de la sección ordenada que son más pequeñas y las vacas de la sección no ordenada que están adelante— obtenemos el número total de pasos que esa vaca necesita dar para llegar a su lugar correcto. De esta forma, nos aseguramos de tener en cuenta todos los obstáculos que cada vaca tiene que pasar para llegar a donde debe estar.

Implementación

Complejidad temporal: $\mathcal{O}(N\log N)$

C++Java


#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
 
using std::vector;
 
// BeginCodeSnip{Segment Tree}
template <class T> class SumSegmentTree {
  private:
	const T DEFAULT = 0;
	vector<T> segtree;
	int len;
 
  public:
	SumSegmentTree(int len) : len(len), segtree(len * 2, DEFAULT) {}
 
	void set(int ind, T val) {
		ind += len;
		segtree[ind] = val;
		for (; ind > 1; ind /= 2) {
			segtree[ind / 2] = segtree[ind] + segtree[ind ^ 1];
		}
	}
 
	T range_sum(int start, int end) {
		T sum = DEFAULT;
		for (start += len, end += len; start < end; start /= 2, end /= 2) {
			if (start % 2 == 1) { sum += segtree[start++]; }
			if (end % 2 == 1) { sum += segtree[--end]; }
		}
		return sum;
	}
};
// EndCodeSnip
 
int main() {
	std::ifstream fin("sleepy.in");
	int n;
	fin >> n;
	vector<int> cows(n);
	for (int &x : cows) {
		fin >> x;
		x--;
	}
 
	int suffix_length = 1;
	for (int i = n - 1; i > 0; i--) {
		// If current cow is in order, increment suffix length and continue
		// Otherwise, there has been an inversion so we break from the loop
		if (cows[i] > cows[i - 1]) {
			suffix_length++;
		} else {
			break;
		}
	}
 
	std::ofstream fout("sleepy.out");
	int k = n - suffix_length;
	fout << k << '\n';
 
	SumSegmentTree<int> segtree(n);
	for (int i = k; i < n; i++) { segtree.set(cows[i], 1); }
 
	for (int i = 0; i < k; i++) {
		// Takes the prefix sum up to cows[i] - 1, which calculates the
		// number of cows smaller than the current cow
		int smaller = segtree.range_sum(0, cows[i]);
 
		fout << smaller + (k - i - 1) << " \n"[i == k - 1];
		segtree.set(cows[i], 1);
	}
}


import java.io.*;
import java.util.*;
 
public class Sleepy {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("sleepy.in"));
		PrintWriter out = new PrintWriter("sleepy.out");
 
		int n = sc.nextInt();
		int[] cows = new int[n];
		for (int i = 0; i < n; i++) { cows[i] = sc.nextInt() - 1; }
 
		int suffixLength = 1;
		for (int i = n - 1; i > 0; i--) {
			// If current cow is in order, increment suffix length and continue
			// Otherwise, there has been an inversion so we break from the loop
			if (cows[i] > cows[i - 1]) {
				suffixLength++;
			} else {
				break;
			}
		}
		int k = n - suffixLegth;
		out.println(k);
 
		SegmentTree seg = new SegmentTree(n);
		for (int i = k; i < n; i++) { seg.add(cows[i], 1); }
		for (int i = 0; i < k; i++) {
			// Takes the prefix sum up to cows[i] - 1, which calculates the
			// number of cows smaller than the current cow
			int smaller = seg.sum(0, cows[i] - 1);
 
			out.print(smaller + (k - i - 1));
			if (i < k - 1) out.print(" ");
			seg.add(cows[i], 1);
		}
		out.println();
		out.close();
	}
 
	static class SegmentTree {
		private int[] tree;
		private int n;
 
		public SegmentTree(int n) {
			this.n = n;
			tree = new int[n * 2];
		}
 
		public int sum(int a, int b) {
			a += n;
			b += n;
			int sum = 0;
			while (a <= b) {
				if (a % 2 == 1) sum += tree[a++];
				if (b % 2 == 0) sum += tree[b--];
				a /= 2;
				b /= 2;
			}
			return sum;
		}
 
		public void add(int index, int amount) {
			index += n;
			tree[index] += amount;
			for (index /= 2; index >= 1; index /= 2) {
				tree[index] = tree[2 * index] + tree[2 * index + 1];
			}
		}
	}
}

Solución alternativa (usando indexed set)

Solución 2

C++


#include <bits/stdc++.h>
using namespace std;
 
// Import indexed sets
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
Tree<int> sorted;
int n;
vector<int> nums;
 
int main() {
	ifstream fin("sleepy.in");
 
	fin >> n;
	// Reading input and look for the longest suffix that is increasing
	for (int i = 0; i < n; i++) {
		int a;
		fin >> a;
		nums.push_back(a);
		if (i > 0) {
			if (nums[i - 1] > nums[i]) { sorted.clear(); }
		}
		sorted.insert(a);
	}
 
	// Need to sort everything except increasing suffix
	int ls = sorted.size();
 
	ofstream fout("sleepy.out");
	fout << n - ls << endl;
 
	for (int i = 0; i < n - ls; i++) {
		if (i != 0) fout << " ";
		sorted.insert(nums[i]);
		fout << sorted.order_of_key(nums[i]) + (n - ls - i - 1);
	}
}