Problema interesante: Permutíndices

Principiante
#1

A continuación un misterioso problema que me pareció muy lindo, porque tiene muchas soluciones con distintas complejidades (tanto espacial como temporal).

El problema: Tenemos número N y un arreglo a que contiene una Permutaciónref1 de los números de 1 a N. Una posición i se dice permutíndice si el subarreglo a[1…i] es permutación de los números de 1 a i.
Calcular cuantas posiciones del arreglo son permutíndices.

Ejemplo: Dada la permutación “1, 2, 3, 4, 5”, todas las posiciones son permutíndices por lo que la respuesta es 5.
Dada la permutación “2,3,1,5,4”; la respuesta es 2, porque a[1…3] es una permutación de los números 1 a 3, y a[1…5] es una permutación de los números de 1 a 5.

En orden creciente de dificultad, resolver el problema con complejidades:

  1. O(N2) temporal
  2. O(N) temporal y O(N) espacial
  3. O(N) temporal y O(1)ref2 espacial

Referencias

  1. Una permutación es un arreglo que contiene exactamente los mismos números con el orden cambiado.
    Por ejemplo, una permutación de los números de 1 a 5 puede ser “1, 2, 3, 4, 5” ó “5, 2, 4, 1, 3” pero NO “1, 2, 2, 3, 4, 5” porque los números deben aparecer igual cantidad de veces.

  2. Esta última es díficil. Lucas Bekier fue quien me iluminó con esta solución mágica.

5 Me gusta
#2

Está copado!

SPOILER, SOLUCIÓN ABAJO
vvvvvvvvvvvvvvvvvvvvvvvvvvv

Solución 
    int n, val;
    long long suma = 0;

    cin >> n;

    for(int i=1; i<=n; i++)
    {
        cin >> val;
        suma += val;
        if(suma == (i*(i+1))/2)
            cout << "Permutindice en la posicion: " << i << endl;
    }
1 me gusta
#3

Hay una variante elegante de la misma idea:

Spoiler

En lugar de la suma podemos tomar el máximo, y tiene que ser i en el paso i.

3 Me gusta
#4

Pst, otra solución copada (con la que salen algunos problemas de OIA de años pasados) es usar…

Summary

Un set, en el que vas metiendo elementos. Para saber si en el set se encuentran todos los números enteros desde A hasta B (A <= B) tenes que fijarte si se cumplen las siguientes tres:

set.ElegirMenor == A
set.ElegirMayor == B
set.Tamaño = B-A+1

Porque el set los mantiene ordenados de menor a mayor, y no permite repetidos :smiley:
Esta solución está copada porque resuelve un problema más general, si existe un sub-array tal que ese sub-array es una permutación de los enteros desde A hasta B. Como sabés el tamaño que ese sub-array tiene que tener, podés aplicar ventana deslizante, ingresando y quitando elementos (aunque acá necesitarías un map o multiset en caso de que el array contenga valores repetidos)

#5

Ah mirá, no se me había ocurrido jajaja

#6

Comentarios:

Spoiler
  • Es overkill usar un set, con su gigante constante y log y complejidad, para un histograma sencillito de números entre 1 y N. Un arreglo de int que cuente la cantidad de veces que aparece cada uno (o un simple arreglo de bool sin repetidos) alcanza.
    Siempre digo que “las cosas que ya vienen programadas” distorsionan la complejidad real de las cosas, pues soluciones mucho más complicadas de hacer desde cero se vuelven mucho más simples porque aprovechan el cañón que ya tenemos :stuck_out_tongue:
  • Además del histograma en el arreglo se puede tener un contador de “cuántos elementos repetidos” hay, que se actualiza en cada operación. Eso haría falta aún con el multiset porque sino “1 3 3 3 5” y “1 2 3 4 5” serían indistinguibles.
#7

Yo decía esto:

Spoiler

http://www.oia.unsam.edu.ar/_media/prob/c3a10n3p2.pdf
Ese problema, yo lo resolví usando un map (donde, si hay repetidos, incremento el value asociado al key. Para sacar, resto al value asociado, y si no puedo restar, entonces lo vuelo del map). Es NlogN, se puede hacer mejor?

#8

Sobre el de OIA:

Spoiler

Sí, sale lineal con lo mismo que puse en el otro post :stuck_out_tongue:

O sea la idea es la misma pero en lugar de un map<int,int> como los elementos son numeros de 1 a M, directamente usas un arreglo de M posiciones (o sea, un arreglo de T siempre implementa naturalmente un map<int, T>, pero donde las claves estan en un rango fijo [0,N) ).

Tenés que saber cuántos elementos mayores que M hay (para pedir que no haya ninguno) y cuántos elementos repetidos hay (para pedir que no haya repetidos), pero ambas cosas se pueden mantener con contadores en O(1) ante cada modificación.

Con eso queda O(N) sin ninguna estructura, porque son todas operaciones baratas en el arreglo y +1 / -1. Como comentario, este problema es esencialmente lo mismo que Writing de la IOI 2006 (que es uno de los problemas más fáciles de toda la historia IOI).

1 me gusta
#9

Genial! Gracias por la aclaración