Desafío Ryckeboer #2

Desafío “Ryckeboer” #2:

Enunciado:

Dados dos arreglos A y B de n y m elementos respectivamente, se permite hacer la siguiente operación:

  • Sumar o restar 1 a algún elemento de alguno de los arreglos.

Se desea encontrar la menor cantidad de operaciones necesarias para que el menor elemento de A sea mayor o igual al mayor elemento de B

Ejemplo:

Si los arreglos son A = \left [1,2,3 \right ] y B = \left [3,4 \right] , la respuesta sería 4 operaciones, que se obtienen aplicando la operación dos veces al A_1 = 1, una vez al A_2 = 2, y una vez al B_2 = 4

Cotas:

  • Entrada
    • 1 \leq n,m \leq 10^5
    • 1 \leq a_i,b_j \leq 10^9
  • Tiempo
    • 1 segundo

Link:

Si quieren enviar sus códigos y que sean evaluados en un juez online, pueden hacerlo en el siguiente link:
Link al problema original

Actualización:

Ya vimos una solución basada en la idea ingeniosa que sugirió @michaelszer. ¿Se les ocurre alguna otra solución?

4 Me gusta

Complicado y divertido!

Lo que se me ocurrio hacer es antes que nada sortear los arrays, después correr un loop que se va fijando desde el número mas alto, en el caso del Array B, y el número mas chico, en el caso del Array A, a cual le es mas barato correr operaciones en base a cuantos números tiene que operar.

Un ejemplo sería: A = [1,1,1,3] y B = [3,4,4]. En este caso agarraría el número 1 del array A que consiste de 3 números, por lo que costaría 3 operaciones subir uno, y el número 4 en B, que consiste de 2 números, por lo que costaría 2 operaciones bajar a todos un número. Se fija cual le costa modificar menos, en este caso el número 4 ya que haría 2 operaciones mas que 3 con el número 1.

Por cada vez que se corre el loop el número mas chico del array A aumenta y en el caso del array B el número mas grande se achica. El loop se correría hasta que el número mas chico del array A sea >= al del array B.

En teoría esto tiene complejidad(n) pero cuando lo corro en codeforces me aparece timeout en el test #11.

De que forma podría optimizar el algoritmo?

Les paso el código para el que le interese.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long> a, b;	
int n, m;
long long quan = 0;

void orderNumbers();

int main(){
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		
		int num;
		
		cin >> num;
		
		a.push_back(num);
	}
	
	for(int i = 0; i < m; i++){
		
		int num;
		
		cin >> num;
		
		b.push_back(num);
	}
	
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	
	orderNumbers();
	
	cout << quan << endl;
}

void orderNumbers(){
	
	int numA, numB;
	
	numA = *(a.begin());
	numB = *(b.end()-1);
	
	vector<long long>::iterator it = a.begin();
	vector<long long>::reverse_iterator revIt = b.rbegin();
		
	long long quanA = 0, quanB = 0;
		
	while(numB > numA){		
		
		while(it != a.end() && *it <= numA){
			
			quanA++;
			
			it++;
		}
		
		while(revIt != b.rend() && *revIt >= numB){
			
			quanB++;
			
			revIt++;
		}
		
		if(quanA > quanB){
			quan += quanB;
			numB--;
		} else {
			quan += quanA;
			numA++;
		}
	}
}
1 me gusta

Hola. ¡Muy buena tu solución, es muy ingeniosa! :slight_smile:

Siguiendo tu algoritmo así como lo contaste, entiendo que la complejidad no es \mathcal{O} (n), sino \mathcal{O}(n+C) donde C es la máxima diferencia que puede haber entre dos números de los arreglos. Usando la notación de tu código sería C = \left | \texttt{numA} - \texttt{numB} \right |.

Para ver el por qué, fijate que en cada iteración del “while” a alguna de esas dos variables (\texttt{numA} o \texttt{numB}) se le suma (o resta) a lo sumo 1. Intuyo que esa es la razón del timeout.

Para clarificar un poco, pensá qué ocurre con el siguiente ejemplo:

  • n = 1, m = 1
  • A = [1]
  • B = [10^9]
1 me gusta

Claro! No me di cuenta :sweat_smile:

Para solucionarlo se me ocurrio que mas que restarle/sumarle 1 (numB-- y numA++), vaya directamente al próximo número más chico/grande. Pero sin embargo cuando lo corro en codeforces me aparece error en el test #5, el input que meten es muy largo como para analizarlo. No encuentro ninguna diferencia, aparte de la velocidad, entre este y el anterior algoritmo.

Estoy hace un tiempo y no se me ocurre porque pasa esto, si me queres dar una mano estas mas que invitado :grinning:!

Cual sera la diferencia entre este y el anterior algoritmo que hace que no funcione en algunos casos?

Código:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<long long> a, b;	
int n, m;
long long quan = 0;

void orderNumbers();

int main(){
	
	cin >> n >> m;
	
	for(int i = 0; i < n; i++){
		
		int num;
		
		cin >> num;
		
		a.push_back(num);
	}
	
	for(int i = 0; i < m; i++){
		
		int num;
		
		cin >> num;
		
		b.push_back(num);
	}
	
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	
	vector<long long>::iterator it = b.end();
	it--;
	int Bmax = *it;
	it = a.begin();
	int Amin = *it;
	
	while(it != a.end()){
		
		if(*it >= Bmax){
			a.erase(it,a.end());
			break;
		}
		
		it++;
	}
	
	it = b.begin();
	
	vector<long long>::reverse_iterator revIt = b.rbegin();
	
	while(revIt != b.rend()){

		if(*revIt <= Amin){
			b.erase(b.begin(), revIt.base());
			break;
		}
		
		revIt++;
	}
	
	if(!a.size() && !b.size()){
		cout << quan << endl;
		return 0;
	}
	
	orderNumbers();
	
	cout << quan << endl;
}

void orderNumbers(){
	
	int numA, numB;
	
	numA = *(a.begin());
	numB = *(b.end()-1);
	
	vector<long long>::iterator it = a.begin();
	vector<long long>::reverse_iterator revIt = b.rbegin();
	vector<long long>::iterator itB = b.begin();
	vector<long long>::reverse_iterator revItA = a.rbegin();
		
	long long quanA = 0, quanB = 0;
		
	while(numB > numA){		
		
		// Recorre al array A desde el principio hasta el final
		while(it != a.end() && *it <= numA){
			
			quanA++;
			
			it++;
		}
		
		// Recorre al array B desde el principio hasta el final
		while(it == a.end() && *itB <= numA){
			
			itB++;
		}
		
		// Recorre al array B desde el final hasta el principio
		while(revIt != b.rend() && *revIt >= numB){
			
			quanB++;
			
			revIt++;
		}

		// Recorre al array A desde el final hasta el principio		
		while(revIt == b.rend() && *revItA >= numB){
			
			revItA++;
		}
		
		long long diffA, diffB;
		
		if(it != a.end()){
			diffA = *it - numA;
		} else {
			diffA = *itB - numA;
		}
		
		if(revIt != b.rend()){
			diffB = numB - *revIt;
		} else {
			diffB = numB - *revItA;
		}
		
		if(quanA*diffA > quanB*diffB){
			
			quan += quanB*diffB;
			numB -= diffB;
		} else {
			quan += quanA*diffA; 
			numA += diffA;
		}	
	}
}
1 me gusta

Hola,

No creo que pueda mirar ese código en detalle hasta dentro de unos días.

Sin embargo, lo corrí contra un par de ejemplos, y encontré un ejemplo pequeño donde la respuesta que da no es la esperada.

Si consideramos:

  • n = 3, m = 3
  • A = [1,5,5]
  • B = [4,5,5]

La respuesta esperada es 4 (que surge de aumentar 4 veces A_1 = 1), sin embargo al correr el código que mostrás me otorga 5 como respuesta :thinking:.

Espero que te ayude a encontrar lo que está pasando. Igual en los próximos días lo miro bien en detalle :smiley:

1 me gusta

Bueno, una forma de ajustar la idea que sugerís en el primer post para que entre en tiempo es tomar las mismas decisiones que antes, pero saltear los pasos intermedios según los números que ya están en el arreglo.

Entonces, arrancamos de la misma forma, y vamos a ver en cada arreglo cuántos números se deben operar en cada caso, y vamos a aumentar o disminuir (según si se deben hacer menos operaciones en A o en B respectivamente) en el arreglo en el que se deban modificar la menor cantidad de números.

Hasta acá ningún cambio. Ahora, para no modificar de a una unidad, surge la pregunta: ¿A qué número debemos modificar a los elementos del arreglo? Aquí tenemos dos opciones:

  • Modificar hasta el próximo número (distinto al valor de los que estamos modificando) del mismo arreglo.
  • Modificar al número más alto (o más bajo, según en qué arreglo estamos situados) del otro arreglo.

Ejemplo Explicado

Voy a ordenar a A creciente y a B decreciente en lo que sigue por comodidad (así los que ya “modificamos” quedan siempre a la izquierda)

Paso 0:

A = [2,4,4,5]
B = [6,3,2]

En ambos casos los grupos de números distintos son de 1 elemento (A_1 o B_1). La elección aquí es arbitraria, analicemos qué ocurriría en ambos casos solo con fines pedagógicos.

  • Si elegimos modificar A_1 debemos hacerlo hasta A_2 = 4, o hasta B_1 = 6. La menor cantidad de modificaciones se alcanza en el primero, entonces lo modificamos hasta A_2
  • Si elegimos modificar B_1 debemos hacerlo hasta B_2 = 3 o hasta A_1 = 2. La menor cantidad de modificaciones se alcanza en el primero, entonces lo modificamos hasta B_2.

Voy a suponer que nuestro algoritmo modificó el A_1 (en cuyo caso lo hace hasta el valor de A_2)

Paso 1:

A = [4,4,4,5]
B = [6,3,2]

Ahora, los grupos de números son A_1,A_2,A_3 que son 3 números en el arreglo A y B_1 en el arreglo B. Por lo tanto vamos a modificar B_1. Ahora, ¿hasta cuándo?

  • Si elegimos modificar B_1 debemos hacerlo hasta B_2 = 3 o hasta A_1 = 4. La menor cantidad de modificaciones se alcanza en el segundo caso, entonces lo modificamos hasta el valor de A_1.

Paso 2:

A = [4,4,4,5]
B = [4,3,2]

Terminamos y en total hicimos 4 operaciones.

A modo de aclaración, si en el Paso 0 modificábamos B_1 hasta 3, hubiéramos alcanzado 4 operaciones también, pero al final tendríamos:

A = [3,4,4,5]
B = [3,3,2]

Ahora, a la hora de la implementación debemos tener cuidado. En particular, no es necesario ir modificando los números como lo mostramos en el ejemplo.

La idea será la misma, la de tener dos punteros/índices que nos indiquen hasta qué números debemos modificar en cada arreglo. En realidad, me gusta pensar que tenemos dos ventanas en cada uno de los arreglos. En A la voy a llamar [i_1,i_2] y en B la voy a llamar [j_1,j_2]. Paso a explicar qué significan, para el caso del arreglo A.

La idea es que [i_1,i_2) (notar que no incluimos el extremo derecho) nos indique el grupo que estamos analizando en el arreglo. Notar que detrás de i_1 ya “modificamos” a los números y todos tienen el mismo valor que A_{i_1}. En la implementación no los vamos a modificar, pero conviene pensarlo así a la hora de entender el algoritmo.

Si seguimos los pasos anteriores, nos queda:

Paso 0:

A = \begin{array} {|c|c|c|c|} \hline i_1 & i_2 & & \\ \hline 2 & 4 & 4 & 5 \\ \hline \end{array} \hspace{25pt} B = \begin{array} {|c|c|c|} \hline j_1 & j_2 & \\ \hline 6 & 3 & 2 \\ \hline \end{array}

Paso 1:

A = \begin{array} {|c|c|c|c|} \hline & i_1 & & i_2 \\ \hline 2 & 4 & 4 & 5 \\ \hline \end{array} \hspace{25pt} B = \begin{array} {|c|c|c|} \hline j_1 & j_2 & \\ \hline 6 & 3 & 2 \\ \hline \end{array}

Paso 2:

A = \begin{array} {|c|c|c|c|} \hline & i_1 & & i_2 \\ \hline 2 & 4 & 4 & 5 \\ \hline \end{array} \hspace{25pt} B = \begin{array} {|c|c|c|} \hline & j_1 & j_2 \\ \hline 6 & 3 & 2 \\ \hline \end{array}

En donde no debemos continuar, pues A_{i_1}\geq B_{j_1}

Código (no recomiendo mirarlo hasta intentar codearlo)

#include <iostream>
#include <algorithm>

typedef long long tint;

#define forn(i,n) for(tint i=0;i<(tint)(n); i++)

using namespace std;

const tint maxN = 131072;
tint a[maxN];
tint b[maxN];

int main()
{
	tint n,m;
	cin >> n >> m;
	// LEEMOS LA ENTRADA
	forn(i,n)
		cin >> a[i];
	forn(i,m)
		cin >> b[i];
	// ORDENAMOS a CRECIENTE Y b DECRECIENTE
	sort(a,a+n);
	sort(b,b+m,greater<tint>());
	// CORREMOS EL ALGORITMO DE DOS VENTANAS
	tint i1 = 0, j1 = 0, i2 = 0, j2 = 0, ans = 0;
	while (i1 < n && j1 < m && a[i1] < b[j1])
	{
		// AVANZAMOS HASTA EL PROXIMO NUMERO EN CADA ARREGLO
		
		// i2 Y j2 NOS DICEN CUANTOS ELEMENTOS TENEMOS QUE 
		// HIPOTETICAMENTE MODIFICAR EN CADA ARREGLO
		
		while (i2 < n && a[i2] == a[i1])
			i2++;
		while (j2 < m && b[j2] == b[j1])
			j2++;
		
		// ra Y rb NOS DICEN CUANTO DEBEMOS MODIFICAR A 
		// CADA ELEMENTO QUE TENEMOS DETRAS EN CADA ARREGLO
			
		tint ra = b[j1]-a[i1], rb = b[j1]-a[i1]; 
		
		// TOMAMOS EL MINIMO ENTRE EL QUE SIGUE EN EL MISMO ARREGLO Y
		// EN EL QUE ESTAMOS SITUADO EN EL OTRO ARREGLO (CON ESO LO INICIALIZAMOS)
		if (i2 < n)
			ra = min(ra,a[i2]-a[i1]);
		if (j2 < m)
			rb = min(rb,b[j1]-b[j2]);
		
		
		if (i2 <= j2) // SI MODIFICA MENOS ELEMENTOS EL ARREGLO A
		{
			ans += i2*ra;
			i1 = i2;
		}
		else // SI MODIFICA MENOS ELEMENTOS EL ARREGLO B
		{
			ans += j2*rb;
			j1 = j2;
		}
	}
	cout << ans << endl;
	return 0;
}

2 Me gusta

Me encanta esta explicación. Por un lado presenta la convención de bordes cerrado abierto [A,B), que es una masa total. Y por otro, desliza sutilmente al pasar la idea de invariante de ciclo, que es híper mega archi fundamental para programar bien.

Hasta usa bien \LaTeX :smiley:

1 me gusta

Muy buena inplementación!

Gracias por el caso de ejemplo que me dijiste, me hiciste dar cuenta que tenía mal. :smile:

Espero el próximo desafío con muchas ganas!

2 Me gusta

Me alegro que el ejemplo te haya ayudado a arreglar tu implementación del algoritmo :slight_smile:

Por cierto, por dar la primera solución al problema en el foro. Acá está la merecida “Insignia Ryckeboer:medal_military:

Sobre el próximo desafío solo puedo adelantar que voy a intentar que no tenga una solución con “Two Pointers o similares :stuck_out_tongue: . Ahora en serio, si bien es una técnica que particularmente me gusta, la solución que tenía pensada para este problema no utilizaba esta técnica (que sí era la que tenía pensada para el desafío #1).

1 me gusta